招人在哪个网站比较好找,网站设计经典案例,户型图装修设计图app,昆明网站制作定制公司所谓的双指针其实就是两个变量#xff0c;不一定真的是指针。
快慢指针#xff1a;一起向前走对撞指针、相向指针#xff1a;从两头向中间走背向指针#xff1a;从中间向两头走
移除值为val的元素
题目描述
27. 移除元素 - 力扣#xff08;LeetCode#xff09;
给你…所谓的双指针其实就是两个变量不一定真的是指针。
快慢指针一起向前走对撞指针、相向指针从两头向中间走背向指针从中间向两头走
移除值为val的元素
题目描述
27. 移除元素 - 力扣LeetCode
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1
输入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]也会被视作正确答案。示例 2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,3,0,4]
解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示
0 nums.length 1000 nums[i] 500 val 100
快慢指针
/*** return 移除后val后数组的新长度*/
public int removeElement(int[] nums, int val)
{int slow 0;for (int fast 0; fast nums.length; fast){//nums[fast] val时slow等待直到下一个nums[fast]! val然后将nums[slow]覆盖if (nums[fast] ! val){nums[slow] nums[fast];slow; //slow移动到下一个待写位置}}return slow;
}上图的val2
对撞指针交换
/*** 核心思想从右侧找到不是val的值来顶替左侧是val的值*/
public int removeElement(int[] nums, int val)
{int left 0;int right nums.length - 1;while (left right){if(nums[left] val nums[right] ! val){int temp nums[left];nums[left] nums[right]; //覆盖删除nums[right] temp; //交换的目的是让right指针能够移动}//更新指针if (nums[left] ! val)left;if (nums[right] val)right--;}return left;
}对撞指针覆盖
public int removeElement(int[] nums, int val)
{int left 0;int right nums.length - 1;while (left right){if (nums[left] val){nums[left] nums[right];right--;}elseleft;}return right 1;
}删除有序数组中的重复项
题目描述
26. 删除有序数组中的重复项 - 力扣LeetCode
给你一个 非严格递增排列 的数组 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] 104nums 已按 非严格递增 排列
快慢指针
public int removeDuplicates(int[] nums)
{int slow 0;for(int fast 0; fast nums.length; fast){//fast往下走直到指向第一个与slow不同的元素if(nums[fast] ! nums[slow]){slow; //slow后移一位存储新的不重复元素nums[slow] nums[fast];}}return slow 1; //返回nums中唯一元素的个数。
}进阶重复元素保留k个
前 k 位直接保留**fast 不断向后遍历 nums[fast] 能够保留的前提是与nums[slow]**的前面第 k 个元素不同保留后 slow 指向新的写入位置
public int removeDuplicates(int[] nums)
{int slow 0;int k 2; //重复元素保留k个for(int fast 0; fast nums.length; fast){if(slow k || nums[slow - k] ! nums[fast]){nums[slow] nums[fast];slow;}}return slow; //返回nums中唯一元素的个数。
}按奇偶排序数组
题目描述
905. 按奇偶排序数组 - 力扣LeetCode
给你一个整数数组 nums将 nums 中的的所有偶数元素移动到数组的前面后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
示例 1
输入nums [3,1,2,4]
输出[2,4,3,1]
解释[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。示例 2
输入nums [0]
输出[0]对撞指针交换
public int[] sortArrayByParity(int[] nums)
{int left 0;int right nums.length - 1;while (left right){//左奇右偶时两边交换把奇数调到后面偶数调到前面if(nums[left] % 2 1 nums[right] % 2 0){int t nums[left];nums[left] nums[right];nums[right] t;}if(nums[left] % 2 0) left; //跳过左边的偶数if(nums[right] % 2 1) right--; //跳过右边的奇数}return nums;
}数组轮转
题目描述
189. 轮转数组 - 力扣LeetCode
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
示例 1:
输入: nums [1,2,3,4,5,6,7], k 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入nums [-1,-100,3,99], k 2
输出[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]提示
1 nums.length 105-231 nums[i] 231 - 10 k 105
进阶
尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
三次翻转
public void rotate(int[] nums, int k)
{//举例nums:[1,2,3,4,5,6,7]k k % nums.length;reverse(nums,0, nums.length - 1); //nums:[7,6,5,4,3,2,1]reverse(nums,0,k-1); //nums:[5,6,7,4,3,2,1]reverse(nums,k, nums.length - 1); //nums:[5,6,7,1,2,3,4]
}//反转指定区间
public void reverse(int[] nums, int left, int right)
{while (left right){int t nums[left];nums[left] nums[right];nums[right] t;left;right--;}
}数组的区间专题
汇总区间
题目描述
228. 汇总区间 - 力扣LeetCode
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表* 。也就是说nums 的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出
a-b 如果 a ! ba 如果 a b
示例 1
输入nums [0,1,2,4,5,7]
输出[0-2,4-5,7]
解释区间范围是
[0,2] -- 0-2
[4,5] -- 4-5
[7,7] -- 7示例 2
输入nums [0,2,3,4,6,8,9]
输出[0,2-4,6,8-9]
解释区间范围是
[0,0] -- 0
[2,4] -- 2-4
[6,6] -- 6
[8,9] -- 8-9提示
0 nums.length 20-231 nums[i] 231 - 1nums 中的所有值都 互不相同nums 按升序排列
解
slow 指向每个区间的起始位置 fast 从 slow 位置开始向后遍历直到不满足连续递增或 fast 达到数组边界。当前区间结束将 slow 指向更新为 fast 1作为下一个区间的开始位置fast继续向后遍历找下一个区间的结束位置如此循环直到 nums 遍历完毕 append(char c)将指定的字符添加到当前StringBuilder对象的末尾。如果参数是数字则自动转为字符 public ListString summaryRanges(int[] nums)
{ArrayListString ans new ArrayList();int slow 0;int fast 0;for (; fast nums.length; fast){if(fast nums.length - 1 || nums[fast]1 ! nums[fast 1]){StringBuilder sb new StringBuilder();sb.append(nums[slow]);if(nums[slow] ! nums[fast])sb.append(-).append(nums[fast]);ans.add(sb.toString());slow fast 1;}}return ans;
}缺失的区间
题目描述
163. 缺失的区间 - 力扣LeetCode
给你一个闭区间 [lower, upper] 和一个 按从小到大排序 的整数数组 nums 其中元素的范围在闭区间 [lower, upper] 当中。
如果一个数字 x 在 [lower, upper] 区间内并且 x 不在 nums 中则认为 x 缺失。
返回 准确涵盖所有缺失数字 的 最小排序 区间列表。也就是说nums 的任何元素都不在任何区间内并且每个缺失的数字都在其中一个区间内。
示例 1
输入: nums [0, 1, 3, 50, 75], lower 0 , upper 99
输出: [[2,2],[4,49],[51,74],[76,99]]
解释返回的区间是
[2,2]
[4,49]
[51,74]
[76,99]示例 2
输入 nums [-1], lower -1, upper -1
输出 []
解释 没有缺失的区间因为没有缺失的数字。提示
-109 lower upper 1090 nums.length 100lower nums[i] uppernums 中的所有值 互不相同
解
public ListListInteger findMissingRanges(int[] nums, int lower, int upper)
{ListListInteger missingRanges new ArrayList();//[lower, upper]缺失if (nums.length 0){missingRanges.add(generateRange(lower, upper));return missingRanges;}//[lower, nums[0] - 1]缺失if (nums[0] lower){missingRanges.add(generateRange(lower, nums[0] - 1));}//i 0起[nums[i] 1, nums[i 1] - 1]缺失for (int i 0; i nums.length - 1; i){if(nums[i 1] - nums[i] 1) //非连续递增{missingRanges.add(generateRange(nums[i] 1, nums[i 1] - 1));}}//[nums[length - 1] 1, upper]缺失if (nums[nums.length - 1] upper){missingRanges.add(generateRange(nums[nums.length - 1] 1, upper));}return missingRanges; //返回所有缺失区间
}//生成区间
public ListInteger generateRange(int start, int end)
{ArrayListInteger range new ArrayList();range.add(start);range.add(end);return range;
}字符串替换空格
题目描述
剑指offer请实现一个函数将一个字符串中的每个空格替换成**“%20”。例如“We Are Happy.”** 经过替换之后为**“We%20Are%20Happy.”**
解
public class replaceSpaces
{public static void main(String[] args){String str1 replaceSpace_immutable(We Are Happy.);System.out.println(str1); //We%20Are%20Happy.(正确)StringBuffer sb new StringBuffer(We Are Happy.);String str2 replaceSpace_variable(sb);System.out.println(str2); //We%20Are%20Happy.(正确)}//存储字符串的空间不可变或者存储空间不算大public static String replaceSpace_immutable(String str){String res ;for (int i 0; i str.length(); i){char c str.charAt(i);if (c )res res %20;elseres %s%s.formatted(res, c); //效果相同}return res;}//存储字符串的空间可变或者存储空间很大public static String replaceSpace_variable(StringBuffer str){int blank 0; //str中的空格数//计算空格数for (int i 0; i str.length(); i)if (str.charAt(i) )blank;int fast str.length() - 1; //fast指向原长度的末尾//设置新的长度(StringBuffer才有的方法String没有)str.setLength(str.length() 2 * blank);int slow str.length() - 1; //slow指向新长度的末尾while (fast 0 fast slow){char c str.charAt(fast);if (c ){str.setCharAt(slow,0); //复制slow--;str.setCharAt(slow,2);slow--;str.setCharAt(slow,%);}elsestr.setCharAt(slow, c);fast--;slow--;}return str.toString();}
}replaceSpace_variable图解
