本人 Leetcode 帐号：
练脑达人
https://leetcode-cn.com/u/liannaodaren/
知识点快速索引
层次遍历（BFS）（树的基本操作- 遍历） 投票算法 hashmap 存储已经访问过的值 使用栈来代替递归 在push的时候利用辅助栈(双栈) 因数分解 二进制表示、2的幂次方特点 位运算、异或运算、左移一位表示进位 carried变量来实现进位 滑动窗口 递归和动态规划介绍 动态规划一 动态规划二 分治法 使用双指针 dummyHead简化操作 二分查找 二分查找（二） 二分查找（动态 start & end） 回溯法 矩阵旋转操作 类似桶排序 冒泡排序的时间复杂度优化 路径动态规划空间优化 爬楼梯问题介绍 爬楼梯问题 二维数组DFS解题模板、连通区域问题 中序遍历一个二叉查找树（BST） 前序遍历二叉树 前缀树（字典树） 递归 + 缓存 / 经典动态规划 多状态动态规划 最大公约数 / 裴蜀定理(贝祖定理) 有序矩阵的套路 背包问题(可参考下方第四题) 背包问题介绍 空间换时间、两两分组，求出两两结合能够得出的可能数，然后合并即可 动态规划求：正数数组求和为特定值的组合的个数 动态规划求：正数数组求和为特定值的组合的个数(数字可重复使用) 给定字符串的最大回文子序列 典型的博弈问题 dp二维建模思路+找规律 游程编码 游程编码和哈夫曼编码介绍 最优二叉树-哈夫曼树(注意字符被编码后用字节表示不够8位后面可补0) 买卖股票的最佳时机 买卖股票的最佳时机 II 数组内部移动（移动零到尾部） 并查集 UnionFind 并查集 UnionFind 介绍 并查集 UnionFind 冗余连接，并查集 UnionFind 闭环处理 Prim and Kruskal(并查集）最小生成树（删除三角形最长边优化） 经典的「拓扑排序」 对一个有向无环图(Directed Acyclic Graph 简称 DAG) G 进行拓扑排序 算法与数据结构（2）——图的表示法与常用的转化算法 后序遍历树，结果层层往前累加得出所有子树特征 满满的 BFS，一次点到圈向外感染，一次线到圈向外感染 最大值窗口移动，使用一个长度为 26 的数组维护每一个字符的出现次数
Problem：number-of-1-bits
https://leetcode.com/problems/number-of-1-bits/description/
Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Note:
Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.求二进制数字中含‘1’的个数
我的答案如下:
function hammingWeight(n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n = n>>1;
}
return count;
}
// hammingWeight(3)
// =>2
// hammingWeight(4)
// =>1
// hammingWeight(11)
// =>3Problem：sum-of-two-integers
https://leetcode.com/problems/sum-of-two-integers/description/
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = -2, b = 3
Output: 1设计函数不能用‘+’和‘-’进行求和
我的答案如下:
// References from https://github.com/azl397985856/leetcode/blob/master/problems/371.sum-of-two-integers.md
var getTwoSum = function(a, b) {
if (a === 0) return b;
if (b === 0) return a;
return getSum(a ^ b, (a & b) << 1);
};
// Extension: sum-of-n-integers
var getSum = function() {
const args = [...arguments]
return (
args.reduce((sum, cur) => getTwoSum(sum, cur), 0)
};
// getSum(4)
// =>4
// getSum(4, 5)
// =>9
// getSum(1, 4, 5)
// =>10
// getSum(-1, 4, 5)
// =>8Problem：longest-substring-without-repeating-characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
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.求最长的非重复的子字符串
我的答案如下:
const lengthOfLongestSubstring = function(s) {
let longestStrMapper = {}; // 记录已经出现过的charactor
let res = 0; // 记录临时结果
let start = 0; // 开始指针
let end = 0; // 结束指针
let char = '' // 临时存储每一轮用于数不重复字符个数的字符
for(let c of s) {
char = c
end = start
longestStrMapper = {}
while(!longestStrMapper[char] && char) {
longestStrMapper[char] = true
char = s.charAt(++end)
}
if(end - start > res) {
res = end - start
}
start++;
}
return res;
};
lengthOfLongestSubstring("bbbbb")
// => 1
lengthOfLongestSubstring("abcabcbb")
// => 3
lengthOfLongestSubstring("pwwkew")
// => 3Problem：partition-equal-subset-sum
https://leetcode.com/problems/partition-equal-subset-sum/description/
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.求数组是否能被拆成两个和相等的子数组
我的答案如下:
/*
----问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi ，价值是 wi 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
-----输入格式
每件物品只有一件我们可以选择拿或者不拿，我们定义v[ i ]为物品的体积，w[i]为物品的价值。
我们再来看状态转移方程 f[ i ][ j ] = max ( f[ i-1 ][ j ] , f[ i-1 ][ j-v[ i ] ] + w[ i ] )
*/
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
let sum = 0
for (let num of nums) {
sum += num
}
if (sum & 1 === 1) return false
const half = sum >> 1
// v[ i ]为物品的体积，w[i]为物品的价值。在此题中，单个数字的体积就是其价值，也就是 v[i] === w[i] === nums[i-1]
let dp = Array(nums.length + 1)
dp[0] = [0, ...Array(nums.length).fill(0)] // 前0个元素，容量为0情况，最大价值都为0
// 前1个元素，容量为j情况，最大价值取决于装不装得下，如果能装得下最大价值就是第一个数
dp[1] = [0, ...Array(nums.length).fill(0)]
for (let j = 1; j < half + 1; j++) {
if (j >= nums[0]) {
dp[1][j] = nums[0]
}
}
// 前两个元素开始，当前i个容积为j的最大价值有两种情况，
// 1、第i个数装不下了，我不要了，值为dp[i - 1][j]；
// 2、装得下，我要，那么第个的值占的容积为nums[i-1]，价值也是nums[i-1]，剩下的可以留给前i-1个数来分的容积为j - nums[i-1]，也就是值为dp[i - 1][j - nums[i-1]] + nums[i-1]
// 状态转移方程 f[ i ][ j ] = max ( f[ i-1 ][ j ] , f[ i-1 ][ j-v[ i ] ] + w[ i ] )
for (let i = 2; i < nums.length + 1; i++) {
dp[i] = [0, ...Array(half).fill(0)]
for (let j = 1; j < half + 1; j++) {
// 要注意前i个数中取第i个数的值是 nums[i-1]，因为是由0开始算
// if(j >= nums[i-1]) { // 这里不注释可以把所有的值都求出来
dp[i][j] = Math.max(dp[i - 1][j], j >= nums[i-1] ? dp[i - 1][j - nums[i-1]] + nums[i-1] : 0)
// }
}
}
// console.log(dp)
return dp[nums.length][half] === half
}Problem：target-sum
https://leetcode.com/problems/target-sum/description/
精彩解题分析（引用自：https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md）：
/*
* @lc app=leetcode id=494 lang=javascript
*
* [494] Target Sum
*
* https://leetcode.com/problems/target-sum/description/
*
* algorithms
* Medium (44.86%)
* Total Accepted: 89.3K
* Total Submissions: 198.5K
* Testcase Example: '[1,1,1,1,1]\n3'
*
*
* You are given a list of non-negative integers, a1, a2, ..., an, and a
* target, S. Now you have 2 symbols + and -. For each integer, you should
* choose one from + and - as its new symbol.
*
*
* Find out how many ways to assign symbols to make sum of integers equal to
* target S.
*
*
* Example 1:
*
* Input: nums is [1, 1, 1, 1, 1], S is 3.
* Output: 5
* Explanation:
*
* -1+1+1+1+1 = 3
* +1-1+1+1+1 = 3
* +1+1-1+1+1 = 3
* +1+1+1-1+1 = 3
* +1+1+1+1-1 = 3
*
* There are 5 ways to assign symbols to make the sum of nums be target 3.
*
*
*
* Note:
*
* The length of the given array is positive and will not exceed 20.
* The sum of elements in the given array will not exceed 1000.
* Your output answer is guaranteed to be fitted in a 32-bit integer.
*
*
*/
// 这个是我们熟悉的问题了
// 我们这里需要求解的是nums里面有多少种可以组成target的方式
var sumCount = function(nums, target) {
// 这里通过观察，我们没必要使用二维数组去存储这些计算结果
// 使用一维数组可以有效节省空间
const dp = Array(target + 1).fill(0);
dp[0] = 1; // 和为0组合只有一种，就是全部元素都不选，dp[0]为1
for (let i = 0; i < nums.length; i++) { // 其他情况每个元素都选时，要累加dp[j]，状态转移方程解释：dp[i,j]===dp[i, j - nums[i]]其实好理解，如果定了要nums[i]那么组合数dp[i, j]就变相等于求dp[i, j-nums[i]]的组合数了
for (let j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]]; // 我们不需要保存所有的过程值，因此dp[i, j]写成累加dp[j] += dp[j - nums[i]]即可
}
}
return dp[target];
};
const add = nums => nums.reduce((a, b) => (a += b), 0);
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function(nums, S) {
const sum = add(nums);
if (sum < S) return 0;
if ((S + sum) % 2 === 1) return 0;
return sumCount(nums, (S + sum) >> 1);
};Problem：maximum-sum-of-two-non-overlapping-subarrays
https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/
Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M. (For clarification, the L-length subarray could occur before or after the M-length subarray.)
Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:
0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
Example 1:
Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.
Example 2:
Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.
Example 3:
Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.
Note:
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000求数组可被拆成的长度分别为L与M的两子数组的组成的最大总和值
我的答案如下:
function sumNums (nums, start, end) {
return nums.slice(start, end + 1).reduce((sum, item) => {
return sum += item
}, 0)
}
function maxSumTwoNoOverlap (nums, l, m) {
let x, y, len = nums.length, maxSum = 0
// l在m左边情况
for (x = 0; x < len - m - l + 1; x++) {
y = x + l
while (y > x + l - 1 && y + m - 1 < len) {
maxSum = Math.max(maxSum, sumNums(nums, x, x + l - 1) + sumNums(nums, y, y + m - 1))
y++
}
}
if(m != l) { // 如果相等就不需要处理了，在右边与在左边结果一样
// l在m右边情况
for (x = 0; x < len - m - l + 1; x++) {
y = x + m
while (y > x + m - 1 && y + l - 1 < len) {
maxSum = Math.max(maxSum, sumNums(nums, x, x + m - 1) + sumNums(nums, y, y + l - 1))
y++
}
}
}
return maxSum
}
