LeetCode

分类

做题方法

发现输入和输出的规律，寻找突破点
当给的例子太简单的时候可以自己多画一些复杂的例子
选择合适的数据结构和程序结构（算法）

小技巧

if..else.. 比较简单的话可以简写成？：的形式
switch case 的写法
对数组用 forEach，参数函数用了 return false，这里似乎只是回跳出循环而不是整个 return false？用 while 语句就不会有这种问题。似乎是因为 forEach 不支持 return false，此外 forEach 也无法终止

字符串

557 反转字符串中的单词 III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: “Let’s take LeetCode contest”
输出: “s’teL ekat edoCteeL tsetnoc”
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
思路 1：先用利用空格分割每个单词，单词变数组，再在每个数组内进行反转

var reverseWords = function(s) {
  return s
    .split(" ")
    .map(item =>
      item
        .split("")
        .reverse()
        .join("")
    )
    .join(" ");
};

思路 2：先把每个字符都颠倒过来,tsetnoc edoCteeL ekat s’teL，之后按照空格分隔开，重新排序

var reverseWords = function(s) {
  return s
    .split("")
    .reverse()
    .join("")
    .split(" ")
    .reverse()
    .join(" ");
};

696 计数二进制子串
给定一个字符串 s，计算具有相同数量 0 和 1 的非空(连续)子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是组合在一起的。
重复出现的子串要计算它们出现的次数。
示例 1 :
输入: “00110011”
输出: 6
解释: 有 6 个子串具有相同数量的连续 1 和 0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

/**
 * 思路1:0011001 每次都起始字符开始检查，直到遇到非它的。比如说第一次，00截止，长度为2，那么看起始字符的开始段是不是满足0011；
 *      第二次，以第二个字符为起始字符，直到遇到非他的，同样操作...
 */
let exportFunction = s => {
  let result = [];
  //  定义检查函数
  let matches = s => {
    let j = s.match(/^(0+|1+)/)[0];
    let i = (j[0] ^ 1).toString().repeat(j.length); //  这里的^是按位异或，效果是能让0和1互相转化
    let all = j + i;
    if (s.startsWith(all)) {
      return true;
    } else {
      return false;
    }
  };
  //  对字符串遍历检查
  for (let i = 0; i < s.length - 1; i++) {
    let r = matches(s.slice(i));
    if (r) {
      result.push(r);
    }
  }
  return result.length;
};
/**
 *   思路2
 *   000111必定有三个子串
 *   00011必定有两个子串
 *   0111必定有1个子串
 *   以此类推, 每两组数据之间长度最短的值为子串的数量
 */
let exportFunction = s => {
  let n = 0,
    arr = s.match(/(1+)|(0+)/g);
  for (let i = 0; i < arr.length - 1; i++) {
    n += Math.min(arr[i].length, arr[i + 1].length);
  }
  return n;
};

数组

17 九宫格键盘的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射(九宫格)。注意 1 不对应任何字母。
示例:
输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

/**
 *   思路：递归
 *   会发现只有2个输入的时候是两个中的字母去组合；3个输入的时候，eg. “234”，是先把“23”结果算出来再与“4”结果得到结果，是一种递归。
 */
let exportFunction = str => {
  // 如果小于1返回空（LeetCode测试用例）
  if (str.length < 1) return [];
  //  建立电话号码键盘映射
  let map = ["", 1, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
  // 如果只给了一个按键，直接把按键内容取出来并按单个字符分组就可以了（LeetCode测试用例）
  if (str.length < 2) return map[str].split("");
  //  把'234'变成['abc','def','ghi']
  let num = str.split("");
  let code = [];
  num.forEach(item => {
    if (map[item]) {
      code.push(map[item]);
    }
  });
  //  对变好的数组进行组合运算
  let group = arr => {
    //  储存结果的数组
    let tmp = [];
    //  第一个for运算arr的第一项，第二个for运算arr的第二项
    for (let i = 0, il = arr[0].length; i < il; i++) {
      for (let j = 0, jl = arr[1].length; j < jl; j++) {
        // 这个写法使得arr的项无论是数组还是字符串都能实现拆分组合
        tmp.push(`${arr[0][i]}${arr[1][j]}`);
      }
    }
    arr.splice(0, 2, tmp);
    if (arr.length > 1) {
      group(arr);
    } else {
      return tmp;
    }
    return arr[0];
  };
  return group(code);
};

914 卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
示例 1：
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

/**
 *   思路：记录每种牌数量后，再比较每两种牌的最大公约数是否大于1（辗转相除法）
 */

// 函数体
let exportFunction = arr => {
  //  存每种卡牌的总数
  let total = [];
  //  创建一个对象来记录每种卡牌的数目(用forEach（需要自己建对象）,reduce都可以)
  let num = arr.reduce((acc, item) => {
    item in acc ? acc[item]++ : (acc[item] = 1);
    return acc;
  }, {});
  for (let i in num) {
    total.push(num[i]);
  }
  //  求两个数最大公约数的函数
  let eva = (a, b) => {
    if (b === 0) {
      return a;
    } else {
      return eva(b, a % b);
    }
  };
  while (total.length > 1) {
    let a = total.shift();
    let b = total.shift();
    let c = eva(a, b);
    if (c == 1) {
      return false;
    } else {
      total.unshift(c);
    }
  }
  return total.length ? total[0] > 1 : false;
};

605 种花问题
种花的规则是花不能相邻。给定一个花坛（表示为一个数组包含 0 和 1，其中 0 表示没种植花，1 表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回 True，不能则返回 False。
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

let exportFunction = ({ flowerbed, n }) => {
  let result = 0;
  //  给数组右边再补一个0,因为判断原来最后一位的时候其实可以默认这一位的虚拟后一位是0
  flowerbed.push(0);
  for (var i = 0; i < flowerbed.length - 1; i++) {
    if (flowerbed[i] === 0) {
      if (flowerbed[i + 1] === 0) {
        result++;
        i++;
      }
    } else {
      i++;
    }
  }
  return result >= n;
};

89 格雷编码
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

/**
 *   首先理解这个题意就有点难了...
 *   如果你百度过1和3的格雷编码长什么样子，或许能找到规律。从直接外观看，规律如下：
 *   输入n之后，列数就是n，行数是2^n；第一列总是前一半是0，后一半是1；后面列你会发现，总体的上部分是n-1的输出结果复制粘贴，
 *   下部分是复制粘贴后上下颠倒。
 *   思路：由上述规律，想知道n的格雷编码序列，必须知道n-1的序列，是一个递归的思想
 */
let exportFunction = n => {
  // 输入为0的时候
  if (n === 0) return ["0"];
  // 递归函数，用来算输入为n的格雷编码序列
  let getGrayCode = n => {
    let result = [];
    if (n === 1) {
      return ["0", "1"];
    } else {
      let pre = getGrayCode(n - 1);
      // 格雷编码的行数（长度）。由于我们输出是数组，index是长度-1
      let resultLength = Math.pow(2, n) - 1;
      for (let i = 0, len = pre.length; i < len; i++) {
        result[i] = `0${pre[i]}`;
        result[resultLength - i] = `1${pre[i]}`;
      }
    }
    return result;
  };
  return getGrayCode(n).map(item => {
    //  把结果按二进制解析
    return parseInt(item, 2);
  });
};

正则

459 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。

// 思路：正则表达式
let exportFunction = s => {
  var reg = /^(\w+)\1+$/;
  //  这个字符串无论从前还是从后开始匹配，都满足是一个匹配项通过 + 得到的
  return reg.test(s);
};

10 实现一个简单的正则表达式（困难）
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和。要求 p 看做是一个正则，能匹配整个 s
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a“
输出: true

let exportFunction = ({ s, p }) => {
  let isMatch = (s, p) => {
    // 边界情况，如果s和p都为空，说明处理结束了，返回true，否则返回false
    if (p.length <= 0) {
      return !s.length;
    }
    // 判断p模式字符串的第一个字符和s字符串的第一个字符是不是匹配
    let match = false;
    if (s.length > 0 && (p[0] === s[0] || p[0] === ".")) {
      match = true;
    }
    // p有模式的
    if (p.length > 1 && p[1] === "*") {
      // 第一种情况：s*匹配0个字符
      // 第二种情况：s*匹配1个字符，递归下去，用来表示s*匹配多个s
      return isMatch(s, p.slice(2)) || (match && isMatch(s.slice(1), p));
    } else {
      return match && isMatch(s.slice(1), p.slice(1));
    }
  };
  return isMatch(s, p);
};

递归

93 复原 IP 地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。（IP 地址有 4 个段，每一个段值为 0~255）
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

/** 思路: IP三个点分成四部分 每部分0-255 每部分最多不超过3位
 *  示例 25525511135 第一部分可能是 2 25 255
 *  如果第一部分是2 那么 第二部分 5 55
 *  如果第二部分 5 那么 第三部分 剩下的超过6位 不满足
 */
let exportFunction = s => {
  // 保存所有符合条件的IP地址
  let result = [];
  // 递归函数  上次处理结果，待处理字符串
  let search = (curResult, sub) => {
    // 非法输入过滤，LeetCode测试用例(111111111111111111111111111111111111111111111111111111111111)
    if (sub.length > 12) {
      return;
    }
    // 边界条件: 已经分为四部分且四部分长度相等
    if (curResult.length === 4 && curResult.join("") === s) {
      result.push(curResult.join("."));
    } else {
      // 正常的处理过程
      for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
        // 待处理子串，取 1位 2位 3位
        tmp = sub.substr(0, i + 1);
        if (tmp < 256) {
          // 转换下数据类型，如 01为1（LeetCode测试用例）
          search(curResult.concat(tmp * 1), sub.substr(i + 1));
        }
      }
    }
  };
  search([], s);
  return result;
};

