[New Star] LeetCode（200道目标）栈与双指针法

宁愿累死自己，也要卷死同学！

844. 比较含退格的字符串
     

普通方法（使用栈的思路）

这道题目一看就是要使用栈的节奏，这种 匹配（消除） 问题也是栈的擅长所在，

这里直接使用字符串string，来作为栈，末尾添加和弹出，string都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。

对于equals()方法： StringBuilder比的是地址，而String比的是里面的内容
代码如下：

class Solution {    public boolean backspaceCompare(String s, String t) {     StringBuilder  sstr = new  StringBuilder();  //string是不可以改变的     StringBuilder tstr = new  StringBuilder();   for(char c : s.toCharArray()){//string 变成chararray      if( c != '#'){   sstr.append(c);}else  if( sstr.length()>0){//不能为空 sstr.deleteCharAt(sstr.length() -1);      }     }     for(char c : t.toCharArray()){  if(c != '#'){      tstr.append(c);  }else  if( tstr.length() >0){      tstr.deleteCharAt(tstr.length() -1);  }     }     return  sstr.toString().equals(tstr.toString());   //不能直接sstr.equals(tstr)    }}

双指针法：从后开始遍历

由于 # 号只会消除左边的一个字符，所以对右边的字符无影响，所以我们选择从后往前遍历 SS，TT 字符串。

思路解析：

1. 准备两个指针 i, j 分别指向 S，T 的末位字符，再准备两个变量 skipS，skipT 来分别存放 S，T 字符串中的 # 数量。

2. 从后往前遍历 S，所遇情况有三，如下所示：

3. 2.1 若当前字符是 #，则 skipS 自增 1；

4. 2.2 若当前字符不是 #，且 skipS 不为 0，则 skipS 自减 1；

5. 2.3 若当前字符不是 #，且 skipS 为 0，则代表当前字符不会被消除，我们可以用来和 T 中的当前字符作比较。

若对比过程出现 SS, TT 当前字符不匹配，则遍历结束，返回 falsefalse，若 SS，TT 都遍历结束，且都能一一匹配，则返回 truetrue。

skipS就是用来判断要不要跳过下一个字母的标准

class Solution {    public boolean backspaceCompare(String s, String t) { int   si = s.length() -1,ti = t.length() -1; int  sskip = 0,tskip = 0; while(si >=0 ||ti >0){//这里是||而不是&&  ，不然会直接退出得到true     while(si>=0){  if(s.charAt(si) == '#'){      si--;      sskip ++;  }else if( sskip >0){      sskip --;      si--; }else  break;     }     while(ti >= 0){  if(t.charAt(ti) =='#'){      ti--;      tskip++;  }else if(tskip > 0){      tskip --;      ti--;  }else    break;     }     if(ti >= 0&& si >=0){   if(s.charAt(si) != t.charAt(ti)){      return false;   }     }else {  if(ti>=0 ||si >=0){//这里是判断某一string过长，就会返回false  ，如果同时<0,就说明string长度相等   return false;  }     }     si--;     ti--; } return true;    }}

第二题 977. 有序数组的平方

给你一个按 非递减顺序排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序排序。

算法为：

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

class Solution {    public int[] sortedSquares(int[] nums) { int  left   = 0, right = nums.length -1; int []  i = new  int[nums.length]; int  index =  i.length -1; while(left <= right){     if(nums[left]*nums[left] >nums[right]*nums[right]){  i[index--] = nums[left]*nums[left];  left++;     }else{  i[index--] =nums[right]*nums[right];  right--;     } } return i;    }}