自知算法薄弱，做不到一步登天，那就脚踏实地，聚沙成塔。
不积跬步无以至千里，不积小流无以成江河。
20200309
题型：树的广度优先遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
var levelOrderBottom = function(root) {
if (!root) return []
let result = []
let depth = 0
let queue = []
queue.push(root)
while (queue.length) {
result[depth] = []
let length = queue.length
for (let i = 0; i < length; i++) {
queue[i].val !== null && result[depth].push(queue[i].val)
if (queue[i].left) queue.push(queue[i].left)
if (queue[i].right) queue.push(queue[i].right)
}
queue.splice(0, length)
depth++
}
return result.reverse()
};
思路：广度优先遍历需要借助队列，每一层结束了就splice掉，一层一层向下，最后翻转一下就好。
时间复杂度：O(n)
20200310
题型：树的深度优先遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
var diameterOfBinaryTree = function(root) {
if (!root) return 0
let result = 0
function getMax (root) {
result = Math.max(result, getDeep(root.left) + getDeep(root.right))
if (root.left) getMax(root.left)
if (root.right) getMax(root.right)
return result
}
function getDeep (node, depth = 0) {
if (node) {
depth++
return Math.max(getDeep(node.left, depth), getDeep(node.right, depth))
} else {
return depth
}
}
return getMax(root)
};
思路：方向是对的，深度优先遍历，但是这边有个坑，不能直接两边最大深度相加，因为这个直径可能根本就不经过根节点，所以要把每个节点都当做根节点进行一次递归求两边最大深度与当前result的大值。
20200311
题型：数学、双向链表
/**
* @param {number[]} A
* @return {boolean}
*/
var canThreePartsEqualSum = function(A) {
let sum = getSum(A)
let left = []
let right = []
if (sum % 3 !== 0) return false
for (let i = 0; i < A.length - 1; i++) {
left.push(A[i])
if (getSum(left) === sum / 3) {
for (let j = A.length - 1; j > i + 1; j--) {
right.push(A[j])
if (getSum(right) === sum / 3) {
return true
}
}
return false
}
}
return false
};
function getSum (arr) {
return arr.reduce((a, b) => (a + b), 0)
}
思路：最重要的是，数组可以分成三段，每段和相同，那么他们一定等于getSum(A) / 3，剩下的就是两边往中间遍历而已。
20200312
** 题型：数学 **
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var gcdOfStrings = function(str1, str2) {
if (str1 === str2) return str1
if (str1.length < str2.length) {
let temp = str2
str2 = str1
str1 = temp
}
let result = ''
for (let i = 1; i <= str2.length; i++) {
let temp = str2.slice(0, i)
if (str1.split(temp).join('') === '' && str2.split(temp).join('') === '') {
result = temp
}
}
return result
};
思路：1、最简单的枚举，从长度1到较小字符串长度一个一个试，2、欧几里得公式，求最大公约数，然后从较小的字符串里取这个长度
20200313
** 题型：哈希表 **
169. 多数元素
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let timeMap = new Map()
if (nums.length === 1) return nums[0]
for (let i = 0; i < nums.length; i++) {
if (timeMap.has(nums[i])) {
if (timeMap.get(nums[i]) + 1 > Math.floor(nums.length / 2)) {
return nums[i]
}
timeMap.set(nums[i], timeMap.get(nums[i]) + 1)
} else {
timeMap.set(nums[i], 1)
}
}
};
思路：hashmap存储元素出现的次数，比较简单
20200314
** 题型：动态规划 **
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let maxUpList = []
for (let i = 0; i < nums.length; i++) {
if (!maxUpList.length) {
maxUpList.push(nums[i])
} else if (maxUpList.slice(-1) < nums[i]) {
maxUpList.push(nums[i])
} else {
let index = maxUpList.findIndex(item => item >= nums[i])
maxUpList[index] = nums[i]
}
}
return maxUpList.length
};
// 动态规划版本
var lengthOfLIS = function(nums) {
let dp = new Array(nums.length).fill(1)
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
// 状态转移方程
dp[i] = Math.max(dp[j] + 1, dp[i])
}
}
}
return dp.reduce((pre, cur) => Math.max(pre, cur), 0)
};
思路：最开始的思路就是对整个数组进行一次遍历，往后插入大值，小值可以替换前面的值，因为遍历还是线性的，所以时间复杂度还是O(n^2)
从动态规划的角度来看，dp[j] = dp[i] + 1，只要满足j位置的值大于前面i位置的值，那么就可以和i位置的最长上升子序列组成一个更长的最长上升子序列，因为每次到j时都得变量一遍前面i个位置的值，所以时间复杂度还是O(n^2)，使用的数组长度小于等于原数组长度，空间复杂度O(n)
20200316
** 题型：空间换取时间 **
试题 01.06. 字符串压缩
思路：用两个组分别存储重复字符和重复字符的长度，最后进行一次比较即可
20200317
** 题型：哈希表计数 **
1160. 拼写单词
var countCharacters = function(words, chars) {
let map = {}
for (let i = 0; i < chars.length; i++) {
if (!map[chars[i]]) {
map[chars[i]] = 1
} else {
map[chars[i]] = map[chars[i]] + 1
}
}
return words.reduce((result, cur) => {
let word = {}
for (let i = 0; i < cur.length; i++) {
if (word[cur[i]]) {
word[cur[i]] = word[cur[i]] + 1
} else {
word[cur[i]] = 1
}
}
if (Object.keys(word).every(key => map[key] >= word[key])) {
return result + cur.length
} else {
return result
}
}, 0)
};
20200318
** 题型：数学 **
/**
* @param {number[]} rec1
* @param {number[]} rec2
* @return {boolean}
*/
var isRectangleOverlap = function(rec1, rec2) {
let [x1, y1, x2, y2] = rec1
let [x3, y3, x4, y4] = rec2
return hasjiaoji([x1, x2], [x3, x4]) && hasjiaoji([y1, y2], [y3, y4])
};
function hasjiaoji (arr1, arr2) {
let da1 = Math.max(arr1[0], arr1[1])
let da2 = Math.max(arr2[0], arr2[1])
let xiao1 = Math.min(arr1[0], arr1[1])
let xiao2 = Math.min(arr2[0], arr2[1])
if (
da1 <= xiao2 || xiao1 >= da2
) {
return false
} else {
return true
}
}
思路：看x轴和y轴是否两两相交，如果是则必有面积重叠
20200319
** 题型：哈希表 || Set **
409. 最长回文串
/**
* @param {string} s
* @return {number}
*/
var longestPalindrome = function(s) {
let map = {}
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
map[s[i]] = map[s[i]] + 1
} else {
map[s[i]] = 1
}
}
let hasSingle = false
return Object.values(map).reduce((result, cur) => {
if (cur % 2 !== 0 && !hasSingle) {
hasSingle = true
}
return result + (Math.floor(cur / 2) * 2)
}, 0) + (hasSingle ? 1 : 0)
};
思路：
1、能组成回文则出现偶数次，若有一个字符出现奇数次，回文长度加一
2、使用Set数据结构，set.has，则长度加2，并set.delete该值，若不存在则set.add
20200322（前两天太忙了，今天补上之后继续，因为代码可以到力扣看，这边简单题只写思路和截图）
题型：hash表
思路：先排序，重复出现的元素仅需要比上一个出现的非重复元素大1即可，累加相差的值就是要move的值
题型：数学
思路：非常硬核的一道题，暴力求解会超时。由于数组中最大的值为1e9也就是10的9次方，因为2^30< 10e9 <2^31也就是说至少需要31位2进制才可以表示这个二进制数，通过num.toString(2)转为二进制之后，遍历每一位上的0和1的个数并统计，当前位汉明距离（任意两个数二进制当前位不同的数量即01组合的个数）等于count[0]*count[1]个，最后31位统一累加，时间复杂度是O(n)，空间复杂度O(1)。
/**
* @param {number[]} nums
* @return {number}
*/
var totalHammingDistance = function(nums) {
let result = 0
let maxBit = 31 // 最大32位
nums = nums.map(num => num.toString(2))
for (let i = 0; i < maxBit; i++) {
let count = {
'0': 0,
'1': 0
}
for (let j = 0; j < nums.length; j++) {
let cur = nums[j]
count[+cur[cur.length - i - 1] ? '1' : '0']++
}
result += count[0] * count[1]
}
return result
};
20200323
题型：链表
思路：
1、单指针两次遍历，第一次记录长度，第二次访问到中间长度时返回节点
2、快慢指针，快指针一次移动两格，慢指针一次移动一格，快指针到达链表尾部时，慢指针也就在中间了~
20200324
** 题型：动态规划**
/**
* @param {number[]} nums
* @return {number}
*/
var massage = function(nums) {
let dp = []
dp[0] = nums[0]
dp[1] = Math.max(nums[1], nums[0])
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[nums.length - 1] || 0
};
每次做到动态规划的题总是知道这道题要用动态规划，可是就是做不出来。。
思路：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。每次中间需要间隔，三个一组，但是不是0,3到3,6，而是0,3到1,4，像滑动窗口一样划过去，计算每个点位的最大值，最后返回dp[i]即可。
20200325
题型：数学
思路：横向，竖向分别遍历一次，按条件捕获即可，时间复杂度O(n^2)。
20200326
题型：动态规划
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let dp = []
let max = nums[0]
dp[0] = nums[0]
for (let i = 1; i < nums.length; i++) {
if (dp[i - 1] < 0) {
dp[i] = nums[i]
} else {
dp[i] = dp[i - 1] + nums[i]
}
max = Math.max(dp[i], max)
}
return max
};
思路：动态规划，dp[i - 1]为负时相当于前面的总和已经是负收益，dp[i]直接等于当前值即可，转移方程是 -> dp[i] = dp[i - 1]是负数 ？nums[i] : dp[i - 1] + nums[i]。
20200326
题型：最小公约数
/**
* @param {number[]} deck
* @return {boolean}
*/
var hasGroupsSizeX = function(deck) {
let arr = {}
for (let i = 0; i < deck.length; i++) {
if (arr[deck[i]] !== void 0) {
arr[deck[i]] = arr[deck[i]] + 1
} else {
arr[deck[i]] = 1
}
}
let g = -1
for (let i = 0; i < 10000; i++) {
if (arr[i]) {
if (g === -1) {
g = arr[i]
} else {
g = gcd(g, arr[i])
}
}
}
return g >= 2
};
// 求最大公约数！谨记，如果x（余）为0，则最大公约数是上一次的x，这一次的y
function gcd (x, y) {
return x === 0 ? y : gcd(y % x, x)
}
思路：先记录所有数字出现的次数，再根据题意最大值不超过10000，求最小公约数，gcb公式（Greatest Common Divisor）要牢记！还有另一种思路，就是记录最大值，遍历到这个最大值最大公约数是否大于2。
20200327
题型：动态规划
思路：
1、>> 符号在js里，如果是>>0相当于Math.floor取整，如果是>>1则表示将2进制位右移一位，并补位0
2、Array.from(arr, item => item + 1)，Array的第二个参数是一个回调，可以操作前面的类数组，并最后返回一个数组
3、最长回文子可以通过暴力枚举、反转字符串求公共子串、动态规划来做
动态规划：将i，j表示为i到j的字符串，值表示为是否是回文子串动态规划方程是
dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j]
true表示是回文串，反之不是
20200328
题型：数学
思路：1、正常思路，控制递增变量，取递增最大的那一次，时间复杂度O(n)，空间复杂度O(1)
2、动态规划，下一个数大于上一个数则 dp[i] = dp[i - 1] + 1 否则 dp[i] = 1
20200329
题型：经典约瑟夫环
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
if (m === 1) return n - 1
let arr = []
for (let i = 0; i < n; i++) {
arr.push(i)
}
let idx = 0
while (arr.length !== 1) {
idx = (idx + m - 1) % arr.length
arr.splice(idx, 1)
}
return arr[0]
}
思路：每次删除后，记录下当前的位置，下次再对数组长度求余，得到新的要删除的位置，勉强通过
20200330
题型：分治
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
if (nums.length <= 1) {
return nums
}
// 归并排序
let length = nums.length
let mid = (length / 2) >> 0
let left = nums.slice(0, mid)
let right = nums.slice(mid, length)
return merge(sortArray(left), sortArray(right))
};
function merge (left, right) {
let result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left).concat(right)
}
思路：Array.sort本质上是快排，选择，归并的合集，根据数组长度来选择最佳的排序规则，做到这道题时想学习一下归并。归并排序采用的是分而治之的思想，将数组拆分成一个一个的小数组进行排序，然后将排序好的小数组再进行一次排序，长度为n的数组本质上仅需要log2n次拆分，时间复杂度为nlogn
20200331
题型：栈
/**
* @param {string} seq
* @return {number[]}
*/
var maxDepthAfterSplit = function(seq) {
if (!seq.length) return []
let result = [0]
let A = [seq[0]]
let B = []
for (let i = 1; i < seq.length; i++) {
// A.slice(-1)
if (seq[i] === ')') {
if (A.length > B.length) {
A.length = A.length - 1
result.push(0)
} else {
B.length = B.length - 1
result.push(1)
}
} else {
if (A.length > B.length) {
B.push(seq[i])
result.push(1)
} else {
A.push(seq[i])
result.push(0)
}
}
}
return result
};
思路：保持AB组的深度一致，相差不超过1即可，可以找规律，也可以像我这样暴力破解，哈哈哈哈哈哈哈哈哈嗝，时间复杂度N，空间复杂度1
20200401
** 题型：数学 **
思路：没什么好说的，按题意来，8个方向都取一次，时间复杂度O(n^2)，空间复杂度O(n)
20200402
** 题型：数学 **
思路：耐心题，确认好函数边界，虚怀若谷，沉住气
20200403
** 题型：数学（木板效应） **
思路：根据木板效应，每一个能接的水取决于左右两边最短的那一块减去当前木板高度的值，暴力法求解，时间复杂度O(n^2)
20200404
** 题型：LFU算法 **
let LFUCache = class {
constructor(capacity) {
this.limit = capacity
this.cache = new Map()
this.freqMap = new Map()
}
get(key) {
let cache = this.cache
let r = -1
if (typeof cache[key] != "undefined") {
let o = cache[key]
r = o.value
//更新频率记录
this.updateL(key, o)
}
return r
};
updateL(key, obj){
let freq = obj.freq;
let arr = this.freqMap[freq]
// 删除原频率记录
this.freqMap[freq].splice(arr.indexOf(key), 1)
// 清理
if (this.freqMap[freq].length == 0) delete this.freqMap[freq]
// 更新频率
freq = obj.freq = obj.freq + 1
if (!this.freqMap[freq]) this.freqMap[freq] = []
this.freqMap[freq].push(key)
}
put(key, value) {
let cache = this.cache
let limit = this.limit
let fmap = this.freqMap
if (limit <= 0) return
if(typeof key=="undefined"||typeof value=="undefined") throw new Error('key or value is undefined')
// 存在则直接更新
if (typeof cache[key] == "undefined") {
// 获取频率 key
// 判断容量是否满
if (Object.keys(cache).length == limit) {
let fkeys = Object.keys(fmap)
let freq = fkeys[0]
// 获取key集合
let keys = fmap[freq]
// 淘汰首位
delete cache[keys.shift()]
// 清理
if (fmap[freq].length == 0) delete fmap[freq]
}
// 频率记录是否存在
if (!fmap[1]) fmap[1] = []
// 插入新值
fmap[1].push(key)
cache[key] = {
value: value,
freq: 1 // 默认的频率
}
} else {
cache[key].value = value
//更新频率记录
this.updateL(key, cache[key])
}
};
};
思路：跟LRU不同，LRU是根据时间来清除最久未使用的数据，LFU是根据频率来清除最久未使用的数据，为了节省时间，这边需要两个map，一个cacheMap用来存储key对应key的val和freq频率，一个freqMap用来存储每一种freq频率对应的keyArr，以便在相同频率的情况下删除最前面的数据，更新map。（做的我自闭了
20200405
题型： 排序
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
var sort = incorporateSort(arr)
return sort.slice(0, k)
};
var incorporateSort = function (arr) {
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid)
return merge(incorporateSort(left), incorporateSort(right))
}
var merge = function (left, right) {
let result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left).concat(right)
}
思路：
1、排序，我用了归并，分治的思想
2、（因为这里没有规定要按顺序返回）最小栈，维护一个栈，先将k个数推入栈内，然后从k+1个数开始遍历，如果它比顶部值要小（最小的k个数肯定会满足这个条件），那就插入栈的尾部，最后返回该栈元素
20200406
题型：动态规划+缓存
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.nums = nums
this.record = new Array(nums.length)
this.record[0] = nums[0]
for (let i = 1; i < nums.length; i++) {
this.record[i] = this.nums[i] + this.record[i - 1]
}
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
if (i === 0) return this.record[j]
return this.record[j] - this.record[i - 1]
};
思路：刚开始想的就是动态规划，结果一做超时，想着用map来缓存求过的值，一做，还是超时，正确的思路是新建一个记录数组，每个位置为0到该位置的和，那么有sum(i, j) = record[j] - record[i - 1]成立，每次只要计算减法就好了，时间复杂度O(n)比动规O(n^2)效率高很多。
20200407
题型：寻路算法、dfs、bfs
/**
* @param {number} m
* @param {number} n
* @param {number} k
* @return {number}
*/
var movingCount = function(m, n, k) {
let result = 0
let record = {}
let runner = function (a, b) {
if (a >= m || b >= n || a < 0 || b < 0) {
return
}
let sum = getSum(a) + getSum(b)
let axis = JSON.stringify([a, b])
if (sum <= k && !record[axis]) {
result++
record[axis] = true
runner(a + 1, b)
runner(a - 1, b)
runner(a, b + 1)
runner(a, b - 1)
}
}
runner(0, 0)
return result
};
function getSum (num) {
let res = 0
while (num > 0) {
res += num % 10
num = Math.floor(num / 10)
}
return res
}
思路：好题。题中只能上下左右移动因此可以将不满足条件的点想成砖块，同时对满足砖块的每个点做上下左右移动的操作，并记录到过的点位，可以计出总数。另外求和总数，每次除10求余数，然后除以10，继续取余数，得到位数和。
20200408
题型：深度优先遍历
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
let result = []
const dfs = function (str, leftNumber, rightNumber) {
if (str.length === n * 2) {
result.push(str)
return
}
if (rightNumber < leftNumber) return
if (leftNumber === n) {
dfs(str + '(', leftNumber - 1, rightNumber)
} else {
leftNumber > 0 && dfs(str + '(', leftNumber - 1, rightNumber)
rightNumber > 0 && dfs(str + ')', leftNumber, rightNumber - 1)
}
}
dfs('', n, n)
return result
};
思路：深度优先遍历，先全部左括弧，然后一个一个右括弧往上叠加，注意有效的括号左括弧的数量要始终大于等于右括弧的数量。最后返回所有结果。
20200409
题型：位运算
/**
* @param {number} num
* @return {number[]}
*/
var findClosedNumbers = function(num) {
let times = getOneTimes(num)
let min = -1
let max
let i = num
let j = num
while (!max) {
++i
if (getOneTimes(i) === times) {
max = i
}
}
while (min === -1 && j > 0) {
--j
if (getOneTimes(j) === times) {
min = j
}
}
return [max, min]
};
function getOneTimes (num) {
let numT = Number(num).toString(2)
return numT.length - numT.split('1').join('').length
}
思路： 暴力解法就是从num往两边移动，分别找到符合条件的最大最小的数。