30 串联所有单词的子串（困难）
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = “barfoothefoobarman”,
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = “wordgoodgoodgoodbestword”,words = ["word","good","best","word"]
输出：[]

/** 思路:对words数组的item进行一个排列组合生成字符串数组，eg.words = [a,b,c]  
    递归排列组合[a]  第一位 b c中选一位放在第二位
    [b] 第一位 a c中选一位放在第二位
    [c] 第一位 a b中选一位放在第二位
 */
let exportFunction = ({ s, words }) => {
  // 结果
  let result = [];
  let num = words.length;
  // 生成递归的函数
  let range = (curResult, wordsArr) => {
    // 边界，计算完毕
    if (curResult.length === num) {
      result.push(curResult);
    } else {
      wordsArr.forEach((item, index) => {
        let tmp = [...wordsArr];
        // 丢出第一位，生成第二位待选数组
        tmp.splice(index, 1);
        range(curResult.concat(item), tmp);
      });
    }
  };
  range([], words);
  // 子串获取完成，检查有没有匹配的子串
  // [0, 9, -1] filter 之后[0,9]
  // 同时最后的结果要数组去重（用reduce），LeetCode测试用例words是["word","good","best","good"]的时候，会
  // 以为这两个good是不同的而多排列组合一遍
  return result
    .map(item => {
      return s.indexOf(item.join(""));
    })
    .filter(item => item !== -1)
    .sort()
    .reduce((acc, curr) => {
      if (acc.indexOf(curr) === -1) {
        acc.push(curr);
      }
      return acc;
    }, []);
};

还有另一种解法，有点长，没写在这里，面试问到这种解法算我输好吧

排序

sort()虽然好用，但底层是一次完整的遍历排序，耗性能，做排序算法题能不用就不用。如果题目中要用数组的最大值/最小值，先想想能不能用冒泡/选择排序。

用 sort()的简单排序

922 奇偶数欧西数组 II
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

let exportFunction = arr => {
  arr.sort((a, b) => a - b);
  let result = [];
  //  声明两个变量来保存下标
  let odd = 1;
  let even = 0;
  arr.forEach(item => {
    if (item % 2 === 1) {
      result[odd] = item;
      odd += 2;
    } else {
      result[even] = item;
      even += 2;
    }
  });
  return result;
};

冒泡排序

164 最大间距（困难）
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

/**
 *   思路：这里的解法1用了一次sort了一次for，时间复杂度相当于是O（n2 + n）。但其实用冒泡排序的话，在排序的时候就已经
 *   能知道前一项跟后一项的差值了。故用冒泡能实现时间复杂度是O（n2）。
 *   具体操作是在每一轮冒泡排序结束后都保存一下目前冒泡终点和终点+1项的差值
 */
