‘力扣简单题’

数组

数组取交集

1
const duplicatedValues = [...new Set(arr1)].filter(item => arr2.includes(item))

数组取差集

1
const diffValues = [...new Set([...arr1,...arr2])].filter(item => !b.includes(item) || !a.includes(item))

数组转对象

1
2
3
4
5
6
7
const arr = [1, 2, 3, 4]
const newObj = {...arr} // {0: 1, 1: 2, 2: 3, 3: 4}
const obj = {0: 0, 1: 1, 2: 2, length: 3}
// 对象转数组不能用展开操作符，因为展开操作符必须用在可迭代对象上
let newArr = [...obj] // Uncaught TypeError: object is not iterable...
// 可以使用Array.form()将类数组对象转为数组
let newArr = Array.from(obj) // [0, 1, 2]

数组摊平

1
2
3
4
5
6
7
8
[1, 2, [3, [4, 5]]].flat()
// [1, 2, 3, [4, 5]]
[1, 2, [3, [4, 5]]].flat(2)
// [1, 2, 3, 4, 5]
//上面代码中，flat()的参数为2，表示要拉平两层的嵌套数组。
//如果不管有多少层嵌套，都要转成一维数组，可以用Infinity关键字作为参数。
[1, [2, [3]]].flat(Infinity)
// [1, 2, 3]

数组去重

原地修改原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    // 记录nums元素个数
    let len = nums.length;
    let count = 0;
    //遍历数组元素，若后一项与前一项相同，则复制后面元素到重复位上
    for(var i = 1; i < nums.length; i++){
        if(nums[i] != nums[i-1]){
            nums[i - count] = nums[i];
        }else{
            count ++;
        }
    }
    return len - count;
};

不修改原数组

