Day1——栈与队列（简单）

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1)

示例

TIP

输入

1
2
3

>["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

>[[],[],[5],[2],[],[]]

输出: [null,-1,null,null,5,2]

题解

解题关键：了解栈和队列的区别，两个栈模拟，一个栈用于进，一个栈用于出

栈和队列的区别：

栈：先进后出(只能一端插入和删除)

队列：先进先出(只能一端插入，另一端删除)

var CQueue = function(quene = []) {
   this.instack = []
   this.outstack = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.instack.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    // 删除的时候先用另一个栈来模拟队列的另一端
    if(!this.outstack.length){
        if(!this.instack.length){ // 没有元素
            return -1
        }
        else{
            while(this.instack.length){
                this.outstack.push(this.instack.pop())
            }
        }
    }
    return this.outstack.pop()
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

剑指 Offer 30. 包含min函数的栈

示例

TIP

输入
1
2
3
>["MinStack","push","push","push","getMin","pop","top","getMin"]

>[],[-2],[0],[-3],[],[],[],[]]
输出: [null,null,null,null,-3,null,0,-2]

解释: MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); –> 返回 -3.

minStack.pop(); minStack.top(); –> 返回 0.

minStack.getMin(); –> 返回 -2.

题解

解题关键：创建辅助栈minStack, 与栈空间保持同步操作, 空间换时间

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.inStack = []
    this.minStack = [Infinity]
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.inStack.push(x)
    this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], x))
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.inStack.pop()
    this.minStack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.inStack[this.inStack.length-1]
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return this.minStack[this.minStack.length - 1]
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

Day2——链表（简单）

剑指 Offer 06. 从尾到头打印链表

示例

TIP

输入
1
>head = [1,3,2]
输出: [2,3,1]

题解

方法：定义一个数组，一边遍历一边往数组前面添加

var reversePrint = function(head) {
    let number = [];
    let node = head
    while(node){
        number.unshift(node.val)
        node = node.next
    }
    return number
};

剑指 Offer 24. 反转链表

示例

TIP

输入
1
>1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题解

方法：定义两个指针，一前一后，一边遍历一边翻转
注意点：注意后指针指向前指针时需要一个暂存指针指向下一次循环的指针

var reverseList = function(head) {
    if(!head) return head
    let prev = null
    let cur = head
    while(cur){
        let temp = cur.next
        cur.next = prev
        prev = cur 
        cur = temp
    }
    return prev
};

剑指 Offer 35. 复杂链表的复制

示例

TIP

输入
1
>head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

题解

陷阱：复制的时候未必所有的节点都生成了新的，要避免指到旧的

方法：

hash表，第一次遍历存好最新的，遍历hash表设置random
遍历旧链表，复制一份到每个节点的后面(不赋值random)，新节点的next指向原来旧节点的下一个节点，这样可以减少空间(空间复杂度O(1))

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
// 方法一: hash表
var copyRandomList = function(head) {
    if(!head) return null
    let map = new Map()
    let node = head;
    while(node){
        map.set(node, new Node(node.val))
        node = node.next
    }
    node = head
    while(node){
        map.get(node).next = node.next ? map.get(node.next) : null
        map.get(node).random = node.random ? map.get(node.random) : null
        node = node.next
    }
    return map.get(head)
}

// 方法二：后继节点
var copyRandomList = function(head){
    if(!head) return null
    let node = head;
    while(node){
        let nodeNew = new Node(node.val, node.next)
        node.next = nodeNew
        node = nodeNew.next
    }
    node = head;
    while(node){
        let nodeNew = node.next;
        nodeNew.random = node.random ? node.random.next ： null；
    }
    node = head
    const returnNode = node.next
    while(node){
        nodeNew.next = nodeNew.next ？ nodeNew.next.next : null
        node = node.next
    }
    return returnNode;
}

Day3——字符串（简单）

剑指 Offer 05. 替换空格

示例

TIP

输入
1
>s = "We are happy."
输出:”We%20are%20happy.”

题解

直接调用现成方法即可

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.replaceAll(' ', '%20')
};

剑指 Offer 58 - II. 左旋转字符串