// 常规解法，时间复杂度不符合题目要求
// let exportFunction = (nums) => {
//   if (nums.length < 0) return 0
//   nums.sort((a, b) => a - b)
//   let max = 0
//   for (let i = 0; i < nums.length - 1; i++) {
//     let now = nums[i + 1] - nums[i]
//     if (now > max) {
//       max = now
//     }
//   }
//   return max
// }
let exportFunction = nums => {
  if (nums.length < 2) return 0;
  let len = nums.length - 1;
  let max = 0;
  let space;
  for (let i = len; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      let tmp = nums[j];
      if (tmp > nums[j + 1]) {
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
    // 是在每一轮冒泡排序结束后都保存一下目前冒泡终点和终点+1项的差值
    if (i < len) {
      space = nums[i + 1] - nums[i];
      if (space > max) {
        max = space;
      }
    }
  }
  return Math.max(max, nums[1] - nums[0]);
};

215 数组中的第 K 个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

/**
 *   思路：冒泡排序，当k比较小的时候只要几轮就能结束，性能好
 */
let exportFunction = ({ nums, k }) => {
  let len = nums.length - 1;
  //  当k刚好想让我们取最小值的时候，直接返回数组最小值
  if (nums.length === k) return Math.min.apply(null, nums);
  //  其他情况就用冒泡排序节约性能
  for (let i = len; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      let tmp = nums[j];
      if (tmp > nums[j + 1]) {
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
    if (len - i + 1 === k) {
      return nums[i];
    }
  }
};

// 解法二：快排.基于数组的第k个数字来调整, 使得比第k个数字小的所有数字都位于数组的左边,比数组大的元素都位于数组的右边。这样调整后 , 位于数组中左边第k个数字就是第k大的元素
var findKthLargest = function(nums, k) {
  let start = 0
  let end = nums.length - 1
  let index = partition(nums, start, end)
  while(index !== k - 1) {
    if (index > k - 1) {
      index = partition(nums, start, index - 1)
    }
    if (index < k - 1) {
      index = partition(nums, index + 1, end)
    }
  }
  return nums[k - 1]
}

function partition(nums, start, end) {
  let target = nums[start]
  while (start < end) {
    while (nums[end] <= target && start < end) {
      end--
    }
    nums[start] = nums[end]
    while (nums[start] > target && start < end) {
      start++
    }
    nums[end] = nums[start]
  }
  nums[start] = target
  return start // 目标位置
}

选择排序

41 缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2

/**
 *   思路：涉及到最小值的排序，用选择排序
 */

// 第一种算法,性能不是很好（用了一个sort和一个for）,这里的sort其实并不是很必要，没必要把所有的都排好
let exportFunction = arr => {
  //  过滤掉负数和0，排序
  arr = arr.filter(item => item > 0);
  arr.sort((a, b) => a - b);
  if (arr.length) {
    if (arr[0] > 1) {
      return 1;
    } else {
      for (let i = 0, len = arr.length - 1; i < len; i++) {
        if (arr[i + 1] - arr[i] > 1) {
          return arr[i] + 1;
        }
      }
      //  如果都是不符合，则是这种[1,2,3,4,5,6],应：
      return arr.pop() + 1;
    }
  } else {
    return 1;
  }
};
//  第二种算法，借用选择排序
let exportFunction = arr => {
  //  过滤掉负数
  arr = arr.filter(item => item > 0);
  //  借用选择排序，先找到第一个最小值，不是1则返回1；不是1则比相邻元素差值，直到找到答案就能停止遍历。
  for (let i = 0, len = arr.length; i < len; i++) {
    let min = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < min) {
        let c = min;
        min = arr[j];
        arr[j] = c;
      }
    }
    arr[i] = min;
    if (i > 0) {
      if (arr[i] - arr[i - 1] > 1) {
        return arr[i - 1] + 1;
      }
    } else {
      if (min !== 1) {
        return 1;
      }
    }
  }
  return arr.length ? arr.pop() + 1 : 1;
};

快速排序

75 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

```

### 栈

**20 有效的括号**
给定一个只包括 '('，')'，'{'，'}'，'['，']'  的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()[]{}"
输出: true
示例 2:
输入: "(]"
输出: false

```javascript
let exportFunction = s => {
  // 建立映射
  let map = {
    "(": -1,
    ")": 1,
    "{": -2,
    "}": 2,
    "[": -3,
    "]": 3
  };
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] < 0) {
      stack.push([s[i]]);
    } else {
      let last = stack.pop();
      if (map[last] + map[s[i]] !== 0) return false;
    }
  }
  if (stack.length !== 0) return false;
  return true;
};

682 棒球比赛

let exportFunction = arr => {
  // 保存结果，实际是一个栈
  let result = [],
    //  建立两个变量储存上个结果和上上个结果
    pre1,
    pre2;
  //  遍历，实现操作
  arr.forEach(item => {
    switch (item) {
      case "+":
        pre1 = result.pop();
        pre2 = result.pop();
        result.push(pre2, pre1, pre1 + pre2);
        break;
      case "D":
        pre1 = result.pop();
        result.push(pre1, pre1 * 2);
        break;
      case "C":
        result.pop();
        break;
      default:
        result.push(Number(item));
    }
  });
  return result.reduce((acc, curr) => acc + curr);
};

85 最大矩形（困难）
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]
输出: 6

```

### 队列

[622 设计循环队列](https://jacleklm.github.io/2019/10/19/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/#more)
**621 任务调度器**
A - Z 字母表示的 26 种不同种类的任务(执行顺序不限),每个任务都可以在 1 个单位时间内执行完,CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为  n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。
示例 1：
输入: tasks = `["A","A","A","B","B","B"]`, n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

```javascript
/** 思路: LeetCode上的题解，其实不是特别理解
 * 最小长度 = （单个字母出现的最大次数 - 1）* （n + 1）+ 出现最大次数的字母总数
   最小长度 小于 任务长度时， 返回任务长度
 */
let exportFunction = ({ tasks, n }) => {
  if (n == 0) return tasks.length;
  let times = new Array(26).fill(0);
  for (let c of tasks) {
    times[c.charCodeAt(0) - "A".charCodeAt(0)]++;
  }
  let maxTimes = times[0],
    maxItems = [0];
  for (let i = 1; i < 26; i++) {
    if (times[i] == maxTimes) {
      maxItems.push(i);
    } else if (times[i] > maxTimes) {
      maxTimes = times[i];
      maxItems = [i];
    }
  }
  let ans = (maxTimes - 1) * (n + 1) + maxItems.length;
  return Math.max(ans, tasks.length);
};

矩阵

54 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

/** 思路:用递归解决
 */
let exportFunction = matrix => {
  let result = [];
  let spiral = (arr, r) => {
    for (let i = 0, len = arr.length; i < len; i++) {
      if (i === 0) {
        r = r.concat(arr[i]);
      } else if (i === len - 1) {
        r = r.concat(arr[i].reverse());
      } else {
        if (arr[i].length) {
          // 增加边界检查（Leetcode测试用例）,防止只有两行的矩阵
          r.push(arr[i].pop());
        }
      }
    }
    arr.shift();
    arr.pop();
    for (let j = arr.length - 1; j >= 0; j--) {
      // 增加边界检查（Leetcode测试用例）,防止只有两行的矩阵
      if (arr[j].length) {
        r.push(arr[j].shift());
      }
    }
    if (arr.length) {
      return spiral(arr, r);
    } else {
      return r;
    }
  };
  return spiral(matrix, result);
};