1
2
3
4
5
//数据结构Set数据结构去重。
function removeDuplicates(nums){
	let arr = [...new Set(nums)];
	return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
//利用object对象键值唯一性去重
function removeDuplicates(nums){
    let obj = {};
    let arr = [];
	for(let item of nums){
		obj[item] = 1;
	}
	for(let key in obj){
        arr.push(key);
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
// 利用indexOf判断
function removeDuplicates(nums){
	let arr = [];
	for(let i = 0; i < nums.length; i++){
		if(arr.indexOf(nums[i]) == -1){
			arr.push(nums[i]);
		}
	}
	return arr;
}
1
2


数组移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElement = function (nums, val) {
    // 记录数组元素个数，当匹配到，将最后的元素填到前面来
    var ans = nums.length;
    for(var i = 0; i< ans;){
        if(nums[i] == val){
            nums[i] = nums[ans -1];
            ans --;
        }else{
            i++;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
//最优解
var removeElement = function (nums, val) {
    // for...of循环数组，不等于val的值的存入nums数组中
    let count = 0;
    for(var num of nums){
        if(num != val){
            nums[ count++] = num;
        }
    }
    return count;
};

移除数组中的元素

移除数组 arr 中的所有值与 item 相等的元素，直接在给定的 arr 数组上进行操作，并将结果返回

示例1

输入

1
[1, 2, 2, 3, 4, 2, 2], 2

输出

1
[1, 3, 4]
1
2
3
4
5
6
7
8
9
10
function removeWithoutCopy(arr, item) {
    for(let i = 0; i < arr.length;i++){
    	if(arr.indexOf(item) == -1) break;
    	if(arr[i] == item){
    		arr.splice(i,1);
    		i--;
    	}
    }
    return arr;
}

数组搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

1
2
3
4
5
6
7
 var searchInsert = function (nums, target) {
    if (nums.indexOf(target) == -1) {
        nums.push(target);
        nums.sort((a,b) => a-b);
    }
    return nums.indexOf(target);
};

合并两个数组

改变原数组

给你两个有序整数数组 nums1 和 nums2*，请你将 *nums2 合并到 nums1 中，使 num1 成为一个有序数组。

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
 //从返回值为空可知，必须修改nums1中的参数
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m,n,...nums2);
    nums1.sort((a,b) => a-b)
};

不改变原数组

1
2
3
4
5
var merge = function(nums1, m, nums2, n) {
    let arr = [...nums1,...nums2];
    arr.splice(m,n);
    return arr;
};

和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let left = 0,
        right = nums.length - 1;
    while (left < right) {
        if (nums[left] + nums[right] == target) {
            return [nums[left], nums[right]];
        } else if (nums[left] + nums[right] < target) {
            left++;
        } else {
            right--;
        }
    }
};
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
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    //nums已经排序了，二分法
    let avg= target/2;
    let j;//接近avg的索引下标
    for(let i = 0; i< nums.length; i++){
        if(avg >= nums[i]){
            j=i;
            break;
        }
    }
    let left=j;
    for(let right=j;right<nums.length;right++){
        let x = target - nums[right];
        while(left>=0 && nums[left] > x){
            left--;
        }
        if(left < 0)break;
        if(nums[left] === x && left!==right)return [nums[left],nums[right]];
        left++;
    }
    return [];
};

和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function(target) {
    ////由规律得，序列中最大值是target的一半+ 或 - 1
    let index = target % 2 ? (target + 1)/2 : target/2;
    
    let res = [];   //存储结果
    let temp = [];   //存储从下标值
    let sum = 0;     //与target作比较
    for(let i = 1; i <= index; i++){
        temp.push(i);
        sum += i;
        while(sum > target){
            sum -= temp[0];
            temp.shift();
        }
        if(sum == target){
            temp.length >= 2 && res.push([...temp]);
        }
    }
    return res;
};

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums 
 * @return {number}
 */
//动态规划法(缺点：突然中断，算出来的是已经遍历过的数)
// 定义一个回调方法ans保存结果值，sum为求和后的值，将ans和sum中的最大值赋给ans
var maxSubArray = function(nums){
    let ans = nums[0];
    let sum = 0;
    for(let num of nums){
        if(sum > 0){
            sum += num;
        }else{
            sum = num;
        }
        ans = Math.max(ans,sum);
    }
    return ans;
};

滑动窗口最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if(nums.length===0)return [];  //边界值
    let max=[];
    for(let i=0; i+k-1<nums.length;i++){  
        let m=Math.max(...nums.slice(i,i+k));
        max.push(m);
    }
    return max;
};

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

1
2
3
4
5
6
7
8
9
//改变数组，利用数组的splice的增加删除操作原地操作
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums,k){
    nums.splice(0,0,...nums.splice(nums.length-k));
};

字符异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    // 利用哈希表存储，键值唯一
    let hash = new Map();
    for(let  i = 0; i < strs.length;i++){
        if(hash.has(str)){
            let temp = hash.get(str);
            temp.push(strs[i]);
            hash.set(str,temp);
        }else{
            hash.set(str,[strs]);
        }
    }
    return [...hash.values()]
};

####

罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

将可能出现的情况存到map中，定义一个变量存返回值。优先判断是否符合两个的字符。

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
/**
 * @param {string} s
 * @return {number}
 */
 
var romanToInt = function (s) {
    let map = {
        I : 1,
        IV: 4,
        V: 5,
        IX: 9,
        X: 10,
        XL: 40,
        L: 50,
        XC: 90,
        C: 100,
        CD: 400,
        D: 500,
        CM: 900,
        M: 1000
    }
    let ans = 0;
    for(var i = 0; i < s.length;){
        if(i + 1 < s.length && map[s.substring(i,i+2)]){
            ans += map[s.substring(i,i+2)];
            i += 2;
        }else{
            ans += map[s.substring(i,i+1)];
            i++;
        }
    }
    return ans;
};

