Two Pointers

96 阅读 0 评论 64 点赞

我是靠谱客的博主爱笑信封，最近开发中收集的这篇文章主要介绍Two Pointers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

两根指针问题，分为两类：同向指针、相向指针，时间复杂度均为O(n)

（一）Move Zeroes （同向指针）

https://leetcode.com/problems/move-zeroes/description/

题目：将数组中所有0元素移动到数组最右边，非零元素顺序不变；

解答：用快慢两指针。快指针每次向前挪一位，若遇到不为0的数，则将快慢指针位置交换并将慢指针挪一位（依次遍历数组，将非0数依次放到数组左边）；

代码：

class Solution {
public void moveZeroes(int[] nums) {
int fast = 0;
int slow = 0;

while (fast < nums.length) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
fast++;
}
}
}

（二）Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

题目：把有序数组中的重复数组移除，并返回无重复数的大小。如[1,1,2]需要返回2且保证数组的前2位为[1,2];

解答：两个指针分别为size和i；使用size来记录当前不重复数存储位置，循环遍历数组，遇到不重复元素则替换当前size的下一个位置元素；

代码：

class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int size = 0;

for (int i = 0; i < nums.length; i++) {
if (nums[i] != nums[size]) {
size++;
nums[size] = nums[i];
}
}
return size + 1;
}
}

（三）Remove Duplicates from Sorted Array II

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

题目：同（四），但是一个元素最多可重复两次；

解答：在（四）基础上，加一个变量存储重复次数；

代码：

class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int size = 0;
int count = 0;

for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[size]) {
count++;
if (count < 2) {
nums[++size] = nums[i];
}
} else {
nums[++size] = nums[i];
count = 0;
}
}
return size + 1;
}
}

（四）Valid Palindrome（相向指针）

https://leetcode.com/problems/valid-palindrome/description/

题目：判断一个字符串是否回文（即头尾元素依次相同），只考虑字母和数字；

解答：使用首尾两指针依次比较有效元素；

代码：

class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}

int left = 0;
int right = s.length() - 1;

while (left <= right) {
while (left < s.length() && !isValid(s.charAt(left))) {
left++;
}
while (right >= 0 && !isValid(s.charAt(right))) {
right--;
}

if (left <= right && Character.toUpperCase(s.charAt(left)) != Character.toUpperCase(s.charAt(right))) {
return false;
} else {
left++;
right--;
}
}
return true;
}

private boolean isValid(Character c) {
return Character.isLetter(c) || Character.isDigit(c);
}
}

（五）Valid PalindromeII

题目：同（四），但是若删掉一个字符依然为回文也返回真；

解答：在（四）的基础上多加一个删掉一个字符是否依然为回文的判断；

代码：

class Solution {
public boolean validPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}

int left = 0, right = s.length() - 1;
while (left < right) {
if (left < right && s.charAt(left) != s.charAt(right)) {
return isPalindromic(s, left, right - 1) || isPalindromic(s, left + 1, right);
} else {
left++;
right--;
}
}
return true;
}

public boolean isPalindromic(String s, int left, int right) {
while (left <= right) {
if (left <= right && s.charAt(left) != s.charAt(right)) {
return false;
} else {
left++;
right--;
}
}
return true;
}
}