代码随想录刷题记录 Day1

发表于 更新于 本文字数： 5.7k 阅读时长 ≈ 21 分钟

To Do List

  • 数组的算法理论知识

  • 二分查找基础

  • LeetCode 704. 二分查找 / Binary Search

  • 704 题扩展题目

  • 双指针法查找基础

  • LeetCode 27. 移除元素 / Remove Elements

  • 27 题扩展题目

  • 总结 / Summary

1. 数组的算法理论知识

1 数组可以通过数组的下标索引方式，获取下标下相对应的数据

2 数组的索引从 0 开始，存储数据时是从 0 下标开始，顺序存储（而不是从 1 开始）。以 Java 为例（如图）

3 对数组进行数据的操作：

增：

1
2
3
1 先在数组末尾分配内存空间；
2 将目标位置以及后面位置的元素对应的内存地址及下标往后移动（指将元素对应的内存地址修改为后一位的内存地址）；
3 将元素写入到目标位置中（写入元素之前的目标位置是空着的，但是内存地址和下标没有变）。

删：

1
2
3
4
首先要注意，数组中的元素不能直接删除！
要想对目标元素进行删除，
1 先将指定下标索引下元素后面的每一个元素的内存地址修改至前一个下标对应的内存地址，此时操作完后末尾的位置没有数据了，但是内存地址仍旧存在
2 将数组末尾位置的内存空间进行释放，即可完成删除操作。

查：

1
直接通过下标索引查找目标位置，获取内存地址下对应的数据。

改：

1
2
直接通过下标索引查找目标位置，将目标位置对应的数据修改即可。
整个过程没有内存地址的任何变动，只动地址下面的数据。

总结：

增删操作需要对元素数据对应的内存地址进行修改以完成操作，故操作速度慢；

查改操作只需通过下标索引查找目标位置进行相应的操作，故操作速度快。

时间复杂度：访问和修改操作为 O(1)，添加和删除操作 O(n)

4 除了一维数组，还有更复杂的二维数组。

二维数组的内存地址是否连续，取决于不同编程语言的内存管理机制。像 C++ 的二维数组是连续分布的（第一行数组后面就接着第二行数组），Java 的数组的内存地址经过处理，没法看到具体的数组内存地址（JavaScript 同理）。

2. 二分查找基础

二分查找法的基本原理：（手写）

这种查找方法还是有一定的局限性，就是数据必须是排序的（无论是升序还是降序），如果数据没有进行排序，需要进行排序才能使用这个二分查找法。

难度：简单

题目要求：

（CN）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

（EN）

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1 / 示例 1:

1
2
3
4
5
6
7
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

Example 2 / 示例 2:

1
2
3
4
5
6
7
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

Constraints / 提示:

  • *1 <= nums.length <= 10^4*（元素的个数在[1, 10000]之间）
  • -10^4 < nums[i], target < 10^4（nums 的每个元素都将在 [-9999, 9999]之间。）
  • All the integers in nums are unique.（nums 中的所有元素是不重复的**）
  • nums is sorted in ascending order. （数组内的元素是升序排序的。）

3.1 解法

这里注意使用二分法即可，我这里区间用了左闭右闭。

3.1.1 左闭右闭

Java：

（For Leetcode / IDEA Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public static int search(int[] nums, int target) {

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int middle = (right + left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] == target) {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{-1, 0, 3, 5, 9, 12},9));
        System.out.println(search(new int[]{-1, 0, 3, 5, 9, 12},2));
    }
}

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */var search = function(nums, target) {
        let left = 0;
        let right = nums.length - 1


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

    console.log(search([-1,0,3,5,9,12],9))
    console.log(search([-1,0,3,5,9,12],2))

3.1.2 左闭右开

也可以使用左闭右开的方式：

Java：

（For Leetcode / IDEA Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public static int search(int[] nums, int target) {

        int left = 0, right = nums.length;

        while (left < right) {
            int middle = (right + left) / 2;
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] == target) {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{-1, 0, 3, 5, 9, 12},9));
        System.out.println(search(new int[]{-1, 0, 3, 5, 9, 12},2));
    }
}