数组中重复数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    for(let i = 0; i < nums.length; i++){
        // 利用向前遍历的与向后遍历的下标值不同找出重复值
        if(nums.lastIndexOf(nums[i]) != i){
            return nums[i];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 使用set,因为set自动忽略重复元素，遍历数组中元素，若长度未增加，则输出当前元素
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    let s=new Set();
    for(var i in nums){
        var curLenth=s.size;
        s.add(nums[i]);
        if(s.size==curLenth)
        return nums[i];
    }
};

二维数组的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

1
2
3
4
5
6
7
8
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    return matrix.flat(Infinity).includes(target);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
// 从左上角看，其上的数值都比该值小，右边的数值都比该值大
var findNumberIn2DArray = function (matrix, target) {
    if (matrix.length == 0) return false;
    let x = 0;
    let y = matrix.length - 1;
    while (x < matrix[0].length  && y >= 0) {
        if (matrix[y][x] > target) {
            y--;
        } else if (matrix[y][x] < target) {
            x++;
        } else {
            return true;
        }
    }
    return false;
};
在排序数组中查找数字

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

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
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    // 第一种方法
    // var count = 0;
    // for(let val of nums){
    //     if(val == target){
    //         count++;
    //     }
    // }
    // return count;
    // 第二种方法
    // let left = 0,
    //     len = nums.length;
    //     right = len - 1;
    // while(left < len && nums[left] != target){
    //     left++;
    // }
    // while(right > 0 && nums[right] != target){
    //     right--;
    // }
    // return left <= right ? right - left + 1 : 0;

    // 第三种方法
    let left = nums.indexOf(target);
    let right = nums.lastIndexOf(target);
    if(left != -1 && right != -1){
        return right - left + 1;
    }
    return 0;
};

字符串

字符串数组中的最长公共前缀

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
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

/**
 * @param {string[]} strs
 * @return {string}
 */
 var longestCommonPrefix = function(strs) {
    if(strs.length == 0) return '';
    let ans = strs[0];
    for(let i = 0;i < strs.length;i++){
        let  j = 0;
        for(;j < ans.length && j < strs[i].length;j++){
            if(ans[j] != strs[i][j]) break;
        }
        ans = ans.substr(0,j);
    }
    return ans;
};
let strs =  ["dog","racecar","car"]
console.log(longestCommonPrefix(strs));

有效字符串

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
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

/*
    边遍历便匹配，即遇到的第一个右括号必须与数组中最后一个元素匹配，否则无效。
    匹配完成后从数组中删除此元素。
    @param {string} s
    @return {boolean}
*/
/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s){
    //构建一个map结构的对象
    let map = {
        "(": ")",
        "{": "}",
        "[": "]"
    };
    let leftArr = []; //用于存放左括号
    for(let ch of s){
        if(ch in map) leftArr.push(ch);
        else{
            if(ch != map[leftArr.pop()]){
                return false;
            }
        }
    }
    return !leftArr.length;   //避免都是左括号
}

字符串中找最大数字

输入一串只有数字和字母的字符串，输出该字符串中最大的数字

输入：hellowolrd520hellowor

ld1314

输出：1314 

1
2
3
4
5
6
7
8
9
10
11
let str = 'hellowolrd520helloworld1314';

let reg = /\d+/g;

let arr = str.match(reg);

console.log(arr);

let max = Math.max(...arr);

console.log(max);
1
2
3
4
5
6
7
8
9
let str = 'hellowolrd520helloworld1314';

let reg = /[a-z]+/g;

let arr = str.split(reg);

let max = Math.max(...arr);

console.log(max);

最后一个单词的长度

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

1
2
3
4
5
6
7
8
var lengthOfLastWord = function(s) {
    // 去除字符串两边的空格
    s = s.trim();
    let arr = s.split(' ');
    let len = arr.length;
    if(len == 0) return 0;
    return arr[len - 1].length;
};

翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”