48 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
思路：旋转其实是两次翻转（一次横轴和一次对角线轴）；并且注意每次翻转并不用遍历全部，找到边界

let exportFunction = arr => {
  //  获取矩阵的维度
  let v = arr.length;
  //  开始垂直翻转（其实是重写数组项）
  for (let i = 0; i < v / 2; i++) {
    //  其实垂直翻转，在纵轴上遍历一半就可以了
    for (let j = 0, tmp; j < v; j++) {
      tmp = arr[i][j];
      arr[i][j] = arr[v - i - 1][j];
      arr[v - i - 1][j] = tmp;
    }
  }
  //  开始斜轴翻转
  for (let i = 0; i < v; i++) {
    for (let j = 0, tmp; j < i; j++) {
      //  这里仔细观察，会发现横轴遍历到小于斜轴处就可以了
      tmp = arr[i][j];
      arr[i][j] = arr[j][i];
      arr[j][i] = tmp;
    }
  }
  return arr;
};

二叉树

101 对称二叉树的判断
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3

/**
 *   思路：这里其实是【给一个数组构造出对应的二叉树】，并且这个二叉树有一个方法能判断本身是否是对称的
 *   (leetCode上只要写这个方法这部分代码就可以了)
 */
class Node {
  constructor(val) {
    this.val = val;
    this.left = this.right = undefined;
  }
}
class Tree {
  constructor(data) {
    //  data是传进来的数组
    //  创建一个数组临时储存所有节点
    let nodeList = [];
    //  顶节点
    let root;
    //  开始遍历
    for (let i = 0; i < data.length; i++) {
      let node = new Node(data[i]);
      nodeList.push(node);
      if (i > 0) {
        //  计算当前节点属于哪一层，sqrt是平方根
        let n = Math.floor(Math.sqrt(i + 1));
        //  计算当前层的起始点，pow() 方法可返回 x 的 y 次幂的值
        let q = Math.pow(2, n) - 1;
        //  计算上一层的起始点
        let p = Math.pow(2, n - 1) - 1;
        //  找出当前层的父节点
        let parent = nodeList[p + Math.floor((i - q) / 2)];
        //  将当前节点和上一层的父节点做关联
        if (parent.left) {
          parent.right = node;
        } else {
          parent.left = node;
        }
      }
    }
    root = nodeList.shift();
    nodeList.length = 0;
    //  构造函数要返回最顶端的根节点,return后就【完成构建了】
    return root;
  }

  //  在这课二叉树中定义了一个静态方法，用来验证该二叉树是否是对称二叉树（递归）
  static isSymmetry(root) {
    if (!root) return true;
    let walk = (left, right) => {
      //  判断终点
      if (!left && !right) return true;
      //  判断不对称的情况
      if ((left && !right) || (!left && right) || left.val !== right.val)
        return false;
      //  若无异常，则进入下一轮递归
      return walk(left.left, right.right) && walk(left.right, right.left);
    };
    return walk(root.left, root.right);
  }
}

98 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树

示例 1:
输入:
    2
   / \
  1   3
输出: true
示例 2:
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false

解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

/**
 *   思路：【给一个数组，构造出二叉搜索树】，并且这个二叉搜索树有一个方法来验证自身是否是二叉搜索树
 */
class Node {
  constructor(val) {
    this.val = val;
    this.left = this.right = undefined;
  }
}
class Tree {
  constructor(data) {
    //  data是接收的数组
    let root = new Node(data.shift());
    data.forEach(item => {
      this.insert(root, item);
    });
    return root;
  }
  //  定义插入方法
  insert(node, data) {
    if (node.val > data) {
      if (node.left === undefined) {
        node.left = new Node(data);
      } else {
        this.insert(node.left, data);
      }
    } else {
      if (node.right === undefined) {
        node.right = new Node(data);
      } else {
        this.insert(node.right, data);
      }
    }
  }
  //  定义验证方法,思路是遍历整个树，如果所有节点都满足node.left.val < node.val <node.right.val 即可
  static walk(root) {
    if (!root.left && !root.right) {
      return true;
    } else if (
      (root.left && root.val < root.left.val) ||
      (root.right && root.val > root.right.val)
    ) {
      return false;
    } else {
      return Tree.walk(root.left) && Tree.walk(root.right);
    }
  }
}

堆

451 根据字符出现频率排序（堆排序）
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。
注意”cacaca”是不正确的，因为相同的字母必须放在一起。
注意：如果没有时间度复杂度的要求的话，用 sort()和 reduce 应该可以做出来。如果要求时间复杂度用堆排序可以优化性能

/** 思路: 第一步统计；第二步排序；第三步输出
 */
// 常规解法，不考虑时间复杂度度与空间复杂度
let exportFunction = s => {
  let result = [];
  let store = s
    .split("")
    .sort()
    .reduce((acc, curr) => {
      curr in acc ? acc[curr]++ : (acc[curr] = 1);
      return acc;
    }, {});
  for (i in store) {
    result.push(i.repeat(store[i]));
  }
  return result.sort((a, b) => b.length - a.length).join("");
};
//  用堆排序，时间复杂度优化。在我们原来的堆的代码中改constructor的代码（此时传入的是字符串）对字符串进行统计
//  新增一个toString方法，在这个方法里用我们的this.sort()进行堆排序后再输出
class Heap {
  constructor(str) {
    let map = new Map();
    str.split("").forEach(item => {
      if (map.has(item)) {
        map.set(item, map.get(item) + 1);
      } else {
        map.set(item, 1);
      }
    });
    this.map = map;
    this.data = Array.from(map.values());
  }
  sort() {
    let iArr = this.data;
    let n = iArr.length;
    if (n <= 1) {
      return iArr;
    } else {
      for (let i = Math.floor(n / 2); i >= 0; i--) {
        // 构建最大堆从最后一个父节点开始循环
        Heap.maxHeapify(iArr, i, n);
      }
      for (let j = 0; j < n; j++) {
        //  不断构建最大堆的过程
        //  因为每次构建都会扔掉一个，所以是n-1-j
        Heap.swap(iArr, 0, n - 1 - j);
        //  每次交换位置扔完之后应该是从顶点开始，所以第二个参数是0
        Heap.maxHeapify(iArr, 0, n - 1 - j - 1);
      }
      return iArr;
    }
  }
  toString() {
    let arr = this.sort();
    let str = [];
    while (arr.length) {
      let top = arr.pop();
      for (let [k, v] of this.map) {
        if (v === top) {
          str.push(k.repeat(v));
          this.map.delete(k);
          break;
        }
      }
    }
    return str.join("");
  }
  // 交换两个元素
  static swap(arr, a, b) {
    if (a === b) {
      return;
    }
    let c = arr[a];
    arr[a] = arr[b];
    arr[b] = c;
  }
  // 构建最大堆的过程
  static maxHeapify(Arr, i, size) {
    // i的左节点（索引），这是堆的固有规律
    let l = i * 2 + 1;
    // i的右节点
    let r = i * 2 + 2;
    let largest = i;
    // 父节点i和左节点l做比较取最大
    if (l <= size && Arr[l] > Arr[largest]) {
      largest = l;
    }
    // 右节点和最大值比较
    if (r <= size && Arr[r] > Arr[largest]) {
      largest = r;
    }
    if (largest !== i) {
      Heap.swap(Arr, i, largest);
      //  交换完之后确保子树也是满足最大堆的条件
      Heap.maxHeapify(Arr, largest, size);
    }
  }
}

