算法通关村第三关|白银|双指针妙用【持续更新】

1.删除元素

1.1 原地删除等于 val 的元素

1.1.1 快慢双指针。

public int removeElement(int[] nums, int val) {
	int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

1.1.2 对撞双指针：用右边不是 val 的元素替换掉左边等于 val 的元素。

public int removeElement(int[] nums, int val) {
	int right = nums.length - 1;
    int left = 0;

    for (left = 0; left <= right; ) {
    	if ((nums[left] == val) && (nums[right] != val)) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        if (nums[left] != val) {
            left++;
        }
        if (nums[right] == val) {
            right--;
        }
    }
    return left;
}

1.1.3 对撞双指针+覆盖：左边等于 val 的时候，直接用右边的数覆盖左边的数。发生覆盖操作的时候 left 不移动，确保从 right 得到的值不为 val 的时候 left 才继续右移。

public int removeElement(int[] nums, int val) {
	int right = nums.length - 1;
    for (int left = 0; left <= right; ) {
    	if (nums[left] == val) {
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    return right + 1;
}

1.2 删除有序数组中的重复项

1.2.1 双指针，重复项保留一个。

public int removeDuplicates(int[] nums) {
	int slow = 1;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

1.2.2 重复项保留两个。

public int removeDuplicates(int[] nums) {
	int slow = 2;
    for (int fast = 2; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow - 2]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

*1.2.3 重复项保留K个。

// 由前两个例子已经得到了模板了
// k可以是0个，1个，2个，3个...
public int removeDuplicates(int[] nums, int k) {
	int slow = k;
    for (int fast = k; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow - k]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
	return slow;
}

2.元素奇偶移动

2.1 对撞双指针。

public int[] sortArrayByParity(int[] A) {
	int left = 0, right = A.length - 1;
    while (left < right) {
        if (A[left] % 2 > A[right] % 2) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }

        if (A[left] % 2 == 0) {
            left++;
        }
        if (A[right] % 2 == 1) {
            right--;
        }
    }
    return A;
}

3.数组轮转

3.1 将数组元素向右轮转 k 个位置：两轮翻转，先将整个数组翻转，再从 k 处分隔成两个部分分别翻转。

public void rotate(int[] nums, int k) {
	k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

public void reverse(int[] nums, int start, int end) {
	while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start += 1;
        end -= 1;
    }
}

4.数组的区间

4.1 返回恰好覆盖数组中所有数字的区间：双指针，快指针遍历，慢指针到了不连续的地方再移动。

public List<String> summaryRanges(int[] nums) {
	List<String> res = new ArrayList<>();
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        // 先判断是不是最后一个，不是的话再判断跟后边的数是否连续
        if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {
            // 是最后一个或者不是连续的话就将该段范围写入结果，并且移动slow
            StringBuilder sb = new StringBuilder();
            sb.append(nums[slow]);
            if (slow != fast) {
                sb.append("->").append(nums[fast]);
            }
            res.add(sb.toString());
            slow = fast + 1;
        }
    }
    return res;
}

4.2 返回缺失的区间：【持续更新】。

5.字符串替换空格

5.1 用指定字符串替换空格：先找到字符串中空格的个数，确定新字符串长度，slow指向末尾处，fast向前遍历，将字符赋给slow指向的地方，然后slow向前移动。

// 这里将空格被替换为"%20"
public String replaceSpace(StringBuffer str) {
	if (str == null) {
        return null;
	}
	int numOfblank = 0;
	// 原字符串长度
	int len = str.length();
	// 遍历计算空格数量
	for (int i = 0; i < len; i++) {
        if (str.charAt(i) == ' ') {
            numOfblank++;
        }
    }
	// 设置字符串新的长度
	str.setLength(len + 2 * numOfblank);
	// 原字符串最后一位
	int fast = len - 1;
	int slow = len + 2 * numOfblank - 1;

	// 如果slow追上了fast，说明空格已经被替换完了，前边的不需要再动了，直接结束循环
	while (fast >= 0 && slow > fast) {
        char c = str.charAt(fast);
        if (c == ' ') {
            fast--;
            str.setCharAt(slow--, '0');
            str.setCharAt(slow--, '2');
            str.setCharAt(slow--, '%');
        } else {
            fast--;
            str.setCharAt(slow--, c);
        }
    }
	return str.toString();
}

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