示例 2：

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
1
2
3
4
//先去空格（此步可省），分割为字符串数组，去除多余空格，翻转后转为字符串
var reverseWords = function(s) {
    return s.trim().split(' ').filter(x => !!x).reverse().join(' ');
};

颠倒二进制

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

1
2
3
4
5
//利用字符串的toString方法转为二进制数
var reverseBits = function(n) {
	//二进制以0b开头
    return +('0b'+n.toString(2).padStart(32,0).split('').reverse().join(''))
};

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

1
2
3
4
5
6
7
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.replace(/\s/g,'%20')
};

因为字符串是不可变的，所以如果直接采用从头到尾遍历原字符串检查空格，并且做替换。那么每次检查到空格后，都需要重新生成字符串。整个过程时间复杂度是 O(N^2)。

优化的关键：提前计算替换后的字符串的长度，避免每次都对字符串做改动。

整体思路如下：

遍历原字符串，统计空格和非空格字符个数，计算替换后的新字符的长度
准备两个指针，指针 i 指向原字符串，指针 j 指向新字符串
i 从头开始遍历原字符串
    str[i]是非空格，那么将 i 指向的字符放入新字符串的 j 位置。i 和 j 都增加 1。
    str[i]是空格，那么 j 指向的位置依次填入%20。i 增加 1，j 增加 3。

时间复杂度是 O(N)。因为需要对新字符串开辟容器，空间复杂度是 O(N)。

链表

1
2
3
4
function ListNode(val){
	this.val = val;
	this.next = null;
}

合并两个排序链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

1
2
3
> 输入：1->2->4, 1->3->4
> 输出：1->1->2->3->4->4
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var mergeTwoLists = function(l1,l2){
	if(l1 == null){
		return l2;
	}
	if(l2 == null){
		return l1;
	}
	if(l1.val < l2.val){
		l1.next = mergeTwoLists(l1.next,l2);
		return l1;
	}else{
		l2.next = mergeTwoLists(l1,l2.next);
		return l2;
	}
}

删除排序列表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
var deleteDuplicates = function(head) {
    let cur = head;
    while(cur && cur.next){
        if(cur.val == cur.next.val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next;
        }
    }
    return head;
};

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    let cnext = null;
    while (curr !== null) {
        cnext = curr.next;
        if (prev === null) {
            curr.next = null;
        } else {
            curr.next = prev;
        }
        prev = curr;
        curr = cnext;
    }
    return prev
};

迭代法

从前到后开始反转，我们需要三个指针，第一个指针指向当前头结点 head，第二个指针指向第二个节点 curP（当前结点）,第三个指针为保存下一个节点的临时节点 temp。

1、反转顺序为，先保存下一节点。

2、然后让当前结点的指向前一节点。

3、最后移动当前结点到下一结点。（head 头节点一开始初始化指向 null）。

4、重复该循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
var reverseList = function(head){
    if(head == null && head.next)  return head;
    let curNode = head.next;
    head.next = null;
    let temp = null;
    while(curNode != null){
        temp = curNode.next;
        curNode.next = head;
        head = curNode;
        curNode = temp;
    }
    return head;
}

删除链表中的值

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    let current = head;
    let prev = null;
    while(current.val != val){
        prev = current;
        current = current.next;
    }
    if(current == head){
        head = current.next;
    }else{
        prev.next = current.next;
    }
    return head;
};

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let length = 0;
    let current = head;
    let count = 0;
    while(current){
        length++;
        current = current.next;
    }
    current = head;
    while(count != length - k){
        count++;
        current = current.next;
    }
    return current;
};

树

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3

/
9 20
/
15 7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

   1
  / \
 2   2
/ \

3 3
/
4 4

返回 false 。

