剑指offer-JavaScript刷题笔记

二叉树

二叉树的深度

牛客

【提示】

• 思路一：后序遍历位置，计算每个节点的高度，返回每个节点的高度。
• 思路二：前序遍历位置，计算每个节点的深度，记录每个节点的深度，最后比较得到最大深度。

深度和高度的区别：二叉树节点的深度是：从根节点到该节点的最长简单路径边的条数；二叉树的高度是：从该节点到叶子结点的最长简单路径边的条数。

---

按之字形顺序打印二叉树

牛客

leetcode

【提示】层序遍历，设置一个标志变量 order，偶数层改变结果的顺序。

---

二叉搜索树的第k个节点

牛客

【提示】BST 中序遍历是有序的（升序），在中序遍历位置进行统计。

---

重建二叉树

牛客

leetcode

【提示】前序遍历和中序遍历可以确定左子树和右子树序列的索引范围，然后在前序遍历位置分别计算得到每次递归时的序列的索引范围，分别递归创建左子树和右子树。

---

==树的子结构==

牛客

leetcode

【提示】将树 A 的每个节点当做根节点，与树 B 进行比较，因此主函数也需要递归。isSubTree(pRoot1, pRoot2) 从 pRoot1 开始与 pRoot2 逐节点比较。HasSubTree(pRoot1, pRoot2) 将 pRoot1 的每个节点当做根节点与 pRoot2 进行比较。

function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    // 题目限制：空树不是子树
    if (pRoot1 === null || pRoot2 === null) {
        return false;
    }
    
    // 首先从pRoot1和pRoot2的根节点开始比较，如果不等，那么分别看pRoot1的左节点和pRoot1的右节点
    return isSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}

// 最开始，pRoot1.val = pRoot2.val，从pRoot1的这个节点开始比较
function isSubTree(pRoot1, pRoot2) {
    // 说明pRoot2的每个节点都比较完了，都是相等的
    if (pRoot2 === null) {
        return true;
    } else if (pRoot1 === null) { // pRoot2还没比较完，但是pRoot1已经比较完了
        return false;
    } else if (pRoot1.val !== pRoot2.val) { // 正在比较的节点的值不相等
        return false;
    }
    
    // 分别比较左节点和右节点
    return isSubTree(pRoot1.left, pRoot2.left) && isSubTree(pRoot1.right, pRoot2.right);
}

---

二叉树的镜像

牛客

leetcode

【提示】交换当前节点的左右子节点，不要和 对称的二叉树 搞混了。

---

从上往下打印二叉树

牛客

leetcode

【提示】最基础的层序遍历。

---

二叉搜索树的后序遍历序列

牛客

leetcode

题解

【提示】1. 递归分治法；2. 辅助单调栈。

（1）递归分治法

从后序遍历区分出左子树序列的索引范围和右子树的索引范围，然后分别判断左子树和右子树是否满足 BST 的条件。

function VerifySquenceOfBST(sequence)
{
    // write code here
    // 分治法--左右子树都要满足条件
    let length = sequence.length;
    if (length === 0) {
        return false;
    }
    /*
    * sequence: 后序遍历序列
    * start: 序列索引的起点
    * end: 序列索引的终点
    */
    const traverse = (sequence, start, end) => {
      	// 只有一个节点或没有节点的情况
        if (start >= end) {
            return true;
        }
        
        let root = sequence[end]; // 根节点
        let leftEnd = end - 1; // 左子树在序列中的末端索引（此时是右子树的末端索引）
        while (leftEnd >= 0 && sequence[leftEnd] > root) { // 找到左子树的末端索引
            leftEnd--;
        }
        
        // 找左子树序列末端的索引时已经判断了右子树，所以这里只需要判断左子树就可以了。
        // 如果左子树中有节点的值大于了根节点，则不满足
        for (let i = start; i <= leftEnd; i++) {
            if (sequence[i] > root) {
                return false;
            }
        }
        
        let left = traverse(sequence, start, leftEnd);
        let right = traverse(sequence, leftEnd + 1, end - 1);
        return left && right;
    }
    
    return traverse(sequence, 0, length - 1);
}
module.exports = {
    VerifySquenceOfBST : VerifySquenceOfBST
};

时间复杂度：$O(n^2)$。每次调用 traverse 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N)。

空间复杂度：$O(n)$。最差情况下（即当树退化为链表），递归深度将达到 n。

（2）辅助单调栈

思路：将后序遍历序列逆序，即“根-右-左”。遍历逆序序列，

// TODO 搞懂单调辅助栈

---

二叉树中和为某一值的路径(一)

牛客

leetcode

【提示】深度优先 DFS。在每个节点处将 sum 减去 curNode.val。返回 true 的条件：

if (curNode.left === null && curNode.right === null && target === 0) {
  return true;
}

---

二叉树中和为某一值的路径(二)

牛客

【提示】DFS，在每个节点处 expectNumber 减去 curNode.val。路径符合条件时的判断：

if (curNode.left === null && curNode.right === null && number === 0) {
  result.push([...path]);
}

// 递归函数的参数
function dfs(curNode, result, path, number) {
  ...
  // 记录路径上的值
  path.push(curNode.val);
  number -= curNode.val;
  
  // 判断路径是否符合条件
  if (root.left === null && root.right === null && number === 0) {
    result.push([...path]);
  } else {
    // 深度优先搜索
    dfs(root.left, result, path, number);
    dfs(root.right, result, path, number); 
  }
  // 回溯
  path.pop();
}

---

二叉树中和为某一值的路径(三)

牛客

leetcode

题解

【提示】两种解法：深度优先搜索和前缀和。

（1）深度优先搜索

计算每个节点作为路径起点时的路径和，计算量大，耗时。

1. 递归函数的参数：节点 root，路径总和 target；
2. 返回值：路径总和满足 target 的路径数量；
3. 退出条件：递归到空节点，返回 0；
4. 单层逻辑：当前节点的值是否等于 target（target 在每次递归时减去当前路径起点的 val）；

注意

主函数中也有递归的逻辑，遍历每个节点，以每个节点作为路径起点计算满足路径和为 target 的路径数量。

/* 主函数 */
var pathSum = function(root, targetSum) {
    if (root === null) {
        return 0;
    }

    let res = rootSum(root, targetSum); // 以 root 为路径起点
    res +=  pathSum(root.left, targetSum); // root 的左子树每个节点作为路径起点
    res += pathSum(root.right, targetSum); // root 的右子树每个节点作为路径起点

    return res;
};

/* 以某个节点作为路径起点时，计算满足路径总和的路径数量 */
function rootSum(root, targetSum) {
    if (root === null) {
        return 0;
    }
		
  	// 前序遍历位置
    let res = 0;

    if (root.val === targetSum) {
        res++;
    }

    res += rootSum(root.left, targetSum - root.val);
    res += rootSum(root.right, targetSum - root.val);

    return res;
}

（2）前缀和

也是递归，计算每个并存储每个节点的前缀和。

