第二个30天，士兵们，新一轮的战斗开始了
20200410
题型：双指针 | 库函数
思路：
1、统计每个单词的左右边界，i，j最后反向插入即可
2、利用库函数split，过滤空格，reverse反正得到结果
20200411
题型：双指针，数学
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let result = []
if (nums.length < 3) return result
// 顺序排序
nums = nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length; i++) {
// 首个元素大于0可以不用再比了
if (nums[i] > 0) return result
// 和上个元素相同，避免重复解
if (i > 0 && nums[i] === nums[i - 1]) {
continue
}
let left = i + 1
let right = nums.length - 1
while (left < right) {
var total = nums[i] + nums[left] + nums[right]
if (total === 0) {
// 先承认该数
result.push([nums[i], nums[left], nums[right]])
// 避免重复解，只需要在得到解之后，遇到相同数的时候继续向后移动即可避免重复解
while (left < right && nums[left + 1] === nums[left]) {
left++
}
while (left < right && nums[right - 1] === nums[right]) {
right--
}
// 避免重复解之后也不要忘了移动指针，否则会死循环
left++
right--
} else if (total > 0) {
right = right - 1
} else {
left = left + 1
}
}
}
return result
};
思路：
三数之和，可以以第一个数为游标（固定数），排序之后向后移动，中间数Left即为 i + 1，最大数Right可暂定num.length - 1
如果和大于0，说明最大数太大，Right向左偏移
如果和小于0，说明中间数太小，Left向右偏移
中间遇到合法的解，为了避免后面有重复的数字，需要判断，并继续偏移
20200412
题型：反向遍历
题号：58 最后一个单词的长度
思路：很简单，不过js的执行效率不够高，解释型语言就是这样。这边复习一下js执行的过程吧，我们都只到js是由v8引擎驱动的，v8要开始执行一段js代码，首先需要对这行js代码进行词法分析，分析每个字符的含义，然后是语法分析，分析这些字符组合在一起的含义，再然后再转成v8引擎能够识别的AST语法树，然后将其编译成字节码（字节码是在机器码上层封装的一种代码格式），然后由JIT编译器逐行执行（补充一下，当某段代码被重复执行时，v8会将其转为机器码，来提高之后的执行效率，不将所有代码转换成机器码的原因是，一行代码转成机器码可能有20行，内存占用大，所以只有部分高频使用的代码才会转成机器码）。
20200413
题型：数组的深度优先遍历 | 回溯 | 全排列
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
let result = []
let resultSet = new Set()
handler(nums, [], result, resultSet)
return result
};
function handler (arr, temp, result, resultSet) {
if (!arr.length) {
if (!resultSet.has(JSON.stringify(temp))) {
resultSet.add(JSON.stringify(temp))
result.push(temp)
}
return
}
for (let i = 0; i < arr.length; i++) {
let t = [...temp, arr[i]]
let next = arr.slice(0, i).concat(arr.slice(i + 1))
handler(next, t, result, resultSet)
}
}
思路：同全排列I，这道全排列II，只是多了去重的一步，重要的是回溯的思路，为了得到全排列，必须每一位都和剩下的任意一位组合，因此回溯必不可少，回溯的过程中需要组合的元素会越来越少，每一次回溯都会取出一个元素与上一次的temp进行组合，然后从数组中刨除这个元素，开始下一轮的组合，此类组合方式也是深度优先遍历的一种，第一步会从第一位组合到最后一位比如[1,2,3,4]，第二步会从第一位到倒数第二位开始组合即[1,2,4,3]，然后[1,3,2,4]、[1,3,4,2]以此类推。
20200414
题型：链表 | 栈
思路：关键点在于我们所需的结果和链表的存储顺序是相反的，遇到这种问题首先要想到栈，把两个链表分别推入栈中，然后再依次出栈相加，record记录下是否需要进位，很容易得到结果。
20200415
题型：指针
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
while (m > 0 && n > 0) {
if (nums1[m - 1] > nums2[n - 1]) {
nums1[n + m - 1] = nums1[m - 1]
m--
} else {
nums1[n + m - 1] = nums2[n - 1]
n--
}
}
if (m === 0) {
while (n >= 0) {
nums1[n - 1] = nums2[n - 1]
n--
}
return nums1
}
return nums1
};
思路：解题并不难，但最优解是时间复杂度O(m+n)，空间复杂度O(1)的，从后向前双指针移动，最后补全，无需额外变量。
20200416
题型：递归
思路：全排列的变种，关键在于剪枝，及时中断，否则很容易超时
20200417
题型：贪心算法
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
if (nums.length === 1) return true
let max = nums[0]
for (let i = 0; i < max; i++) {
let step = i
while (step < nums.length && nums[step] !== 0) {
step += nums[step]
max = Math.max(max, step)
}
if (max >= nums.length - 1) {
return true
}
}
return false
};
思路：每次往前跳最大格，可以到达的位置max随之增大，step起始位置也增大，如果有符合条件的跳跃方式max > nums.length - 1，则说明条件成立。（少见的贪心算法题，关键在于遍历的条件i < max中的max在随着贪心条件的变化而变化）
20200418
题型：数学规律
var nextPermutation = function(nums) {
let i = nums.length - 2
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--
}
// i是破坏升序的数如3，5，4，2，1中的3
if (i >= 0) {
let j = nums.length - 1
// 找到j遍历过的数中比破坏数大的数的位置，像是4
while (j >= i && nums[j] <= nums[i]) {
j--
}
// 进行一次交换，得到4，5，3，2，1
swap(nums, i, j)
}
// 然后要保证后面的数升序，得到下一个排列
if (i >= 0) {
i = i + 1
// console.log(i, nums, '-----')
let j = nums.length - 1
while (i < j) {
swap(nums, i, j)
i++
j--
}
return nums
}
return nums.reverse()
};
function swap (nums, i, j) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
思路：寻找下一个排列更大的数，解法倒序遍历，先找到第一个破坏了降序的数，然后在前面的数里找到比这个数大的数对它进行替换，再把遍历过的数进行翻转，保证是下一个排列更大的数即可，最多遍历两次（每次做到这种题，就觉得对刷题的兴趣越来越不够了，这种找规律的题就算法来说并没有什么规律可言，只是数学上的一种规则，如果做过或许很快就能找到规律，没做过，可能很久也想不出来，时间花在这上面，带来的收益是成正比的吗？）
20200419
题型：链表
var deleteDuplicates = function(head) {
loop(head)
return head
};
function loop (linked) {
if (linked && linked.next) {
if (linked.val === linked.next.val) {
linked.next = linked.next.next
loop(linked)
} else {
loop(linked.next)
}
}
}
思路：正向遍历链表好了，如果重复，则舍弃重复链，重新比较，否则继续向下遍历。
20200420
题型：无向图遍历
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let num = 0;
if(grid && grid.length) {
const maxI = grid.length - 1, maxJ = grid[0].length - 1
function overturn(i, j) {
if(i < 0 || j < 0 || i > maxI || j > maxJ) return;
if(grid[i][j] === '1') {
// 该值周边所有相连的1都可以翻转成0看做同一个岛屿
grid[i][j] = '0'
overturn(i, j-1)
overturn(i-1, j)
overturn(i+1, j)
overturn(i, j+1)
}
}
for(let i = 0; i < grid.length; i++) {
for(let j = 0; j < grid[i].length; j++) {
if(grid[i][j] === '1') {
num++;
overturn(i, j)
}
}
}
}
return num;
};
思路：找到陆地时，继续遍历其周边的陆地，如果有相连的陆地，则他们属于同一座岛屿，可以置为0，两次for循环即可，同之前做的机器人的问题，只能上下左右走一个，找准题目条件是关键，这个题还挺好玩的
20200421
题型：广度优先遍历
var rightSideView = function(root) {
if (!root) return []
let queue = [root]
let result = []
let depth = 0
while (queue.length) {
let l = queue.length
result[depth] = []
for (let i = 0; i < l; i++) {
let temp = queue.shift()
result[depth].push(temp.val)
if (temp.left) queue.push(temp.left)
if (temp.right) queue.push(temp.right)
}
depth++
}
return result.map(arr => arr.slice(-1))
};
思路：老题了，bfs一次取最右侧数据即可
20200422
题型：矩阵、数学
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
if (!matrix.length || !matrix[0].length) return []
// right,down,left,up
let dir = 'right'
let il = matrix.length
let jl = matrix[0].length
let total = il * jl
let center = `${Math.floor(il / 2)}${Math.floor(jl / 2)}`
let leftL = 0
let topL = 0
let i = 0
let j = 0
let result = []
while (result.length !== total - 1) {
while (dir === 'right' && j <= jl - 1 && result.length !== total - 1) {
if (j === jl - 1) {
topL++
dir = 'down'
} else {
result.push(matrix[i][j])
j++
}
}
while (dir === 'down' && i <= il - 1 && result.length !== total - 1) {
if (i === il - 1) {
jl--
dir = 'left'
} else {
result.push(matrix[i][j])
i++
}
}
while (dir === 'left' && j >= leftL && result.length !== total - 1) {
if (j === leftL) {
il--
dir = 'up'
} else {
result.push(matrix[i][j])
j--
}
}
while (dir === 'up' && i >= topL && result.length !== total - 1) {
if (i === topL) {
leftL++
dir = 'right'
} else {
result.push(matrix[i][j])
i--
}
}
}
return result.concat([matrix[i][j]])
};
思路：按照题意来即可，每次收窄边界，长度达到限度则已经收集完毕。
20200423
题型：斐波那契、dp
思路：dp[n] = dp[n - 1] + dp[n - 2] 唯一的问题是要在循环里取模，不然最后的精度会丢失。
20200424
题型：链表，双指针
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let temp = head
let l = getLinkedLength(temp)
for (let i = 0; i <= l - k; i++) {
head = head.next
}
return head
};
function getLinkedLength (head) {
let length = 0
while (head && head.next) {
length++
head = head.next
}
return length
}
思路：第一时间想到的是统计链表长度，返回l-k位置的链表就行，其实也可以不统计长度，使用快慢指针的形式，快指针先走k次，然后快慢指针一起走，快指针走到头了，慢指针所指的位置即为倒数第k个的位置。
20200425
题型：hash表，桶排序
思路：两次遍历，进行减少遍历条件，减少哈希表大小，正常思路来即可。
20200426
题型：栈和队列的应用
/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
let temp = []
for (let i = 0; i < pushed.length; i++) {
temp.push(pushed[i])
while (temp[temp.length - 1] === popped[0] && popped[0] !== void 0) {
temp.pop()
popped.shift()
}
}
while (popped.length) {
if (temp[temp.length - 1] === popped[0]) {
temp.pop()
popped.shift()
} else {
return false
}
}
return true
};
思路：栈底等于队列头部则出栈，出队列，若不等则继续推入栈中，最后判断出栈队列是否清空即可。
20200427
题型：js的异或操作
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let result = 0
for (let i = 0; i < nums.length; i++) {
result ^= nums[i]
}
return result
};
思路：思路新奇，不需要借助额外的空间，因为相同的元素进行异或操作一定是0，只要把所有元素进行异或，得到的值肯定就是只出现一次的那个值。
js的位操作 与、或、非、异或、左移、右移操作
与：&
或：|
非：~
异或：^
左移：5 << 1
右移：5 >> 1
20200428
题型：快慢指针
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
let slow = n
let fast = n
do {
slow = getNumT(slow)
fast = getNumT(fast)
fast = getNumT(fast)
} while (slow !== fast)
return slow === 1
};
function getNumT (n) {
let temp = String(n).split('').map(item => Number(item))
return temp.reduce((pre, cur) => {
return pre + Math.pow(cur, 2)
}, 0)
}
思路：
思路1：就是递归，然后HashSet存储判断，但是遇到特别大的数可能会超出存储限制
思路2：快慢指针，最后归于一致说明已经经过了一次循环，归于一致的值如果是1，说明是快乐数
20200429
题型：双指针
/**
* @param {number[]} nums
* @return {number[]}
*/
var exchange = function(nums) {
let i = 0
let j = nums.length - 1
while (i < j) {
if (nums[i] % 2 === 0) {
while (i < j && nums[j] % 2 === 0) {
j--
}
swap(i, j, nums)
}
i++
}
return nums
};
function swap (i, j, nums) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
思路：一开始想的是遍历一次，造两个数组时间复杂度O(n)，空间复杂度O(n)
更好的思路：双指针，数组内部交换位置，时间复杂度O(n)，空间复杂度O(1)
20200430
题型：链表
var mergeTwoLists = function(l1, l2) {
if (!l1) {
return l2
} else if (!l2) {
return l1
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
};
思路：不借助额外的空间，递归链表，当有一个链表为null时返回另一个链表接到上一个链表的尾部
20200501
题型：双指针，滑动窗口，数学
var lengthOfLongestSubstring = function(s) {
let result = 0
let begin = -1
let end = 0
const map = new Map()
for (let i = 0; i < s.length; i++) {
// 碰到重复出现的字符，后面的子序列长度要和前面最大的子序列长度做对比
if (!map.has(s[i]) || map.get(s[i]) <= begin) {
end = i
result = Math.max(end - begin, result)
} else {
// 已存在，更新begin位置，为上一个出现s[i]的后一位
begin = map.get(s[i])
}
// 更新begin的位置
map.set(s[i], i)
}
return result
};
思路：记录begin和end的位置，遇到重复字符，如果重复字符已经在begin之前，则不再更新begin位置，但是需要判断当前end-begin的长度是否已经超过前面的最大子序列的长度，如果重复字符在begin之后，那么可以直接更新begin了，避免[begin, end]的区间内有重复字符。
20200526
无题
插入排序
function insertSort (arr) {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i] // 记录要插入的元素
let j = i
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1]
j--
}
arr[j] = temp
}
return arr
}
思路：假设第一项已经排好序，第一项作为插入项，与前面位进行比较，如果前面位较大，则替换当前位置，每次循环都能保证到第一次不满足条件的位置，之前的数已经排好序了，最好将插入项插入到第一个不满足条件的位置即可，sort函数在长度小于10的数组时采用的就是插入排序，性能比快排和冒泡效率偏高，在10-1000位时采用的是快排，取中位数作为哨兵，大于1000位时取哨兵元素有些许不同