核心思路：
1，从左到右递归树的节点，记录节点的最大深度
2，在记录节点的同时对该树的节点的左子树与右子树的最大深度做一次对比，如果差值超过1则返回false

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isNodeBalance(node){
    if(!node) return 0;
    let left = isNodeBalance(node.left);
    let right = isNodeBalance(node.right);
    if(left < 0 || right < 0){
        // 短路机制，有一个子树不满足情况就返回
        return -1;
    }else{
        if(Math.abs(left - right) > 1){
            return -1;
        }else{
            return Math.max(left,right) + 1;
        }
    }
}
var isBalanced = function(root){
    let ret = isNodeBalance(root);
    if(ret >= 0)  return true;
    return false;
}

判断B树是否为A的子树

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
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    // 题目约定：约定空树不是任意一个树的子结构
    if (!A || !B) {
        return false;
    }

    return (
        isSubTree(A, B) ||
        isSubStructure(A.left, B) ||
        isSubStructure(A.right, B)
    );
};

function isSubTree(pRoot1, pRoot2) {
    // B树遍历完了，说明B是A的子结构
    if (!pRoot2) {
        return true;
    }
    // A遍历完了，但是B还没有遍历完，那么B肯定不是A的子结构
    if (!pRoot1) {
        return false;
    }

    if (pRoot1.val !== pRoot2.val) {
        return false;
    }

    return (
        isSubTree(pRoot1.left, pRoot2.left) &&
        isSubTree(pRoot1.right, pRoot2.right)
    );
}

层序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//层序遍历
   let levelOrderTraversal = function(root){
       if(!root) return false;   //头节点为空返回false
       let result = [];   //创建一个数组存放结果
       let tree = [];    //创建一个数组存放二叉树
       tree.push(root);    //先传入头节点
       while(tree.length){       //当tree数组长度不为空
           let node = tree.shift();     //将数组中的第一个节点放到node中
           result.push(node.key);         // 将node节点的值放入result中
           if(node.left){                 //如果node的左节点不为空，就将左节点压入tree数组中
               tree.push(node.left);
           }
           if(node.right){                //如果node的右节点不为空，就将左节点压入tree数组中
               tree.push(node.right);
           }
       }
       return result;
   }

之字形遍历

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
借助 level 变量标记层数，当 level 为偶数的时候，镜像翻转遍历结果。代码实现如下：
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const res = [];
    let level = 0; // 代表当前层数
    while (queue.length) {
        res[level] = []; // 第level层的遍历结果

        let levelNum = queue.length; // 第level层的节点数量
        while (levelNum--) {
            const front = queue.shift();
            res[level].push(front.val);
            if (front.left) queue.push(front.left);
            if (front.right) queue.push(front.right);
        }
        // 行号是偶数时，翻转当前层的遍历结果
        if (level % 2) {
            res[level].reverse();
        }

        level++;
    }
    return res;
};

二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

4

/
2 7
/ \ /
1 3 6 9
镜像输出：

4

/
7 2
/ \ /
9 6 3 1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    if(!root) return root;

    // 交换左右节点
    let leftCopy = root.left;
    root.left = root.right;
    root.right = leftCopy;

    // 对左右节点进行同样的操作
    mirrorTree(root.left);
    mirrorTree(root.right);

    return root;
};

对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return isMirror(root,root);
};

var isMirror = function(node1,node2){
    // 如果两个节点都是null的，势必是对称的
    if(!node1 && !node2) return true;
    // 如果其中一个为null，另一个不为null，则不是对称的
    if(!node1 || !node2) return false;

    return node1.val == node2.val && isMirror(node1.left,node2.right) && isMirror(node1.right,node2.left);
}

正则

正则表达式匹配

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

1
2
3
var isMatch = function(s, p) {
    return new RegExp("^" + p + "$", "g").test(s);
};

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”0123”及”-1E-16”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isNumber = function(s) {
    var point = s.match(/\./g);
    if((point && point.length>1) || !/\d/.test(s)){
        return false;
    }
    s = s.replace(/^\s*|\s*$/g,"");   //消除前后空格
    
    if(!/e/i.test(s)){  //不含e的: 正负+整数+点+小数随意搭配 
        return /^[\+\-]?(\d*\.?\d*)$/i.test(s); 
    }else{              //含e的: 正负+ (整数+点+小数) 随意搭配 +e+ 正负可带可不带+ 数字一定要带  
        return /^[\+\-]?((\d+\.?\d*)|(\d*\.?\d+))e[\+\-]?\d+$/i.test(s)
    }
    return false;
};