1. 递归参数：节点 node，前缀和 prefix（hash表），当前节点的前缀和 curSum，路径总和 targetSum。
2. 返回值：满足 targetSum 的路径数量；
3. 退出条件：递归到空节点，返回 0；
4. 单层逻辑：计算当前节点的前缀和，从前缀和中获取前缀和为 (curSum - targetSum) 的值，这个值就是满足条件的路径数量。将当前节点的前缀和存储起来，分别递归当前节点的左右子树，回溯时将相应的前缀和 -1。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
    if (root === null) {
        return 0;
    }

    const prefix = new Map();
    prefix.set(0, 1); // 初始化前缀和

    let res = dfs(root, prefix, 0, targetSum);

    return res;
};

function dfs(node, prefix, curSum, targetSum) {
    if (node === null) {
        return 0;
    }

    let res = 0;

    curSum += node.val;
    res = prefix.get(curSum - targetSum) || 0;
    prefix.set(curSum, (prefix.get(curSum) || 0) + 1);

    res += dfs(node.left, prefix, curSum, targetSum);
    res += dfs(node.right, prefix, curSum, targetSum);
		
  	// 回溯
    prefix.set(curSum, (prefix.get(curSum) || 0) - 1);
    
    return res;
}

---

在二叉树中找到两个节点的最近公共祖先

牛客

leetcode

题解

【提示】后序遍历位置，分别在左右子树上搜索，需要搜索整棵树。

---

二叉搜索树的最近公共祖先

牛客

leetcode

题解

【提示】利用 BST 遍历顺序的特点，在前序遍历位置，只搜索某一条边，在某一条边找到 cur.val 在 区间 [p.val, q.val]（或者 [q.val, p.val]），则返回 cur，不需要遍历整棵树。

---

二叉搜索树与双向链表

牛客

leetcode

【提示】BST 的中序遍历是有序的，算法逻辑都在中序遍历位置。

// 定义两个全局变量
let pre = null; // 指向中序遍历的前一个节点
let head = null; // 指向双向链表的头节点，也就是中序遍历的第一个节点

// 递归原地转换
function BST2BDList(curNode) {
  if (curNode === null) {
    return ;
  }
  
  BST2BDList(curNode.left);
  
  ...(更新pre，处理 pre 的后继和 cur 的前驱)
  
  BST2BDList(curNode.right);
}

---

判断是不是平衡二叉树

牛客

leetcode

平衡二叉树的定义（Balanced Binary Tree）：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

【提示】后序遍历位置。

// 后序遍历，-1表示不是平衡二叉树
// 只要左子树或右子树的高度为-1就返回，此时不是平衡二叉树
const getHeight = (node) => {
  if (node === null) {
    return 0;
  }
  let leftHeight = getHeight(node.left);

  if (leftHeight === -1) {
    return -1;
  }
  let rightHeight = getHeight(node.right);
  if (rightHeight === -1) {
    return -1;
  }
  // 后序遍历位置，对每个节点的操作
  let height = 0;
  // 左右子树的高度须满足条件，不满足直接 return 。满足后再计算当前节点的高度：左子树高度和右子树高度重最大的一个 + 1
  return height;
}

---

二叉树的下一个节点

牛客

leetcode

【提示】解法 1：先找到根节点，然后中序遍历整棵树，最后匹配目标节点；解法 2：分析中序遍历的特点，分组判断。

解法 2：

1. 节点的右子树不为空，找到该节点右子树最左边的节点并返回；
2. 节点右子树为空，且该节点是其父节点的左节点，直接返回其父节点；
3. 节点右子树为空，该节点是其父节点的右节点，则该节点一直沿着next指针往上走，直到指针指向的节点的左子节点是指针上一次指向的节点，返回当前指针的 next；

---

对称的二叉树

牛客

leetcode

【提示】分别比较当前节点的外侧和内侧节点是否一致。

// 递归参数：当前节点的左节点和当前节点的右节点
const compare = (leftNode, rightNode) => {
  // 递归退出条件
  if (leftNode === null && rightNode !== null) {
    return false;
  } else if (leftNode !== null && rightNode === null) {
    return false;
  } else if (leftNode === null && rightNode === null) {
    return true;  
  } else if (leftNode.val !== rightNode.val) {
    return false; 
  }

  let outside = compare(leftNode.left, rightNode.right); // 比较外侧
  let inside = compare(leftNode.right, rightNode.left); // 比较内侧

  return outside && inside;
}

注意

不要跟 二叉树的镜像

---

把二叉树打印成多行

牛客

leetcode

【提示】层序遍历，但注意打印格式，每一层的节点值放在一个数组中，最终的结果是二维数组。

---

JZ37 序列化二叉树

牛客

leetcode

【提示】

• 层序遍历（前中后序都可以，这三种解法还没看懂）

• 遍历用数组存放结果，反序列化时用split(‘,’)得到字符数组

  for (let i = 1; i < nodes.length; ) {
          let parentNode = queue.shift();
          // i相当于指针，每次都指向当前节点的左子节点或右子节点
    			// i++没有放在for循环中，for循环体内有两次i++
    			// 每次将非空的节点入队，循环一个节点队列
          let left = nodes[i++];
          if (left !== '#') {
              parentNode.left = new TreeNode(parseInt(left));
              queue.push(parentNode.left);
          } else {
              parentNode.left = null;
          }
          
          let right = nodes[i++];
          if (right !== '#') {
              parentNode.right = new TreeNode(parseInt(right));
              queue.push(parentNode.right);
          } else {
              parentNode.right = null;
          }
      }

---

JZ36 二叉搜索树与双向链表

牛客

leetcode

【提示】

• 中序遍历位置使用pre和cur指针记录前一个访问的节点和当前访问的节点；

  BST2BDList(cur.left);
      
      if (pre !== null) {
        pre.right = cur; // 如果pre不为空，pre右指针指向下一个要访问的节点
      } else {
        head = cur; // 如果pre为空，head指向当前节点
      }
      cur.left = pre; // 当前节点的左指针指向pre
      
      pre = cur; // 更新pre
      
  BST2BDList(cur.right);

• 画图更好理解

---

链表

JZ25 合并两个排序的链表

牛客

leetcode

题解

【提示】

• 双指针分别指向两个链表

• 创建一个dum伪头节点指向合并后的链表；

  let l1 = pHead1; // 指向链表1的指针 
  let l2 = pHead2; // 指向链表2的指针 
  let dum = new ListNode(0); // 合并后链表的伪头节点 
  let cur = dum; // 指向合并后链表的当前节点

• 当l1或l2为空时退出循环

• 两个链表的长度都为n，所以退出循环后最多剩一个节点，把这个节点添加到cur后面

---

JZ52 两个链表的第一个公共结点

牛客

leetcode

【提示】

1. 双指针指向两个链表；

   let curA = pHead1;
   let curB = pHead2;

2. 定义一个计算链表长度的函数；

3. 始终让链表A是最长的链表；

4. 对齐两个链表;

   /* 从尾部对齐两个链表 */
     let gap = lenA - lenB;
     while (gap--) {
       curA = curA.next;
     }

5. curA和curB同时移动，找到公共节点就退出循环

---

JZ23 链表中环的入口结点

牛客

leetcode

题解

【提示】双指针，两次相遇，第二次相遇即环入口。