JavaScript:

（For Leetcode / WebStorm Custom）

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
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
        let left = 0;
        let right = nums.length - 1


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


    console.log(search([-1,0,3,5,9,12],9))
    console.log(search([-1,0,3,5,9,12],2))

4. 704 题扩展题目

4.1 LeetCode 35. 搜索插入位置 / Search Insert Position

难度：简单

题目要求：

（CN）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

（EN）

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

1
2
3
4
5
Input: nums = [1,3,5,6], target = 5
Output: 2

输入: nums = [1,3,5,6], target = 5
输出: 2

Example 2:

1
2
3
4
5
Input: nums = [1,3,5,6], target = 2
Output: 1

输入: nums = [1,3,5,6], target = 2
输出: 1

Example 3:

1
2
3
4
5
Input: nums = [1,3,5,6], target = 7
Output: 4

输入: nums = [1,3,5,6], target = 7
输出: 4

Constraints / 提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order. (nums 为 无重复元素 的 升序 排列数组)
  • -10^4 <= target <= 10^4

与第 704 题类似，都是查找位置，但是这题又分以下情况来讨论：

（1）如果待插入的目标值恰好在有序数组里面，那么查询成功后直接输出目标值在数组中的位置即可。这是最简单的情况。

（2）如果待插入的目标值在有序数组的第一个元素之前，虽然 middle 值输出为 -1（即找不到），但是目标值排序后为有序数组的第一个元素之前，则输出插入的位置在第 0 个，即 -1 + 1 = 0. 这也是最简单的情况。

（3）如果待插入的目标值不在有序数组里面，但是排序后又在数组中的两个元素之间，则输出右边界的最近一次更改后的位置，并且 + 1，这样即为目标值将要插入数组的位置。

（4）如果待插入的目标值排序后在有序数组的最后一个元素之后，因为是右闭区间，则直接输出 nums.length 的值即可。

4.1.1 左闭右闭

Java：

（For Leetcode / IDEA Custom）

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
class Solution {

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int middle = (right + left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] == target) {
                return middle;
            }
        }

        return right + 1;
    }

   public static void main(String[] args) {
       System.out.println(searchInsert(new int[]{1,3,5,6},5));
       System.out.println(searchInsert(new int[]{1,3,5,6},2));
       System.out.println(searchInsert(new int[]{1,3,5,6},7));
   }
}

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0, right = nums.length - 1

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

    return right + 1
};

console.log(searchInsert([1,3,5,6],5))
console.log(searchInsert([1,3,5,6],2))
console.log(searchInsert([1,3,5,6],7))

4.1.2 左闭右开

Java：

（For Leetcode / IDEA Custom）

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
class Solution {

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;

        while (left < right) {
            int middle = (right + left) / 2;
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] == target) {
                return middle;
            }
        }

        return right;
    }

   public static void main(String[] args) {
       System.out.println(searchInsert(new int[]{1,3,5,6},5));
       System.out.println(searchInsert(new int[]{1,3,5,6},2));
       System.out.println(searchInsert(new int[]{1,3,5,6},7));
   }
}

JavaScript:

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0, right = nums.length

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

    return right
};

console.log(searchInsert([1,3,5,6],5))
console.log(searchInsert([1,3,5,6],2))
console.log(searchInsert([1,3,5,6],7))

4.2 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 / Find First and Last Position of Element in Sorted Array

难度：中等

题目要求：

（CN）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

（EN）

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

1
2
3
4
5
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

Example 2:

1
2
3
4
5
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

Example 3:

1
2
3
4
5
Input: nums = [], target = 0
Output: [-1,-1]

输入：nums = [], target = 0
输出：[-1,-1]