简单排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
实现数组的sort((a,b) => a-b);
function Bubble_sort(arr){
let len = arr.length;
	for(let p = len - 1; p >= 0;p--){
	let flag = 0;    //标记交换
		for(let i = 0; i < p; i++){   //一趟冒泡
			if(arr[i] > arr[i+1]){
				swap(arr[i],arr[i+1]);
			}
		}
		if(flag == 0)  break;   //全程无交换
	}
}

最好情况：顺序 T = O(N)

最坏情况： 逆序 T = O(pow(N,2))

从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3

/
9 20
/
15 7

返回：

[3,9,20,15,7]

提示：

节点总数 <= 1000
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
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function(root) {
	//判断是否为空树
    if(!root){
        return [];
    }
    let data = [];
    //将头节点放到队列中
    let queue = [root];
    while(queue.length != 0){
        let first = queue.shift();
        data.push(first.val);
        first.left && queue.push(first.left);
        first.right && queue.push(first.right);
    }
    return data;
};

其他

圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function(n, m) {
    let ans = 0;
    for(let i = 2; i <= n; i++){
        ans = (ans + m) % i;
    }
    return ans;
};

股票最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    //此问题的实质就是找到两个差值最大的数，前提是小的在前，大的在后
    //要把此问题的时间复杂度控制在O(n-1)并不难
    let profits = 0;
    let min = prices[0];
    const len = prices.length;
    for(let i = 1; i < len; i ++) {
        min = Math.min(min, prices[i]);
        profits = Math.max(profits, prices[i] - min);
    }
    return profits;
};

游戏必败问题

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

Nim 游戏

如果堆中石头的数量 nnn 不能被 444 整除，那么你总是可以赢得 Nim 游戏的胜利。

推理

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。

显然，它以相同的模式不断重复 n=4,8,12,16,…n=4,8,12,16,\dotsn=4,8,12,16,…，基本可以看出是 4的倍数。

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return !!(n % 4);
};

