一、双指针编程技巧
方法参数传递数组
将数组通过方法参数传递，方法操作的数组和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;
}
三、学习分享