Constraints / 提示:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non-decreasing array. (nums 是一个非递减数组)
  • -10^9 <= target <= 10^9

这道题的输出结果并不是一个单独值，而是一个包含两个已知值的元素集合 {x0,x}. 所以可以分以下情况来讨论：

（1）如果待插入的目标值恰好在有序数组范围之外，则直接输出 {-1, -1}，即不存在。

（2）如果待插入的目标值在有序数组的范围之内，但是目标值不在数组内，则直接输出 {-1, -1}，即不存在。

（3）如果待插入的目标值在有序数组范围之内，目标值也恰好存在数组内（一个即以上），则输出目标值在数组的首末位集合 {x0,x}.

故此题最好使用至少两个二分函数来分别求解左边界和右边界，如果不是高手就不要尝试单独一个函数来解左右边界了，容易出错。

4.2.1 解法

Java：

（For Leetcode / IDEA Custom）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {

    public static int findRight(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int rBorder = -2;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
                rBorder = l;
            }
        }
        return rBorder;
    }

    public static int findLeft(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int lBorder = -2;
        while (l <= r) {
            int mid = (r + l) / 2;
            if(nums[mid] >= target){
                r = mid - 1;
                lBorder = r;
            } else l = mid + 1;
        }
        return lBorder;
    }
    public static int[] searchRange(int[] nums, int target) {
        int lBorder = findLeft(nums, target);
        int rBorder = findRight(nums, target);

        if(lBorder == -2 || rBorder == -2) {
            return new int[]{-1,-1};
        }
        else if(rBorder - lBorder > 1){
            return new int[]{lBorder + 1, rBorder - 1};
        }
        else return new int[]{-1,-1};

    }

    public static void main(String[] args) {
        System.out.println(searchRange(new int[]{5, 7, 7, 8, 8, 10},4));
        System.out.println(searchRange(new int[]{5, 7, 7, 8, 8, 10},4));
        System.out.println(searchRange(new int[]{},0));
        //        System.out.println(searchInsert(new int[]{1,3,5,6},7));
    }
}

JavaScript：

（For Leetcode / WebStorm Custom）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var findLeft = function(nums, target) {
    let left = 0
    let right = nums.length - 1
    let leftBorder = -2;

    while (left <= right) {
        let middle = Math.floor((left + right) / 2)
        if (nums[middle] < target) {
            left = middle + 1
        } else {
            right = middle - 1
            leftBorder = right
        }
    }

    return leftBorder
}

var findRight = function(nums, target) {
    let left = 0;
    let right = nums.length - 1
    let rightBorder = -2;

    while (left <= right) {
        let middle = Math.floor((left + right) / 2)

        if (nums[middle] <= target) {
            left = middle + 1
            rightBorder = left
        }
        else {
            right = middle - 1
        }
    }

    return rightBorder
}

var searchRange = function(nums, target) {
    let leftBorder = findLeft(nums,target)

    let rightBorder = findRight(nums, target)

    if (leftBorder === -2 || rightBorder === -2) {
        return [-1,-1]
    } 
    else if (rightBorder - leftBorder > 1) {
        return [leftBorder + 1, rightBorder - 1]
    }
    else return [-1,-1]
};

console.log(searchRange([5,7,7,8,8,10],6))
console.log(searchRange([5,7,7,8,8,10],6))
console.log(searchRange([],0))

4.3 LeetCode 69. x 的平方根 / Sqrt(x)

难度：简单

题目要求：

（CN）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

（EN）

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

1
2
3
4
5
6
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

输入：x = 4
输出：2

Example 2:

1
2
3
4
5
6
7
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

Constraints / 提示:

  • 0 <= x <= 2^31 - 1

注意，

（0）不要直接用目标值来作为右边界，正确的做法是将目标值除以 2；另外还需加 1，因为 Java 的除法会向下取整，会造成目标值为 1 的时候解答错误：（JavaScript 反而没有这种问题）