313 超级丑数（堆查找）
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

```

### 贪婪算法

**122 买卖股票的最佳时机 II**

```javascript
/** 思路: 从最低点买入，到价格最高点卖出，不断买卖（在保证单词利益的基础上，实现多次交易）
 */
let exportFunction = prices => {
  // 用一个变量保存利润
  let count = 0;
  // i是买入的时间点，j是卖出的时间点
  for (let i = 0, len = prices.length; i < len; i++) {
    for (let j = i; j < len - 1; j++) {
      if (prices[j + 1] > prices[j]) {
        //  发现有利可图，立刻把股票卖了。在j这一天又买入（i = j）
        count += prices[j + 1] - prices[j];
        i = j;
      } else {
        i = j;
      }
    }
  }
  return count;
};

860 柠檬水找零

/** 思路: 贪心算法，每次找零优先把手头最大的钱扔出去
 */
let exportFunction = bills => {
  //  钱箱，显示自己的零钱
  let hand = [];
  while (bills.length) {
    let money = bills.shift();
    if (money === 5) {
      hand.push(money);
    } else {
      hand.sort((a, b) => b - a);
      let change = money - 5;
      for (let i = 0, len = hand.length; i < len; i++) {
        if (hand[i] <= change) {
          change -= hand[i];
          hand.splice(i, 1);
          i--;
        }
        if (change == 0) {
          break;
        }
      }
      if (change !== 0) {
        return false;
      } else {
        hand.push(money);
      }
    }
  }
  return true;
};

动态规划

53 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

// 思路：动态规划，状态转移方程：sum[i] = max{sum[i-1]+nums[i],nums[i]} （(sum[i]记录以nums[i]为子序列末端的最大序子列连续和)）
let exportFunction = nums => {
  let max = nums[0];
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (sum > 0) {
      sum += nums[i];
    } else {
      sum = nums[i];
    }
    max = Math.max(max, sum);
  }
  return max;
};

121 买卖股票的最佳时机
给一个数组为各天股票价格，只有一次买入和一次卖出的机会，求利润最大值
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格

let exportFunction = prices => {
  let min = Number.MAX_SAFE_INTEGER;
  let sum = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] <= min) {
      min = Math.min(prices[i], min);
    } else {
      sum = Math.max(prices[i] - min, sum);
    }
  }
  return sum;
};

找出 0 或 1 的字符串中 0 和 1 连续出现的最大次数
示例：
输入：’0001111100’
输出： 5

let exportFunction = str => {
  let max = 0;
  let sum = 1;
  for (let i = 0; i < str.length - 1; i++) {
    if (str[i] === str[i + 1]) {
      sum++;
    } else {
      sum = 1;
    }
    max = Math.max(max, sum);
  }
  return max;
};

62 不同路径

/**注意：机器人不会走一些钻牛角尖的路线。eg，m=2，n=3的话，它不会[0,0],[0,1],[1,1],[1,0],[2,0],[2,1]
 * 思路: 状态转移方程为 d[i][j] = d[i][j-1] + d[i-1][j]；因为机器人不会钻牛角尖，会认为 d[0][j]=1,d[i][0]=1
 */
let exportFunction = ({ m, n }) => {
  // 构建矩阵肯定是先构建纵，这里认为纵为n。然后进行 1 的填充
  let dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(m);
    dp[i][0] = 1;
  }
  for (let j = 0; j < m; j++) {
    dp[0][j] = 1;
  }
  for (let l = 1; l < n; l++) {
    for (let k = 1; k < m; k++) {
      dp[l][k] = dp[l][k - 1] + dp[l - 1][k];
    }
  }
  return dp[n - 1][m - 1];
};

刷题

要理解成链表是客观存在的，变量只是一个指针
链表边界如果老是处理不好，考虑下用数组储存。虽然浪费空间但是能跑起来就行

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1: 输入: “abcabcbb”。输出: 3 （abc）
示例 3: 输入: “pwwkew”。输出: 3 （wke）

let exportFunction = s => {
  let sum = 0;
  let max = 0;
  let store = [];
  for (let i = 0; i < s.length; i++) {
    if (store.indexOf(s[i]) === -1) {
      store.push(s[i]);
      sum++;
    } else {
      // store = [s[i]]
      // sum = 1
      store = store.slice(store.indexOf(s[i]) + 1); // 这一步比较精妙，使得字符串能舍弃同个部分后继承
      store.push(s[i]);
      sum = store.length;
    }
    max = Math.max(max, sum);
  }
  return max;
};

19 删除链表的倒数第 N 个节点

可以用双循环法，第一次循环得到链表长度，第二次循环删除节点。也可以借用数组，如下所示：

// leetcode的另一种方法，借用数组
let exportFunction = (head, n) => {
  let store = [];
  let curr = head;
  while (curr) {
    store.push(curr);
    curr = curr.next;
  }
  let pre = store[store.length - n - 1]; // 获取到需要删除的节点的【前一个】
  pre ? (pre.next = pre.next.next) : (head = head.next); //【删除操作】
  return head;
};

21 合并两个有序链表

// 思路：合并两个有序链表，有点像归并排序的后半部分操作。所以类似的我们也新建一个链表储存合并的结果
let exportFunction = (l1, l2) => {
  let head = new ListNode(-1);
  // 【利用js对象地址传递的方式动态更新范围链表的尾结点插入操作】
  let tmp = head;
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      // 这部分连接链表的操作
      tmp.next = l1;
      l1 = l1.next;
    } else {
      tmp.next = l2;
      l2 = l2.next;
    }
    tmp = tmp.next;
  }
  // 排完了，剩下的尾巴的第一个是谁就接上去
  tmp.next = l1 ? l1 : l2;
  // 返回哨兵结点的next即为所求
  return head.next;
};

