数组

1.删除排序数组中的重复项

一开始想的是通过一个空数组记录每次循环的数字，如果已经存在了，就不存入，最后返回数组的长度。但是题目要求不使用额外的数组空间，无奈还是去看了其他大神的解法，在这里记录一下。

看到最多的是 “双指针” 解法，因为数组是排序的，所以相同的肯定是挨着的，就可以左右两个数字两两比较，如果左边数字与右边数字相同，那么左边数字的指针就不变，右边数字的指针加一；当遇到不同的数字，左边指针加一，右边指针后移，并且将右指针的值赋值给左指针。

在 JavaScript 中，指针就对应为数组的索引，从零开始，一直到数组的长度结束：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function removeDuplicates(nums) {
  if(!nums || nums.length === 0) {
    reutrn 0
  }

  let num = 0

  for (let i = 1; i < nums.length; i++) {
    if(nums[num] !== nums[i]) {
      // 下面两行可以简写为 nums[++num] = nums[i]
      nums[num + 1] = nums[i]
      num += 1
    }
  }

  return num + 1
}

2.买卖股票的最佳时机 II

这道题实在是没有一点点思路，看了解法，用到了动态规划，好吧，超出我的理解范围了。

1
2
3
4
5
6
7
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // 做不来
}

3.旋转数组

这道题自己想了想，写了几种，都是错的。还是去看题解了- -

大致的思路如下：

  1. 先将整个数组全部反转
  2. 反转前 k 个数据
  3. 反转后 k 个数据

然后还看到一个很高级的环形旋转，没怎么仔细去看，打算二刷的时候再去看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k %= nums.length

  reverse(nums, 0, nums.length - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, nums.length - 1)
}

const reverse = function (nums, start, end) {
  while (start < end) {
    const temp = nums[start]
    nums[start] = nums[end]
    nums[end] = temp
    start += 1
    end -= 1
  }
}

4.存在重复元素

这道题，自己终于想到了一个解法，虽然提交之后排名不尽人意，但好歹还是做出来了…

自己想到的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  const singeArr = []

  let isDuplicate = false

  for (let i = 0; i < nums.length; i++) {
    if (singeArr.includes(nums[i])) {
      isDuplicate = true
    } else {
      singeArr.push(nums[i])
    }
  }

  return isDuplicate
}

题解思路里面有一个很简单的方法，利用 Set 数据结构的唯一性，去除掉数组中的重复数据，然后通过 Array 转换，对比前后数组的长度就行。

1
2
3
4
5
6
7
8
9
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  const newNums = Array.from(new Set(nums))

  return newNums.length !== nums.length
}

上面的方法我觉得已经很好了，然后我又看到一个比较常规的，首先对数组进行排序，然后判断数组中相邻的数字是否相同就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  nums.sort((a, b) => a - b)

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) return true
  }

  return false
}

5.只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  // return nums.reduce((a, b) => a ^ b) // 最厉害的解法 按位异或运算

  const set = new Set()

  for (let i = 0; i < nums.length; i++) {
    set.has(nums[i]) ? set.delete(nums[i]) : set.add(nums[i])
  }

  return Array.from(set)[0]
}

6.两个数组的交集 Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
  const result = []

  let i = 0,
    n = 0

  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)

  while (i < nums1.length && n < nums2.length) {
    if (nums1[i] < nums2[n]) {
      i++
    } else if (nums1[i] > nums2[n]) {
      n++
    } else {
      result.push(nums1[i])
      i++
      n++
    }
  }

  return result
}

7.加一

刚开始还觉得这道题的确蛮简单，自己想到的思路是将数组拼成字符串，然后转成数字加一，在分割成数组，测试了一下，都通过了。但是在提交的时候，发现数字长度太大了，超出了 JavaScript 的数值范围，这就很尴尬了。

后来又想了一项，发现可以通过倒着遍历数组，最简单的情况便是最后一位加一就可。可是很快就发现问题，对于可以进位的数字，也就是 9，加一之后进一，这块想了很久，一直在考虑不断进位的该怎么写，然后看了别人写的题解，发现真的是陷进去了，想复杂了。对于不等于 9 的数字，直接加一然后返回当前数组就可，等于 9 的，使其为 0 即可。至于都要进位的，那么必然是 1 开头的，后面全都是 0。举个例子：[9,9,9]加一之后肯定是[1,0,0,0]。那么数组的长度便是传进来的数组长度加一，数组的值可以先全部设置为 0，然后将第一位设置为 1 就可以了。

第一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] !== 9) {
      digits[i] += 1
      return digits
    } else {
      digits[i] = 0
    }
  }

  return [1, ...new Array(digits.length).fill(0)]
}

第二种写法，区别不大，就是少开辟了一个数组空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] !== 9) {
      digits[i] += 1
      return digits
    } else {
      digits[i] = 0
    }
  }

  const arr = new Array(digits.length).fill(0)
  arr[0] = 1

  return arr

这种写法是别人写的，大体思路和上面说的差不多，只不过更加简洁，并且是原地算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  let carry = false
  digits[digits.length - 1]++
  for (let i = digits.length - 1; i >= 0; i--) {
    if (carry) digits[i]++
    carry = digits[i] > 9
    digits[i] %= 10
  }
  if (carry) digits.unshift(1)
  return digits
}

8.移动零

利用双指针就可以做出来，通过循环，把不是零的数字往后靠。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let index = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      let temp = nums[index]
      nums[index] = nums[i]
      nums[i] = temp
      index++
    }
  }
}

9.两数之和

两数之和是力扣的第一题，当初使用两个 for 循环做的，暴力破解，然后又用双指针试了一下，发现和暴力破解的做法差不多；看了别人写的题解，可以用哈希表来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map()

  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    } else {
      map.set(nums[i], i)
    }
  }
}

10.有效的数独

11.旋转图像

字符串

1.反转字符串

思路非常简单，利用双指针解决，左指针为 0，右指针为数组长度-1，然后对称交换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let i = 0,
    j = s.length - 1

  while (i <= j) {
    let temp = s[i]
    s[i] = s[j]
    s[j] = temp
    i++
    j--
  }
}

也可以利用JavaScript数组中的reverse方法直接反转，比较骚的操作。

1
2
3
4
5
6
7
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  s.reverse()
}