概述

学习自代码随想录，一些自己的记录和整理，题目来自力扣 (LeetCode) 全球极客挚爱的技术成长平台

基础

  • 数组是存放在连续内存空间上的相同类型数据的集合
  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的
  • 在C++中二维数组在地址空间上是连续的

二分查找

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

例1：

输入： nums = [-1, 0, 3, 5, 9, 12], target = 9

输出： 4

例2：

输入： nums = [-1, 0, 3, 5, 9, 12], target = 2

输出： -1

写法

  • 左闭右闭写法
  • 左闭右开写法

根本在于设置的区间，更新区间后要求查找的值一定在这个区间里，如对于左闭右闭区间，更新只能是mid = left + 1或者mid = right - 1（前提，if不包括等于），因为如果为mid = left或mid = right，则把已经确定了不是的位置，还保留在了搜索区间里

也可以是其他写法，可以视情况而定

此外推荐如下找mid的写法，避免溢出

int mid = left + (right - left) / 2;

左闭右闭

[left, right] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target){
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

左闭右开

[left, right) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target){
            right = mid;
        } else {
            return mid;
        }
    }
    return -1;
}

题目

  • 搜索插入位置（🟩）[2]
  • x的平方根（🟩）[3]
  • 有效的完全平方数（🟩）[4]
  • 在排序数组中查找元素的第一个和最后一个位置（🟨）[5]

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。必须使用时间复杂度为 O(log n) 的算法

例1：

输入： nums = [1, 3, 5, 6], target = 5

输出： 2

例2：

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

输出： 1

例3：

输入： nums = [1, 3, 5, 6], target = 7

输出： 4

💡思考

二分查找其所在位置，多了个如果不存在，则返回应该被插入的位置，其实就是返回left

📘答案

搜索插入位置 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target){
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return left;
}

x的平方根

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

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

例1：

输入： x = 4

输出： 2

例2：

输入： x = 8

输出： 2

💡 思考

二分查找这个数即可，注意边界条件

📘 答案

x的平方根 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int mySqrt(int x) {
        int l = 1, r = x;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid < x) {
                l = mid + 1;
            } else if ((long long)mid * mid > x) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return r;
    }
};

🔍 其他写法

数学

思路来源于使用指数函数 $e$ 和对数函数 $ln$ 代替平方根的办法

$$
\sqrt{x}=x^{\frac{1}{2}}=(e^{\ln\ x})^{\frac{1}{2}}
$$

x的平方根-数学 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

牛顿法

牛顿迭代法是用来快速求解函数零点的方法，对于本题，就是找 $y=f(x)=x^{2}-C$ 的解，即 $C$ 为本题中的 $x$

通过设置初值 $x_{0}$ ，来找到这个函数上对应的点，然后在该点作一条斜率为该点导数的线，交 $x$ 轴于 $x_{1}$ 点，再重复以上操作，直到 $x_{n}$ 极为接近真实的 $\sqrt{C}$ ，如下图所示（源于69. x 的平方根 - 力扣（LeetCode））

fig1

通过数学推导，可以得到 $x_{i+1}$ 和 $x_{i}$ 的关系如下：
$$
x_{i+1}=\frac{1}{2}(x_{i}+\frac{C}{x_{i}})
$$

  1. 选择 $x_{0}=C$ 作为初始值的原因是因为该函数存在两个零点，一个正一个负，选择一个较小的值，可能会迭代到负的那个，那不是我们要的答案
  2. 迭代到两次迭代的误差非常小时，即可停止迭代
  3. 数学推导得知选择初始值大于等于 $\sqrt{C}$ 时，每次得到的 $x_{i}$ 都对大于等于 $\sqrt{C}$ ，所以只要选取的误差 $\epsilon$ 足够小，就不会得到错误的情况
牛顿法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};

有效的完全平方数

给你一个正整数num。如果num是一个完全平方数，则返回true，否则返回false。
完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如sqrt

例1：

输入： nums = 16

输出： true

例2：

输入： nums = 14

输出： false

💡 思考

直接二分查找即可，等于则true

📘答案

有效的完全平方数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid < num) {
                l = mid + 1;
            } else if ((long long)mid * mid > num) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return false;
    }
};

在排序数组中查找元素的第一个和最后一个位置

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

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

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

例1：

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

输出： [3, 4]

例2：

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

输出：[-1, -1]

例3：

输入： nums = [], target = 0

输出：[-1, -1]

💡 思考

分解成两步来看，第一步找到这个数第一次出现的位置，第二步找到比这个数大1的数第一次出现的位置（可能不存在）

首先排除最特殊的情况，target不在nums范围内，可以在最开始就加一个判断即可

思考第一步的做法，此时target必须在nums范围里，且存在，那么第一步可以理解为二分找一个比target小的左闭右开的区间，这样最终的r就是target出现的位置，每次的mid如果比target小，则l = mid+1，如果大于等于target，则r=mid，不断确保在[l, r)区间内，都是比target小的，这样最终退出循环时，l = r，且此时r即为第一个等于target的数，返回即可

考虑特殊情况，如果nums不存在target，但target在nums的最大最小值范围内，那么最终的r会是比target小的最后一个数。此时可在外部通过判断此时该位置是否为target即可

对于第二个位置，则找比target + 1小的左闭右开的区间，此时r即为小于等于target + 1的第一个数，返回后做减一即可