• fast和slow指针指向头节点，fast每次移动两步，slow指针移动一步；

  • fast指针走到链表尾部==》没有环，返回null；
  • fast指针和slow指针第一次在环中相遇==》此时将fast指针重新指向头节点；

• fast指针和slow指针同时移动一步，第二次将在环入口相遇，返回fast指针；

  let fast = pHead;
  let slow = pHead;
  
  while (true) {
    // fast走到了链表的末端，说明无环
    if (fast === null || fast.next === null) {
      return null;
    }
    fast = fast.next.next; // fast指针每次向前走两步
    slow = slow.next; // slow指针每次向前走一步
    if (fast === slow) { // fast和slow第一次在环中相遇
      break;
    }
  }
  fast = pHead; // fast指针指向头节点
  // fast和slow同时每次移动一步，第二次将在环入口相遇
  while (fast !== slow) {
    fast = fast.next;
    slow = slow.next;
  }
  return fast;

  ---

JZ18 删除链表的节点

牛客

【提示】虚拟头节点+双指针

// 虚拟头节点+双指针
let dummy = new ListNode();
dummy.next = head;
let pre = dummy;
let cur = head;

循环找到要删除的节点，然后pre.next=cur.next，返回dummy.next。

---

JZ76 删除链表中重复的结点

牛客

leetcode

题解

【提示】虚拟头节点指向pHead，cur指针指向虚拟头节点，需要循环删除重复的节点。

if (cur.next.val === cur.next.next.val) {
  let temp = cur.next.val;
  // 循环删除重复的连续节点
  while (cur.next !== null && cur.next.val === temp) {
    cur.next = cur.next.next; // 关键的地方
  }
} else {
  cur = cur.next; // 移动cur指针指向下一个节点
}

---

JZ35 复杂链表的复制

牛客

leetcode

题解

【提示】两种解法：Hash表（更直观，更好理解）和拼接+拆分（降低空间复杂度）

（1）遍历链表，Hash表建立原链表节点与新链表节点的映射；

（2）遍历链表，建立新链表节点next指针指向和random指针指向；

function Clone(pHead)
{
  // write code here
  if (!pHead) {
    return null;
  }
  
  const dic = new Map(); // hash表
  let cur = pHead; // 之前原链表的指针
  
  // 1. 构建原链表与新链表的节点映射关系
  while (cur) {
    dic.set(cur, new RandomListNode(cur.label));
    cur = cur.next;
  }
  
  // 2. cur重新指向原链表的头节点
  cur = pHead;
  
  // 3. 构建新链表的next指针指向和random指针指向
  while (cur) {
    let node = dic.get(cur);
    node.next = dic.get(cur.next);
    node.random = dic.get(cur.random);
    cur = cur.next;
  }
  
  return dic.get(pHead);
    
}

---

栈和队列

JZ9 用两个栈实现队列

牛客

leetcode

【提示】

let stackA = []; // 存储数据
let stackB = []; // 删除时中转数据（暂存）

---

JZ31 栈的压入、弹出序列

牛客

leetcode

题解

【提示】循环入栈序列，用一个辅助栈 stack 模拟入栈情况，stack 入栈栈顶元素与出栈序列的当前指针指向的元素比较，如果相同，则stack 栈顶元素出栈，继续比较；全部比较完后，stack 为空说明出栈序列顺序正确，否则就是错误的。

function IsPopOrder(pushV, popV)
{
  const stack = []; // 辅助栈，模拟压栈顺序
  let cur = 0; // 指向出栈序列的指针
  // write code here
  for (const num of pushV) {
    stack.push(num); // num入栈
    // stack的栈顶元素等于cur指向的出栈序列的元素
    while (stack.length && stack[stack.length - 1] === popV[cur]) {
      stack.pop(); // stack栈顶元素出栈
      cur++; // 指针向后移动 
    }
  }
  return stack.length === 0 ? true : false; // stack为空说明出栈序列正确
}

---

JZ30 包含min函数的栈

牛客

leetcode

题解

【提示】使用一个单调栈-辅助栈 stackMin，辅助栈栈顶始终保存压入 stack 中的最小元素。

• 注意 push 时，如果入栈元素小于和等于 stackMin 栈顶元素都要入 stackMin，不然可能在执行 pop 操作后，stackMin 为空了。

function push(node)
{
  // write code here
  // 元素入栈时，1.stackMin为空，元素入栈；2.元素小于等于stackMin栈顶元素，入栈，否则不入栈
  stack.push(node); 
  if (stackMin.length === 0 || node <= stackMin[stackMin.length - 1]) {
    stackMin.push(node);
  }
}

JZ59 滑动窗口的最大值

牛客

leetcode

题解：

• https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/
• https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/dan-diao-dui-lie-si-lu-zhi-you-3ju-hua-d-djj9/

【提示】暴力法，一共有 n - size + 1 个窗口，每个窗口遍历的时间复杂度为 $O(k)$，总的时间复杂度为$O((n-size+1)size)\approx O(n\cdot size)$。size 是窗口大小。关键点在如何将获取窗口最大值的时间复杂度从 $O(n \cdot size)$ 降为 $O(1)$。本题使用双端队列 deque，维护一个非严格单调递减的序列，队头是窗口内的最大值。窗口每次移动，窗口内会新增加一个元素并删除一个元素，deque 在每次窗口移动时检查窗口删掉的元素是不是等于队首元素，相等则删掉队首元素（因为这是上一个窗口内的最大值）；同时 deque 检查队尾和之前的所有小于新增加的元素的元素，全部都删掉，然后将新增的元素添加到队尾，保持队列的非严格递减。

• 初始时，窗口左右指针的位置：left = 1 - size, right = 0

/** 
 * 定义一个双端队列 
*/
const Deque = function() {
  this.queue = [];
}

/* 判断队列是否为空 */
Deque.prototype.isEmpty = function() {
    return this.queue.length === 0 ? true : false;
  }

/* 获取队头元素 */
Deque.prototype.peekFirst = function() {
  if (!this.isEmpty()) {
    return this.queue[0];
  } else {
    return null;
  }
}

/* 获取队尾元素 */
Deque.prototype.peekLast = function() {
  if (!this.isEmpty()) {
    return this.queue[this.queue.length - 1];
  } else {
    return null;
  }
}

/* 往队尾添加元素 */
Deque.prototype.addLast = function (num) {
  this.queue.push(num);
}

/* 删除队头元素 */
Deque.prototype.removeFirst = function() {
  if (!this.isEmpty()) {
    return this.queue.shift();
  } else {
    return null;
  }
}

/* 删除队列最后一个元素 */
Deque.prototype.removeLast = function() {
  if (!this.isEmpty()) {
    return this.queue.pop();
  } else {
    return null;
  }
}

