4.雙指針+遞歸

一、雙指針編程技巧

在這里插入圖片描述
方法參數傳遞數組

將數組通過方法參數傳遞，方法操作的數組和main方法中的數組指向同一塊內存區域，意味著方法操作數組，同時會引起main方法中數組的改變以引用的方式作為方法參數進行傳遞的
元素交換
在這里插入圖片描述
定義臨時變量temp，每個都訪問了兩次，影響性能

1. 快慢指針

1.1 lc 283：移動零

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
請注意，必須在不復制數組的情況下原地對數組進行操作。
在這里插入圖片描述

1.2 樸素解法

在這里插入圖片描述
遍歷nums數組，將不為0的數據挪到tmp中，新建一個數組tmp將nums中的非零元素放入tmp中

 public int[] moveZeroes(int[] nums) {if(nums == null || nums.length ==0){return new int[]{};}int[] tmp = new int[nums.length];int j = 0;for (int i = 0; i < nums.length; i++) {if(nums[i]!=0){tmp[j] = nums[i];j++;}}return tmp;}?public static void main(String[] args) {int[] nums = new int[]{0,6,0,3,8,0};int[] res = new MoveZeros().moveZeroes(nums);System.out.println(Arrays.toString(res));}

1.3 移動零輸入輸出同一個數組