url解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function parseUrl(url) {
    let s = url.split('?')[0];
    let str = url.split('?')[1];
    let items = str.split('&');
    let res = {};
    let result = {};
    let arr = s.split("://");
    result['protocol'] = arr[0];
    result['host'] = arr[1].substr(0, arr[1].indexOf('/'));
    if(arr[1].indexOf('/') != arr[1].length - 1){
        result['path'] = arr[1].substr(arr[1].indexOf('/'));
    }
    for (let i = 0, len = items.length; i < len; ++i) {
        res = items[i].split('=');
        result[res[0]] = res[1];
        if(res[1].split('#').length > 1){
            result[res[0]] = res[1].split('#')[0];
            result['hash'] = res[1].split('#')[1];
        }
    }
    return JSON.stringify(result).replace(/\"/g,"'");
}

读取一行输入：read_line()，输出一行：print(something)，注意使用print函数输出时，末尾自动带有换行符，无需自己添加；

  • 读取size个字符：gets(size)
    将读取至多size个字符，当还未达到size个时如果遇到回车或结束符，会提前结束。回车符可能会包含在返回值中。
  • 输出信息：printsth(sth, …)
    往控制台输出sth，当有多个参数时，空格分隔；最后不加回车。
  • 输出一行：print(sth, …) console.error(sth, …) console.debug(sth, …) console.info(sth, …) console.log(sth, …)
    往控制台输出sth，当有多个参数时，空格分隔；最后加回车。
  • 读取一个（长）整数：readInt()
    从控制台读取一个（长）整数。
  • 读取一个浮点型：readDouble()
    从控制台读取一个浮点型。
  • 读取一行输入：read_line()

Math

模拟 sqrt的整数部分

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
4
5
6
var mySqrt = function(x){
	return Math.trunc(Math.sqrt(x));
}
//es6新增的去除一个数的小数部分，
非数值的话会先将其转为数值，
控制和无法截取整数的值，返回NaN

判断素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function sushu(n){
    if(n == 0 || n == 1){
        return false;
    }
    if(n ==  2){
        return true;
    }
    for(var i = 2; i <= Math.round(Math.sqrt(n));i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

遍历n内的素数

1
2
3
4
5
6
7
8
9
10
function getSushu(n){
	//存放素数的数组
	var arr = [];
	for(var i = 2; i < n; i++){
		if(sushu(i)){
			arr.push(i);
		}
	}
	console.log(...arr);
}

值加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

1
2
3
4
5
6
7
8
9
10
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    let str = Number(digits.join('')) + 1;
    let arr = str.toString().split('');
    return arr;
 };
 //当数字位达32位及以上时，数值相加有问题
1
2
3
4
5
var plusOne = function(digits) {
    return BigInt(BigInt(digits.join('')) + 1n).toString().split('')
};
//利用BigInt解决数字边界问题
//要创建BigInt，只需在整数的末尾追加n即可

递增求和

1
2
3
var sumNums = function(n) {
    return (1+n)*n/2;
};

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1
2
3
4
5
6
7
8
9
10
var sumNums = function(n) {
    return multi(n, n+1, 0) >> 1
};

function multi(a, b, sum) {
    if (b === 0) return sum

    if (b & 1) return multi(a, b-1, sum + a)
    return multi(a + a, b >> 1, sum)
}

斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

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
39
40
41
42
43
44
/**
 * @param {number} n
 * @return {number}
 */
 var fib = function(n){
 	// 1.非常普通，没有优化的递归
 	//优点：非常容易想到，fib在不加额外参	  数且不引入外部变量的情况下只能这么调用自身
    //缺点：fib会重复计算之前的项，计算结果是一次性的，极其浪费时间和空间，在本题必定超时，完全无法通过
	/*
	if(n<=1) return n;
	return (fib(n-1) + fib(n-2)) % 1000000007;
	*/
	// 2.普通的尾递归+ES6尾调用优化解法
	// 优点：不创建心得栈帧，现有栈帧被重复利用，不会爆栈，性能比未经优化的递归明显提高
	// 缺点：需要反复清除栈帧的数据，性能不如下面的循环解法。
	/* 'use strict';
	function f(n,a=1,b=1){
		if(n <= 1) return n;
		if(n == 2) return b;
		return f(n-1,b,(a+b)%100000007);  //最后一步调用自身，将数据处理的步骤变成参数的变化
	}
	return f(n);
	*/
	 //4.很好的循环计算解法

    //优点：每一次计算结果都能得到利用，易于理解，只保存前两个计算结果，性能最优
    //缺点：没有明显的缺点，在本题中记得看清题目中取模的要求

    //注：其他题解有提到，但这题不需要用到新的BigInt类型，取模就是为了防止结果溢出，
    //而且中间计算结果也达不到 Number.MAX_SAFE_INTEGER (9007199254740991) 的量级
    //变量c不是必要的，可以直接用代数方法或ES6解构赋值做进一步优化，这种循环解法也可以看做是一种动态规划解法

    
        if(n<=1)return n;
        let a=b=1,c=0;
        while(n-->0){

            a = b;
            b = c;
            c = (a + b) % 1000000007;

        }
        return c;
 }

青蛙跳台阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

答题思路

  1. 如果只有1级台阶，那显然只有一种跳法
  2. 如果有2级台阶，那么就有2种跳法，一种是分2次跳。每次跳1级，另一种就是一次跳2级
  3. 如果台阶级数大于2，设为n的话，这时我们把n级台阶时的跳法看成n的函数，记为f(n),第一次跳的时候有2种不同的选择：一是第一次跳一级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1),二是第一次跳二级，此时跳法的数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2),因此n级台阶的不同跳法的总数为f(n) = f(n-1) + f(n-2)，不难看出就是斐波那契数列

