Title: leetcode

Q: 双指针问题的思路以及相关题目有哪些？
A: 双指针简化问题，优化复杂度的题目还是挺多的，这类题目的关键点是想到使用双指针，
双指针有很多种，最常见的是头尾指针，当然还有别的。 比如如何最优地获取链表的倒数第三个节点？这个时候需要一个指针走三步，另外一个指针再走（有点龟兔赛跑的意思）
相关题目：
- 11.container-with-most-water 盛最多的水
- 26.remove-duplicates-from-sorted-array 删除有序数组中的重复元素
- 167.two-sum-ii-input-array-is-sorted  two-sum 进化版
- 19. removeNthNodeFromEndofList 删除链表中倒数第N个节点

Q: 如何用栈的特点来简化操作， 涉及到的题目有哪些？
A: 由于栈的特点是先进后出（FILO），我们可以用来解决一些直觉上需要递归的问题， 或者做一些”匹配“操作，比如括号匹配。
相关题目：
- 20. validParentheses
- DFS算法相关的题目
-150.evaluate-reverse-polish-notation   逆波兰表达式
- 445.addTwoNumbers ii

Q: 二分法解决问题的关键点是什么，相关问题有哪些
A: 二分法解决问题的关键是是否可以将问题的规模缩小一半（如果缩小到三分之一就是三分法了），关键点并不是是否是有序数组，这个只是二分法解决问题的一个很小子集。
相关问题：
- 老鼠试毒
- 875.koko-eating-bananas

Q: 滑动窗口问题的思路以及相关题目有哪些？
A: 滑动窗口算法广泛应用于网络协议等，其实滑动窗口算法是一种思路，可以解决很多问题，比较适合滑动窗口解决的问题通常是题目要求连续的情况。
解题的套路通常是建立一个数组来表示滑动窗口，然后不断更新滑动窗口的范围（通常是往后移动），
解题的不同点其实就在于如何更新滑动窗口的范围而已。
相关题目：
- 3.longestSubstringWithoutRepeatingCharacters
- 209.minimum-size-subarray-sum
- 239.sliding-window-maximum

Q: 回溯法解题的思路以及相关题目有哪些？
A: 回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
这个过程可以形象地比喻成我们打游戏，存档，打不过了或者达到了某个分支结局了，就回到存档点继续探索，知道完成所有的游戏结局。
这种题目有一个通用的解题框架，拿combinationSum来说就是：
1
2
3
4
5
6
7
8
9
function backtrack(list, tempList, nums, remain, start) {
  if (remain < 0) return;
  else if (remain === 0) return list.push([...tempList]);
  for (let i = start; i < nums.length; i++) {
    tempList.push(nums[i]);
    backtrack(list, tempList, nums, remain - nums[i], i); // 数字可以重复使用， i + 1代表不可以重复利用
    tempList.pop();
  }
}
1
2
3
4
5
var combinationSum = function(candidates, target) {
  const list = [];
  backtrack(list, [], candidates.sort((a, b) => a - b), target, 0);
  return list;
};
用图表示就是：
相关题目：
- 39.combination-sum
- 40.combination-sum-ii
- 46.permutations
- 47.permutations-ii
- 78.subsets
- 90.subsets-ii

Q: 数论问题的关键点是什么，相关问题有哪些
A: 解决这类题目的关键是需要了解一些基本的数论知识。 比如常见的性质有：
1. sum([1,n]) = n * (n+1) / 2
2. 质数的概念和性质
3. 欧拉定理
4. 幂运算
5. 裴蜀定理
等等
我们只有对这些基本的定理比较熟练，做这种题目才能手到擒来，因此建议做这部分题目之前学习一下数论的知识，至少是《初等数论》。
相关题目：
- 172.factorial-trailing-zeroes
- 204.count-primes
- 263.ugly-number
- 268.missing-number
- 326.power-of-three
- 342.power-of-four
- 365.water-and-jug-problem
- 575.distribute-candies

Q: 位运算问题的关键点是什么，相关问题有哪些
A: 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果。
位运算在很多地方都有应用，位运算的性质在解决一些题目的时候有着先天的优势，一些精妙的解法也是基于位运算的性质。
解决好这部分题目的关键是了解位运算的性质，并且能够在头脑中建立这种位的表示和位的运算模型。
常见的性质有：
1.  与， 或， 异或 的特点和性质
2. 接上， 比如异或的特点有： 任何数和本身异或则为0
3. n && 1 === 1 则表示n为奇数，否则为偶数
4. n & (n - 1) 可以消除 n 最后的一个1
n & (n - 1) === 0 表示 n为2的幂次方
等等
有的题目比较直接，要求你直接运用位运算进行解答（比如190.reverse-bits），有些则比较隐含，可以借助位运算以及位的性质做到“精妙”的效果（比如老鼠试毒问题，136.single-number 问题）。
^如果碰到这种题目没有思路，可以尝试在纸上画出来一些特殊的数字的二进制形式，然后看看能不能找出规律，好多题目都可以这样找到思路
相关题目：
- 136.single-number
- 190.reverse-bits
- 191.number-of-1-bits
- 201.bitwise-and-of-numbers-range
- 338.counting-bits
- 老鼠试毒问题
- 用位运算实现加法运算

