剑指 Offer 53 - II. 0 ～ n-1 中缺失的数字、剑指 Offer 61. 扑克牌中的顺子、剑指 Offer 42. 连续子数组的最大和、剑指 Offer 18. 删除链表的节点

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

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 ～ n-1 之内。在范围 0 ～ n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
 示例 1:

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

示例  2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：
1 <= 数组长度 <= 10000

思路

遍历

最简单的遍历，如果下标不等于数，返回下标。时间复杂度 O(n)。

二分查找

题目关键词，有序数组，所以使用二分查找。如果下标和数相同，令 min 等于 mid + 1。若下标和数不同，若 mid 为 0，缺少的为 0，再确认上一个数是否和数相同，是的话返回当前下标，不是的话令 max 等于 mid - 1。时间复杂度 O(logn)。

解答

遍历

太简单了，不写了。

二分查找

var missingNumber = function (nums) {
  let p = 0;
  let q = nums.length - 1;
  let mid = 0;
  while (p <= q) {
    mid = parseInt((p + q) / 2);
    if (nums[mid] === mid) {
      p = mid + 1;
    } else {
      if (mid === 0) {
        return 0;
      }
      if (nums[mid - 1] !== mid) {
        return mid;
      } else {
        q = mid - 1;
      }
    }
  }
  return nums.length;
};

剑指 Offer 61. 扑克牌中的顺子

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2 ～ 10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 示例  1:

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

示例  2:

输入: [0,0,1,2,5]
输出: True

限制：
数组长度为 5 
数组的数取值为 [0, 13] .

思路

先对数组排序，如果为 0，直接跳过。如果为对子，则这不是 0 的对子，直接返回 false。计算剩余的牌的最大值及最小值，如果他们的差小于等于四则为顺子

解答

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isStraight = function (nums) {
  nums.sort();
  let max = 0;
  let min = 13;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
      continue;
    }
    if (nums[i] === nums[i + 1]) {
      return false;
    }
    if (nums[i] > max) max = nums[i];
    if (nums[i] < min) min = nums[i];
  }
  return max - min <= 4;
};

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

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例 1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

思路

复习，本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/。
先比较 sum 加上当前数是否令 sum 变大，是的话，再判断 sum 是不是最大的 sum 存在 max 中。如果不是，则把当前设为一个子数组的开始，即 sum 重新开始计算。

解答

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let sum = nums[0];
  let max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    sum = Math.max(nums[i], sum + nums[i]);
    max = Math.max(sum, max);
  }
  return max;
};

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

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:

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

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

思路

判断头结点值是否相等，是的话，返回头结点的 next。使用一个 pre 记录上一个节点，如果当前节点值相等，则将上一个节点的 next 设为当前节点的 next，返回 res。

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function (head, val) {
  let res = head;
  if (res.val === val) return res.next;
  let pre = head;
  while (head) {
    pre = head;
    head = head.next;
    if (head && head.val === val) {
      pre.next = head.next;
      break;
    }
  }
  return res;
};