雙指針
雙指針法（快慢指針法）： 通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作。
雙指針法（快慢指針法）在數組和連結清單的操作中是非常常見的，很多考察數組、連結清單、字元串等操作的面試題，都使用雙指針法。
- 移除元素
給你一個數組 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,4,0,3]
解釋：函數應該傳回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0,
4。注意這五個元素可為任意順序。你不需要考慮數組中超出新長度後面的元素。
# python
# 雙指針法（快慢指針法）在數組和連結清單的操作中是非常常見的，
# 很多考察數組、連結清單、字元串等操作的面試題，都使用雙指針法。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = fast = 0
n = len(nums)
while(fast < n):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
# java
class Solution {
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;
}
}
- 删除有序數組中的重複項
給你一個有序數組 nums ，請你 原地 删除重複出現的元素，使每個元素 隻出現一次 ，傳回删除後數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。
示例 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 。不需要考慮數組中超出新長度後面的元素。
# python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = fast = 0
n = len(nums)
while(fast < n-1):
if nums[fast] != nums[fast+1]:
nums[slow+1] = nums[fast+1] # slow = 0 的資料一定是不重複的，是以直接 ++slow
slow += 1
fast += 1
return slow+1
# Java
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 0;
while(fast < nums.length - 1){
if(nums[fast] != nums[fast+1]){
nums[slow+1] = nums[fast+1];
slow += 1;
}
fast += 1;
}
return slow+1;
}
}
- 移動零
給定一個數組 nums，編寫一個函數将所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12] 輸出: [1,3,12,0,0]
# python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow = fast = 0
while(fast<len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
fast += 1
for i in range(slow,len(nums)):
nums[i] = 0
# Java
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for(int fast = 0; fast < nums.length; fast++){
if(nums[fast] != 0){
nums[slow++] = nums[fast];
}
}
for(int i = slow; i < nums.length; i++){
nums[i] = 0;
}
}
}
- 比較含倒退的字元串
給定 S 和 T 兩個字元串，當它們分别被輸入到空白的文本編輯器後，判斷二者是否相等，并傳回結果。 # 代表倒退字元。
注意：如果對空文本輸入倒退字元，文本繼續為空。
示例 1：
輸入：S = “ab#c”, T = “ad#c” 輸出：true
解釋：S 和 T 都會變成 “ac”。
示例 2：
輸入：S = “ab##”, T = “c#d#” 輸出：true
解釋：S 和 T 都會變成 “”。
示例 3：
輸入：S = “a##c”, T = “#a#c” 輸出：true
解釋：S 和 T 都會變成 “c”。
示例 4：
輸入：S = “a#c”, T = “b” 輸出：false
解釋：S 會變成 “c”，但 T 仍然是 “b”。
# python
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def solve(s):
slow = fast = 0
while(fast<len(s)):
if (s[fast] != '#'):
s[slow] = s[fast]
slow += 1
else:
if slow:
slow -= 1
fast += 1
return s[0:slow]
s = solve(list(s))
t = solve(list(t))
return s==t
# Java
class Solution {
public boolean backspaceCompare(String s, String t) {
Solution test = new Solution();
char[] s1 = test.solve(s.toCharArray());
char[] t1 = test.solve(t.toCharArray());
System.out.println(s1);
System.out.println(t1);
boolean isEqual=true;
if(s1.length!=t1.length){
return false;
}
for(int i = 0; i < s1.length; i++){
if(s1[i] != t1[i]){
isEqual=false;
break;
}
}
if(isEqual){
return true;
}else{
return false;
}
}
public char[] solve(char[] s){
int slow = 0;
for(int fast = 0; fast<s.length; fast++){
if(s[fast] != '#'){
s[slow++] = s[fast];
}else{
if(slow > 0){
slow--;
}
}
}
return Arrays.copyOfRange(s,0,slow);
}
}
-
有序數組的平方
給你一個按 非遞減順序 排序的整數數組 nums，傳回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方後，數組變為 [16,1,0,9,100]
排序後，數組變為 [0,1,9,16,100]
進階：
請你設計時間複雜度為 O(n) 的算法解決本問題
# python
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left, right, index = 0, n - 1, n - 1
result = [-1]*n
while(left<=right):
l = nums[left] ** 2
r = nums[right] ** 2
if(l >= r):
result[index] = l
left += 1
else:
result[index] = r
right -= 1
index -= 1
return result
# Java
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
int index = n - 1;
int[] result = new int[n];
while(left<=right){
if(nums[left]*nums[left]>=nums[right]*nums[right]){
result[index--] = nums[left]*nums[left++];
}else{
result[index--] = nums[right]*nums[right--];
}
}
return result;
}
}
滑動視窗
滑動視窗的思想：
用i,j表示滑動視窗的左邊界和右邊界，通過改變i,j來擴充和收縮滑動視窗，可以想象成一個視窗在字元串上遊走。
步驟一
不斷增加j使滑動視窗增大，直到視窗滿足條件。
步驟二
不斷增加i使滑動視窗縮小，将不必要的元素排除在外，使長度減小，直到碰到一個必須包含的元素，這個時候不能再扔了，再扔就不滿足條件了，記錄此時滑動視窗的長度，并儲存最小值。
步驟三
讓i再增加一個位置，這個時候滑動視窗肯定不滿足條件了，那麼繼續從步驟一開始執行，尋找新的滿足條件的滑動視窗，如此反複，直到j超出範圍。
-
長度最小的子數組
給定一個含有 n 個正整數的數組和一個正整數 target 。
找出該數組中滿足其和 ≥ target 的長度最小的 連續子數組 [numsl, numsl+1, …, numsr-1, numsr] ，并傳回其長度。如果不存在符合條件的子數組，傳回 0 。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
# python
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left = 0;
sum = 0;
result = float("inf") # 定義一個無限大的數
for i in range(n):
sum += nums[i]
while(sum >= target):
result = min(result,i-left+1)
sum -= nums[left]
left += 1
# if(result == float("inf")):
# return 0
# else:
# return result
return 0 if result == float("inf") else result
# Java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
sum += nums[i];
while(sum >= target){
result = Math.min(result,i-left+1);
sum -= nums[left++];
}
}
// if(result==Integer.MAX_VALUE){
// return 0;
// }else{
// return result;
// }
return result==Integer.MAX_VALUE ? 0 : result;
}
}
-
水果成籃
在一排樹中，第 i 棵樹産生 tree[i] 型的水果。
你可以從你選擇的任何樹開始，然後重複執行以下步驟：
把這棵樹上的水果放進你的籃子裡。如果你做不到，就停下來。
移動到目前樹右側的下一棵樹。如果右邊沒有樹，就停下來。
請注意，在選擇一顆樹後，你沒有任何選擇：你必須執行步驟 1，然後執行步驟 2，然後傳回步驟 1，然後執行步驟 2，依此類推，直至停止。
你有兩個籃子，每個籃子可以攜帶任何數量的水果，但你希望每個籃子隻攜帶一種類型的水果。
用這個程式你能收集的水果樹的最大總量是多少？
示例 1：
輸入：[1,2,1]
輸出：3
解釋：我們可以收集 [1,2,1]。
示例 2：
輸入：[0,1,2,2]
輸出：3
解釋：我們可以收集 [1,2,2]
如果我們從第一棵樹開始，我們将隻能收集到 [0, 1]。
示例 3：
輸入：[1,2,3,2,2]
輸出：4
解釋：我們可以收集 [2,3,2,2]
如果我們從第一棵樹開始，我們将隻能收集到 [1, 2]。
示例 4：
輸入：[3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：我們可以收集 [1,2,1,1,2]
如果我們從第一棵樹或第八棵樹開始，我們将隻能收集到 4 棵水果樹。
# python
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
left = 0
result = 0
# temp = {}
temp = collections.Counter()
for i,x in enumerate(fruits):
# if temp.get(x)==None:
# temp[x] = 1
# else:
# temp[x] += 1
temp[x] += 1
while(len(temp)>=3):
temp[fruits[left]] -= 1
if temp[fruits[left]] == 0:
del temp[fruits[left]]
left += 1
result = max(result,i-left+1)
return result
# Java
class Solution {
public int totalFruit(int[] fruits) {
int left = 0;
int result = 0;
Counter count = new Counter();
for(int i = 0; i < fruits.length; i++){
count.add(fruits[i],1);
while(count.size()>=3){
count.add(fruits[left],-1);
if(count.get(fruits[left])==0){
count.remove(fruits[left]);
}
left++;
}
result = Math.max(result,i-left+1);
}
return result;
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
}
- 最小覆寫子串
給你一個字元串 s 、一個字元串 t 。傳回 s 中涵蓋 t 所有字元的最小子串。如果 s 中不存在涵蓋 t 所有字元的子串，則傳回空字元串 “” 。
注意：
對于 t 中重複字元，我們尋找的子字元串中該字元數量必須不少于 t 中該字元數量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
示例 3:
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個字元 ‘a’ 均應包含在 s 的子串中， 是以沒有符合條件的子字元串，傳回空字元串。
進階：你能設計一個在 o(n) 時間内解決此問題的算法嗎？
參考題解
# python
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = collections.Counter()
for c in t:
need[c] += 1
needCNT = len(t)
left = 0
res = (0,float("inf"))
for i,c in enumerate(s):
if need[c] > 0:
needCNT -= 1
need[c] -= 1
while(needCNT == 0): # 步驟一：滑動視窗包含了所有T元素 步驟二：增加left，排除多餘元素
if i-left<res[1]-res[0]: #記錄結果
res=(left,i)
if(need[s[left]] == 0):
needCNT += 1
need[s[left]] += 1 # 步驟三：left增加一個位置，尋找新的滿足條件滑動視窗
left += 1
return '' if res[1]>len(s) else s[res[0]:res[1]+1]
# Java
class Solution {
public String minWindow(String s, String t) {
Counter need = new Counter();
for(int i = 0; i < t.length(); i++){
need.add(t.charAt(i),1);
}
int left = 0;
int needCNT = t.length();
int[] res = {0, Integer.MAX_VALUE};
for(int i = 0; i < s.length(); i++){
if(need.get(s.charAt(i))>0){
needCNT -= 1;
}
need.add(s.charAt(i),-1);
while(needCNT==0){
if ((i - left)<(res[1] - res[0])){
res[0] = left;
res[1] = i;
}
if (need.get(s.charAt(left)) == 0){
needCNT += 1;
}
need.add(s.charAt(left),1);
left++;
}
}
return res[1]>s.length() ? "" : s.substring(res[0],res[1]+1);
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
}
我們會用i掃描一遍S，也會用left掃描一遍S，最多掃描2次S，是以時間複雜度是O(n).
- 螺旋矩陣
給你一個 m 行 n 列的矩陣 matrix ，請按照 順時針螺旋順序 ，傳回矩陣中的所有元素。
示例 1：
輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]
示例 2：
輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出：[1,2,3,4,8,12,11,10,9,5,6,7]
# python
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m = len(matrix)
n = len(matrix[0])
left, right, up ,down = 0, n-1, 0, m-1
temp = []
while(left<=right and up<=down):
for i in range(left,right+1):
temp.append(matrix[up][i])
for j in range(up+1,down+1):
temp.append(matrix[j][right])
if(up != down):
for i in range(right-1,left,-1):
temp.append(matrix[down][i])
if(left != right):
for j in range(down,up,-1):
temp.append(matrix[j][left])
left += 1
right -= 1
up += 1
down -= 1
return temp
# Java
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int left = 0, right = n - 1, up = 0, down = m - 1;
//int[] temp = new int[m*n];
List<Integer> temp = new ArrayList<Integer>();
//int count = 0;
while(left <= right && up <= down){
for(int i = left; i <= right; i++){
//temp[count++] = matrix[up][i];
temp.add(matrix[up][i]);
}
for(int i = up + 1; i <= down; i++){
//temp[count++] = matrix[i][right];
temp.add(matrix[i][right]);
}
if(up != down){
for(int i = right - 1; i > left; i--){
//temp[count++] = matrix[down][i];
temp.add(matrix[down][i]);
}
}
if(left != right){
for(int i = down; i > up; i--){
//temp[count++] = matrix[i][left];
temp.add(matrix[i][left]);
}
}
left++;
right--;
up++;
down--;
}
return temp;
}
}
- 螺旋矩陣II
給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
示例 1：
輸入：n = 3
輸出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
輸入：n = 1
輸出：[[1]]
# python
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
left, right, up, down = 0, n-1, 0, n-1
matrix = [[0]*n for _ in range(n)]
count = 1
while(left<right and up<down):
for i in range(left, right):
matrix[up][i] = count
count += 1
for j in range(up, down):
matrix[j][right] = count
count += 1
for i in range(right, left, -1):
matrix[down][i] = count
count += 1
for j in range(down, up, -1):
matrix[j][left] = count
count += 1
left += 1
right -= 1
up += 1
down -= 1
if(n % 2):
matrix[n//2][n//2] = count
return matrix
# Java
class Solution {
public int[][] generateMatrix(int n) {
int left = 0, right = n-1, up = 0, down = n-1;
int[][] matrix = new int[n][n];
int count = 1;
while(left < right && up < down){
for(int i = left; i < right; i++){
matrix[up][i] = count++;
}
for(int j = up; j < down; j++){
matrix[j][right] = count++;
}
for(int i = right; i > left; i--){
matrix[down][i] = count++;
}
for(int j = down; j > up; j--){
matrix[j][left] = count++;
}
left++;
right--;
up++;
down--;
}
if(n % 2 != 0){
matrix[n/2][n/2] = count;
}
return matrix;
}
}