斐波那契数列

使用递归

1
2
3
4
5
6
7
8
9
10
11
12
var cache = {};
function fib(n){
    if(cache.hasOwnProperty(n)){
        return cache[n];
    }
    var v= n == 0 || n == 1?fib(n-1) + fib(n-2)
    cache[n] = v;
    return v;
}
for(let i=0;i<=9;i++){
    fib(i);
}

不使用递归

1
2
3
4
5
6
function a(n){
    var arr = [1,1];
    while(arr.length <= n){
        arr.push(arr[arr.length-1] + arr[ arr.length-2])
}
console.log(arr)

重复字符串中连续重复次数最多的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
var s = "aaadafakssssshhhhhrrrrrgggggkkkkkffffwwwwddddd"
var maxRepeatCount = 0,maxReapeatChar = '';
var i = 0,j = 1;
while ( i <= s.length - 1 ) {
    if(s[i] !== s[j]){
        i = j;
        if(maxRepeatCount < j-i){
            maxRepeatCount = j-i;
            maxReapeatChar = s[i]
        }
    }
    j++;
}

智能重复

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
var str = "2[1[a]3[b]2[3[c]4[d]]]";
function smartRepeat(str) {
    var index = 0,
        stack1 = [],
        stack2 = [],
        rest = str;
    while (index < str.length - 1) {
        rest = str.substring(index);
        if (/^\d+\[/.test(rest)) {
            // 剩余字符串以数字开头，1）取出这个数字压入数字栈；2）字符栈压入空字符串；3）指针后移至[之后
            let times = Number(rest.match(/^(\d+)\[/)[1]);
            stack1.push(times);
            stack2.push('');
            index += times.toString().length + 1;
        } else if (/^\w+\]/.test(rest)) {
            // 剩余字符串以字母开头，1）取出字符并压入字符栈；2）指针后移至字符之后
            let word = rest.match(/^(\w+)\]/)[1];
            stack2[stack2.length - 1] = word;
            index += word.length;
        } else if (rest[0] == ']'){
            // 剩余字符串以]开头，1）数字栈弹栈；2）字符栈弹栈3）弹出的字符重复刚才弹栈的次数并拼接到新的字符栈顶
            let times = stack1.pop();
            let word = stack2.pop();
            stack2[stack2.length - 1] += word.repeat(times)
            index++;
        }
    }
    // 当while结束后，stack1和stack2中肯定存在剩余1项，返回stack2中剩余的这一项，重复stack1中剩余的这一项的次数，返回这个字符串
    return stack2[0].repeat(stack1[0])
}

判断标签是否闭合

使用while与replace

1
2
3
4
5
6
7
8
9
10
function isValid(s) {
    while (s.length) {
        let temp = s;
        s = s.replace('()', '');
        s = s.replace('[]', '');
        s = s.replace('{}', '');
        if (s == temp) return false
    }
    return true;
}

使用指针与栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isValid(s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for(let i = 0; i < s.length ; i++) {
        // 如果此字符在集合中存在，存入栈中
        if(map[s[i]]) {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            // 如果此字符与栈顶不同，则说明字符串并不是封闭的
            return false
        }
    }
    return stack.length === 0
}

树

树的遍历

深度优先（DFC）

以深度优先为策略，从根节点开始一直遍历到某个叶子结点，再遍历另外一个分支

广度优先（BFC）

##路径总和

相同的树

对称二叉树

翻转二叉树

另一个树的子树

验证二叉搜索树

二叉树的最小深度

平衡二叉树

将有序数组转换为二叉搜索树

二叉搜索树迭代器

二叉搜索树的最近公共祖先

二叉树的最近公共祖先

链表

合并两个有序链表

反转链表

回文链表

倒数第K个节点

找出链表的中间节点

两个链表的第一个公共节点

LRU的缓存机制

#数组

打乱数组

构建乘积数组

##使数组唯一的最小增量
##扑克牌中的顺子
##数组的交集
##数组的交集II
##数组中的第K个最大元素
##合并两个有序数组
##全排列
##螺旋矩阵
##螺旋矩阵II
##三数之和
##更接近的三数之和

数学

##计算质数
##求众数
##中位数
##只出现一次的数字
##有效的三角形个数

#动态规划

斐波那契数列

买卖股票的最佳时机I

买卖股票的最佳时机II

盛最多水的容器

接雨水

无重复字符的最长子串

最大子序和

最长公共前缀

最长回文子串

打家劫舍

打家劫舍 II

打家劫舍 III

最后更新： 2021年06月21日 16:13