59 螺旋矩阵 II

/** 思路: 当输入的为4的时候，可以看出是先输入1234，再567，再8910，再1112，1314，15，16。所以步数数组是[4,3,3,2,2,1,1]
 *  再提出一个当前输入点的概念，用步数数组的index % 4 判断当前输入点的走向
 */

// 函数体
let exportFunction = n => {
  // 构建结果矩阵的空矩阵
  let result = [];
  for (let i = 0; i < n; i++) {
    result[i] = new Array();
  }
  // 构建步数数组
  let step = [];
  step.push(n);
  while (n > 1) {
    step.push(n - 1);
    step.push(n - 1);
    n--;
  }
  // 当前输入点和当前输入值
  let currPoint = [0, -1];
  let value = 0;
  for (let i = 0; i < step.length; i++) {
    let P = i % 4;
    // 当P=0时候，是从左往右输入;1是从上往下；2是从左往右；3是从下往上
    for (let j = 0; j < step[i]; j++) {
      value++;
      switch (P) {
        case 0:
          currPoint[1] = currPoint[1] + 1;
          break;
        case 1:
          currPoint[0] = currPoint[0] + 1;
          break;
        case 2:
          currPoint[1] = currPoint[1] - 1;
          break;
        case 3:
          currPoint[0] = currPoint[0] - 1;
          break;
      }
      result[currPoint[0]][currPoint[1]] = value;
    }
  }
  return result;
};

78 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

let exportFunction = nums => {
  let result = [[]];
  for (let i = 0; i < nums.length; i++) {
    let len = result.length;
    for (let j = 0; j < len; j++) {
      result.push(result[j].concat([nums[i]]));
    }
  }
  return result;
};

102. 二叉树的层次遍历 === 剑指offer把二叉树打印成多行

let exportFunction = root => {
  if (!root) return [];
  let result = [];
  let que = [root];
  while (que.length) {
    // 这一层的打印结果
    let thisResult = [];
    // 下一层的节点
    let nextque = [];
    while (que.length) {
      let node = que.shift();
      thisResult.push(node.val);
      if (node.left) nextque.push(node.left);
      if (node.right) nextque.push(node.right);
    }
    que = nextque;
    result.push(thisResult);
  }
  return result;
};

617 合并二叉树

let mergeTrees = ({ t1, t2 }) => {
  if (t1 === null) {
    return t2;
  } else if (t2 === null) {
    return t1;
  } else {
    t1.val = t1.val + t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
  }
  return t1;
};

单链表冒泡排序

剑指 offer

字符串

整数中 1 出现的次数

考点是时间效率
暴力低效法：

function NumberOf1Between1AndN_Solution(n) {
  if (n == 0) return 0;
  let str = "1";
  for (let i = 2; i < n + 1; i++) {
    str += i;
  }
  let count = 0;
  str.split("").forEach(item => {
    {
      if (item === "1") count++;
    }
  });
  return count;
}

数组

数字在排序数组中出现的次数

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

function GetNumberOfK(data, k) {
  if (data.indexOf(k) == -1) return 0;
  let count = data.lastIndexOf(k) - data.indexOf(k) + 1;
  return count;
}

数组中只出现一次的数字（易）

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

function FindNumsAppearOnce(array) {
  let result = [];
  array.sort();
  for (let i = 0; i < array.length; i++) {
    if (array[i] === array[i + 1]) {
      i++;
    } else {
      result.push(array[i]);
    }
  }
  return result;
}

栈和队列

两个栈来实现队列

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型(一种数据类型，用于定义整数类型变量的标识符)
思路：stack2 反向接在 stack1 的前面，中间部分都是 stack 的头（画图理解）。stack1 为入队栈，stack2 为出队栈

let stack1 = [];
let stack2 = [];
function push(node) {
  while (stack2.length) {
    stack1.push(stack2.pop());
  }
  stack1.push(node);
}
function pop() {
  while (stack1.length) {
    stack2.push(stack1.pop());
  }
  return stack2.pop();
}

栈的压入和弹出序列

注意这个知识点

1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列（先入 1234 出 4，进 5，出 5321），但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。同理 4,3,5,1,2 可是返回 true（先入 1234 出 43，入 5 出 512）

思路：借助辅助栈，模拟压出弹出的过程。第一个希望被弹出的数字是 4,因此 4 需要先压入到辅助栈里面。压入栈的顺序由压栈序列确定了，也就是在把 4 压入进栈之前，数字 1、2、3 都需要先压入到栈里面。此时栈里包含 4 个数字，分别是 1、2、3、4,其中 4 于栈顶。把 4 弹出栈后，剩下的三个数字是 1、2 和 3。接下来希望被弹出的数字是 5，由于它不是栈顶数字，因此我们接着在第一个序列中把 4 以后数字压入辅助栈中，直到压入了数字 5。这个时候 5 位于栈顶，就可以被弹出来了。接下来希望被弹出的三个数字依次是 3、2 和 1。由于每次操作前它们都位于栈顶，因此直接弹出即可。

function IsPopOrder(pushV, popV) {
  if (pushV.length == 0 || popV.length == 0) return true;
  let stack = [];
  let index = 0;
  for (let i = 0; i < pushV.length; i++) {
    if (pushV[i] === popV[index]) {
      index++;
      while (stack.length > 0 && stack[stack.length - 1] == popV[index]) {
        stack.pop();
        index++;
      }
    } else {
      stack.push(pushV[i]);
    }
  }
  if (stack.length === 0) {
    return true;
  } else {
    return false;
  }
}

滑动窗口的最大值

function maxInWindows(num, size) {
  if (!size || size > num.length) return [];
  let curr = num.slice(0, size);
  let result = [];
  result.push(Math.max.apply(null, curr));
  for (let i = size; i < num.length; i++) {
    curr.push(num[i]);
    curr.shift();
    result.push(Math.max.apply(null, curr));
  }
  return result;
}

链表

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/
function Clone(pHead) {
  if (pHead === null) {
    return null;
  }
  let node = new RandomListNode(pHead.label);
  node.random = pHead.random;
  node.next = Clone(pHead.next);
  return node;
}

二叉搜索树与双向链表（有点难）

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
思路：递归

