每日打卡算法题

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // for(let i = 0; i < nums.length; i++) {
    //     for(let j = 0; j<nums.length; j++) {
    //         if(nums[i] + nums[j] === target && i !== j) return [i,j]
    //     }
    // }
    let obj = {}
    for(let i =0; i<nums.length; i++) {
        let num = nums[i];
        if(num in obj) {
            return [obj[num], i]
        } else {
            obj[target - num] = i
        }
    }
};

利用空间换取时间

有效的括号 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = []
    const map = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    for(let i=0;i<s.length;i++) {
        if(s[i] in map) {
            stack.push(s[i])
        } else {
            if(map[stack.pop()] !== s[i]) {
                return false
            }
        }
    }
    return !stack.length
};

利用字典的思想

简化路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const stack = []
    const paths = path.split('/')
    for(let i =0;i<paths.length;i++) {
        const p = paths[i]
        if(p === '..') {
            stack.pop()
        } else if(p && p !== '.') {
            stack.push(p)
        }
    }
    return '/' + stack.join('/')
};

一个简单的链表

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 手动实现链表结构
class Node {
  constructor(element) {
    this.element = element
    this.next =null
  }
}

class LinkNodeList {
  constructor() {
    this.head = null
    this.length = 0
  }

  append(element) {
    let node = new Node(element)
    let cur
    if(!this.head) {
      this.head = node
    } else {
      cur = this.head
      while(cur.next) {
        cur = cur.next 
      }
      cur.next =node
    }
    this.length += 1
  }

  print() {
    let cur = this.head
    let ret = []
    while(cur) {
      ret.push(cur.element)
      cur = cur.next
    }
    return ret.join('==>')
  }

  removeAt(index) {
    let prev
    let cur = this.head
    let i = 0
    if(index === 0) {
      this.head = cur.next
    } else {
      while(i < index) {
        prev = cur
        cur = cur.next
        i++
      }
      prev.next = cur.next
      cur.next = null
    }
    this.length -= 1;
    return cur.element;
  }
}

const linkList = new LinkNodeList()
linkList.append('hah')
linkList.append('yy')
linkList.removeAt(1)
linkList.print()

链表的中间节点

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
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    // 初学时的暴力解法
    // let n = 0
    // let p = {}
    // p.next = head
    // let node = p
    // let arr = []
    // while(node) {
    //     if(node.val) {
    //         arr.push(node)
    //         n++
    //     }
    //     node = node.next
    // }
    // if(n%2 === 0) {
    //     return arr[n/2]
    // } else {
    //     return arr[Math.floor(n/2)]
    // }
    // 快慢指针法
    let slow = head
    let fast = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

没有写边界判断的逻辑，只是一个简单的熟悉链表结构的demo

链表的删除

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    // 添加一个哨兵元素
    let prev = {
        next: head
    }
    let cur = prev

    while(cur.next) {
        if(cur.next.val === val) {
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return prev.next
};

链表翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let cur = head
    let prev = null
    while(cur !== null) {
        let next = cur.next
        cur.next = prev
        prev = cur
        cur = next    
    }
    return prev
};

环形链表II

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 singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    // 解法一
    // const cache = new Set()
    // while(head) {
    //     if(cache.has(head)) {
    //         return head
    //     } else {
    //         cache.add(head)
    //         head = head.next
    //     }
    // }
    // return null
    // 解法二 快慢指针
    let fast = head
    let slow = head
    let start = head
    
    while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(slow == fast) {
            while(slow && start) {
                if(slow == start) {
                    return slow
                }
                slow = slow.next
                start = start.next         
            }
        }
    }
    return null
};

翻转二叉树

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
/*
 * @lc app=leetcode.cn id=226 lang=javascript
 *
 * [226] 翻转二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
  if(root == null) {
    return root
  }
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]

  return root
};

二叉树遍历

前序遍历：自己-》left-》right
中序遍历：left-》自己-》right
后序遍历：left-》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
28
29
30
31
32
33
34
35
36
37
// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root, arr = []) {
  // 递归
  // if(root) {
  //   arr.push(root.val)
  //   preorderTraversal(root.left, arr)
  //   preorderTraversal(root.right, arr)
  // }
  // return arr
  // 迭代
  let result = []
  let stack = [] // 用来得到right
  let cur = root

  while(cur || stack.length > 0) {
    while(cur) {
      result.push(cur.val)
      stack.push(cur)
      cur = cur.left
    }
    cur = stack.pop()
    cur = cur.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
var inorderTraversal = function(root) {
    // 递归
    // if(root == null) {
    //     return arr
    // }
    // inorderTraversal(root.left, arr)
    // if(root.val) arr.push(root.val)
    // inorderTraversal(root.right, arr)
    // return arr
    // 迭代
    let result = []
    let stack = []
    let cur = root
    while(cur || stack.length > 0) {
        while(cur) {
            stack.push(cur)
            cur = cur.left
        }
        cur = stack.pop()
        result.push(cur.val)
        cur = cur.right
    }
    return result
};

二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    // 递归
    if(root == null) {
        return 0
    }
    
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var lowestCommonAncestor = function(root, p, q) {
    // 递归
    // if(p.val > root.val && q.val > root.val) {
    //     return lowestCommonAncestor(root.right, p, q)
    // } else if(p.val < root.val && q.val < root.val) {
    //     return lowestCommonAncestor(root.left, p, q)
    // } else {
    //     return root
    // }
    // 迭代
    while(root) {
        if(p.val > root.val && q.val > root.val) {
            root = root.right
        } else if(q.val < root.val && p.val < root.val) {
            root = root.left
        } else {
            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
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // 递归
    if(root == null || root == p || root == q) {
        return root
    }

    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)

    if(left == null) {
        return right
    }
    if(right == null) {
        return left
    }
    return root
};

二分法查找

  1. 二分法依赖顺序表结构
  2. 二分法查找针对的是有序数据
  3. 数据量太大、太小不适合二分法

四种常见的二分法变形问题：

  1. 查找第一个值等于给定值的元素
  2. 查找最后一个值等于给定值的元素
  3. 查找第一个大于等于给定值的元素
  4. 查找最后一个小于等于给定值的元素