時間復雜度為O(n)，空間復雜度為O(n)

 public void moveZeroes(int[] nums) {if(nums == null || nums.length ==0){return;}int[] tmp = new int[nums.length];int j = 0;for (int i = 0; i < nums.length; i++) {if(nums[i]!=0){tmp[j] = nums[i];j++;}}?//輸入輸出都在同一個數組for (int i = 0; i < nums.length; i++) {nums[i] = tmp[i];}}?public static void main(String[] args) {int[] nums = new int[]{0,6,0,3,8,0};new MoveZeros().moveZeroes(nums);System.out.println(Arrays.toString(nums));}

1.4 移動零雙指針解法

目的是在常量的空間復雜度下解決，不借助額外的數組
需要再使用一個指針j，用來指向非零元素存放的位置，指針i的話用來遍歷數組每個元素
在這里插入圖片描述

1.5 移動零雙指針代碼實現

 //雙指針解法//時間復雜度為O(n)//空間復雜度為O(1)public void moveZeroes1(int[] nums) {if(nums == null || nums.length ==0){return;}int j = 0;for (int i = 0; i < nums.length; i++) {if(nums[i] !=0){//交換i和j指向的元素int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;j++;}}}

1.6 移動零雙指針之快慢指針

i指針走的快，j指針走的慢
用fast來代替i，slow代替j，提高代碼的可讀性

 public void moveZeroes1(int[] nums) {if(nums == null || nums.length ==0){return;}int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if(nums[fast] !=0){//交換fast和slow指向的元素int tmp = nums[fast];nums[fast] = nums[slow];nums[slow] = tmp;slow++;}}}

1.7 移動零雙指針實現性能優化

減少兩個元素交換的次數
在這里插入圖片描述
當fast==slow的時候是不用交換的
交換的兩個元素都訪問了兩次

直接將非零值賦值到slow指針指向位置，不進行交換，當fast走完
將slow指向元素都設置為0，直到結束

 //兩個元素不進行交換，直接賦值public void moveZeroes2(int[] nums) {if(nums == null || nums.length ==0){return;}int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if(nums[fast] !=0){ //減少賦值的次數//交換fast和slow指向的元素if(slow!=fast){nums[slow] = nums[fast];}slow++;}}for (; slow < nums.length; slow++) {nums[slow] = 0;}}

2. 對撞指針

2.1 lc 344：反轉字符串

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
示例 1：
輸入：s = [“h”,“e”,“l”,“l”,“o”]
輸出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
輸入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
輸出：[“h”,“a”,“n”,“n”,“a”,“H”]

2.2 反轉字符串樸素解法

在這里插入圖片描述

 //樸素解法，定義一個額外數組用來存放反轉后的字符串//時間復雜度(n)//空間復雜度O(n)public void reverseString(char[] s) {char[] tmp = new char[s.length];int j = s.length-1;for (int i = 0; i < s.length; i++) {tmp[j] = s[i];j--;}for (int i = 0; i < s.length; i++) {s[i] = tmp[i];}}?public static void main(String[] args) {String s = "hello";char[] chars = s.toCharArray();new ReverseString().reverseString(chars);System.out.println(chars);}

2.3 反轉字符串雙指針解法

在這里插入圖片描述

 //雙指針解法public void reverseString1(char[] s) {int i = 0;int j = s.length-1;while (i<j){char tmp = s[i];s[i] = s[j];s[j] = tmp;i++;j--;}}

2.4 反轉字符串雙指針之對撞指針

一個指針是從左往右，一個是從右往左
左邊i指針設置為left，右邊設置為right

 //雙指針解法public void reverseString1(char[] s) {int left = 0;int right = s.length-1;while (left<right){char tmp = s[left];s[left] = s[right];s[right] = tmp;left++;right--;}}

3. 雙指針總結

使用一個指針可能會導致空間復雜度的升高
增加一個指針記錄更多的信息，可以降低空間復雜度，提升性能，降低時間復雜度

3.1 lc 27：移除元素

給你一個數組 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素，并返回移除后數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并原地修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。
說明:
為什么返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對于調用者是可見的。
你可以想象內部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);// 在函數里修改輸入數組對于調用者是可見的。
// 根據你的函數返回的長度, 它會打印出數組中該長度范圍內的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 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。注意這五個元素可為任意順序。你不需要考慮數組中超出新長度后面的元素。

3.2 移動元素雙指針解法

public int removeElement(int[] nums, int val) {//雙指針int j = 0;for (int i = 0; i < nums.length; i++) {if(nums[i] != val){nums[j] = nums[i];j++;}}return j;
}

3.3 lc 125：驗證回文串

給定一個字符串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫。
說明：本題中，我們將空字符串定義為有效的回文串。
示例 1:
輸入: “A man, a plan, a canal: Panama”
輸出: true
解釋：“amanaplanacanalpanama” 是回文串
示例 2:
輸入: “race a car”
輸出: false
解釋：“raceacar” 不是回文串

3.4 驗證回文串雙指針

public class lc125_Palindrome {public boolean isPalindrome(String s) {StringBuffer sb = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);//isLetterOrDigit()：確定指定的字符是字母還是數字。if (Character.isLetterOrDigit(ch)) {sb.append(Character.toLowerCase(ch));}}//回文判斷String s1 = sb.toString();char[] chars = s1.toCharArray();int left = 0;int right = chars.length-1;while (left < right){if(chars[left] != chars[right]){return false;}left++;right--;}return true;}
}

二、遞歸編程技巧

1. 方法調用系統棧

方法入棧，執行完某個方法后出棧
在這里插入圖片描述
方法入棧后一個方法對應一個棧幀，棧幀中包括局部變量表，操作數棧，動態連接，方法返回地址

2. 方法調用本身

在這里插入圖片描述
不斷調用方法本身，導致出現棧溢出的錯誤StackOverFlowException
需要給調用本身方法一個終止條件，避免一直調用下去

3. 方法調用本身的參數變化

在這里插入圖片描述
調用方法前為1代碼塊
調用方法后為2代碼塊

4. 方法調用本身的意義

在這里插入圖片描述
使用另外一種思路解決：

遞歸程序的三個特點：

每個大問題可以拆分成若干個子問題，子問題解決了，大問題就解決了
每個子問題的解決方法和大問題的解決方法邏輯是一模一樣的
一定存在遞歸終止條件，一定存在最小子問題

遞推程序編寫：

寫出遞推公式
寫出遞歸終止條件

5. 斐波那契數

在這里插入圖片描述

//斐波那契數
public int fibonacci(int n){if(n==1)return 1;if(n==2)return 2;int fib1 = fibonacci(n-1);int fib2 = fibonacci(n-2);return fib1+fib2;
}

6. 走臺階

在這里插入圖片描述

//1.遞推公式：f(n) = f(n-1) + f(n-2)
//2.遞推終止條件：f(1)=1,f(2)=2
public int walkStair(int n){if(n==1)return 1;if(n==2)return 2;int res = walkStair(n-1)+walkStair(n-2);return res;
}