Q: 题目：2.addTwoNumbers
描述：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
A: 思路：
设立一个表示进位的变量carried，建立一个新链表，
把输入的两个链表从头往后同时处理，每两个相加，将结果加上carried后的值作为一个新节点到新链表后面。
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
关键点：
1. 链表这种数据结构的特点和使用
2. 用一个carried变量来实现进位的功能，每次相加之后计算carried，并用于下一位的计算
代码：
 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
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  var carried = 0; // 用于进位
  const head = new ListNode();
  const noop = {
    val: 0,
    next: null
  };
  let currentL1 = l1;
  let currentL2 = l2;
  let currentNode = head; // 返回的链表的当前node
  let newNode; // 声明在外面节省内存
  let previousNode; // 记录前一个节点，便于删除最后一个节点
  while (currentL1 || currentL2) {
    newNode = new ListNode(0);
    currentNode.val =
      ((currentL1 || noop).val + (currentL2 || noop).val + carried) % 10;
    currentNode.next = newNode;
    previousNode = currentNode;
    currentNode = newNode;
    if ((currentL1 || noop).val + (currentL2 || noop).val + carried >= 10) {
      carried = 1;
    } else {
      carried = 0;
    }
    currentL1 = (currentL1 || noop).next;
    currentL2 = (currentL2 || noop).next;
  }
  if (carried) {
    // 还有位没进呢
    previousNode.next = new ListNode(carried)
  } else {
    previousNode.next = null;
  }
  return head;
};

Q: 题目：3.longestSubstringWithoutRepeatingCharacters
描述：
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
A: 思路：
用一个hashmap来建立字符和其出现位置之间的映射。
维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
（1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；
（2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
（3）重复（1）（2），直到左边索引无法再移动；
（4）维护一个结果res，每次用出现过的窗口大小来更新结果res，最后返回res获取结果。
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
关键点：
1. 用一个mapper记录出现过并且没有被删除的字符
2. 用一个滑动窗口记录当前index开始的最大的不重复的字符序列
3. 用res去记录目前位置最大的长度，每次滑动窗口更新就去决定是否需要更新res
代码：
 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
var lengthOfLongestSubstring = function(s) {
  const mapper = {}; // 记录已经出现过的charactor
  let res = 0;
  let slidingWindow = [];
  for (let c of s) {
    if (mapper[c]) {
      // 已经出现过了
      // 则删除
      const delIndex = slidingWindow.findIndex(_c => _c === c);
      for (let i = 0 ; i < delIndex; i++) {
        mapper[slidingWindow[i]] = false;
      }
      slidingWindow = slidingWindow.slice(delIndex + 1).concat(c);
    } else {
      // 新字符
      if (slidingWindow.push(c) > res) {
        res = slidingWindow.length;
      }
    }
    mapper[c] = true;
  }
  return res;
};

Q: 题目：11.container-with-most-water
描述：
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
A: 思路：
符合直觉的解法是，我们可以对两两进行求解，计算可以承载的水量。 然后不断更新最大值，最后返回最大值即可。
这种解法，需要两层循环，时间复杂度是O(n^2)
eg:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    // 这个解法比较暴力，效率比较低
    // 时间复杂度是O(n^2)
    let max = 0;
    for(let i = 0; i < height.length; i++) {
        for(let j = i + 1; j < height.length; j++) {
            const currentArea = Math.abs(i - j) * Math.min(height[i], height[j]);
            if (currentArea > max) {
                max = currentArea;
            }
        }
    }
    return max;
> 这种符合直觉的解法有点像冒泡排序， 大家可以稍微类比一下
那么有没有更加优的解法呢？我们来换个角度来思考这个问题，上述的解法是通过两两组合，这无疑是完备的，
那我门是否可以先计算长度为n的面积，然后计算长度为n-1的面积，... 计算长度为1的面积。 这样去不断更新最大值呢？
很显然这种解法也是完备的，但是似乎时间复杂度还是O(n ^ 2), 不要着急。
考虑一下，如果我们计算n-1长度的面积的时候,是直接直接排除一半的结果的。
如图：
比如我们计算n面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为n-1的做法是没有意义的，
因为`新的形成的面积变成了(n-1) * heightOfLeft 这个面积一定比刚才的长度为n的面积nn * heightOfLeft 小`
也就是说最大面积`一定是当前的面积或者通过移动短的线段得到`。
关键点：
- 双指针优化时间复杂度
代码：
 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
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    if (!height || height.length <= 1) return 0;
    // 双指针来进行优化
    // 时间复杂度是O(n)
    let leftPos = 0;
    let rightPos = height.length - 1;
    let max = 0;
    while(leftPos < rightPos) {
        const currentArea = Math.abs(leftPos - rightPos) * Math.min(height[leftPos] , height[rightPos]);
        if (currentArea > max) {
            max = currentArea;
        }
        // 更新小的
        if (height[leftPos] < height[rightPos]) {
            leftPos++;
        } else { // 如果相等就随便了
            rightPos--;
        }
    }
    return max;
};