示例

TIP

输入
1
>s = "abcdefg", k = 2
输出: “cdefgab”

题解

方法一：运用取余的特性去解 (遍历到的第i项 + 第n位开始翻转) / 字符串长度 就是对应位置

方法二：直接切割成俩数组, 倒转拼接

// 方法一：
var reverseLeftWords = function(s, n) {
    return Array.from(s).map((_v,i)=>s[((i+n))%s.length]).join('')
};

// 方法二：
var reverseLeftWords = function(s, n) {
    const left = s.slice(0, n)
    const right = s.slice(n, s.length)
    return right + left
};

Day4——查找算法（简单）

Day4实在太简单了，稍微挑一个有技巧一点的

剑指 Offer 53 - II. 0～n-1中缺失的数字

示例

TIP

输入
1
>[0,1,3]
输出:2

题解

二分查找法

左指针指向第一个，右指针指向最后一个，定义一个指针指向中间
如果number[middle] === middle, 那么右边缺, 否则左边缺
当跳出循环的时候, 左指针指向右区间第一个元素，右指针指向左区间最后一个元素, 即返回左指针

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let i = 0;
    let j = nums.length - 1
    while(i <= j){
        let middle = Math.floor(i + (j - i) / 2)
        if(number[middle] === middle){
            i = middle + 1
        }
        else{
            j = middle - 1
        }
    }
    return i
};

Day5——查找算法（中等）

剑指 Offer 04. 二维数组中的查找

示例

TIP

输入

>二维数组
>[
 [1,   4,  7, 11, 15],
 [2,   5,  8, 12, 19],
 [3,   6,  9, 16, 22],
 [10, 13, 14, 17, 24],
 [18, 21, 23, 26, 30]
>]
>target 5

输出: true

题解

技巧：从右上角开始找，如果target小，找左边一列，target大，找下一行

var findNumberIn2DArray = function(matrix, target) {
    if(!matrix || !matrix.length || !matrix[0].length) {
        return false
    }
    var line = 0;
    var col = matrix[0].length - 1
    while(line <= matrix.length && col >= 0){
        if(target < matrix[line][col]){
            col--
        }
        else if(target > matrix[line][col]){
            line++
        }
        else{
            return true
        }
    }
    return false
};

剑指 Offer 50. 第一个只出现一次的字符

示例

TIP

输入
1
>s = "abaccdeff"
输出:’b’

题解

关键: 两次遍历，第一次用hash表存字符出现的次数，第二次如果次数为1直接返回

var firstUniqChar = function(s) {
    var map = new Map();
    for(var i = 0;i < s.length;i++){
        const time = map.get(s[i]) || 0
        map.set(s[i], time + 1)
    }

    for(var i = 0;i < s.length;i++){
        if(map.get(s[i]) === 1) return s[i]
    }
    return " "
}

Day6——搜索与回溯算法（简单）

三个题目长得一样的，挑一个讲

剑指 Offer 32 - III. 从上到下打印二叉树 III

之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印

示例

TIP

输入
1
>[3,9,20,null,null,15,7]
输出:[
[3],
[20,9],
[15,7]
]

题解

关键点：

广度优先(需要一个队列)
一正一反，push结果的时候根据是否需要倒序输出决定用push还是unshift

var levelOrder = function(root) {
    if(!root) return [];
    var quene = [[root]];
    var res = [];
    var isLeft = 1; // 奇数表示正序，偶数表示倒序
    while(quene.length){
        const level = quene.shift();
        const levelRes = [];
        const levelQuene = [];
        level.forEach(item => {
            if(item.left) {
                levelQuene.push(item.left)
            }
            if(item.right) {
                levelQuene.push(item.right)
            }
            if(isLeft % 2){
                levelRes.push(item.val)
            }else{
                levelRes.unshift(item.val)
            }
        })
        isLeft++
        if(levelQuene.length){
            quene.push(levelQuene)
        }
        if(levelRes.length){
            res.push(levelRes)
        }
    }
    return res
}

Day7——搜索与回溯算法二（简单）

剑指 Offer 26. 树的子结构(判断子树)