（1）如果使用 mid*mid<(>)x 这个判定条件，会卡在第 14 个用例，因为超大数与超大数相乘过大必会造成整型溢出。

屏幕截图 2023-02-17 165941

（2）不添加 x <= 0 的判定条件的话，会直接判定执行出错，因为除数不能为 0

屏幕截图 2023-02-17 170510

所以把判定条件改成 mid <(>) x / mid，添加 x <= 0 和 x == 1 的判定条件即可通过：

屏幕截图 2023-02-17 170641

解法参考：Link

4.3.1 左闭右闭

Java：

（For Leetcode / IDEA Custom）

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
29
30
31
32
class Solution {

    public static int mySqrt(int x) {
        int left = 0, right = (x / 2) + 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (x <= 0) {
                return 0;
            }
            if (x == 1) {
                return 1;
            }
            if (mid == x / mid) {
                return mid;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else if (mid < x / mid) {
                left = mid + 1;
            }

        }

        return right;
    }

     public static void main(String[] args) {
         System.out.println(mySqrt(4));
         System.out.println(mySqrt(8));
         System.out.println(mySqrt(2147395599));
 //        System.out.println(searchInsert(new int[]{1,3,5,6},7));
     }
}

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0;
    let right = x

    while (left <= right) {
        let middle = Math.floor((left + right) / 2)

        if (middle * middle < x) {
            left = middle + 1
        } else if (middle * middle > x) {
            right = middle - 1
        } else return middle
    }
    return right
};

console.log(mySqrt(4))
console.log(mySqrt(8))
// console.log(searchInsert([1,3,5,6],7))

4.3.2 左闭右开

Java：

（For Leetcode / IDEA Custom）

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
29
30
31
32
class Solution {

    public static int mySqrt(int x) {
        int left = 0, right = (x / 2) + 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (x <= 0) {
                return 0;
            }
            if (x == 1) {
                return 1;
            }
            if (mid == x / mid) {
                return mid;
            } else if (mid > x / mid) {
                right = mid;
            } else if (mid < x / mid) {
                left = mid + 1;
            }

        }

        return right - 1;
    }

     public static void main(String[] args) {
         System.out.println(mySqrt(4));
         System.out.println(mySqrt(8));
         System.out.println(mySqrt(2147395599));
 //        System.out.println(searchInsert(new int[]{1,3,5,6},7));
     }
}

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0;
    let right = x + 1

    while (left < right) {
        let middle = Math.floor((left + right) / 2)

        if (middle * middle < x) {
            left = middle + 1
        } else if (middle * middle > x) {
            right = middle
        } else return middle
    }
    return right - 1
};

console.log(mySqrt(4))
console.log(mySqrt(8))
// console.log(searchInsert([1,3,5,6],7))

4.4 LeetCode 367. 有效的完全平方数 / Valid Perfect Square

难度：简单

题目要求：

（CN）

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

（EN）

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Example 1:

1
2
3
4
5
6
7
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

Example 2:

1
2
3
4
5
6
7
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

Constraints / 提示:

  • 1 <= num <= 2^31 - 1

要注意：

（1）测试用例有大数，定义变量要使用长整型 long （Java 专属）

（2）1 一定是完全平方数，可以加个判定条件，让其直接返回 true 即可。

4.4.1 左闭右闭

Java：

（For Leetcode / IDEA Custom）

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
29
30
31
32
class Solution {

    public static boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }

        long l = 0, r = num;
        while (l <= r) {
            long mid = (l + r) / 2;
            if ((mid*mid) == num) {
                return true;
            }
            else {
                if ((mid*mid) < num) {
                    l = mid + 1;
                }
                else if ((mid*mid) > num) {
                    r = mid - 1;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(14));
        System.out.println(isPerfectSquare(16));
//        System.out.println(isPerfectSquare(new int[]{},0));
//        System.out.println(searchInsert(new int[]{1,3,5,6},7));
    }
}