function maxInWindows(num, size)
{
  // write code here
  let window = new Deque(); // 创建一个双端队列，队首存储当前窗口内的最大值，整体保持非严格递减（单调队列）
  let res = [];
  
  // 左右指针分别指向窗口的两端
  for (let left = 1 - size, right = 0; right < num.length; left++, right++) {
    // 窗口移动前的窗口内最大值刚好在最左边 num[left - 1]，移动窗口后在双端队列 window 内将这个最大值删掉
    if (left > 0 && window.peekFirst() === num[left - 1]) {
      window.removeFirst()
    }
    
    // 删除双端队列中比新加入元素 num[j] 小的元素，保持非严格递减，队首是窗口内的最大值
    while (!window.isEmpty() && window.peekLast() < num[right]) {
      window.removeLast();
    }
    window.addLast(num[right]); // 将num[j]添加到窗口内
    
    // 形成窗口后记录窗口内的最大值
    if (left >= 0) {
      res[left] = window.peekFirst();
    }
  }
  
  return res;
}

---

回溯

JZ12 矩阵中的路径

牛客

leetcode

题解

【提示】矩阵的暴力搜索

• 递归退出条件

  // 索引越界或对应位置的字符不同或已经访问过矩阵中i, j位置的字符
  if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] !== words[k]) {
      return false;
    }
    if (k === words.length - 1) {
      return true;
    }

• 回溯

  matrix[i][j] = ''; // 已经访问过的字符设为''
  let res = dfs(matrix, words, i + 1, j, k + 1) || dfs(matrix, words, i - 1, j, k + 1) || 
              dfs(matrix, words, i, j - 1, k + 1) || dfs(matrix, words, i, j + 1, k + 1);
  matrix[i][j] = words[k]; // 回溯到这个位置时还原字符

---

JZ13 机器人的运动范围

牛客

leetcode

题解

【提示】

• 深度优先搜索DFS，从一个点往左往下递归搜索；

  let left = dfs(i, j + 1, si, sjLeft); // 往左移动-递归
  let right = dfs(i + 1, j, siBottom, sj); // 往下移动-递归
  let result = 1 + left + right; // 每成功移动一格+1

• 退出条件

  （1）索引值i, j越界；

  （2）横纵坐标的数位和大于threshold；

  （3）已经访问了索引处的格子（可行性剪枝）

  // 退出条件
  if (i >= rows || j >= cols || si + sj > threshold || visited[i][j] === true) {
    return 0;
  }

• 数位的计算（用不到）

  function getSum(num) {
    let sum = 0;
    while (num) {
      sum += num % 10;
      num = Math.floor(num / 10);
    }
    return sum;
  }

• 用到数位和的更新公式

  数位和增量公式： 设 $x$ 的数位和为$s_x$ ，$x+1$ 的数位和为$S_{x+1}$；

  1. 当 $(x + 1) \odot 10 = 0(x+1)⊙10=0$ 时： $s_{x+1} = s_x - 8$，例如 19, 20的数位和分别为 10, 2 ；
  2. 当 $(x + 1) \odot 10 = 0(x+1)⊙10\ne0$ 时： $s_{x+1} = s_x+1$，例如 1, 2的数位和分别为 1, 2 ；

---

JZ38 字符串的排列

牛客

leetcode

【提示】全排列+树层去重

• 全排列—used[i]
• 树层去重—（i > 0 && str.charAt(i - 1) === str.charAt(i) && !used[i - 1]）

// 全排列+树层去重
if (used[i] || (i > 0 && str.charAt(i - 1) === str.charAt(i) && !used[i - 1])) {
  continue ;
}

---

动态规划

JZ42 连续子数组的最大和

牛客

leetcode

题解

【提示】

三种解法：

1. 暴力解法（两个for循环）
   • 时间复杂度$O(N^2)$，空间复杂度$O(1)$；
2. 贪心解法
   • 时间复杂度$O(N)$，空间复杂度$O(1)$；
3. 动态规划
   • 不复用array数组，时间复杂度$O(N)$，空间复杂度$O(N)$；
   • 复用array数组，时间复杂度$O(N)$，空间复杂度$O(1)$；

1. 暴力解法

以每一个数为子数组起点，搜索最大子数组数值和

for (let i = 0; i < array.length; i++) {
  sum = 0;
  for (let j = i; j < array.length; j++) {
    sum += array[j];
    maxSum = sum > maxSum ? sum : maxSum;
  }
}

2. 贪心解法

局部保持每次sum加上array[i]>0，则sum是最优的。如果sum加上array[i]后sum<0，说明array[i]对最大和没有用，sum重置为0，从array[i+1]重新累加。

for (let i = 0; i < array.length; i++) {
  sum += array[i];

  if (sum > maxSum) {
    maxSum = sum;
  }
	
  if (sum < 0) {
    sum = 0;
  }
}

3. 动态规划

1. dp数组：dp[i]: 以array[i]结尾的子数组的最大和；
2. 递推公式：分两种情况：
   • dp[i - 1] < 0时，dp[i] = array[i]; （dp[i - 1]对dp[i]产生负贡献）
   • dp[i - 1]>=0时，dp[i] = array[i] + dp[i - 1];
3. dp数组初始化：dp[0]=array[0];

// 复用array数组作为dp数组
for (let i = 1; i < array.length; i++) {
  array[i] += Math.max(array[i - 1], 0); // 递推
  maxSum = Math.max(array[i], maxSum); // 判断最大值
}

---

JZ85 连续子数组的最大和(二)

牛客

leetcode

题解

相比上一个题，这个题需要求最大子数组和的最长长度。

【提示】动态规划（空间复杂度可以优化）

1. 用两个指针分别指向子数组区间的start和end，再用两个指针指向最大子数组和时的子数组区间

   let left = 0, right = 0;
   let resL = 0, resR = 0;

2. dp数组含义：dp[i]: 以array[i]结尾的子数组的最大和；

3. 递推公式：dp[i] = Math.max(dp[i-1] + array[i], array[i])；

4. dp数组初始化：dp[0] = array[0]；

5. 什么时候更新子数组区间的起点指针

   if (dp[i - 1] + array[i] < array[i]) {
     left = right;
   }

6. 什么时候更新最大值和最大值子数组区间索引

   if ((dp[i] > maxSum) || 
       (dp[i] === maxSum && (right - left) > (resR - resL))) {
     maxSum = dp[i];
     resR = right;
     resL = left;
   }

7. 怎样优化？

   • 没有优化时，定义一个dp数组，此时的空间复杂度为$O(N)$；
   • 从递推公式看出，dp[i]只跟dp[i-1]有关，因此用两个变量x, y分别表示dp[i-1]和dp[i]，此时的空间复杂度为$O(1)$；
   • 时间复杂度都为$O(N)$；

   y = Math.max(x + array[i], array[i]); // 更新当前状态
   ...
   // 更新上一个状态
   x = y;

   JZ69 跳台阶

   牛客

   leetcode

   【提示】dp数组初始化时，dp[0]=dp[1]=1

   ---

   JZ71 跳台阶扩展问题

   牛客

   题解

   【提示】分析递推公式，$dp(n)=dp(n−1)+dp(n−2)+…+dp(n−(n−1))+dp(n−n)=dp(0)+dp(1)+dp(2)+…+dp(n−1)$，因为$dp(n−1) = dp(n−2)+dp(n−3)+…+dp(1)+dp(0)$，经整理得$dp(n)=dp(n−1)+dp(n−1)=2∗dp(n−1)$

   ---

   JZ63 买卖股票的最好时机(一)

   牛客

   leetcode

   题解

   【提示】只能买卖一次，两种解法：贪心和动态规划。