示例

例如:
给定的树 A:

 3

/ \

4 5

/ \

1 2

给定的树 B：

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

TIP

输入
1
>A = [1,2,3], B = [3,1]
输出:false

题解

解题关键：

深度遍历父树，遇到val相同的，就有可能是子树，依次比较父树和子树的每个节点
递归判断相等时，如果B没有了，说明已经匹配完成了，为true。如果A没有了，说明越过A树，为false，如果val值不一样，那么匹配失败，false。

var isSubStructure = function(A, B) {
    if(!A || !B) return false;
    return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
}

function isSameTree(A, B){
    if(!B){
        return true
    }
    if(!A){
        return false
    }
    if(A.val !== B.val){
        return false
    }
    return isSameTree(A.left, B) && isSameTree(A.right, B)
}

剑指 Offer 27. 二叉树的镜像

示例

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

TIP

输入
1
>root = [4,2,7,1,3,6,9]
输出: [4,7,2,9,6,3,1]

题解

解题思路：

交换left和right，递归交换

var mirrorTree = function(root) {
    if(!root) return null;
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    if(root.left){
        mirrorTree(root.left)
    }
    if(root.right){
        mirrorTree(root.right)
    }
    return root;
}

剑指 Offer 28. 对称的二叉树

示例

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/ \

2 2

/ \ / \

3 4 4 3

TIP

输入
1
>root = [1,2,2,3,4,4,3]
输出: true

题解

解题思路：

用两个指针，一根往左走，另一根就往右走。一根往右走，另一根就往左走。

var isSymmetric = function(root) {
    return isMirror(root, root)
}

function isMirror(p, q){
    if(!p && !q){
        return true
    }
    if(!p || !q){
        return false
    }
    return p.val === q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left)
}

Day8——动态规划（简单）

剑指 Offer 10- I. 斐波那契数列

示例

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

TIP

输入
1
>n = 2
输出:1

题解

不要用递归（暴掉的概率太大了）

提供两种解法

滚动数组解法

var fib = function(n) {
    const mod = 1000000007; // 防止过大
    if(n < 2){
        return n
    }
    let p = 0, q = 1, r = 1;
    for(var i = 2;i < n;i++){
        p = q;
        q = r;
        r =(p + q) % mod;
    }
    return r;
}

矩阵快速幂

2.1 快速幂 O(logn) 的复杂度
- a^n = a^(2^log2(n)), 因此计算O(logn)的复杂度次数即可得到高次幂的结果
- 任意正整数的偶数n次幂，等于其(n/2)^2，基数则是n >> 2后的(n/2)^2 * (该数)
  
  2.2 矩阵的目的是得到递推关系
  
  得出我们的目的是求出矩阵的n次幂再乘以初始值

// 矩阵乘法
var mutiply = (a, b) => {
    var c = new Array(2).fill(0).map(() => new Array(2).fill(0))
    for(var i = 0;i < 2; i++){
        for(var j = 0;j < 2;j++){
            c[i][j] = (BigInt(a[i][0]) * BigInt(b[0][j])) + (BigInt(a[i][1]) * BigInt(b[1][j]))
        }
    }
    return c;
}
// 快速幂算法，固定格式可以说
var pow = (a, n) => {
    var ret = [[1, 0], [0, 1]]
    while(n > 0){
        if((n & 1) === 1){ // 奇数
            ret = mutiply(ret, a)
        }
        n >> 1
        a = mutiply(a, a)
    }
}
var fib = function(n) {
    if (n < 2) {
        return n;
    }
    const mod = 1000000007; // 防止过大
    const m = [[1, 1], [1, 0]]
    const res = pow(m, n - 1) // 需要得出来的是[F(n), F(n - 1)]，因此F(n) = res[0][0] * F(1) + res[0][0] * F(0)
    return BigInt(res[0][0]) % BigInt(mod)
}

剑指 Offer 10- II. 青蛙跳台阶问题

示例

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

TIP

输入
1
>n = 2
输出:2

题解

和上面的斐波那契数列一毛一样，唯一的区别就是F(0)和F(1)的初始值不一样