其实就是c++里的lower_bound函数，在指定区域内查找不小于目标值的第一个元素，我的代码不是完全的lower_bound实现

📘答案

在排序数组中查找元素的第一个和最后一个位置 
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
class Solution {
public:
    int lower_bound(vector<int> &nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] >= target) {
                r = mid;
            } 
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0 || nums[nums.size()-1] < target || nums[0] > target) {
            return {-1, -1};
        }
        vector<int> ans(2);
        int first = lower_bound(nums, target);
        if (nums[first] != target) {
            return {-1, -1};
        } else {
            int second = lower_bound(nums, target + 1);
            return {first, second - 1};
        }
    }
};

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量[6]。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

例 1：

输入：nums = [3, 2, 2, 3], val = 3

输出： 2, nums = [2, 2, _, _]

解释： 返回 k = 2, 并且 nums 中的前两个元素均为 2。

例 2：

输入：nums = [0, 1, 2,2, 3, 0, 4, 2], val = 2

输出： 5, nums = [0, 1, 4, 0, 3, _, _, _]

解释： 返回 k = 2, 并且 nums 中的前五个元素为 0, 0, 1, 3, 4。这五个元素可以任意顺序返回

写法

由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，所以可以把输出的数组直接写在输入数组上。使用双指针：右指针 right指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置

双指针 
1
2
3
4
5
6
7
8
9
10
11
12
13
public:
	int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};
上面写法问题在于如果针对[1,2,3,4,5]，当val等于1时，需要移动4次，可以把双指针一个首一个尾放置
优化双指针 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

以及我的交换写法（菜），异或交换时要注意不能相同位置交换，否则会归零

交换元素 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void swap(int *a, int *b) {
        if (a == b) {
            return;
        }
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
    int removeElement(vector<int>& nums, int val) {
        int idx = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                swap(&nums[++idx], &nums[i]);
            } 
        }
        return idx + 1;
    }
};
## 题目
  • 删除有序数组中的重复项（🟩）[7]
  • 移动零（🟩）[8]
  • 比较含退格的字符串（🟩）[9]
  • 有序数组的平方（🟩）[10]

删除有序数组中的重复项

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

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

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

例1：

输入： nums = [1, 1, 2]

输出： 2, nums = [1, 2, _]

例2：

输入： nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

输出： 5, nums = [0, 1, 2, 3, 4]

💡思考

双指针简单题

📘答案

删除有序数组中的重复项 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 1) {
            return 1;
        }
        int left = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[left]) {
                continue;
            } else {
                nums[++left] = nums[i];
            }
        }
        return ++left;
    }
};

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作

例1：

输入： nums = [0, 1, 0, 3, 12]

输出： [1, 3, 12, 0, 0]

例2：

输入： nums = [0]

输出：[0]

💡思考

只保留非零元素再填充零即可

📘答案

移动零 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[++left] = nums[i];
            }
        }
        for (int i = left + 1; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符

**注意：**如果对空文本输入退格字符，文本继续为空

例1：

输入： s = “ab#c”, t = “ad#c”

输出： true

例2：

输入： s = “ab##”, t = “c#d#”

输出： true

例3：

输入： s = “a#c”, t = “b”

输出： false

💡思考

把不被删除的字符覆盖前面的，并注意特殊情况即可，leetcode的解法是逆序遍历，遇到#则做处理

📘答案

比较含退格的字符串 
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
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int left1 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != '#') {
                s[left1++] = s[i];
            } else if (left1 > 0) {
                left1--;
            }
        }
        int left2 = 0;
        for (int i = 0; i < t.length(); i++) {
            if (t[i] != '#') {
                t[left2++] = t[i];
            } else if (left2 > 0) {
                left2--;
            }
        }
        if (left1 != left2) return false;
        for (int i = 0; i < left1; i++) {
            if (s[i] != t[i]) {
                return false;
            }
        }
        return true;
    }
};

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序

例1：

输入： nums = [-4, -1, 0, 3, 10]

输出： [0, 1, 9, 16, 100]

例2：

输入： nums = [-7, -3, 2, 3, 11]

输出： [4, 9, 9, 49, 121]

💡思考

要么平方后直接sort，要么就根据这个非递减的性质，然后一个首指针，一个末尾指针，来比较排序

📘答案

有序数组的平方 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = nums[i] * nums[i];
        }
        int i = 0, j = nums.size() - 1;
        vector<int> res(nums.size());
        int idx = nums.size() - 1;
        while (i <= j) {
            if (nums[i] >= nums[j]) {
                res[idx--] = nums[i++];
            } else {
                res[idx--] = nums[j--];
            }
        }
        return res;
    }
};

引用

  1. 704. 二分查找 - 力扣（LeetCode） ↩︎

  2. 35. 搜索插入位置 - 力扣（LeetCode） ↩︎

  3. 69. x 的平方根 - 力扣（LeetCode） ↩︎

  4. 367. 有效的完全平方数 - 力扣（LeetCode） ↩︎

  5. 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） ↩︎

  6. 27. 移除元素 - 力扣（LeetCode） ↩︎

  7. 26. 删除有序数组中的重复项 - 力扣（LeetCode） ↩︎

  8. 283. 移动零 - 力扣（LeetCode） ↩︎

  9. 844. 比较含退格的字符串 - 力扣（LeetCode） ↩︎

  10. 977. 有序数组的平方 - 力扣（LeetCode） ↩︎