JavaScript：

（For Leetcode / WebStorm Custom）

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
29
30
31
32
33
34
35
36
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var isPerfectSquare = function(num) {
    if (num === 1) {
        return true
    }

    let left = 0;
    let right = num;

    while (left <= right) {
        let middle = left + Math.floor((right - left) / 2)

        if (num === middle * middle) {
            return true
        }
        if (num > middle * middle) {
            left = middle + 1
        } else if (num < middle * middle) {
            right = middle - 1
        } else {
            return true
        }
    }
    return false
};

console.log(isPerfectSquare(14))
console.log(isPerfectSquare(16))
// console.log(isPerfectSquare([],0))


4.4.2 左闭右开

Java：

（For Leetcode / IDEA Custom）

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
29
30
31
32
class Solution {

    public static boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }

        long l = 0, r = num + 1;
        while (l < r) {
            long mid = (l + r) / 2;
            if ((mid*mid) == num) {
                return true;
            }
            else {
                if ((mid*mid) < num) {
                    l = mid + 1;
                }
                else if ((mid*mid) > num) {
                    r = mid;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(14));
        System.out.println(isPerfectSquare(16));
//        System.out.println(isPerfectSquare(new int[]{},0));
//        System.out.println(searchInsert(new int[]{1,3,5,6},7));
    }
}

JavaScript：

（For Leetcode / WebStorm Custom）

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
29
30
31
32
33
34
35
36
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var isPerfectSquare = function(num) {
    if (num === 1) {
        return true
    }

    let left = 0;
    let right = num + 1;

    while (left < right) {
        let middle = left + Math.floor((right - left) / 2)

        if (num === middle * middle) {
            return true
        }
        if (num > middle * middle) {
            left = middle + 1
        } else if (num < middle * middle) {
            right = middle
        } else {
            return true
        }
    }
    return false
};

console.log(isPerfectSquare(14))
console.log(isPerfectSquare(16))
// console.log(isPerfectSquare([],0))


5. 双指针法算法基础

6. LeetCode 27. 移除元素 / Remove Elements

难度：简单

题目要求：

（CN）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

*不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。*

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

（EN）

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

Example 2:

1
2
3
4
5
6
7
8
9
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

Constraints / 提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

6.1 解法

使用双指针之快慢指针法。

Java：

（For Leetcode / IDEA Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {

    public static int removeElement(int[] nums, int val) {
        int s = 0;
        for (int f = 0;f < nums.length;f++) {
            if(nums[f] != val) {
                nums[s++] = nums[f];
            }
        }
        return s;
    }

    public static void main(String[] args) {
        System.out.println(removeElement(new int[]{3,2,2,3}, 3));
        System.out.println(removeElement(new int[]{0,1,2,2,3,0,4,2},2));
    }
}

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let s = 0;
    for (let f = 0; f < nums.length; f++) {
        if (nums[f] != val) {
            nums[s++] = nums[f];
        }
    }
    return s;
};

console.log(removeElement([3,2,2,3],3))
console.log(removeElement([0,1,2,2,3,0,4,2],2))


7. 27 题扩展题目

（后面再补，时间不够了(((）

7.1 LeetCode 26. 删除有序数组中的重复项 / Remove Duplicates from Sorted Array

难度：简单

要求：

给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 升序 排列

7.1.1 解法

JavaScript：

（For Leetcode / WebStorm Custom）

1
2
3
4
5
6
7
8
9
10
var removeDuplicates = function (nums) {
    if (nums.length === 0) return 0
    var s = 1;
    for (var f = 1; f < nums.length; f++) {
        if (nums[f] != nums[f - 1]) {
            nums[s++] = nums[f]
        }
    }
    return s
}

8. 总结 / Summary

认识了数组的结构与操作，了解了二分法和双指针法的原理。

完成 LeetCode 题数：6