// ...省略矩阵计算方法和快速幂算法
var numWays = function(n) {
    if(n < 2) return 1;
    const m = [[1, 1], [1, 0]];
    const res = pow(m, n - 1); // 需要得出来的是[F(n), F(n - 1)]，因此F(n) = res[0][0] * F(1) + res[0][0] * F(0)
    const ways = (res[0][0] * 1 + res[0][0] * 1) % mod;
    return ways;
}

剑指 Offer 63. 股票的最大利润

示例

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

TIP

输入
1
>[7,1,5,3,6,4]
输出: 5

题解

方法：

遍历每一天，每一天都在幻想买的是最低点，卖的是最高点即可

var maxProfit = function(prices) {
    if(!prices.length) return 0;
    var minPrice = price[0];
    var maxEarn = 0;
    for(var i = 0; i < prices.length;i++){
        if(prices[i] < minPrice){
            minPrice = prices[i]
        }
        if(prices[i] - minPrice > maxEarn){
            maxEarn = prices[i] - minPrice
        }
    }
    return maxEarn > 0 ? maxEarn : 0
}

Day9——动态规划（中等）

剑指 Offer 42. 连续子数组的最大和

示例

TIP

输入
1
>nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

题解

提供两种解法，均比较重要

动态规划, 滚动数组
- Max{F(n - 1) + nums[i], nums[i]}

var maxSubArray = function(nums) {
    if(!nums.length) return 0;
    var q = nums[0], max = nums[0]
    for(var i = 1; i < nums.length;i++){
        // 看q是取之前的和还是说取本次这个数
        q = Math.max(q + nums[i], nums[i]);
        // 重新设置max
        max = Math.max(q, nums[i])
    }
    return max;
}

分治算法

分治算法就是将一个复杂的问题分成几个相似或者相同的小问题，再将小问题合并。

本题思路：

分成多段，分别找出其中连续子数组中的最大和

如果只有1个元素，那么最大和就是那个元素
如果有多个元素，那么递归拆分
合并求最大和时，加入分治了两个数组a、b, 针对两个数组合并
- 分别拿两个数组每个元素的和得出一个iSum(跨数组)
- 分别拿两个数组的头作为起点算个最大和lSum = Max{a.lSum, b.lSum + a.iSum}
- 分别拿两个数组的尾巴作为终点算个最大和rSum = Max{b.rSum, a.rSum + b.iSum} 比较的都是不跨数组和跨数组的情况
- 两个数组的最大和为 mSum = Max{a.mSum, b.mSum, a.rSum + b.lSum}

function Status(l, r, m, i){
    this.lSum = l
    this.rSum = r
    this.mSum = m
    this.iSum = i
}
function mergeArr(aStatus, bStatus){
    const l = Math.max(aStatus.lSum, bStatus.lSum + aStatus.iSum)
    const r = Math.max(aStatus.rSum + bStatus.iSum, bStatus.rSum)
    const m = Math.max(aStatus.mSum, bStatus.mSum, aStatus.rSum + bStatus.lSum)
    const i = aStatus.iSum + bStatus.iSum
    return new Status(l, r, m, i)
}

function getInfo(arr, start, end){
    if(start === end){
        return new Status(arr[start], arr[start], arr[start], arr[start])
    }
    const middle = (start + end) >> 1;
    const lStatus = getInfo(arr, start, middle)
    const rStatus = getInfo(arr, middle + 1, end)
    return mergeArr(lStatus, rStatus)
}

var maxSubArray = function(nums) {
    return getInfo(nums, 0, nums.length - 1).mSum
}

剑指 Offer 47. 礼物的最大价值

示例

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

TIP

输入
1
2
3
4
5
>[
 [1,3,1],
 [1,5,1],
 [4,2,1]
>]
输出: 12

解释：路径 1→3→5→2→1 可以拿到最多价值的礼物

题解

动态规划题，设置dp数组，这个数组存着走到那一步能获取到的最大价值