数学函数表示如下f(x)=\left\{ \begin{aligned} & 0 & n=0 \\ & 1 & n=1 \\ & 2 & n=2 \\ & f(n-1)+f(n-2) & n > 2 \end{aligned} \right.

1
2
3
4
5
6
7
8
9
var numWays = function(n){
	if( n<= 1) return 1;
	let dp = [1,1,2];
	const ModNum = 1e9+7;
	for(let i = 2;i <= n;i ++){
		dp[i] = (dp[i - 1] + dp[i - 2]) % ModNum;
	}nx
	return dp[n];
}

本文标题:‘力扣简单题’

文章作者:陈楚吟

发布时间:2020-06-23, 15:43:03

最后更新:2020-08-08, 19:51:46

原始链接:http://yoursite.com/2020/06/23/‘力扣简单题’/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数组
    1. 1.0.1. 数组取交集
    2. 1.0.2. 数组取差集
    3. 1.0.3. 数组转对象
    4. 1.0.4. 数组摊平
    5. 1.0.5. 数组去重
    6. 1.0.6. 数组移除元素
    7. 1.0.7. 移除数组中的元素
    8. 1.0.8. 数组搜索插入位置
    9. 1.0.9. 合并两个数组
    10. 1.0.10. 和为s的两个数字
    11. 1.0.11. 和为s的连续正数序列
    12. 1.0.12. 最大子序和
    13. 1.0.13. 滑动窗口最大值
    14. 1.0.14. 旋转数组
    15. 1.0.15. 字符异位词分组
    16. 1.0.16. 罗马数字转整数
    17. 1.0.17. 数组中重复数字
    18. 1.0.18. 二维数组的查找
      1. 1.0.18.0.1. 在排序数组中查找数字
  • 2. 字符串
    1. 2.0.1. 字符串数组中的最长公共前缀
    2. 2.0.2. 有效字符串
    3. 2.0.3. 字符串中找最大数字
    4. 2.0.4. 最后一个单词的长度
    5. 2.0.5. 翻转单词顺序
    6. 2.0.6. 颠倒二进制
    7. 2.0.7. 替换空格
  • 3. 链表
    1. 3.0.1. 合并两个排序链表
    2. 3.0.2. 删除排序列表中的重复元素
    3. 3.0.3. 反转链表
    4. 3.0.4. 删除链表中的值
    5. 3.0.5. 链表中倒数第k个节点
  • 4. 树
    1. 4.0.1. 平衡二叉树
    2. 4.0.2. 判断B树是否为A的子树
    3. 4.0.3. 层序遍历二叉树
    4. 4.0.4. 之字形遍历
    5. 4.0.5. 二叉树的镜像
    6. 4.0.6. 对称的二叉树
  • 5. 正则
    1. 5.0.1. 正则表达式匹配
    2. 5.0.2. 表示数值的字符串
  • 6. 简单排序
    1. 6.0.1. 冒泡排序
    2. 6.0.2. 从上到下打印二叉树
    3. 6.0.3. 其他
    4. 6.0.4. 圆圈中最后剩下的数字
    5. 6.0.5. 股票最大利润
    6. 6.0.6. 游戏必败问题
    7. 6.0.7. url解析
  • 7. Math
    1. 7.0.1. 模拟 sqrt的整数部分
    2. 7.0.2. 判断素数
    3. 7.0.3. 遍历n内的素数
    4. 7.0.4. 值加一
    5. 7.0.5. 递增求和
    6. 7.0.6. 斐波那契数列
    7. 7.0.7. 青蛙跳台阶问题
    • |