前言
算法是很有趣的东西，我们多思考一下就会掉好多头发。
一、图解字节&leetcode14：最长公共前缀
1. 题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
答案：
1.解法一：逐个比较
解题思路： 从前往后一次比较字符串，获取公共前缀
function searchMax(arr){
if(!arr || !arr.length) return ''
let result = arr[0]
for(let i=1;i<arr.length;i++){
let j= 0
for(;j<result.length;j++){
if(result.charAt(j) !== arr[i].charAt(j)){
break
}
}
result = result.substring(0,j)
}
return result
}
时间复杂度：O(s)，s 是所有字符串中字符数量的总和
空间复杂度：O(1)
解法二：分治策略 归并思想
分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。
这道题就是一个典型的分治策略问题：
问题：求多个字符串的最长公共前缀：
-
分解成多个相似的子问题：求两个字符串的最长公共前缀
-
子问题可以简单求解：两个字符串的最长公共前缀求解很简单
-
原问题的解为子问题解的合并： 多个字符串的最长公共前缀为两两字符串的最长公共前缀的最长公共前缀，
我们可以归并比较两最长公共前缀字符串的最长公共前缀，知道最后归并比较成一个
则为字符串数组的最长公共前缀： LCP(S1, S2, …, Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))
var longestCommonPrefix = function(strs) {
if(!strs || strs.length === 0)return ''
return splitArr(strs)
};
function splitArr(arr){
if(arr.length === 1){
return arr[0]
}
const mid = Math.floor(arr.length/2)
const left = arr.slice(0,mid)
const right = arr.slice(mid)
return twoStr(splitArr(left),splitArr(right))
}
function twoStr(str1,str2){
let res = ''
const minLength = str1.length > str2.length?str2.length: str1.length
for(let i= minLength;i>=0;i--){
if(str2.indexOf(str1.substring(0,i)) === 0){
res = str1.substring(0,i)
break
}
}
return res
}
二、图解字节&leetcode151：翻转字符串里的单词
1. 题目
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
解法一：正则 + JS API
var reverseWords = function(s) {
return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};
解法二：双端队列（不使用 API）
双端队列，故名思义就是两端都可以进队的队列
解题思路：
首先去除字符串左右空格
逐个读取字符串中的每个单词，依次放入双端队列的对头
再将队列转换成字符串输出（已空格为分隔符）
var reverseWords = function(s) {
let left = 0
let right = s.length - 1
let queue = []
let word = ''
while (s.charAt(left) === ' ') left ++
while (s.charAt(right) === ' ') right --
while (left <= right) {
let char = s.charAt(left)
if (char === ' ' && word) {
queue.unshift(word)
word = ''
} else if (char !== ' '){
word += char
}
left++
}
queue.unshift(word)
return queue.join(' ')
};
三、leetcode160 找到两个单链表相交的起始节点
注意：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)
解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。
若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null
var getIntersectionNode = function(headA, headB) {
while(headA) {
headA.flag = true
headA = headA.next
}
while(headB) {
if (headB.flag) return headB
headB = headB.next
}
return null
};
时间复杂度：O(n)
空间复杂度：O(n)
解法二：双指针法
解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。
我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。
解题步骤：
同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），设A为长链表
那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null
var getIntersectionNode = function(headA, headB) {
// 清除高度差
let pA = headA, pB = headB
while(pA || pB) {
if(pA === pB) return pA
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return null
};
时间复杂度：O(n)
空间复杂度：O(1)
四、leetcode19：删除链表倒数第 n 个结点
1. 题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
解法：需要删除链表中的倒数第 n 个节点，我们需要知道的就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的后继节点即可
使用 2 个指针：
fast 快指针提前走 n+1 步
slow 指针指向当前距离 fast 倒数第 n 个节点， 初始为 head
然后， fast 、 slow 同步向前走，直到 fast.next 为 null
此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点
但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以此时有两种解决思路：
创建一个头节点 preHead ，设置 preHead.next = head ，这样就可以解决以上问题，删除倒数第 n 个节点后，返回的 preHead.next 即可
解决方案一：添加 preHead 节点
var removeNthFromEnd = function(head, n) {
let preHead = new ListNode(0)
preHead.next = head
let fast = preHead, slow = preHead
// 快先走 n+1 步
while(n--) {
fast = fast.next
}
// fast、slow 一起前进
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return preHead.next
};
另外一种是，fast 快指针提前走 n 步后，判断 fast.next 是否为 null ，即 fast 是否是最后一个节点，如果是，则 head 为倒数第 n 个节点，此时问题可以简化为删除头节点；如果不是， fast = fast.next ，fast 再前进一步，slow 为倒数第 n+1 个节点，也解决了以上问题。
解决方案二：单独处理倒数第 n 节点
var removeNthFromEnd = function(head, n) {
let fast = head, slow = head
// 快先走 n 步
while(--n) {
fast = fast.next
}
if(!fast.next) return head.next // 链表为n时 删除头节点，返回头节点的next
fast = fast.next
// fast、slow 一起前进
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return head
};
五、leetcode876：求链表的中间结点
1. 题目
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
2. 解法：快慢指针
解题思路： 快指针一次走两步，慢指针一次走一步，当快指针走到终点时，慢指针刚好走到中间
var middleNode = function(head) {
let fast = head, slow = head
while(fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
};
时间复杂度：O(n)
空间复杂度：O(1)
六、图解leetcode206：反转链表
1. 题目
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法一：迭代法
解题思路： 将单链表中的每个节点的后继指针指向它的前驱节点即可
确定边界条件： 当链表为 null 或链表中仅有一个节点时，不需要反转
代码实现：
var reverseList = function(head) {
if(!head || !head.next) return head
var prev = null, curr = head
while(curr) {
// 用于临时存储 curr 后继节点
var next = curr.next
// 反转 curr 的后继指针
curr.next = prev
// 变更prev、curr
// 待反转节点指向下一个节点
prev = curr
curr = next
}
head = prev
return head
};
-
时间复杂度：O(n)
-
空间复杂度：O(1)
七 字节&leetcode1：两数之和[2]
var twoSum = function(nums, target) {
const obj = {}
// 记录下标
nums.forEach((item,index)=>{
obj[item] =index
})
for(let i =0;i<nums.length;i++){
let item = nums[i]
const rest = target-item
// 需要判断是不是为当前元素和空
if( obj[rest]>=0 && obj[rest]!== i){
return [i,obj[target - item]]
}
}
};
八 leetcode88：合并两个有序数组[1]
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解决
var merge = function(nums1, m, nums2, n) {
nums1.splice(m,n,...nums2)
return nums1.sort((a,b)=> a-b)
};
九 腾讯：数组扁平化、去重、排序[3]
写个扁平化吧其他的都是老套了
function flat(arr){
if(!Array.isArray(arr)){
return arr
}
return arr.reduce((total,next)=>{
return total.concat(flat(next))
},[])
}