• 贪心：直接找差值最大的区间；时间复杂度：$O(N)$，空间复杂度$O(1)$；

  let low = Number.MAX_SAFE_INTEGER;
  let res = 0;
  
  for (let i = 0; i < prices.length; i++) {
    low = Math.min(low, prices[i]);
    res = Math.max(res, prices[i] - low);
  }
  return res;

• 动态规划：时间复杂度：$O(N)$，空间复杂度$O(N)$；

  • dp数组的含义：dp[i][0]: 第i天持有股票时的最大收益，dp[i][1]: 第i天不持有股票时的最大收益；
  • 持有股票：买入股票或者前一天已经买入保持前一天的状态；不持有股票：卖出股票或保持前一天已经卖出的状态；
  • 递推公式：$dp[i][0] = max(dp[i - 1][0], -prices[i])$，$dp[i][1] = max(dp[i - 1][1], prices[i]+dp[i-1][0])$;
  • 初始化：$dp[0][0]=-prices[0]$，$dp[0][1]=0$；
  • 遍历顺序：从前往后遍历；

  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i][0]);
  }

  ---

  JZ47 礼物的最大价值

  牛客

  leetcode

  题解

  【提示】

• dp数组的含义：dp[i][j]表示在棋盘的i, j位置拿到礼物的最大价值；

• 递推公式：

  $d p(i, j)=\left{\begin{array}{ll}
  \operatorname{grid}(i, j) & , i=0, j=0 \
  \operatorname{grid}(i, j)+d p(i, j-1) & , i=0, j \neq 0 \
  \operatorname{grid}(i, j)+d p(i-1, j) & , i \neq 0, j=0 \
  \operatorname{grid}(i, j)+\max [d p(i-1, j), d p(i, j-1)] & , i \neq 0, j \neq 0
  \end{array}\right.$

• 初始化：dp[0][0]=grid[0][0]；

• dp[i][j]的状态依赖于dp[i-1][j]和dp[i][j-1]；

• 未优化时，时间复杂度为$O(MN)$，空间复杂度为$O(MN)$；优化后，时间复杂度为$O(MN)$，空间复杂度为$O(1)$；

  // 利用原数组优化空间复杂度
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        continue;
      } else if (i === 0 && j !== 0) {
        grid[i][j] = grid[i][j - 1] + grid[i][j];
      } else if (i !== 0 && j === 0) {
        grid[i][j] = grid[i - 1][j] + grid[i][j];
      } else {
        grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
      }
    }
  }

  ---

  JZ48 最长不含重复字符的子字符串

  牛客

  leetcode

  题解

  【提示】方法大体两种：动态规划或双指针+Hash表（动态规划没懂）

• 双指针：left和right

  // left每次指向s[right]的位置
  let left = -1, right = 0; // 定义左右指针

• 找到相同字符时，更新left为重复字符的索引；

• 子串长度=right-left；

  for (right = 0; right < s.length; right++) {
    let char = s.charAt(right);
    if (charMap.has(char)) {
      left = Math.max(left, charMap.get(char)); // 更新左指针
    }
    charMap.set(char, right); // 记录字符
    maxLen = Math.max(maxLen, right - left); // 更新子字符串的最大长度
  }
  return maxLen;

  ---

  JZ46 把数字翻译成字符串

  牛客

  leetcode

  题目有差异。

  题解

  【提示】牛客上的题目是数字126对应字母a-z，leetcode上是`025`对应a-z。

设$nums=x_{1}x_{2}x_{3}\cdots x_{i-1}x_{i}$

牛客

• dp数组含义：dp[i]表示以$x_i$结尾的数字的翻译方案数量；

• 递推公式：

  （1）$x_i$可以单独翻译成字母==》dp[i] = dp[i - 1];

  （2）$x_{i-1}x_{i}$可以一起翻译成字母，如果i=1, dp[i] = dp[i - 1] + 1；如果i > 1, dp[i] = dp[i - 1] + dp[i - 2];

• 初始化：dp[0] = 1;

  for (let i = 1; i < n; i++) {
    // 当前数字翻译成字母
    if (nums.charAt(i) !== '0') {
      dp[i] = dp[i - 1];
    }
    // 当前数字和前一个数字，两个一起翻译成字母
    let num = nums.charAt(i - 1) + nums.charAt(i);
    num = parseInt(num);
    if (num >= 10 && num <= 26) {
      if (i === 1) {
        dp[i] += 1;
      } else {
        dp[i] += dp[i - 2];
      }
    }
  }

leetcode

---

JZ70 矩形覆盖

牛客

题解

【提示】先具体写几个情况观察规律，归纳总结，最后得到递推公式为dp[i] = dp[i - 1] + dp[i - 2];

• dp数组含义：用2*1的矩形覆盖宽度为2*i的矩形一共有dp[i]中方法；
• 递推公式：dp[i] = dp[i - 1] + dp[i - 2]；
• 初始化：dp[0] = 0, dp[1] = 1, dp[2] = 2；
• 跟斐波那契数列的规律一样。

---

JZ19 正则表达式匹配（还没搞懂）

牛客

leetcode

题解

【提示】

---

搜索算法

JZ3 数组中重复的数字

牛客

【提示】两种解法

1. 利用集合set的不重复特性；
2. 先将原数组排序，然后遍历数组

---

JZ51 数组中的逆序对

牛客

leetcode

题解

【提示】在并排序的过程中统计逆序对（==归并排序不熟悉==）

function InversePairs(data)
{
  // write code here
  /* 归并排序(递归)时统计逆序对 */
  const tmp = new Array(data.length); // tmp数组存储原始的data数组
  
  const mergeSort = (left, right) => {
    // 终止条件
    if (left >= right) {
      return 0;
    }
    
    // 递归划分
    let middle = Math.floor((left + right) / 2); // 数组的中间位置-二分
    let res = mergeSort(left, middle) + mergeSort(middle + 1, right);
    
    // 合并阶段
    let i = left, j = middle + 1; // i指针指向做左数组起点，j指针指向右数组起点
    for (let k = left; k <= right; k++) { // 复制data的数据到tmp数组
      tmp[k] = data[k];
    }
    
    for (let k = left; k <= right; k++) { // 遍历整个数组
      if (i === middle + 1) { // 左子数组已经合并完毕 
        data[k] = tmp[j];
        j++;
      } else if (j === right + 1 || tmp[i] <= tmp[j]) { // 右子数组已经合并完毕或者左子数组当前元素小于右子数组当前元素
        data[k] = tmp[i];
        i++;
      } else { // 左子数组当前元素大于右子数组当前元素，则左子数组当前元素所在位置i和后面的元素(middle-i+1)与右子数组当前元素都构成逆序对
        data[k] = tmp[j];
        j++;
        res += middle - i + 1;
      }
    }
    return res;
  }
  
  return mergeSort(0, data.length - 1) % (1e9+7);
}

---

JZ4 二维数组中的查找

牛客

leetcode

题解

