甘肃建设监理协会网站,显示网站目录,分销系统什么意思,备案 个人网站名称移除元素 简介[简单] 27. 移除元素[简单] 26. 删除有序数组中的重复项[简单] 283. 移动零[简单] 844. 比较含退格的字符串[简单] 977. 有序数组的平方 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路#xff0c;如果有错误#x… 移除元素 简介[简单] 27. 移除元素[简单] 26. 删除有序数组中的重复项[简单] 283. 移动零[简单] 844. 比较含退格的字符串[简单] 977. 有序数组的平方 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路如果有错误可以在评论区提醒一下。 一旦设计到数组移除元素就可以首先考虑一下双指针法解题。快慢指针法经常可以比较高效的对数组做一遍处理把需要删除的元素删掉进行压缩。
[简单] 27. 移除元素
原题链接
注意这样的方法是一种不保留原先顺序的方法 方法①其实也是一种双指针的思路。设置一个下标指向数组最右边从头开始遍历一旦遍历到有元素需要移除就把他往最后放并将下标左移右边区域不再参与遍历记住一旦有元素被置换到后面需要将当前循环下标做i--处理因为你换过来的元素依然可能是一个需要移除的元素。
class Solution {public int removeElement(int[] nums, int val) {int length nums.length;int right nums.length - 1; //替换指针for(int i 0; i length; i){if(nums[i] val){int temp nums[right];nums[right] nums[i];nums[i] temp;right--;length--; //相当于舍弃末尾的部分长度i--; //置换之后当前位置可能还是一个需要置换的元素继续检查}}return length;}
}注意该方法保留了原数组的顺序 方法②快慢指针法相当于慢指针负责对快指针指向的元素进行复制而快指针则会跳过那些不需要复制的元素。
class Solution {public int removeElement(int[] nums, int val) {int fastIndex 0;int slowIndex 0;int count 0;while(fastIndex nums.length slowIndex nums.length - count){nums[slowIndex] nums[fastIndex];if(nums[fastIndex] val){count; }else{slowIndex;}fastIndex;}return nums.length - count;}
}[简单] 26. 删除有序数组中的重复项
原题链接
方法①根据有序数组的条件对上面的双指针法进行一定的改造定义一个tag标记目前碰到的数之后碰到相同的则快指针跳过碰到不同的则标记新的tag。
class Solution {public int removeDuplicates(int[] nums) { int fastIndex 1;int slowIndex 1;int count 0;int tag nums[1]; //题目为有序数组while(fastIndex nums.length slowIndex nums.length - count){nums[slowIndex] nums[fastIndex];if(nums[fastIndex] tag){count;}else{tag nums[fastIndex];slowIndex;}fastIndex;}return nums.length - count;}
}方法②直接省去标记的问题因为数组是有序的慢指针和快指针所指向的元素只有nums[fastIndex] nums[slowIndex]以及nums[fastIndex] nums[slowIndex]两种情况相等的时候快指针即可跳过一旦不相等即可做赋值操作。
public int removeDuplicates(int[] nums) {//题目为有序数组int fastIndex 0;int slowIndex 0;while(fastIndex nums.length){if(nums[fastIndex] nums[slowIndex]){nums[slowIndex] nums[fastIndex];}else{fastIndex;}}return slowIndex 1;}方法①与方法②速度差距 [简单] 283. 移动零
原题链接
经典的双指针法。因为末尾要保留0所以使用对换的swap方式来做。但这样时间效率不是最高的直接覆盖然后在末尾使用Arrays.fill(nums,count,nums.length,0);直接填充0能够更高效。
class Solution {public void moveZeroes(int[] nums) {int fastIndex 0;int slowIndex 0;while(fastIndex nums.length){if(nums[fastIndex] ! 0){int temp nums[fastIndex];nums[fastIndex] nums[slowIndex];nums[slowIndex] temp;slowIndex;}fastIndex;}}
}[简单] 844. 比较含退格的字符串
原题链接
方法①也可以用快慢指针法把两个字符串该删的删了对最后的结果作比较这里就不重复实现了。
方法②看到退格操作#就想到使用栈用两个栈保存s和t经过退格操作之后的值然后再出栈进行比较。
class Solution {public boolean backspaceCompare(String s, String t) {StackCharacter sStack new Stack();StackCharacter tStack new Stack();for(int i 0; i s.length(); i){if(s.charAt(i) # !sStack.empty()){sStack.pop();}else if(s.charAt(i) ! #){sStack.push(s.charAt(i));}//System.out.println(sStack.toString());}for(int i 0; i t.length(); i){if(t.charAt(i) # !tStack.empty()){tStack.pop();}else if(t.charAt(i) ! #){tStack.push(t.charAt(i));}//System.out.println(tStack.toString());}if(sStack.size() ! tStack.size()) return false;while(!sStack.empty() !tStack.empty()){if(sStack.pop() ! tStack.pop()) return false;}return true;}
}方法③两个指针从后往前遍历效率高但是对边界的控制比较麻烦没有栈写起来简单
class Solution {public boolean backspaceCompare(String s, String t) {int sIndex s.length() - 1;int tIndex t.length() - 1;int sCount 0;int tCount 0;while(sIndex 0 || tIndex 0){//让sIndex指向s中接下来要比较的字符能够确定最后不被删除while (sIndex 0){if (s.charAt(sIndex) #) {sCount;sIndex--;} else if (sCount 0) {sCount--;sIndex--;} else{break;}}while (tIndex 0){if (t.charAt(tIndex) #) {tCount;tIndex--;} else if (tCount 0) {tCount--;tIndex--;} else{break;}}if(sIndex 0 || tIndex 0) break;if (s.charAt(sIndex) ! t.charAt(tIndex)){return false;}sIndex--;tIndex--;}if(sIndex 0 || tIndex 0) return false;return true;}
}[简单] 977. 有序数组的平方
原题链接
题目中没有强调在原数组上修改返回值也是int[]就可以思考是不是创建一个新的数组更方便一些。 找到数组中正负值的分界点然后从分界点向两边遍历按照绝对值的大小挨个平方计算后加入到新的数组中。正数或者负数用完之后无法继续进行绝对值比较的循环。然后再将左边或者右边剩下的数依次放入答案数组中。 时间复杂度O(n)
class Solution {public int[] sortedSquares(int[] nums) {int[] answer new int[nums.length];int zeroIndex 0;//找到正负分界点while(zeroIndex nums.length nums[zeroIndex] 0){zeroIndex;}int negativeIndex zeroIndex - 1;int positiveIndex zeroIndex;int i 0;while(negativeIndex 0 positiveIndex nums.length){if (Math.abs(nums[negativeIndex]) Math.abs(nums[positiveIndex])) {answer[i] nums[negativeIndex] * nums[negativeIndex];negativeIndex--;continue;} else {answer[i] nums[positiveIndex] * nums[positiveIndex];positiveIndex;continue;}}while(negativeIndex 0){answer[i] nums[negativeIndex] * nums[negativeIndex];negativeIndex--;}while(positiveIndex nums.length){answer[i] nums[positiveIndex] * nums[positiveIndex];positiveIndex;}return answer;}
}
