26.删除排序数组中的重复项
题目描述
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 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 。不需要考虑数组中超出新长度后面的元素。
思路分析
方法一:暴力法(超时)
方法二:双指针
参考代码
暴力法
//方法一:暴力枚举法 (但会超时) int removeDuplicates(vector<int>& nums) { int size = nums.size() ; for(int i = 1; i < size; i++) { if(nums[i]==nums[i-1]) { //i后面的所有元素向前移动 for(int j = i+1; j < size; j++) { nums[j-1] = nums[j]; } size--; i--; } } return size; }
双指针
//方法二:双指针法 int removeDuplicates(vector<int>& nums) { int slowIndex,fastIndex; slowIndex = 1;//这里注意slowIndex为1,第一个是一定要放的,因为前面没有元素. for(fastIndex = 1;fastIndex<nums.size();fastIndex++) { if(nums[fastIndex]!=nums[fastIndex-1]){ nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; }
283.移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
参考代码
暴力法
void moveZeroes(vector<int>& nums) { int size = nums.size(); for(int i = 0;i<size;i++){ if(!nums[i]){ for(int j = i+1;j<size;j++){ nums[j-1] = nums[j]; } size--;//不过多解释... i--; } } for(int i = size;i<nums.size();i++){ nums[i] = 0; } }
双指针法
void moveZeroes(vector<int>& nums) { int slowIndex,fastIndex; slowIndex = 0; for(fastIndex = 0; fastIndex<nums.size(); fastIndex++) { //fastIndex遍历整个数组 if(nums[fastIndex]!=0) { //slowIndex控制将和目标不相同的元素从前往后依次放置. nums[slowIndex++] = nums[fastIndex] ; } } while(slowIndex<nums.size()){ nums[slowIndex++] = 0; } }
844.比较含退格的字符串
题目描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 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 = "#a#c" 输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b" 输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
参考代码
方法一 栈模拟
bool backspaceCompare(string s, string t) { return backspaceCompare(s)==backspaceCompare(t); } string backspaceCompare(string s) { string s1; for(int i = 0; i < s.size(); i++) { if(s[i]!='#') { s1.push_back(s[i]); } else if(!s1.empty()) { s1.pop_back(); } } return s1; }
时间复杂度:O ( n + m )
方法二 双指针法
//方法一:双指针 string changeString(string &str) { int slowIndex = 0,fastIndex; for(fastIndex = 0; fastIndex<str.size(); fastIndex++) { //当 str[fastIndex]!='#' ,str[fast]覆盖 str[slowIndex],然后slowIndex++ if(str[fastIndex]!='#') { str[slowIndex++] = str[fastIndex]; //当 str[fastIndex]=='#' ,并且slowIndex>0,则slowIndex前移动 } else if(str[fastIndex]=='#'&&slowIndex>0) { slowIndex--; } } return str.substr(0,slowIndex);//进行截取 } bool backspaceCompare(string s, string t) { return changeString(s)==changeString(t); }
时间复杂度:O ( n )
方法三 双指针法 (不推荐该种方法,思路较为复杂)
//方法二:双指针 //https://leetcode-cn.com/problems/backspace-string-compare/solution/shuang-zhi-zhen-bi-jiao-han-tui-ge-de-zi-8fn8/ bool backspaceCompare(string s, string t) { int i = s.size()- 1,j = t.size()-1; int skipS = 0,skipT = 0; while(i>=0 || j>=0) { while(i>=0) { if(s[i]=='#') { skipS++; i--; } else if(skipS>0) { skipS--; i--; } else { break; } } while(j>=0) { if(t[j]=='#') { skipT++; j--; } else if(skipT>0) { skipT--; j--; } else { break; } } if(i>=0 && j>=0) { if(s[i]!=t[j]){ return false; } }else{ if(i>=0 || j>=0){ return false; } } i--; j--; } return true; }
977.有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 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]
思路分析
方法一:暴力法
直接for循环+sort排序
方法二:双指针
数字本身是有序的,只是负数平方之后也可能成为最大数.
但是最大的那个数只可能在数组的最左边或者在最右边,不可能在中间的.中间的数的平方都小于两边数的平方.所以我们考虑使用双指针.
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i];
参考代码
暴力法
vector<int> sortedSquares(vector<int>& nums) { for(int i = 0; i < nums.size(); i++) { nums[i] = nums[i]*nums[i]; } sort(nums.begin(),nums.end()); return nums; }
双指针法
vector<int> sortedSquares(vector<int>& nums) { vector<int> result(nums.size(),0); int i = 0,j = nums.size()-1,k = nums.size()-1; while(i<=j){ if(nums[i]*nums[i] < nums[j]*nums[j]){ result[k] = nums[j]*nums[j]; j--; k--; }else{ result[k] = nums[i]*nums[i]; i++; k--; } } return result; }
