本文最后更新于：2023年3月19日晚上

牛客网多题

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：

1
2
3

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1 2	`输入: "cbbd" 输出: "bb"`

思路

暴力

暴力遍历所有可能，无法通过，超时

中心扩展法

回文串一定是对称的，每次选择一个中心，进行中心向两边扩展比较左右字符是否相等
中心点的选取有两种
aba，中心点是 b
aa，中心点是两个 a 之间
所以共有两种组合可能
left：i，right：i
left：i，right：i+1

解答

暴力

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) return s;
  const isReverse = (s) => {
    return s.split("").reverse().join("") === s;
  };
  let max = 0;
  let res = "";
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j < s.length + 1; j++) {
      let str = s.slice(i, j);
      let length = str.length;
      if (isReverse(str) && Math.max(max, length) === length) {
        max = length;
        res = str;
      }
    }
  }
  return res;
};

中心拓展法

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) return s;
  let max = 0;
  let start = 0,
    end = 0;
  const center = (left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  };
  let index = 0;
  while (index < s.length) {
    let maxLen = Math.max(center(index, index), center(index, index + 1));
    let len1 = center(index, index);
    let len2 = center(index, index + 1);
    if (maxLen > max) {
      if (maxLen % 2 === 0) {
        max = maxLen;
        start = index - maxLen / 2 + 1;
        end = index + maxLen / 2 + 1;
      } else {
        max = maxLen;
        start = index - (maxLen - 1) / 2;
        end = index + (maxLen + 1) / 2;
      }
    }
    index++;
  }
  return s.slice(start, end);
};

寻找第 K 大

有一个整数数组，请你根据快速排序的思路，找出数组中第 K 大的数。
给定一个整数数组 a,同时给定它的大小 n 和要找的 K(K 在 1 到 n 之间)，请返回第 K 大的数，保证答案存在。
测试样例：

1 2	`[1,3,5,2,2],5,3 返回：2`

思路

提示使用快速排序的思路，快排一次以后，一个下标的元素在排序后的数组中的位置已经确认。所以不需要全部排完再得到答案，判断当前下标的值大于或小于 K，大于 K 则需要在左边查找，小于 K 则在右边查找，直到查找到 K 为止，

解答

/**
 *
 * @param a int整型一维数组
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
function findKth(a, n, K) {
  // write code here
  function quickSort(start, end) {
    if (start >= end) return;
    let i = start;
    let j = end;
    let tmp = a[start];
    while (i < j) {
      while (i < j && a[j] >= tmp) j--;
      while (i < j && a[i] <= tmp) i++;
      [a[i], a[j]] = [a[j], a[i]];
    }
    [a[start], a[i]] = [a[i], a[start]];
    return i;
  }
  let index = quickSort(0, n - 1);
  while (index !== n - K) {
    if (index > n - K) {
      index = quickSort(0, index - 1);
    } else {
      index = quickSort(index + 1, n - 1);
    }
  }
  return a[index];
}

module.exports = {
  findKth: findKth,
};

链表中的节点每 k 个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度** O(1)**
例如：
给定的链表是 1→2→3→4→5
对于k=2, 你应该返回 2→1→4→3→5
对于k=3, 你应该返回 3→2→1→4→5
示例 1
输入

1	`{1,2,3,4,5},2`

输出

1	`{2,1,4,3,5}`

思路

不限制空间复杂度及修改方式

刚开始没看到限制空间复杂度为 O(1)，和不能直接修改值。若不限制有简单的实现方法。

解答

不限制空间复杂度及修改方式

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
function reverseKGroup(head, k) {
  // write code here
  let tmp = head;
  while (tmp) {
    let reverseStack = [];
    let tmp2 = tmp;
    while (reverseStack.length < k && tmp2) {
      reverseStack.push(tmp2.val);
      tmp2 = tmp2.next;
    }
    if (reverseStack.length === k) {
      while (reverseStack.length) {
        tmp.val = reverseStack.pop();
        tmp = tmp.next;
      }
    } else {
      break;
    }
  }
  return head;
}
module.exports = {
  reverseKGroup: reverseKGroup,
};

括号匹配

给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。

思路

比较简单，栈实现即可，使用一个对象来判断括号合法性

解答

/**
 *
 * @param s string字符串
 * @return bool布尔型
 */