function Convert(root) {
  // 递归的终点判断
  if (!root) return null;
  if (!root.left && !root.right) return root;
  //构建左子树为双向链表，返回链表头节点left
  var left = Convert(root.left);
  var tmp = left;
  //若左子树存在，则用tmp定位到左双向链表最后一个节点
  while (tmp && tmp.right) {
    tmp = tmp.right;
  }
  //若左子树存在，将左双向链表最后一个节点和当前节点连接起来
  //注意这里，tmp与left的存在与否完全相同
  if (tmp) {
    tmp.right = root;
    root.left = tmp;
  }
  //构建右子树为双向链表，返回链表头结点right
  var right = Convert(root.right);
  //将右双向链表头节点和当前节点连接起来
  if (right) {
    right.left = root;
    root.right = right;
  }
  //若有左子树，返回的永远是最左边的叶子节点（也就是最小的节点），若无左子树，则根节点就是最小的节点
  return left ? left : root;
}

删除排序链表中的重复节点

额外空间，双指针

function deleteDuplication(pHead) {
  let head = new ListNode(-1);
  head.next = pHead;
  let pre = head;
  let cur = head.next;
  while (cur) {
    if (cur.next !== null && cur.val === cur.next.val) {
      while (cur.next !== null && cur.val === cur.next.val) {
        cur = cur.next;
      }
      pre.next = cur.next;
      cur = cur.next;
    } else {
      pre = pre.next;
      cur = cur.next;
    }
  }
  return head.next;
}

二叉树

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度

function TreeDepth(pRoot) {
  if (!pRoot) return 0;
  let left = TreeDepth(pRoot.left);
  let right = TreeDepth(pRoot.right);
  return Math.max(left, right) + 1;
}

平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。eg. [1,2,3,4,5,6,7]是平衡的

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

function

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树.如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
思路：寻找能把左右子树区分开的 index，结合递归

function reConstructBinaryTree(pre, vin) {
  if (pre.length == 0 || vin.length == 0) {
    return null;
  }
  //前序第一个为根节点 也是中序左右子树的分割点
  var index = vin.indexOf(pre[0]);
  var left = vin.slice(0, index); //中序左子树
  var right = vin.slice(index + 1); //中序右子树
  return {
    val: pre[0],
    //递归左右子树的前序，中序
    left: reConstructBinaryTree(pre.slice(1, index + 1), left),
    right: reConstructBinaryTree(pre.slice(index + 1), right)
  };
}

树的子结构

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构

// 先序遍历用于打印树的结构。先序遍历两个树，看结果是否包含
function HasSubtree(pRoot1, pRoot2) {
  if (!pRoot2) {
    return false;
  }
  return preTraversal(pRoot1).includes(preTraversal(pRoot2));
}
function preTraversal(root) {
  let result = [];
  // 【这种立刻执行的函数，上一句最后要有 ; 不然会有bug！】
  (function pre(node) {
    if (node) {
      result.push(node.val);
      pre(node.left);
      pre(node.right);
    }
  })(root);
  return result.join(",");
}

二叉树的镜像操作

递归版：

function Mirror(root) {
  if (root === null) return null;
  [root.left, root.right] = [root.right, root.left];
  Mirror(root.left);
  Mirror(root.right);
}

非递归版，有点像层次遍历不过是用栈

function Mirror(root) {
  if (root === null) return null;
  let stack = [root];
  while (stack.length) {
    let node = stack.pop();
    [node.left, node.right] = [node.right, node.left];
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
}

判断是否是对称二叉树

同 leetCode

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes,否则输出 No。假设输入的数组的任意两个数字都互不相同
思路：后序遍历是左-右-中，所以数组第一个是二叉树最小值，最后一个是 root。左子树所有节点都小于 root。
依次与数组最后一个值比较，一直小于最后一个数的是左子树的，计数，剩下的是右子树的，依次判断剩下的是否全部大于最后一个数，若否，则为 false。类似于二分法

function VerifySquenceOfBST(sequence) {
  if (sequence.length === 0) return false;
  function judge(sequence, sta, end) {
    if (sta >= end) {
      return true;
    }
    // end是根节点
    let i = end;
    // 通过这个while能用i把左右子树区分开，并且右子树满足搜索树
    while (i > sta && sequence[i - 1] > sequence[end]) {
      i--;
    }
    // 验证左子树是否满足都小于根节点
    for (let j = i - 1; j >= sta; j--) {
      if (sequence[j] > sequence[end]) return false;
    }
    return judge(sequence, sta, i - 1) && judge(sequence, i + 1, end);
  }
  return judge(sequence, 0, sequence.length - 1);
}

二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的 list 中，数组长度大的数组靠前)
思路：

前序遍历二叉树，每次更新当前路径的和 curtSum
判断当前结点是否是叶子结点，以及 curtSum 是否等于 expectNumber。如果是，把当前路径保存在 res 结果中
若不符合条件，则弹出此结点

function FindPath(root, expectNumber) {
  let result = [];
  if (root === null) return result;
  _find(root, expectNumber, [], 0, result);
  return result;
}
function _find(root, expectNumber, path, currSum, result) {
  currSum += root.val;
  path.push(root.val);
  if (currSum === expectNumber && root.left === null && root.right === null) {
    result.push([...path]);
  }
  if (root.left !== null) {
    _find(root.left, expectNumber, path, currSum, result);
  }
  if (root.right !== null) {
    _find(root.right, expectNumber, path, currSum, result);
  }
  path.pop();
}

二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针
思路：
（画一个4层的树容易理解）

若该节点存在右子树：则下一个节点为右子树最左子节点
若该节点不存在右子树：这时分两种情况：

2.1 该节点为父节点的左子节点，则下一个节点为其父节点
2.2 该节点为父节点的右子节点，则沿着父节点向上遍历，直到找到一个节点的父节点的左子节点为该节点，则该节点的父节点下一个节点

function GetNext(pNode) {
  if(!pNode) return pNode
  // 1. 存在右子树的情况
  if(pNode.right) {
    pNode = pNode.right
    while(pNode.left) {
      pNode = pNode.left
    }
    return pNode
  }
  // 2. 不存在右子树
  while(pNode.next) {
    if(pNode === pNode.next.left) {
      // 2.1
      return pNode.next
    }
    pNode = pNode.next
  }
  return null
}

查找和排序

旋转数组的最小数字

1	return Math.min.apply(null, rotateArray);

最小的 k 个数

输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4
思路：找最小的，显然是选择排序