【提示】题目要求的时间复杂度为$O(M+N)$，暴力搜索的时间复杂度为$O(M\cdot N)$。利用给定矩阵的行列元素递增的性质，不断缩小搜索范围。

以左下角元素array[i][j]为搜索的起点（i，j是指向该元素的指针），然后判断target与array[i][j]的大小。

• 初始时，i=row-1, j=0；

• target > array[i][j]，则j++；

• target < array[i][j]，则i--；

• 当指针i，j的索引越界时，说明矩阵中不存在target。

---

JZ11 旋转数组的最小数字

牛客

leetcode

题解

【提示】旋转数组numbers是将一个升序排列的数组，在某个元素处将这个元素之前的序列旋转到数组的末尾。如果把旋转数组分为两部分：左排序数组和右排序数组，则有左排序数组的任意元素大于等于右排序数组的任意元素。求旋转数组的最小值等价于求右排序数组的第一个元素。

• 定义左右指针left和right，分别指向旋转数组的左右两端；

• 循环二分： 设$ m = (i + j) / 2m=(i+j)/2 $为每次二分的中点（ “/“ 代表向下取整除法，因此恒有$ i \leq m < j $），可分为以下三种情况：

  1. 当 $nums[m] > nums[j]$ 时： m 一定在 左排序数组 中，即旋转点 x 一定在$ [m + 1, j]$闭区间内，因此执行 $i = m + 1$；
  2. 当 $nums[m] < nums[j]$ 时： m 一定在 右排序数组 中，即旋转点 x 一定在$[i, m]$闭区间内，因此执行 j = m；
  3. 当 $nums[m] = nums[j]$ 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在$ [i, m] $还是$ [m + 1, j] $区间中。解决方案： 执行$ j = j - 1$缩小判断范围。

  function minNumberInRotateArray(rotateArray)
  {
    // write code here
    let left = 0, right = rotateArray.length - 1; // 左右指针
    
    while (left !== right) {
      let mid = Math.floor((left + right) / 2);
      if (rotateArray[mid] > rotateArray[right]) {
        left = mid + 1;
      } else if (rotateArray[mid] < rotateArray[right]) {
        right = mid;
      } else {
        right--;
      }
    }
    return rotateArray[right];
  }

  ---

  JZ44 数字序列中某一位的数字

  牛客

  leetcode

  题解

  

  时间复杂度：$O(logn)$，空间复杂度：$O(logn)$；

  function findNthDigit( n ) {
    // write code here
    let digit = 1; // 数字n对应的数字的位数
    let start = 1; // 数字n对应的数字的起始值（如，n=23，则start=10）
    let count = 9; // digit位数的范围内一共有多少个数
    
    // 找到n对应的以上三个数据
    while (n > count) {
      n -= count;
      digit += 1;
      start *= 10;
      count = digit * start * 9;
    }
    let num = start + (n - 1) / digit; // 确定n对应的数
    return (num + '').charAt((n - 1) % digit) - '0'; // 确定n对应的是序列中的哪个数字
  }

JZ53 数字在升序数组中出现的次数

牛客

leetcode

题解

https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

【提示】

• 因为data是一个非降序数组，它是有序的，这种时候我们可能会想到用二分查找。但是一个数组可能有多个k，而且我们要查找的并非常规二分法中k出现的位置，而是k出现的左界和k出现的右界。要是能刚好找到恰好小于k的数字位置和恰好大于k的数字的位置就好了。

/* 查找k出现区间的左边界 */
  const biSearch = (data, k) => {
    let left = 0, right = data.length - 1;

    while (left <= right) {
      let middle = Math.floor((left + right) / 2);
      if (data[middle] < k) {
        left = middle + 1;
      } else if (data[middle] > k) {
        right = middle - 1;
      }
    }
    return left;
  };

• 再有因为数组中全是整数，因此我们可以考虑，用二分查找找到k+0.5k+0.5k+0.5应该出现的位置和k−0.5k-0.5k−0.5应该出现的位置，二者相减就是k出现的次数。

// 分两次查找，(k+0.5)和(k-0.5)的左边界之间的数就是k出现的次数
return biSearch(data, k + 0.5) - biSearch(data, k - 0.5);

---

位运算

JZ65 不用加减乘除做加法

牛客

leetcode

题解

【提示】：

（1）使用位运算，先是通过异或得到在不进位的情况下的结果；

（2）通过与运算得到只进位的结果；

（3）重复（1）和（2），直到只进位的结果为0，即此时不需要进位，得到的是最终结果；

/* 递归 */
function Add(num1, num2)
{
   // write code here
  if (num2 === 0) {
    return num1;
  }
  
  return Add(num1 ^ num2, (num1 & num2) << 1);
}

---

JZ15 二进制中1的个数

牛客（所有数）

leetcode（无符号整数）

题解：

• https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/
• https://blog.nowcoder.net/n/82793d9724ff4f07bb07ba5cdf19b261

【提示】两种解法：

（1）逐位与运算，n & 1；

（2）利用n & (n - 1)会将n的最右边的1变为0，当统计完后，n=0；

---

JZ16 数值的整数次方

牛客

leetcode

题解

【提示】两种解法：

（1）直接相乘；

while (exponent--) {
    result *= base;
}

（2）快速幂（二进制角度或二分法角度）

/* 二进制角度 */
while (exponent > 0) {
  // exponent二进制这一位是1
  if ((exponent & 1) === 1) {
    result *= base;
  }

  base *= base; // 更新exponent二进制下一位对应的乘数
  exponent = exponent >> 1; // exponent向右移一位
}

/* 二分法角度 */
while (exponent > 0) {
  // exponent为奇数时，将此时的base乘入result中
  if (exponent % 2 === 1) {
    result *= base;
  }

  base *= base; // 更新base
  exponent = Math.floor(exponent / 2); // exponent二分
}

---

JZ56 数组中只出现一次的两个数字

牛客

leetcode（跟牛客的题有差异）

题解

【提示】两种思路：1. 哈希表存储数字出现的次数（暂未实现）；2. 二进制角度（异或运算^和与运算&）

（2）二进制角度：

1.所有的数进行异或运算得到能够代表所有数之间差异的一个数（二进制角度）；

let tmp = 0;
for (const num of array) {
  tmp ^= num;
}

2.从最低位开始，找到一个可以将所有数区分为两组的一个数（二进制只有一位）；

let mask = 1;
while ((tmp & mask) === 0) {
  mask = mask << 1;
}

3.将所有数分为两组，然后分别找这两组中只出现一次的数；

let a = 0, b = 0;
for (const num of array) {
  if ((num & mask) === 0) {
    a ^= num;
  } else {
    b ^= num;
  }
}

---

JZ64 求1+2+3+…+n

牛客

leetcode

题解

【提示】：题目限制不能使用加减乘除，以及条件判断语句和循环语句。从求解的方法中进行排除（1. 乘法-等差数列求和公式；2. 迭代相加；3. 递归-判断），最终选择迭代法，递归退出的条件判断用短路与&&替代。

逻辑运算的短路效应：

if(A && B)  // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false

if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

---

模拟

JZ29 顺时针打印矩阵

牛客

leetcode

