Eighteen Blog

题目说明

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

### 解题思路一
1. 第一种方法,比较常规,符合我们的脑回路。
2. 遍历数组,求遍历过的和sum。
3. 当sum >= s时,依次减去sum前面的数字,并判断是否依旧符合sum >= s。
4. 直到sum >= s不成立,记录start--到end的长度。
5. 继续遍历数组的下一位,循环2-3步骤,比较之后取最小长度。
### 代码实现一
```javascript
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
let sum = 0;
let start = 0;
let end = 0;
let min = nums.length + 1;
for(let i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum >= s) {
end = i;
while(sum >= s) {
sum -= nums[start++];
}
start--;
sum += nums[start];
if (min > (end - start)) {
min = end - start + 1;
}
}
}
if (min > nums.length) {
return 0;
}
return min;
};

解题思路二(双指针)

  1. 先求出nums数组中第一次符合条件的情况。也就是看nums的前多少位>=s。记录start,end。
  2. start,end即为我们的双指针,分别代表子序列的开头和结尾。
  3. 如果sum >= s, 我们就右移动start,求最小长度。
  4. 如果sum < s, 我们就右移动end,求符合条件的情况。
  5. 直到end到达nums的尾部结束。

    代码实现二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /**
    * @param {number} s
    * @param {number[]} nums
    * @return {number}
    */
    var minSubArrayLen = function(s, nums) {
    let sum = 0;
    let start = 0;
    let end = 0;
    let min = nums.length + 1;
    while (sum < s) {
    sum += nums[end++];
    }
    min = Math.min(end - start, min);
    while(end <= nums.length) {
    if (sum >= s) {
    sum -= nums[start++];
    if (sum >= s) {
    min = Math.min(end - start, min);
    }
    } else {
    sum += nums[end++];
    }
    }
    if (min > nums.length) {
    return 0;
    }
    return min;
    };

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。



示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。


提示:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

首先这个题可以使用3重for循环来遍历求值,并记录最接近target的值,但是会超时。

解题思路一

  1. 对数组进行从小到大排列
  2. 结果由三个数构成,我们提取出第一个数字nums[i], 剩下的值就是target-nums[i],我们需要在剩余数组元素中找到两个值nums[pb],nums[pc],最接近target-nums[i]
  3. 由于三个元素不可重复,所以我们首先遍历nums,然后在每次遍历中,设定pb的初始值为 i + 1pc的初始值为nums.length - 1
  4. 当前我们所求的当前值为target_close_help = nums[i] + nums[pb] + nums[pc];,另外用target_close记录最接近target的值。
  5. 每次遍历,nums[i]是确定的。所以只需要判断target_close_help 是否大于 target,如果大于pc--,否则pb++;若target_close_help等于target则直接返回。
    1. 由于nums小到大排列,所以pc--代表nums[pc]的值会变小target_close_help的值也会变,这样才会慢慢接近target,反之亦然pb++是同样的道理。
  6. 最后判读target_close_help 是否更接近target,若更接近则用target_close记录该次target_close_help
  7. 若没有相等于target的情况出现,最后则返回target_close的值。

    代码实现一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /**
    * @param {number[]} nums
    * @param {number} target
    * @return {number}
    */
    var threeSumClosest = function(nums, target) {
    nums = nums.sort((a,b) => {
    return a-b;
    })
    let target_close = 100001;
    for (let i = 0; i < nums.length; i++) {
    let pb = i + 1;
    let pc = nums.length - 1;
    while(pc > pb) {
    let target_close_help = nums[i] + nums[pb] + nums[pc];
    if (target_close_help < target) {
    pb++;
    } else if (target_close_help > target) {
    pc--;
    } else {
    return target;
    }
    if (Math.abs(target_close_help - target) < Math.abs(target_close - target)) {
    target_close = target_close_help;
    }
    }
    }
    return target_close;
    };

题目说明

1
2
3
4
5
根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

暴力方法就不提了,直接循环判断即可。

解题思路一(栈)

  1. 首先i位的值,为j-i的差值。j为下一位比i处大的最小下标
  2. 建立一个index栈,先入栈下标0,遍历T,判断T[i]T[index[index.length-1]] (栈顶元素对应的T内值)。
  3. T[i] > T[index[index.length-1]] 将栈顶排出indexTop = index.pop(); 赋值T[indexTop] = i - indexTop
  4. 循环此步骤直到栈顶对应的T值大于T[i]。
  5. 最后将i置入栈内。
  6. 遍历完数组,最后将栈排空,栈内剩余值都为0。(我们也可以初始化结果数组为0)

代码实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function(T) {
let res = new Array(T.length).fill(0);
let index = [0];
for (let i = 1; i < T.length; i++) {
while (T[i] > T[index[index.length - 1]]) {
let indexTop = index.pop();
res[indexTop] = i - indexTop;
}
index.push(i);
}
return res;
};

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:

你能不将整数转为字符串来解决这个问题吗?

解题思路一(字符串反转)

  1. 第一反应数字转字符串,然后前后对比。可以解决问题。

代码实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
let xStr = x + '';
let mid = +(xStr.length >> 1) + (+xStr.length % 2);
for (let i = 0; i < mid; i++) {
if (xStr.charAt(i) != xStr.charAt(xStr.length - i - 1)) {
return false
}
}
return true;
};

解题思路二(求得x的位数,xLen = Math.log10(x))

  1. 求得长度,接下来跟字符串一样了。
  2. parseInt(x / Math.pow(10, xLen)) 得到首位
  3. x % 10 得到尾位
  4. 对比是否相等

代码实现二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if(x < 0) {
return false
}
let xLen = parseInt(Math.log10(x));
while(x >= 1) {
if(x % 10 != parseInt(x / Math.pow(10, xLen))) {
return false
}
x = x % Math.pow(10, xLen);
x = parseInt(x /= 10);
xLen-=2;
}
return true
};

解题思路三(反转尾部)

  1. 这个是官方题解,反转尾部,直到前半部分小于等于反转后的尾部
  2. 将x的尾部移出来,反转。一直到x剩下的前半部分等于或者小于反转的尾部。
  3. 前半部分小于尾部,说明到了x的中间位。
    1. 跳出循环时,回文数只有两种情况。
    2. 第一种,x为偶数,直接判断首尾是否相同。
    3. 第二种,x为奇数,尾部除以10,再进行判断。

代码实现三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if(x < 0 || (x % 10 == 0 && x > 9)) {
return false
}
let xTail = 0;
let length = 0;
while(x > xTail) {
xTail *= 10;
xTail += x % 10;
x = parseInt(x / 10);
length++;
}
if (x == xTail || x == parseInt(xTail / 10)) {
return true
} else {
return false
}
};

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。



示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"


提示:

0 <= num < 231

解题思路一(斐波那契数列)

  1. 我一般做题前喜欢先测试几个用例, 测试完发现这就是斐波那契数列
  2. 该题主要判断 i-1, i 两位组合成的数字是否在(10, 25)闭区间内. 如果在就是斐波那契f(n) = f(n-1) + f(n-2), 否则跟上一种情况一致f(n) = f(n-1).

代码实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number} num
* @return {number}
*/
var translateNum = function(num) {
let numStr = num + '';
let res;
if (+(numStr[0] + numStr[1]) < 26 && +numStr[0] > 0) {
res = [1, 2];
} else {
res = [1, 1];
}
for(let i = 2; i < numStr.length; i++) {
if (+(numStr[i - 1] + numStr[i]) < 26 && +numStr[i - 1] > 0) {
res[i] = res[i - 1] + res[i - 2];
} else {
res[i] = res[i - 1];
}
}
return res[res.length-1]
};

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。



示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
注意:本题与主站 54 题相同:https://leetcode-cn.com/problems/spiral-matrix/

解题思路一(分层+递归)

  1. 首先明白题意,题目给出的示例数组是平铺的,不是特别清晰,可能短时间反应不过来它是想干嘛,我们先转换一下.
1
2
3
4
5
6
7
8
[
[1,2,3],
[4,5,6],
[7,8,9]
]
1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

矩形外围开始,顺时针输出.
  1. 因为是从外层开始顺时针的,所以我们先看最外层的我们如何得到.
    1. 首先最外层相当于一个正方形的四条边.(我们将顶点放入上下两条边)
    2. top: [2], 加入左上和右上两个顶点为[1, 2, 3]
    3. right: [6]
    4. bottom: [8], 加入左下和右下两个顶点为 [7, 8, 9]
    5. left: [4]
    6. 结果[1,2,3,6,9,8,7,4,5] 其中left, bottom 需要反转过来.(因为顺时针)
  2. 剥离之后,原来的矩形只剩下了[[5]], 假若我们矩形是多层的, 那么剩下来的仍然是个矩形,那么我们就可以将剩下的矩阵重新传入, 重复上面第二步求出top right bottom left

    代码实现一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /**
    * @param {number[][]} matrix
    * @return {number[]}
    */
    var spiralOrder = function(matrix) {
    if (matrix.length <= 1) {
    return matrix[0] || [];
    }
    if (matrix[0].length <= 1) {
    return matrix.reduce(function(sum, item) {
    return [...sum, ...item];
    }, [])
    }
    let top = matrix.shift();
    let right = [], left = [];
    for (let i = 0; i < matrix.length; i++) {
    right.push(matrix[i].pop());
    left.unshift(matrix[i].shift());
    }
    let bottom = matrix.pop().reverse();
    let res = [...top, ...right, ...bottom, ...left];
    return res.concat(spiralOrder(matrix));
    };

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。



示例:

输入: [1,2,3,4]
输出: [24,12,8,6]


提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

解题思路一(左右乘积列表)

  1. 如果可以用除法,那我们只需要求出列表乘积,然后除以nums[i]就是所求值了。
  2. 不用除法的情况下,我们需要求得nums[i]的左侧乘积L,和右侧乘积R,然后L*R求得目标值
  3. 那么我们创建两个乘积列表L,RL[i]代表从nums中从0 ~ i的乘积,R[i]代表nums中从i ~ nums.length - 1的乘积。
  4. 那么我们所求的output[i]就变成了L[I-1] * R[i+1];

    代码实现一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
    * @param {number[]} nums
    * @return {number[]}
    */
    var productExceptSelf = function(nums) {
    if (nums.length <= 2) {
    return nums.reverse();
    }
    let L = [nums[0]]
    let R = new Array(nums.length);
    R[nums.length-1] = nums[nums.length-1];
    for(let i = 1, j = nums.length - 2; i < nums.length; i++, j--) {
    L[i] = L[i-1] * nums[i];
    R[j] = R[j + 1] * nums[j];
    }
    for(let i = 1; i < nums.length - 1; i++) {
    nums[i] = L[i-1] * R[i + 1];
    }
    nums[0] = R[1];
    nums[nums.length-1] = L[nums.length-2];
    return nums;
    };

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。



示例 1:

输入:candies = [2,3,5,1,3], extraCandies = 3
输出:[true,true,true,false,true]
解释:
孩子 1 有 2 个糖果,如果他得到所有额外的糖果(3个),那么他总共有 5 个糖果,他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果,他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果,即使他得到所有额外的糖果,他也只有 4 个糖果,无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。
示例 2:

输入:candies = [4,2,1,1,2], extraCandies = 1
输出:[true,false,false,false,false]
解释:只有 1 个额外糖果,所以不管额外糖果给谁,只有孩子 1 可以成为拥有糖果最多的孩子。
示例 3:

输入:candies = [12,1,12], extraCandies = 10
输出:[true,false,true]

解题思路一

  1. 这个题的话,理解好题意,很好回答。
  2. 题意转化后的意思就是,看candies中各项candies[i] + extraCandies 是否是candies中的最大值max
  3. 那么首先我们先找出来最大值,然后看其他各位加上extraCandies 之后能不能大于或者等于它,可以的话,该i位为true,否则为false。

    代码实现一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
    * @param {number[]} candies
    * @param {number} extraCandies
    * @return {boolean[]}
    */
    var kidsWithCandies = function(candies, extraCandies) {
    let max = Math.max(...candies);
    return candies.map(item => {
    return (item + extraCandies >= max)
    })
    };

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。



示例:

输入:A = [4,5,0,-2,-3,1], K = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 K = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]


提示:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。