1. 数组理论基础:
数组是一种基础的数据结构,表示存放在连续内存空间上的相同类型数据的集合,集合中的元素通过下标索引访问。
数组的基本概念:
- 索引(Index):数组中元素的位置编号,一般从0开始
- 长度(Length):数组中元素的总个数,一旦创建就不可改变(动态数组除外)
- 元素(Element):数组中存储的具体数据
数组的特点:
- 访问速度快:通过索引可以直接访问元素,时间复杂度为O(1)
- 插入/删除效率低:在中间位置插入或删除元素时,需要移动其他元素
- 数组的元素是不能删的,只能覆盖
2. 二分查找(leetcode704
)
题目描述:给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果 target
存在返回下标,否则返回 -1
。你必须编写一个具有 O(log n)
时间复杂度的算法。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设
nums
中的所有元素是不重复的。 n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
思路
使用二分法的前提条件:
- 有序数组
- 无重复元素
循环不变量原则:
在二分查找的过程中,区间的定义就是不变量,每一次边界处理都要坚持根据区间的定义来操作。二分法的区间定义有两种:左闭右闭,左闭右开。
①定义target在[left, right]区间
int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] < target) {left = mid + 1;}else if (nums[mid] > target) {right = mid - 1;}else {return mid;}}return -1;
}
②定义target在[left, right)区间
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;
}
3.选择插入位置(leetcode35
)
题目描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
为 无重复元素 的 升序 排列数组-104 <= target <= 104
思路
nums
为无重复元素的升序排列数组,满足二分法的使用条件。- 目标值存在4种情况:
- 目标值在数组所有元素之前
- 目标值等于数组中某一个元素
- 目标值插入数组中的某一位置
- 目标值在数组所有元素之后
①在区间[left, right]上搜索
int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = left + ((right - left) >> 1);if(target < nums[mid]) {right = mid - 1;}else if(target > nums[mid]) {left = mid + 1;}else {return mid;}}// 目标值在数组所有元素之前 [0, -1] return right + 1// 目标值等于数组中某一位置 return mid// 目标值插入数组中的某一位置 [left, right] return right + 1// 目标值在数组所有元素之后 [left, right] return right + 1return right + 1;
}
②在区间[left, right)上搜索
int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while(left < right) {int mid = left + ((right - left) >> 1);if(target < nums[mid]) {right = mid;}else if(target > nums[mid]) {left = mid + 1;}else {return mid;}}// 目标值在数组所有元素之前 [0, 0) return right + 1// 目标值等于数组中某一位置 return mid// 目标值插入数组中的某一位置 [left, right) return right// 目标值在数组所有元素之后 [left, right) return rightreturn right;
}
4.在排序数组中查找元素的第一个和最后一个位置(leetcode34
)
题目描述:给你一个按照非递减顺序排列的整数数组 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]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
思路
-
特点:数组非递减顺序排列,存在重复元素
-
寻找target的左右边界,有如下三种情况:
-
target在数组范围的左边或右边,例如数组{3, 4, 5},target为2或者target为6,此时应该返回
-
target在数组范围内,且数组中不存在target,例如数组{3, 6, 7},target为5,此时应该返回
-
target在数组范围中,且数组中存在target,例如数组{3, 6, 7},target为6,此时应该返回
-
-
二分法能够找到某个元素的索引,但无法判断重复元素的索引范围,需要制定新的搜索策略。
- 策略1:线性逼近法。在找到某个目标元素的索引后,左边界和右边界向中间试探移动,直到
nums[left] == nums[right]
。 - 策略2:分别寻找左右边界。使用两遍二分法,分别找到左边界和右边界。原始二分法,在找到某个目标元素的索引后,就直接退出了;现在仍然移动左右边界,直到不满足边界条件。
- 策略3:中间向两边搜索。先使用二分法,找到某个目标元素的索引,然后向两边搜索,直到
nums[left] != target
且nums[right] != target
。
- 策略1:线性逼近法。在找到某个目标元素的索引后,左边界和右边界向中间试探移动,直到
策略①
vector<int> searchRange(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (target > nums[mid]) {left = mid + 1;}else if (target < nums[mid]) {right = mid - 1;}else {if (nums[left] == nums[right]){return {left, right};}if (nums[left] != target) {left++;}if (nums[right] != target) {right--;}}}return {-1, -1};
}
策略②
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;// 记录一下rightBorder没有被赋值的情况int rightBorder = -2; while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界,nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;// 记录一下leftBorder没有被赋值的情况int leftBorder = -2; while (left <= right) {int middle = left + ((right - left) / 2);// 寻找左边界,nums[middle] == target的时候更新rightif (nums[middle] >= target) { right = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};
策略③
class Solution {public int[] searchRange(int[] nums, int target) {int index = binarySearch(nums, target); // 二分查找// nums 中不存在 target,直接返回 {-1, -1}if (index == -1) { return new int[] {-1, -1}; // 匿名数组 }// nums 中存在 target,则左右滑动指针,来找到符合题意的区间int left = index;int right = index;// 向左滑动,找左边界// 防止数组越界。逻辑短路,两个条件顺序不能换while (left - 1 >= 0 && nums[left - 1] == nums[index]) { left--;}// 向右滑动,找右边界// 防止数组越界。while (right + 1 < nums.length && nums[right + 1] == nums[index]) {right++;}return new int[] {left, right};}/*** 二分查找* @param nums* @param target*/public int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1; // 不变量:左闭右闭区间while (left <= right) { // 不变量:左闭右闭区间int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1; // 不变量:左闭右闭区间}}return -1; // 不存在}
}
4.移除元素(leetcode27
)
题目描述:给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素。元素的顺序可能发生改变。然后返回 nums
中与 val
不同的元素的数量。假设 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。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3,_,_,_]
解释:你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
思路
- 数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
- 移除某元素涉及数组其它元素的移动,总共有三种思路:
- 排序法。先排序,然后将相同的元素一起移除。
- 快慢指针法。快指针遍历数组元素,慢指针移除元素,更新数组。
- 暴力法。外循环遍历数组,寻找待删除的元素,内循环更新数组。
①排序法
int removeElement(vector<int>& nums, int val) {size_t len = nums.size();sort(nums.begin(), nums.end());int cnt = 0; for (size_t i = 0; i < len; i++) {if (nums[i] == val) {cnt++;}else {nums[i - cnt] = nums[i];}}return len - cnt;
}
②快慢指针法
int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0; fast < nums.size(); fast++) {if (nums[fast] != val) {nums[slow++] = nums[fast];}}return slow;
}
③暴力法
int removeElement(vector<int>& nums, int val) {size_t len = nums.size();for (size_t i = 0; i < len; i++) {if (nums[i] == val) {for (size_t j = i; j < len - 1; j++) {nums[j] = nums[j + 1];}i--;len--;}}return len;
}
5.删除有序数组中的重复项(leetcode26
)
题目描述:给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。考虑 nums
的唯一元素的数量为 k
,你需要做以下事情确保你的题解可以被通过:
- 更改数组
nums
,使nums
的前k
个元素包含唯一元素,并按照它们最初在nums
中出现的顺序排列。nums
的其余元素与nums
的大小不重要。 - 返回
k
。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [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]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums
已按 非严格递增 排列
思路:
- 数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
- 两种方法:
- 快慢指针法
- 暴力法
①快慢指针法
int removeDuplicates(vector<int>& nums) {int slow = 0;for (int fast = 0; fast < nums.size(); fast++) {if (nums[slow] != nums[fast]){nums[++slow] = nums[fast];}}return slow + 1;
}
②暴力法
int removeDuplicates(vector<int>& nums) {size_t len = nums.size();int index = nums[0];for (size_t i = 1; i < len; i++) {if (nums[i] == index) {for (size_t j = i; j < len - 1; j++) {nums[j] = nums[j + 1];}i--;len--;}else {index = nums[i];}}return len;
}
6.移动零(leetcode283
)
题目描述:给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
思路:
- 数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
- 两种方法:
- 快慢指针法
- 暴力法
①快慢指针法
void moveZeroes(vector<int>& nums) {size_t slow = 0;for (size_t fast = 0; fast < nums.size(); fast++) {if (nums[fast] != 0) {nums[slow++] = nums[fast];}}for (; slow < nums.size(); slow++) {nums[slow] = 0;}
}
②暴力法
void moveZeroes(vector<int>& nums) {size_t len = nums.size();for (size_t i = 0; i < len; i++) {if (nums[i] == 0) {for (size_t j = i; j < len - 1; j++) {nums[j] = nums[j + 1];}i--;len--;}}for (; len < nums.size(); len++) {nums[len] = 0;}
}
7.比较含退格的字符串(leetcode844
)
题目详情:给定 s
和 t
两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true
。#
代表退格字符。注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。
示例 2:
输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。
示例 3:
输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。
提示:
1 <= s.length, t.length <= 200
s
和t
只含有小写字母以及字符'#'
进阶:
- 你可以用
O(n)
的时间复杂度和O(1)
的空间复杂度解决该问题吗?
思路:
-
重构字符串并比较
- 快慢指针
- 栈
-
逆向双指针
①字符串重构——快慢指针
void showVisiableString(string& s) {size_t slow = 0;for (size_t fast = 0; fast < s.size(); fast++) {if (s[fast] == '#') {slow = (slow == 0? 0 : slow - 1);}else {s[slow++] = s[fast]; }}s.resize(slow);
}bool backspaceCompare(string s, string t) {showVisiableString(s);showVisiableString(t);if(s.size() != t.size()) {return false;}for (size_t i = 0; i < s.size(); i++) {if (s[i] != t[i]) {return false;}}return true;
}
②字符串重构——栈
stack<char> stackHelper(string s) {stack<char> result;for (int i = 0; i < s.size(); i++) {if (s[i] != '#') {result.push(s[i]);}else if (!result.empty()) {result.pop();}}return result;
}bool backspaceCompare(string s, string t) {stack<char> S, T;S = stackHelper(s);T = stackHelper(t);if(S.size() != T.size()) {return false;}while (!S.empty()) {if (S.top() != T.top()) {return false;}S.pop();T.pop();}return true;
}
③逆向双指针
bool backspaceCompare(string s, string t) {int sl = s.size() - 1, tl = t.size() - 1;int sCount = 0, tCount = 0;while (sl >= 0 || tl >= 0) {while (sl >= 0) {if (s[sl] == '#') {sl--;sCount++;}else if (sCount > 0) {sCount--;sl--;}else {break;}}while (tl >= 0) {if (t[tl] == '#') {tl--;tCount++;}else if (tCount > 0) {tCount--;tl--;}else {break;}}if (sl >= 0 && tl >= 0){if (s[sl] != t[tl]) {return false;}}else {if (sl >=0 || tl >= 0) {return false;}}sl--;tl--;}return true;
}
8.有序数组的平方
题目描述:给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序
思路
- 直接排序法
- 双指针法
- 归并排序法
①直接排序法
vector<int> sortedSquares(vector<int>& nums) {vector<int> ans;for (int i = 0; i < nums.size(); i++) {ans.push_back(nums[i] * nums[i]);}sort(ans.begin(), ans.end());return ans;
}
②双指针法
vector<int> sortedSquares(vector<int>& nums) {vector<int> ans(nums.size());int left = 0, right = nums.size() - 1;int pos = right;while (left <= right) {int vl = nums[left] * nums[left];int vr = nums[right] * nums[right];if (vl < vr) {ans[pos--] = vr;right--;}else {ans[pos--] = vl;left++;}}return ans;
}
③归并排序法
vector<int> sortedSquares(vector<int>& nums) {int neg = -1, len = nums.size();for (int i = 0; i < len; i++) {if (nums[i] < 0) {neg = i;}}int i = neg, j = neg + 1;vector<int> ans;while (i >= 0 || j < len) {if (i < 0) {ans.push_back(nums[j] * nums[j]);j++;}else if (j == len) {ans.push_back(nums[i] * nums[i]);i--;}else if (nums[i] * nums[i] <= nums[j] * nums[j]) {ans.push_back(nums[i] * nums[i]);i--;}else {ans.push_back(nums[j] * nums[j]);j++;}} return ans;
}