前言
最近在leetcode上做算法题，记录一下心得
（我的答案是用js写的）
由易至难
第一题： 1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
我的答案：
var twoSum = function(nums, target) {
var l = nums.length;
var b = [];
for(var i= 0 ;i < l; i++){
for(var j = i+1 ;j < l;j++){
if(nums[i] + nums[j] == target){
b.push(i);
b.push(j);
}
}
}
return b;
};
官方：
1. Approach #1 (Brute Force) [Accepted]
最直观的方法遍历每个元素的值和该元素的下一个的值是相加是否等于target的值。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
算法分析： 时间复杂度：O(n²)。对每一个元素都通过循环找到剩余数组的其他元素的O（n）次。
空间复杂度：O（1）。
2. Approach #2 (Two-pass Hash Table 二次哈希表) [Accepted]
为了提高我们的运行时间复杂度，我们需要一个更有效的方法来检查数组中的指数是否存在。 如果指数存在，我们需要查找它的索引。在数组中维护每个元素的映射的最佳方法是什么?一个哈希表。
我们以交易空间换取速度将查找时间从o（n）到o（1）到o。哈希表正是为了这个目的而构建的，它支持在几乎恒定的时间内快速查找。之所以说“近乎”， 最坏的情况下，查询时间可能为O（n）。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
算法分析：
时间复杂度：O（n）。通过将数组放到hashmap中，并利用for循环遍历元素，通过tagert - i 的值，判断map是否含有这个值，且这个值（y）不和 i相等， 则返回i，这返回[i,y],这样算法的时间复杂度为O（n）；
空间复杂度：O（n）。需要额外的空间存储数组，且和n成线性关系。
3. Approach #3 (One-pass Hash Table 一次哈希表) [Accepted]
我们还可以一次完成。当我们在表中迭代并插入元素时，我们还会回顾一下，看看当前元素的补充是否已经存在于表中。如果存在，我们已经找到了解决方 案，并立即返回。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
同2：此方案的优化是在插入的时候就判断是否有元素，少了一次遍历的操作。
第二题 561. Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1: Input: [1,4,3,2]
Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4). Note: n is a positive integer, which is in the range of [1, 10000]. All the integers in the array will be in the range of [-10000, 10000].
本题是为了求一个最大最小值问题，看懂题目之后我们容易发现其实最终问题可以转化为将数组进行排序，然后各一个求和，因为为了使最后的和最大，我们 需要让最大值和第二大值在一个数对里面，依次类推，只有这样才能使“资源浪费最少”
我的答案
var arrayPairSum = function(nums) {
var nums = nums.sort(
function(a,b){
if (a>b) {
return 1;
}else if(a<b){
return -1
}else{
return 0;
}
}
);
var result = 0;
var l = nums.length
for(var i = 0 ;i < l;i+=2){
result += nums[i]
}
return result;
};
第三题 728. Self Dividing Numbers
A self-dividing number is a number that is divisible by every digit it contains.
For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.
Also, a self-dividing number is not allowed to contain the digit zero.
Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.
Example 1: Input: left = 1, right = 22 Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] Note:
The boundaries of each input argument are 1 <= left <= right <= 10000.
我的答案
var selfDividingNumbers = function(left, right) {
var result = [];
for(var i = left;i <= right;i++){
if(canDivde(i)){
result.push(i);
}
}
return result;
}
var canDivde = function(number){
var str = number + '';
var l = str.length;
var can = true;
for( var i = 0 ; i < l ;i++){
var number_i = str.charAt(i);
if(number%number_i !== 0){
can = false;
break;
}
}
return can;
};
官方答案
class Solution {
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> ans = new ArrayList();
for (int n = left; n <= right; ++n) {
if (selfDividing(n)) ans.add(n);
}
return ans;
}
public boolean selfDividing(int n) {
for (char c: String.valueOf(n).toCharArray()) {
if (c == '0' || (n % (c - '0') > 0))
return false;
}
return true;
}
}
解题思路：根据输入的值从left-right遍历其中的值，对每一个值得每一位进行自除检测，有一位不能整除则返回false。
算法分析
时间复杂度：D= right - left考虑最坏情况，数组中的每一位都是和right一样长，所以最多要循环（D * right.length ）次 O（D*log（Right））
空间复杂度：O(D)需要分配空间对l-r进行计算。
第四题 461. Hamming Distance 汉明距离
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note: 0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑
The above arrows point to positions where the corresponding bits are different.
分析： 关键是在二进制位如何计算1的个数上。有两个方法：
* 将num和0x1进行与操作，结果是1，代表num的最右位是1，否则是0，然后将num右移一位，循环判断，结束条件为num===0
* 将num和num-1进行与操作，该操作会将num中最右边的为1的二进制位变为0（注意是最右边的1，而不是最右边的位），循环计算，结束条件为num===0
答案
var hammingDistance = function(x, y) {
var count = 0;
var n = x ^ y;
while (n) {
++count;
n = (n - 1) & n;
}
return count;
};
备注：
^ 运算符随后查看两个表达式的二进制表示形式的值，并执行按位“异或”运算。此运算的结果如下所示：
JavaScript
0101 (expression1)
1100 (expression2)
----
1001 (result)
^ 当且仅当只有一个表达式的某位为 1 时，结果中的该位才为 1。否则，结果中的该位为 0。
& 对两个 32 位表达式的每一个位执行按位“与”运算。 如果两个位均为 1，则结果是 1。 否则，结果为 0。
第五题 657. Judge Route Circle
题目大意：
初始位于坐标(0, 0)，UDLR分别表示向上下左右移动，求移动结束后是否位于原点。
答案
var judgeCircle = function(moves) {
moves=" " + moves + " ";
return moves.split("L").length==moves.split("R").length && moves.split("U").length == moves.split("D").length;
};
解题思路：
-
初始化x，y ，使L，R对应x++ 和x–，UD对应y++ 和y–，最后返回判断x和y是否都为0
-
把LRUP当作字符插入到字符串中，通过spilt函数分离，判断LURUD的数量是否相等，非常巧妙。
第六题476. Number Complement
题目大意：
给定一个正整数，输出其补数。补充策略就是按二进制位反转。
注意:
给定正数确保是32位带符号整数。
可以假设整数的二进制表示不包含前导0
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
解题思路：
是求其二进制补数的值 ：如 ：输入5 他的二进制范围位2的三次方即8，（0～7） ，其补数则为8-5-1（之所以-1 是因为从0开始的） #### 答案
var findComplement = function(num) {
var i =0;
for(let j = 0 ;i<=num;j++){
i= Math.pow(2,j);
}
return i - num -1;
};
// 位运算答案
var findComplement = function(num) {
var mask = ~0;
while (num & mask) mask <<= 1;
return ~mask & ~num;
};
num = 00000101
mask = 11111000
~mask & ~num = 00000010
第⑦题 557. Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: “Let’s take LeetCode contest” Output: “s’teL ekat edoCteeL tsetnoc”
思考：
1.如何找到空格位置？
2.如何截断字符串并把它旋转？
#### 思路：可以用start和end变量找到并控制空格位置，然后再用循环把字符串逆序。
#### 解法
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
var str = s.split(" "); //截断成数组
for(let i=0;i<str.length;i++){
str[i] = str[i].split("").reverse().join(""); //把各子字符串截断为数组，再逆转，再拼成字符串
}
return str.join(" "); //再用空格分开字符串
};
第八题 500. Keyboard Row
Example 1:
Input: [“Hello”, “Alaska”, “Dad”, “Peace”]
Output: [“Alaska”, “Dad”]
Note:
You may use one character in the keyboard more than once. You may assume the input string will only contain letters of alphabet.
思路：
** 1.用Map存储字母到所在行的映射。**
** 2.变量words，对每一个单词，先做小写字母转换存入word，再对word的每个字母进行遍历。用flag标记是否是第一个字母，用row存储第一个字母所在 的行，对后续的字母，判断其所在行是否等于row，若不是，直接跳出内层循环继续判断下一个单词。考虑到数组需要预先设置长度，而数组长度未知，所以判断整个单词完毕后将其县存入List， 最后再把List的元素存入结果数组。**
解
var findWords = function(words) {
var obj = {
"q": "1",
"w": "1",
"e": "1",
"r": "1",
"t": "1",
"y": "1",
"u": "1",
"i": "1",
"o": "1",
"p": "1",
"a": "2",
"s": "2",
"d": "2",
"f": "2",
"g": "2",
"h": "2",
"j": "2",
"k": "2",
"l": "2",
"z": "3",
"x": "3",
"c": "3",
"v": "3",
"b": "3",
"n": "3",
"m": "3"
}
function isInline(str) {
var isIn = true;
var first = str.toLowerCase().charAt(0);
var numLine = obj[first] || 0;
for (var i = 1; i < str.length; i++) {
var n = obj[str.toLowerCase().charAt(i)] || 0;
if (n != numLine && n>0) {
isIn = false;
break;
}
}
return isIn;
}
var result = [];
for (var i = 0; i < words.length; i++) {
if (isInline(words[i])) {
result.push(words[i]);
}
}
return result;
}; ### 第九题 682. Baseball Game > You're now a baseball game point recorder. > > Given a list of strings, each string can be one of the 4 following types: > > Integer (one round's score): Directly represents the number of points you get in this round. > "+" (one round's score): Represents that the points you get in this round are the sum of the last two valid round's points. > "D" (one round's score): Represents that the points you get in this round are the doubled data of the last valid round's points. > "C" (an operation, which isn't a round's score): Represents the last valid round's points you get were invalid and should be removed. > Each round's operation is permanent and could have an impact on the round before and the round after. > > You need to return the sum of the points you could get in all the rounds. >
> Example 1:
> Input: ["5","2","C","D","+"]
> Output: 30
> Explanation:
> Round 1: You could get 5 points. The sum is: 5.
> Round 2: You could get 2 points. The sum is: 7.
> Operation 1: The round 2's data was invalid. The sum is: 5.
> Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
> Round 4: You could get 5 + 10 = 15 points. The sum is: 30.
> Example 2:
> Input: ["5","-2","4","C","D","9","+","+"]
> Output: 27
> Explanation:
> Round 1: You could get 5 points. The sum is: 5.
> Round 2: You could get -2 points. The sum is: 3.
> Round 3: You could get 4 points. The sum is: 7.
> Operation 1: The round 3's data is invalid. The sum is: 3.
> Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
> Round 5: You could get 9 points. The sum is: 8.
> Round 6: You could get -4 + 9 = 5 points. The sum is 13.
> Round 7: You could get 9 + 5 = 14 points. The sum is 27. > Note: > The size of the input list will be between 1 and 1000. > Every integer represented in the list will be between -30000 and 30000.
解
var calPoints = function(ops) {
let length = ops.length;
let array_length = 0;//用来存取栈的长度
let array = [];
for(let i=0;i<length;i++) {
if(ops[i] == "+") {
let opsi = array[array_length-1]+array[array_length-2];
array[array_length] = opsi;
array_length++;//前两个数字的和
}else if (ops[i] == "D") {
let opsi = array[array_length-1]*2;
array[array_length] = opsi;
array_length++;//前一个数字的二倍
}else if (ops[i] == "C") {
array_length--;//出栈
}else {
let opsi = parseInt(ops[i]);
array[array_length] = opsi;
array_length++;//当前值入栈
}
}
let sum = 0;
for(let i=0;i<array_length;i++) {
sum+=array[i];//求目前数组的和就可以返回了
}
return sum;
};
#### 速度最快的解答 var calPoints = function(ops) { var result = 0 var opValues = [] ops.forEach(op => { if (!isNaN(op)) opValues.push(Number(op)) else if (op === ‘+’) { opValues.push(opValues[opValues.length - 1] + opValues[opValues.length - 2]) } else if (op === ‘C’) { opValues.pop() } else if (op === ‘D’) { opValues.push(opValues[opValues.length - 1] * 2) } }) for (var i = 0; i < opValues.length; i++) { result += opValues[i] } return result };
第十题575. Distribute Candies
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies. > Example 2:
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies. > > The length of the given array is in range [2, 10,000], and will be even. > The number in given array is in range [-100,000, 100,000].
思路：
记录糖果种类，若糖果种类大于数组的一半，妹妹最多得到candies.size()/2种糖果,否则每种糖果都可以得到.
重点是判断数组中糖果的种类
- 遍历数组重复数量需要二次遍历
- 通过集合使用json同名key覆盖的特性，判断重复数量。
解
var distributeCandies = function(candies) {
var result = 0;
var l = candies.length;
var dep = {};
for(var i=0;i<l;i++){
dep[candies[i]] = candies[i]
}
var l_ =Object.keys(dep).length;
return (l_ >= l/2?l/2:l_);
}; #### 最优解
var distributeCandies = function(candies) {
return Math.min((new Set(candies)).size, candies.length / 2);
};
566. Reshape the Matrix
In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.
You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
` Example 1: Input: nums = [[1,2], [3,4]] r = 1, c = 4 Output: [[1,2,3,4]] `
Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation: There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
The height and width of the given matrix is in range [1, 100]. The given r and c are all positive.
解
var matrixReshape = function(nums, r, c) {
var result = [];
var l = nums.length * nums[0].length;
if(l < r*c){
result = nums;
}else{
var tmp = [].concat.apply([],nums);
for(var i= 0;i<r;i++){
var br = [];
for(var j=0;j<c;j++){
br.push(tmp[i*c+j]);
}
result.push(br);
}
}
return result;
};