var maxValue = function(grid) {
    var line = grid.length;
    var column = grid[0].length;
    const dp = new Array(line).fill(0).map(() => new Array(column).fill(0))
    dp[0][0] = grid[0][0] // 这个初始值必须设置
    for(var i = 0;i < line;i++){ // 初始化每一列
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    for(var j = 0; j < column;j++){
        dp[0][j] = dp[0][j - 1] + grid[0][j - 1]
    }
    for(var i = 1; i < line;i++){
        for(var j = 1;j < column;j++){
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    return dp[line - 1][column - 1]
}

Day10——动态规划二（中等）

剑指 Offer 46. 把数字翻译成字符串

示例

TIP

输入
1
>12258
输出:5

解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

题解

动态规划，滚动数组，条件判断(类似青蛙跳台阶)

F(n) = F(n - 1) (如果最后两个数无法构成一个字母)
F(n) = F(n - 1) + F(n - 2) (如果最后两个数可以构成一个字母)

var translateNum = function(num) {
    let stringNum = String(num)
    let p = 0, q = 1, ways = 1;
    for(var i = 0; i < stringNum.length;i++){
        p = q;
        q = ways;
        ways = 0;
        ways += q;
        let lastSecondNum = stringNum[i - 1] + stringNum[i]
        if(Number(lastSecondNum) >= 10 || (Number(lastSecondNum) <= 25){
            ways += p
        }
    }
    return ways;
}

剑指 Offer 48. 最长不含重复字符的子字符串

示例

TIP

输入
1
>"abcabcbb"
输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

题解

滑动窗口(双指针) + 哈希表

var lengthOfLongestSubstring = function(s) {
    if(!s.length) return 0;
    let left = -1, res = 0, hashMap = new Map();
    for(var i = 0; i < s.length; i++){
        if(hashMap.has(s[i])){ // 如果存在
            const index = hashMap.get(s[i])
            left = Math.max(index, left)
        }
        hashMap.set(s[i], i)
        res = Math.max(res, i - left)
    }
    return res;
}

Day11——双指针（简单）

剑指 Offer 18. 删除链表的节点

示例

TIP

输入
1
>head = [4,5,1,9], val = 5
输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

题解

建一个空的头结点，定义两个指针，一个先走一步，一个后走

注意点：head也要指向空节点，因为头结点也有可能被删除

var deleteNode = function(head, val) {
    const empty = new ListNode()
    empty.next = head;
    let prev = empty;
    let node = empty;
    head = empty
    while(node){
        if(node.val === val){
            prev.next = node.next
        }
        prev = node;
        node = node.next
    }
    return head.next
}

剑指 Offer 22. 链表中倒数第k个节点

示例

TIP

输入
1
>给定一个链表: 1->2->3->4->5, 和 k = 2.
输出: 返回链表 4->5.

题解

解题思路：双指针，前一个指针先走k步，第二根指针开始走，第一个指针走完的时候第二个指针走到第k个元素

var getKthFromEnd = function(head, k) {
    var front = head;
    var back = head;
    var i = 1;
    while(front){
        if(i > k){
            back = back.next
        }
        front = front.next
        i++
    }
    return back;
}

Day12——双指针二（简单）

剑指 Offer 25. 合并两个排序的链表

示例

TIP

输入
1
>1->2->4, 1->3->4
输出:1->1->2->3->4->4

题解

一根新链表加两个指针

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let node1 = l1;
    let node2 = l2;
    const newHead = new ListNode();
    let newNode = newHead;
    while(node1 && node2){
        if(node2.val <= node1.val){
            newNode.next = node2
            node2 = node2.next;
        }
        else{
            newNode.next = node1;
            node1 = node1.next
        }
        newNode = newNode.next
    }
    newNode.next = node1 ? node1 : node2
    return newHead.next
};

剑指 Offer 52. 两个链表的第一个公共节点

示例

TIP

输入

输出:Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

题解

双指针，一根走完了指向另一根的头部, 相交说明有公共节点，都为null说明没有。类似于找环状链表

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }
    var nodeA = headA;
    var nodeB = headB;
    while(nodeA !== nodeB){
        nodeA = nodeA ? nodeA.next : headB;
        nodeB = nodeB ? nodeB.next : headA;
    }
    return nodeA
};

Day13——双指针三（简单）

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

示例

TIP

输入
1
>nums = [1,2,3,4]
输出:[1,3,2,4]

题解

双指针，一根指向头，一根指向尾部，同时往中间移动

头部指针移动到第一个偶数位置停止

尾部指针移动到第一个奇数位置停止

var exchange = function(nums) {
    if(!nums.length) return [];
    let i = 0, j = nums.length - 1;
    while(i < j){
        while(i < j && (nums[i] & 1) === 1) i++;
        while(i < j && (nums[i] & 1) === 0) j--;
        let temp = nums[i];
        nums[i] = nums[j]
        nums[j] = temp
    }
    return nums;
}

剑指 Offer 57. 和为s的两个数字

示例

TIP

输入
1
>nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

题解

头尾指针和小，头指针往后，和大，尾指针往前

var twoSum = function(nums, target) {
    let i = 0; j = nums.length - 1
    while(i < j){
        if(nums[i] + nums[j] === target) {
            return [nums[i], nums[j]]
        }
        if(nums[i] + nums[j] > target){
            j--
        }
        if(nums[i] + nums[j] < target){
            i++
        }
    }
    return []
};

剑指 Offer 58 - I. 翻转单词顺序

示例

TIP

输入
1
>"  hello world!  "
输出:”world! hello”

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

题解

var reverseWords = function(s) {
    const wordArray = s.trim().split(' ').filter(item => item !== '')
    let i = 0, j = wordArray.length;
    while(i < j){
        let temp = wordArray[i];
        wordArray[i] = wordArray[j];
        wordArray[j] = temp
        i++;
        j--;
    }
    return wordArray.join(' ').trim()
};

Day14——搜索与回溯算法（中等）

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例

TIP

输入

1	>board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出:true

题解

回溯思想: 类似于在一个节点的枚举过程，不满足条件就回到那个节点

本题思路：

从盘中任意一个节点开始走，因此是一个二重循环，需要考虑每一个节点，有一个节点满足则返回true
对每一个节点进行枚举，不满足条件则回溯，满足条件的标记需要标记已经访问过了，避免再次访问

var exist = function(board, word) {
    const line = board.length;
    const column = board[0].length;
    let flag = false;
    const visited = new Array(line).fill(false).map(() => new Array(column).fill(false))  

    const checkWords = (i, j, _word, k) => {
        // 走的方向
        const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        if(board[i][j] !== word.charAt(k)){
            return false
        }
        if(k === _word.length - 1){
            return true
        }
        visited[i][j] = true;
        let result = false;
        for(var [dx, dy] of directions){
            const newX = i + dx;
            const newY = j + dy;
            if(newX >= 0 && newY >= 0 && newX <= line && newY <= column){
                if(!visited[newX][newY]){
                    const res = checkWords(newX, newY, _word, k + 1)
                    if(res){
                        result = true;
                        break;
                    }
                }
            }
        }
        return result;
    }

    for(var i = 0; i < line;i++){
        for(var j = 0;j < column;j++){
            flag = checkWords(i, j, word, 0)
            if(flag){
                return true
            }
        }
    }
}

剑指 Offer 13. 机器人的运动范围

示例

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

TIP

输入
1
>m = 2, n = 3, k = 1
输出:3

题解

是一个深度优先遍历或者广度优先遍历的题

深度优先遍历：相当于暴力的算法，一个方向走到底，然后回溯到节点再走

广度优先遍历：

var movingCount = function(m, n, k) {
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false)) // 标记是否访问
    const calc = (val) => {
        let sum = 0;
        while(x !== 0){
            sum += x % 10;
            x = Math.floor(x / 10);
        }
        return sum
    }

    const walk = (visit, m, n, i, j, k) =>{
        const sum = calc(i) + calc(j);

        if(sum > k || visit[i][j] || i > m || j > n) return 0;

        visit[i][j] = true;

        return 1 + walk(visit, m, n, i + 1, j, k) + walk(visit, m, n, i, j + 1, k)
    }
    
    return walk(visited, m, n, 0, 0, k)
}