通過(guò)快慢指針，每次先讓快指針移動(dòng)，完成操作后慢指針++，如此重復(fù)。
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != 0) {
nums[slow++] = nums[fast];
}
fast++;
}
while (slow < nums.length) {
nums[slow++] = 0;
}
}
}
26. 刪除有序數(shù)組中的重復(fù)項(xiàng)
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
}
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != val) {
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
}
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null) {
if(fast.val == slow.val) {
slow.next = fast.next;
}else {
slow = slow.next;
}
fast = fast.next;
}
return head;
}
}
167. 兩數(shù)之和 II - 輸入有序數(shù)組
雙指針?lè)? O(n)
class Solution {
public int[] twoSum(int[] numbers, int target) { //題目數(shù)組要求下標(biāo)從1開(kāi)始
int left = 0, right = numbers.length - 1;
while (left < right) {
if(numbers[left] + numbers[right] == target) {
return new int[] {left + 1, right + 1};
}else if(numbers[left] + numbers[right] > target){
right--;
}else{
left++;
}
}
return new int[] {left + 1, right + 1};
}
}
雙指針+二分 best:O(logn) worst:O(n)
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (numbers[left] + numbers[mid] > target) { //如果中間都超過(guò)，則 right = mid - 1
right = mid - 1;
} else if (numbers[mid] + numbers[right] < target) { //如果中間都不夠，則 left = mid + 1
left = mid + 1;
} else if (numbers[left] + numbers[right] > target) {
right--;
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
return new int[] {left + 1, right + 1};
}
}
return null;
}
}
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
}
從中間向兩端雙指針：對(duì)于奇數(shù)和偶數(shù)都適用。時(shí)間:O(n2) 空間:O(1)
給定如下函數(shù)，若 l == r 找奇數(shù)回文串，若 l、r 相鄰則尋找偶數(shù)回文串。
String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--; r++;
}
return s.substring(l + 1, r);
}
完整代碼
class Solution {
public String longestPalindrome(String s) {
String res = "";
for(int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
public String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}
(有空記得看)Manacher's Algorithm 馬拉車(chē)算法。時(shí)間:O(n) 空間:O(n)
雙指針：由于#只影響前面的字母，所以可以逆向處理。
每次處理 s 和 t 是否存在#，并改變對(duì)應(yīng)指針位置，知道遇到字母再去比較字母是否一樣。
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int skipi = 0, skipj = 0;
while(i >= 0 || j >= 0) {
while(i >= 0) {
if(s.charAt(i) == '#') {
skipi++;
i--;
}else if(skipi > 0) {
skipi--; // 不能直接 i -= skipi?！叽嬖谶B續(xù)兩個(gè)## + 一個(gè)字母 的情況
i--;
}else break;
}
while(j >= 0) {
if(t.charAt(j) == '#') {
skipj++;
j--;
}else if(skipj > 0) {
skipj--;
j--;
}else break;
}
if(i >= 0 && j >= 0) {
if(s.charAt(i) != t.charAt(j)) {
return false;
}
}else{
if(i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
}
依舊使用雙指針，比較兩端平方數(shù)哪個(gè)更大。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] ans = new int[nums.length];
int count = nums.length;
while (left <= right) {
int a = nums[left] * nums[left];
int b = nums[right] * nums[right];
if(a <= b) {
ans[--count] = b;
--right;
}else {
ans[--count] = a;
++left;
}
}
return ans;
}
}