function GetLeastNumbers_Solution(input, k) {
  if (input.length < k) return [];
  for (let i = 0; i < input.length - 1; i++) {
    let min = input[i];
    for (let j = i + 1; j < input.length; j++) {
      if (input[j] < min) {
        let c = min;
        min = input[j];
        input[j] = c;
      }
    }
    input[i] = min;
    if (i === k) return input.slice(0, k);
  }
  return input;
}

递归和循环

斐波那契数列

输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）

斐波那契数列。满足如下的动态规划方程：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)

普通递归容易导致内存溢出而超时，尾递归能算出结果。动态规划解法最好
递归解法：

let exportFunction = n => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return exportFunction(n - 1) + exportFunction(n - 2);
};

尾递归：

function tailFibonacci(n, ac1, ac2) {
  if (n == 0) {
    return 0;
  }
  if (n == 1 || n == 2) {
    return ac2;
  }
  return tailFibonacci(n - 1, ac2, ac1 + ac2);
}
function Fibonacci(n) {
  return tailFibonacci(n, 1, 1);
}

动态规划解法：

let exportFunction = n => {
  let dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i < n + 1; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

跳台阶

同理动态规划

变态跳台阶

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级
思路：状态转移方程 F(n)=F(n-1)+F(n-2)+…F(2)+F(1)+1; 由上式得 F(n)=2F(n-1);F(1)=1 ;可得到 Fn(n)=2^(n-1)。
思路也可以是：由于可以 n 阶，每一跳可以跳 1,2,3….n 阶，但是每一跳不可以跳 0 阶，这就相当于是在 n(n>1)个相同的球分堆（组），有多少种分类情况。转成一个排列组合问题，答案是 2^(n-1)

function jumpFloorII(number) {
  if (number <= 1) return number;
  return Math.pow(2, number - 1);
}

矩阵覆盖

用 n 个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
可以发现依旧是斐波那契数列，用动态规划解答即可

动态和贪心

剪绳子

给你一根长度为 n 的绳子，请把绳子剪成 m 段（m、n 都是整数，n>1 并且 m>1），每段绳子的长度记为 k[0],k[1],…,k[m]。请问 k[0] x k[1] x … x k[m]可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18

动态规划思路：

当 n 大于等于 5 时，我们尽可能多的剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成两段长度为 2 的绳子。为什么选 2，3 为最小的子问题？因为 2，3 包含于各个问题中，如果再往下剪得话，乘积就会变小（所以是临界状态）。所以在 dp 数组中，dp[2]=2，dp[3]=3。
状态转移方程父绳乘积最大值 = 子绳 1 乘积最大值 * 子绳 2 乘积最大值（这个状态转移方程使得题目中剪成 m 段这个说法可以略去），然后做 for 循环，max = Math.max(max, curr)

function cutRope(number) {
  if (number === 2) return 1;
  if (number === 3) return 2;
  let dp = [1, 1, 2, 3];
  for (let i = 4; i < number + 1; i++) {
    // 用一个变量记录不同剪法乘积的最大值
    let max = 0;
    for (let j = 1; j <= i / 2; j++) {
      // 父绳乘积最大值 = 子绳1乘积最大值 * 子绳2乘积最大值
      let curr = dp[j] * dp[i - j];
      max = Math.max(max, curr);
    }
    dp[i] = max;
  }
  return dp[number];
}

贪心思路：由动态规划的思路，我们知道当绳子最小为 3 或 2 的时候就不能分了。那么绳子应该优先按 3 去分得到的乘积才是最大，剩下的尾巴再去 2 分（并且如果尾巴是 1 的话，说明最后一段是 4，那这段应该按 2 x 2 分）

function cutRope(number) {
  if (number === 2) return 1;
  if (number === 3) return 2;
  let timesOf3 = Math.floor(number / 3);
  // 当最后尾巴为1时，说明最后一段是4，应分割成 2 x 2更好，因为2*2=4 > 3=3*1
  if (number - timesOf3 * 3 === 1) timesOf3--;
  // 3分完最后尾巴2分
  timesOf2 = Math.floor((number - timesOf3 * 3) / 2);
  return Math.pow(3, timesOf3) * Math.pow(2, timesOf2);
}

数学题

二进制中 1 的个数

输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示
牛客网大佬的思路：如果一个整数不为 0，那么这个整数至少有一位是 1。如果我们把这个整数减 1，那么原来处在整数最右边的 1 就会变为 0，原来在 1 后面的所有的 0 都会变成 1(如果最右边的 1 后面还有 0 的话)。其余所有位将不会受到影响。eg，二进制 1100，减去 1 会变成 1011。此时我们做与操作，1100&1011 = 1000。也就是说，把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0.那么一个整数的二进制有多少个 1，就可以进行多少次这样的操作

let exportFunction = n => {
  let count = 0;
  while (n != 0) {
    count++;
    n = n & (n - 1);
  }
  return count;
};

和为 S 的连续正数序列

输出所有和为 S 的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。每个子序列长度至少为 2

其他

比较版本号

实现一个方法，用于比较两个版本号（version1、version2）,如果version1 > version2，返回1；如果version1 < version2，返回-1，其他情况返回0。版本号规则x.y.z，xyz均为大于等于0的整数，至少有x位

let exportFunction1 = ({ curV, reqV }) => {
  if (curV && reqV) {
    //将两个版本号拆成数字
    var arr1 = curV.split('.'),
      arr2 = reqV.split('.')
    var minLength = Math.min(arr1.length, arr2.length),
      position = 0,
      diff = 0
    //依次比较版本号每一位大
    while (
      position < minLength &&
      (diff = parseInt(arr1[position]) - parseInt(arr2[position])) == 0
    ) {
      position++
    }
    if(diff == 0) {
      return arr1.length - arr2.length > 0 ? 1 : 0
    } else {
      return diff > 0 ? 1 : -1
    } 
  } else {
    //输入为空
    console.log('版本号不能为空')
    return false
  }
}

随机生成字符串

实现一个随机符串生成函数 randomStr()，要求如下：

生成的随机的字符串应该以字母开头，并包含 [a-z][0-9] 这些字符。
生成的字符串长度为 8。
生成的字符串不能够在程序运行的生命周期中存在重复的情形

// 解法一： 三十六进制实际上就是（0-9，a-z），十个数字加26个英文字母: "0.ryv9e51n6s3u8adqksxscerk9"  
const randomStr = () => {
  return Math.random().toString(36).slice(2, 10)
}
// 解法2: 笨方法。
const randomStr1 = () => {
  const map = arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
  let res = ''
  for(let i = 0;i < 8; i++) {
    const randomIndex = Math.floor(Math.random() * 37)
    res = res + map[randomIndex]
  }
  return res
}

呓语
 LeetCode
慕课网

部分刷题记录