【提示】按从左到右，从上到下，从右到左，从下到上的顺序遍历；

let m = matrix.length;
let n = matrix[0].length;
let middle = Math.floor(m / 2); // 当m===n，且为奇数时需要单独加上middle位置的数
let startX = 0, startY = 0; // 每一轮遍历的起点
let loopCount = m < n ? Math.ceil(m / 2)  : Math.ceil(n / 2); // 循环的次数
let offset = 1; // 控制边界

// 当m!=n时，无法完成完整的一圈循环，需要单独处理边界处的值
if (m !== n) {
  if (m - offset === startX || n - offset === startY) {
    res.push(matrix[i][j]);
    continue;
  }
}

// m=n，处理middle处的值
 if (m === n && m % 2 !== 0) {
   res.push(matrix[middle][middle]);
 }

---

JZ61 扑克牌顺子

牛客

leetcode

题解

【提示】关键在于判断是否有重复的数字和这组数中最大值与最小值的差是否超过这组数的长度（题目给的是5）。

（1）集合+遍历

（2）排序+遍历

if (number === 0) {
  return false;
}

max - min < 5

---

JZ66 构建乘积数组

牛客

leetcode

题解

【题解】

---

JZ67 把字符串转换成整数(atoi)

牛客

leetcode

题解

【提示】：

1. 连续数字字符转数字

   num = num * 10 + (char - '0')

2. 超出边界值时的处理

   if (num >= BOUNDRY) {
     num = sign === 1 ? BOUNDRY - 1 : BOUNDRY;
     break;
   }

3. javascript需要注意：0和-0是不同的两个数

   if (num === 0 && sign === -1) {
     return num;
   }

---

JZ20 表示数值的字符串

牛客

leetcode

题解

【提示】较好的两种解法：1. ==有限状态机==；2. 正则表达式。

（1）有限状态机

数字表示状态，digit, blank, sign, dot, e表示状态转移的条件，满足条件就可以从当前状态转移至另一个状态。合法的结束状态有：2, 3, 7, 8。

1. 定义状态转移表

2. 初始化当前状态；

3. 循环字符串判断每一个字符的类型，即状态转移的条件；

4. 判断能否进行状态转移，不能直接return false;

5. 状态转移；

6. 判断结束状态是否合法；

---

（2）正则表达式（暂未实现）

---

其他算法

JZ21 调整数组顺序使奇数位于偶数前面(一)

牛客

leetcode

【提示】两种解法：1. 辅助数组（odd和even），然后合并；2. 在原数组的基础上，移动数字的位置。

（1）辅助数组

定义数组odd存储array中的奇数，even存储array中的偶数，遍历array后，将odd和even合并。

时间复杂度：$O(n)$，空间复杂度：$O(n)$；

（2）在原数组上移动数字

定义$j$表示array中奇数的个数，初始化$j=0$；$i$是遍历array的索引变量，初始化$i=0$；

1. 遇到奇数，j++；
2. temp记录当前位置的奇数temp=array[i]；
3. [j-1,i]位置的数向后移动一位；
4. 将奇数temp插入到j-1处。

for (let i = 0; i < array.length; i++) {
    if (array[i] % 2 === 1) {
      j++;
      let temp = array[i];
      for (let k = i; k >= j - 1; k--) {
        array[k] = array[k - 1];
      }
      array[j - 1] = temp;
    }
  }

---

JZ81 调整数组顺序使奇数位于偶数前面(二)

牛客

【提示】如果不要求保证奇数和奇数，偶数与偶数之间的相对位置，则使用双指针分别指向数组的左右两端，将奇数交换到数组前面，偶数交换到数组后面。

function reOrderArrayTwo( array ) {
  // write code here
  let left = 0, right = array.length - 1;
  
  while ( left < right) {
    // 左指针指向的数是偶数
    if(array[left] % 2 === 0) {
      // 右指针指向的数是奇数
      if (array[right] % 2 !== 0) {
        [array[left], array[right]] = [array[right], array[left]];  // 交换位置
      } else {
        right--; // 右指针也指向偶数，则右指针往前移动一位
      }
    } else {
      left++; // 左指针指向的数是奇数，左指针往后移动一位
    }
  }
  return array;
}

---

---

JZ39 数组中出现次数超过一半的数字

牛客

leetcode

题解

【提示】三种常用解法：

1. 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 $O(N)$。
2. 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
3. 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 $O(N)$ 和 $O(1)$ ，为本题的最佳解法。

对于摩尔投票法，基本思想是如果一个数是众数则票数+1，如果不是众数则票数-1。初始化票数vote = 0，当vote === 0时，设置众数x = num。

function MoreThanHalfNum_Solution(numbers)
{
  // write code here
  let vote = 0; // 票数
  let x = numbers[0]; // 众数
  
  for (const num of numbers) {
    if (vote === 0) {
      x = num; // 票数为0时假设当前num为众数
    }
    if (num === x) {
      vote++;
    } else {
      vote--;
    }
  }
  return x;
}

---

JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

牛客

leetcode

题解

【提示】具体来说是三个公式：

（1）$cur=0$ 时，1的个数为$high * digit$；

（2）$cur=1$ 时，1的个数为$high * digit + low + 1$；

（3）$cur=2 \cdots 9$ 时，1的个数为$(high + 1) * digit$；

==代码中先更新低位。==

function NumberOf1Between1AndN_Solution(n)
{
  // write code here
  let cur = n % 10; // 当前位
  let low = 0; // 低位
  let high = Math.floor(n / 10); // 高位
  let digit = 1; // 位因子
  let count = 0; // 1的个数
  
  // 当高位和当前位同时为0时，说明已经统计完成
  while (high !== 0 || cur !== 0) {
    if (cur === 0) {
      count += high * digit;
    } else if (cur === 1) {
      count += high * digit + low + 1;
    } else {
      count += (high + 1) * digit;
    }
    low += cur * digit; // 先更新低位
    cur = high % 10;
    high = Math.floor(high / 10);
    digit *= 10;
  }
  
  return count;
}

---

JZ45 把数组排成最小的数

牛客

leetcode

题解

【提示】使用排序算法按照指定的排序规则进行排序，然后拼接起来就是最小的数。

排序规则：

设数组 nums中任意两数字的字符串为x和y，则规定排序判断规则为：
* 若拼接字符串 x + y > y + x ，则 x “大于” y ；
* 反之，若 x + y < y + x，则 x“小于”y ；

// 使用自带的排序函数
function PrintMinNumber(numbers)
{
  // write code here
  const strs = numbers.map(num => '' + num);
  strs.sort(sortRule);

  return strs.reduce((preValue, curValue) => preValue + curValue, '');
}

// 排序规则
function sortRule(x, y) {
  let  a, b;
  [a, b] = [x + y, y + x];
  if (a > b) {
    return 1;
  } else if ( a < b) {
    return -1;
  } else {
    return 0;
  }
}

---

JZ49 丑数

牛客

leetcode

题解

【提示】（动态规划）只包含质因子2、3和5的数称作丑数（Ugly Number），因此存在递推关系。