function isValid(s) {
  // write code here
  const valid = {
    "()": true,
    "{}": true,
    "[]": true,
  };
  if (s.length % 2 !== 0) return false;
  const stack = [];
  for (const arr of s) {
    if (stack.length) {
      let top = stack[stack.length - 1];
      let str = top + arr;
      if (valid[str]) stack.pop();
      else return false;
    } else {
      stack.push(arr);
    }
  }
  return stack.length === 0;
}
module.exports = {
  isValid: isValid,
};

斐波那契数列（跳楼梯）

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0，第 1 项是 1）。
n<=39

思路

dp 求解即可

解答

function Fibonacci(n) {
  if (n === 0) return 0;
  // write code here
  let a = 0;
  let b = 1;
  let sum = a + b;
  for (let i = 2; i < n; i++) {
    a = b;
    b = sum;
    sum = a + b;
  }
  return sum;
}
module.exports = {
  Fibonacci: Fibonacci,
};

实现二叉树先序，中序和后序遍历

分别按照二叉树先序，中序和后序打印所有的节点。
示例 1
输入

{1,2,3}

输出

1	`[[1,2,3],[2,1,3],[2,3,1]]`

思路

一次遍历即可建立好结果数组

解答

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 *
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
function threeOrders(root) {
  // write code here
  let res = [[], [], []];
  const visit = (root) => {
    if (!root) return null;
    res[0].push(root.val);
    visit(root.left);
    res[1].push(root.val);
    visit(root.right);
    res[2].push(root.val);
  };
  visit(root);
  return res;
}

module.exports = {
  threeOrders: threeOrders,
};

链表中是否有环

判断给定的链表中是否有环

思路

hash 表

通过 map 存节点，判断 map 中是否已有节点，已有则存在

增加 isVisit 字段判断

通过 js 特性来判断

快慢指针

快指针走两次，慢指针走一次，如果有环，快指针会赶上慢指针。

解答

hash 表

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
function hasCycle(head) {
  // write code here
  const map = new Map();
  while (head) {
    if (map.has(head)) return true;
    else map.set(head, true);
    head = head.next;
  }
  return false;
}
module.exports = {
  hasCycle: hasCycle,
};

增加 isVisit 字段判断

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
function hasCycle(head) {
  // write code here
  while (head) {
    if (head.isVisit) return true;
    head.isVisit = true;
    head = head.next;
  }
  return false;
}
module.exports = {
  hasCycle: hasCycle,
};

快慢指针

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
function hasCycle(head) {
  // write code here
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) return true;
  }
  return false;
}
module.exports = {
  hasCycle: hasCycle,
};

反转字符串

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过 1000）

思路

双指针

一个指向字符串头，一个指向字符串尾。当两个指针相遇强，不断交换指针的值，得到答案。

解答

/**
 * 反转字符串
 * @param str string字符串
 * @return string字符串
 */
function solve(str) {
  // write code here
  let start = 0;
  let end = str.length - 1;
  str = str.split("");
  while (start < end) {
    [str[start], str[end]] = [str[end], str[start]];
    start++;
    end--;
  }
  return str.join("");
}
module.exports = {
  solve: solve,
};

合并两个有序的数组

给出两个有序的整数数组和，请将数组合并到数组中，变成一个有序的数组
注意：
可以假设数组有足够的空间存放数组的元素，和中初始的元素数目分别为和

思路

即归并排序中的合并原理，设置一个指针指向排序结果结尾下标 m+n-1，从这里开始排序。将两个指针指向 A、B 结尾，判断指针指向的值哪个大，大的放入结果指针指向的地方，令结果指针和大的那个值的数组指针减一，当 m、n 其中一个小于 0，结束循环，将另外一个数组剩下的元素赋值进 A 即可。