• dp数组的含义：dp[i]表示第i+1个丑数；
• 递推公式：dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)，其中a,b,c分别指向某个乘以2, 3,或5刚好小于等于dp[i]的丑数。
• 初始化：dp[0]=1，第一个丑数是1。
• 当dp[a], dp[b]或dp[c]等于dp[i]时，分别更新a, b, c（加1）;

---

JZ74 和为S的连续正数序列

牛客

leetcode

题解

【提示】两种解法：求和公式和滑动窗口；

（1）求和公式

等差数列的求和公式：$sum=\frac{(i+j)×(j-i+1)}{2}$，其中i，j分别表示连续序列的左右边界；

求根公式：对于一元二次方程$ax^{2}+bx+c=0 \quad(a \ne 0)$，有 $x = \frac{-b \pm \sqrt{b^{2}-4 a c}}{2 a}$

当sum和i已知时，根据一元二次方程的求根公式得到：

$\begin{equation}x = \frac{-b \pm \sqrt{b^{2}-4 a c}}{2 a}j=\frac{-1+\sqrt{1+4\left(2 \times \operatorname{target}+i^{2}-i\right)}}{2} \end{equation}$

（2）滑动窗口

窗口内的值之和大于等于sum，则左边界移动一格；窗口内的值之和小于sum，则右边界移动一格；当窗口内的值等于sum时，将left和right之间的数添加到path中，然后将path添加到res中。

function FindContinuousSequence(sum)
{
  // write code here
  const res = [];
  const path = [];
  
  let left = 1, right = 2, sumOfWindow = 3;
  
  while (left < right) {
    if (sumOfWindow === sum) {
      for (let i = left; i <= right; i++) {
        path.push(i);
      }
      res.push([...path]);
      path.length = 0;
    }
    if (sumOfWindow < sum) {
      right++;
      sumOfWindow += right;
    } else if (sumOfWindow >= sum) {
      sumOfWindow -= left;
      left++;
    }
  }
  
  return res;
}

---

JZ57 和为S的两个数字

牛客

leetcode

题解

【提示】给定的array是升序的，题目要求是找到两个数的和为sum，有可能不存在，因此用回溯的话没有退出条件。这个的思路是双指针。

let left = 0, right = array.length - 1;
while (left < right) {
  let numSum = array[left] + array[right];
  if (numSum < sum) {
    numSum -= array[left];
    left++;
  } else if (numSum > sum) {
    numSum -= array[right];
    right--;
  } else {
    res.push(array[left]);
    res.push(array[right]);
    break;
  }
}

---

JZ58 左旋转字符串

牛客

leetcode

题解

【提示】两种思路：“字符串切片”和“字符串拼接”。

（1）字符串切片（用到了字符串的substring()方法）

const num = n % str.length;
res = str.substring(num, str.length) + str.substring(0, num);
return res;

（2）字符串拼接（循环拼接字符串，用取余简化代码）

let res = [];
for (let i = n; i < (n + str.length); i++) {
  res.push(str.charAt(i % str.length));
}
return res.join('');

---

JZ62 孩子们的游戏(圆圈中最后剩下的数)

牛客

leetcode

题解

【提示】约瑟夫环问题，动态规划

• dp[i]数组: i, m问题的解为dp[i]；
• 递推公式：dp[i] = (dp[i - 1] + m) % i；
• 初始化：dp[1] = 0；

let res = 0; // 使用一个变量执行状态转移
for (let i = 2; i <= n; i++) {
  res = (res + m) % i;
}
return res;

---

JZ75 字符流中第一个不重复的字符

牛客

题解

【提示】HashMap记录字符的个数，字符流的存储有两种：字符串（空间复杂度 $O(n)$）和队列（空间复杂度 $O(1)$）;

注意：JS中字符串在底层是不能改变的，对字符串的操作都会返回一个新的字符串，因此str不能用const定义。

//Init module if you need

// let str = new String();
const queue = [];
const hashMap = new Map();

//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
  // write code here
  while (queue.length) {
    let char = queue[0];
    if (hashMap.get(char) === 1) {
      return char;
    } else {
      queue.shift();
    }
  }
  
  return '#';
}

---

JZ17 打印从1到最大的n位数

牛客

【提示】最大的n为十进制数，先用循环得到n位的全是9的字符串，然后转为数字。

let max = '';
for (let i = 0; i < n; i++) {
  max += '9';
}
let maxNum = parseInt(max);

---

JZ14 剪绳子

牛客

leetcode

题解

【提示】记住两个推论：

（1）当所有绳段的长度相等时，乘积最大；

（2）最优的绳段长度为3，次优为2，最差为1；

根据以上推论，有绳子长度 $n=3a+b$。

• b=0时，最大乘积为$3^a$；
• b=1时，拿出一个3凑成2+2，最大乘积为$3^{a-1}*4$；
• b=2时，最大乘积为 $3^{a}*2$；

---

JZ83 剪绳子（进阶版）

牛客

leetcode

题解

【题解】最终结果很大，需要对结果求余。两种解法：循环求余和快速幂求余。

（1）循环求余

公式：

$\begin{align}
x^{a} \odot \boldsymbol{p} & = \left[\left(x^{a-1} \odot \boldsymbol{p}\right)(x \odot p)\right] \odot \boldsymbol{p} & = \left[\left(x^{a-1} \odot \boldsymbol{p}\right) x\right] \odot \boldsymbol{p}
\end{align}$

function remainder(a, p) {
  let rem = 1;
  while (a--) {
    rem = (rem * 3) % p;
  }
  
  return rem;
}

（2）快速幂求余（JS通不过）

公式：

$\begin{align}
a^{b} \bmod c & = \left(\begin{array}{l}
a \bmod c)^{b}
\end{array}\right.
\end{align}$

$\begin{align}
x^{a} \odot p & = \left(x^{2}\right)^{a / 2} \odot p & = \left(x^{2} \odot p\right)^{a / 2} \odot p
\end{align}$

function remainder2(x, a, p) {
  let rem = 1;

  while (a > 0) {
    if (a % 2 === 1) {
      rem = (rem * x) % p;
    }
    x = (x * x) % p;
    a = Math.floor(a / 2);
  }

  return rem;
}

References:

• https://www.cnblogs.com/Dfkuaid-210/p/12115238.html#:~:text=%E5%BF%AB%E9%80%9F%E5%B9%82%E5%8F%96%E4%BD%99%E4%BE%9D%E8%B5%96%E4%BA%8E%E4%BB%A5%E4%B8%8B%E5%85%AC%E5%BC%8F%3A%20a%20b%20mod%20c%20%3D%20%28%20%28,mod%20c%20%C3%97%20a%29%20mod%20c%20%E5%B0%B1%E5%8F%AF%E4%BB%A5%E4%BA%86%E3%80%82.%20%E4%BA%8E%E6%98%AF%E6%88%91%E4%BB%AC%E5%BE%97%E5%88%B0%E4%BB%A5%E4%B8%8B%E7%AE%97%E6%B3%95%EF%BC%9A.

---

常用代码片段

创建一个二维数组

new Array(rows).fill().map(item => new Array(cols).fill(false));

字符数组转字符串

const arr = ['a', 'b', 'c']
arr.join(‘’)

---