解答

/**
 *
 * @param A int整型一维数组
 * @param B int整型一维数组
 * @return void
 */
function merge(A, m, B, n) {
  // write code here
  let k = m + n - 1;
  m = m - 1;
  n = n - 1;
  while (m >= 0 && n >= 0) {
    if (A[m] > B[n]) {
      A[k--] = A[m--];
    } else {
      A[k--] = B[n--];
    }
  }
  while (m >= 0) {
    A[k--] = A[m--];
  }
  while (n >= 0) {
    A[k--] = B[n--];
  }
}
module.exports = {
  merge: merge,
};

删除链表倒数第 k 个元素

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为:1->2->3->4->5, n= 2.
删除了链表的倒数第 n 个节点之后,链表变为 1->2->3->5.
备注：
题目保证 n 一定是有效的
请给出请给出时间复杂度为**O(n)**的算法

思路

使用队列存链表的值，删除倒数第 n 个元素，重新生成链表即可

解答

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @param n int整型
 * @return ListNode类
 */
function removeNthFromEnd(head, n) {
  // write code here
  if (n < 1) return head;
  const queue = [];
  let tmp = head;
  while (tmp) {
    queue.push(tmp.val);
    tmp = tmp.next;
  }
  tmp = new ListNode(null);
  queue.splice(queue.length - n, 1);
  let res = tmp;
  while (queue.length) {
    tmp.next = new ListNode(queue.shift());
    tmp = tmp.next;
  }
  return res.next;
}
module.exports = {
  removeNthFromEnd: removeNthFromEnd,
};

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

思路

哈希表存储，如果出现的次数大于数组一半，返回值。不存在则返回 0

解答

function MoreThanHalfNum_Solution(numbers) {
  // write code here
  const map = new Map();
  for (const number of numbers) {
    map.set(number, map.has(number) ? map.get(number) + 1 : 1);
    if (map.get(number) > Math.floor(numbers.length / 2)) return number;
  }
  return 0;
}
module.exports = {
  MoreThanHalfNum_Solution: MoreThanHalfNum_Solution,
};

二分查找

请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例 1
输入

1	`5,4,[1,2,4,4,5]`

输出

思路

判断数组第一个值是否大于查找值，是的话直接返回 1。后面是常规的二分查找，知道找到中点大于等于查找值，中点的前一个点小于查找值为止。

解答

/**
 * 二分查找
 * @param n int整型 数组长度
 * @param v int整型 查找值
 * @param a int整型一维数组 有序数组
 * @return int整型
 */
function upper_bound_(n, v, a) {
  // write code here
  if (n > 0) {
    if (a[0] >= v) return 1;
  }
  let start = 0;
  let end = n - 1;
  let middle = null;
  while (start <= end) {
    middle = Math.floor((start + end) / 2);
    if (a[middle] >= v && a[middle - 1] < v) {
      return middle + 1;
    } else if (a[middle] >= v) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  return n + 1;
}
module.exports = {
  upper_bound_: upper_bound_,
};

算法

LeetCode 算法数组动态规划二叉树哈希表链表二分算法快慢指针栈

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

手动实现trim 上一篇

ES6,CommonJS 区别下一篇

「每日LeetCode」2020年9月20日

5. 最长回文子串

思路

暴力

中心扩展法

解答

暴力

中心拓展法

寻找第 K 大

思路

解答

链表中的节点每 k 个一组翻转

思路

不限制空间复杂度及修改方式

解答

不限制空间复杂度及修改方式

括号匹配

思路

解答

斐波那契数列（跳楼梯）

思路

解答

实现二叉树先序，中序和后序遍历

思路

解答

链表中是否有环

思路

hash 表

增加 isVisit 字段判断

快慢指针

解答

hash 表

增加 isVisit 字段判断

快慢指针

反转字符串

思路

双指针

解答

合并两个有序的数组

思路

解答

删除链表倒数第 k 个元素

思路

解答

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

思路

解答

二分查找

思路

解答