上一份是二叉树的实现和想法，觉得在总结之中放入题目过于冗余，因为大家都会打开leetcode来看原题是什么，因此这份总结之中将题目部分删去，便于阅读。
在下面的资料基础之上加上个人的理解，部分代码进行明晰化，不搞缩写。
1. 有序数组的two sum
167 Two Sum II - Input array is sorted (Easy)
其过于经典，只要两个指针，一个从前向后，一个从后向前，二者不相遇循环不停止。
当和小于给定值的时候，前面指针向后一位。大于的时候后面指针向前一位。
package Leetcode;
class Solution {
public int[] twoSum(int[] numbers, int target) {
int length = numbers.length;
int i = 0, j = length - 1;
int[] result = new int[2];
while (i < j) {
if (numbers[i] + numbers[j] == target) {
result[0] = i + 1;
result[1] = j + 1;
break;
} else if (numbers[i] + numbers[j] < target) {
i++;
} else if (numbers[i] + numbers[j] > target) {
j--;
}
}
return result;
}
}
* 2. 两数平方和
633 Sum of Square Numbers
https://leetcode.com/problems/sum-of-square-numbers/
本题之中最重要的是对右边的剪枝。而且不剪枝的话计算平方的时候，会直接把int撑爆。
如果让开始指针节点为0，那么结束指针节点应该是Math.sqrt(target)，这种情况下就会直接去掉很多的冗余的值。注意，Math.sqrt(target)之中返回的是double，因此要转换成(int)。
class Solution {
public boolean judgeSquareSum(int c) {
int i=0,j=(int)Math.sqrt(c);
while(i<=j){
if(i*i+j*j==c) return true;
else if(i*i+j*j>c) j--;
else if(i*i+j*j<c) i++;
}
return false;
}
}
3. 反转元音字符
345 Reverse Vowels of a String
https://leetcode.com/problems/reverse-vowels-of-a-string/
本题之中我和参考资料不大一样：
-
其使用了HashSet进行存储和寻找元素，但我是直接if比较。相对而言hashSet的时间复杂度更低。
此处也参阅：https://mp.weixin.qq.com/s/5Y_ES1XfE-xvX88wCTxq3g
- 对于生成的字节码，switch之中只取出了一次变量和条件进行比较，而if之中每次都要取出变量和条件进行比较
- switch之中的字节码也不同：在switch的判断条件比较紧凑的时候使用tableswitch，例如1…2…3…4这种依次递增的判断条件。其结构类似于数组，直接使用索引来进行查找，几乎是O(1)的。而case是1…33…555这种非紧凑就是lookupswitch，会逐个分支进行比较，或者使用二分法查询，因此查询的时间复杂度是O(logn)，使用lookupswitch比tableswitch慢。
-
其将生成数组和值的判断放在一起使用，我是先生成后判断，分开进行。
class Solution {
public String reverseVowels(String s) {
if(s.length()==0) return s;
int i=0,j=s.length()-1;
char[] charArray = new char[s.length()];
for(int k=0;k<s.length();k++){
charArray[k]=s.charAt(k);
}
while(i<j){
while(!isVowel(charArray[i]) && i<j){
i++;
}
while(!isVowel(charArray[j]) && i<j){
j--;
}
if(charArray[i]!=charArray[j]){
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}
i++;
j--;
}
StringBuilder sb =new StringBuilder();
for(char c:charArray){
sb.append(c);
}
return sb.toString();
}
public boolean isVowel(char c){
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U') return true;
return false;
}
}
4. 容许一个字母不符合规则的回文字符串
- Valid Palindrome II (Easy)
题目之中允许了一个字母不符合规则。也就是如果删掉一个字母，是符合规则的，那么也可以。
本题之中还需要一个辅助函数boolean isPalindrome(String s,int start,int end)。
那么就分成了两部分：
-
直接按照回文串的标准判断，不管其他的部分
-
如果有一个字符不满足标准，假设此时的前指针是i，后指针是j，那么借助辅助函数来做：
return isPalindrome(s,i+1,j) || isPalindrome(s,i,j-1);也就是将第一个指针往后挪一位，或者将最后一个指针往前挪一位进行判断，因为只要有符合的就可以，所以二者是或的关系。且指针范围之外的部分已经判断完毕，所以可以直接略去。
class Solution {
public boolean validPalindrome(String s) {
if(s.length()==0) return true;
int i=0,j=s.length()-1;
while(i<=j){
if(s.charAt(i)==s.charAt(j)){
i++;
j--;
}else{
return isPalindrome(s,i+1,j) || isPalindrome(s,i,j-1);
}
}
return true;
}
public boolean isPalindrome(String s,int start,int end){
if(start>end) return false;
while(start<=end){
if(s.charAt(start)!=s.charAt(end)) return false;
start++;
end--;
}
return true;
}
}
5. 原地合并两个有序数组
本题之中给了两个数组，其中一个数组较长，一个数组较短，较长的数组后面部分全是0. 让我们原地合并这两个数组。
排序，肯定是从小到大。那么如果我们从头开始排序，就会将长的数组的头部的信息抹除掉，导致排序无法完成。所以我们要从尾部开始比较排序。
主要逻辑：
先设置三个指针，一个totalPointer用来指代在最后的大数组之中迭代的位置，一个longPointer用来指代比较长的数组之中的比较位置，一个shortPointer用来指代在比较短的数组之中的比较位置。
- 使用循环：循环结束条件有多种，比如题解之中的
longPointer >=0 || shortPointer >=0，或者是我使用的totalPointer>=0。 - 四个if判断：
- 为了避免NPE，首先需要判断
longPointer<0和shortPointer<0的两种情况，这两种情况代表着某一个数组已经迭代完毕，直接将另一个数组之中剩下的所有值都放到大数组即可。 - 在两个数组没有全部迭代完的情况下，直接比较
longPointer和shortPointer二者指向的数字谁更大，将更大的放在totalPointer位置。
- 为了避免NPE，首先需要判断
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int longPointer = m-1, shortPointer = n-1;
int totalPointer = m+n-1;
while(totalPointer>=0){
if(shortPointer<0){
nums1[totalPointer--]=nums1[longPointer--];
} else if(longPointer<0){
nums1[totalPointer--]=nums2[shortPointer--];
}else if(nums1[longPointer]<nums2[shortPointer]){
nums1[totalPointer--]=nums2[shortPointer--];
}else if(nums1[longPointer]>=nums2[shortPointer]){
nums1[totalPointer--]=nums1[longPointer--];
}
}
}
}
6. 链表之中是否有环
很经典的快慢指针的题目。判断方法如下：
指定一组快慢指针ListNode fast=head, slow = head;然后借助while来不断循环。while之中的循环不需要去考虑slow的下一个指针是否存在，因为fast一定跑的比slow快。但是fast一次会跑两步，有可能遇到跑一步之后就到头的情况，所以要while(fast.next!=null && fast.next.next!=null)两个条件一起判断。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode fast=head, slow = head;
while(fast.next!=null && fast.next.next!=null){
fast=fast.next.next;
slow = slow.next;
if(slow==fast) return true;
}
return false;
}
}
7. 最长子序列
Longest Word in Dictionary through Deleting
本题分成两部分，一部分是判断是否为子序列的方法，一部分是更新替换结果之中的result。
compareTo()这个方法直接进行字典序的排列了，可以a.compareTo(b)当成a-b来看待。- 比较是否为子序列，直接使用双指针即可。一个长序列的指针捋到最后，那么另一个指针如果还没到末尾，就说明不是子序列。
class Solution {
public String findLongestWord(String s, List<String> d) {
String result = "";
for(String tar: d){
int l1 = result.length(), l2 = tar.length();
if(l1>l2||(l1==l2 && result.compareTo(tar)<0)){
continue;
}
if(isSubstring(s,tar)){
result = tar;
}
}
return result;
}
public boolean isSubstring(String s, String tar){
int i=0,j=0;
while(i!=s.length()&&j!=tar.length()){
if(s.charAt(i)==tar.charAt(j)){
j++;
}
i++;
}
return j==tar.length();
}
}
8. 颜色分类
本题是Lucifer的91天学算法的Day2题目，由于也是和双指针相关，所以就一起放上来。
本题思路是使用三个指针，其中一个指向头部，一个指向尾部，然后一个动指针从头一直开始直到超过右边指针。
双指针的用法，目前我个人总结有两点：
- 用来标识两个元素：快慢指针，单纯的二者交换等等
- 用来切割区间：类似本题，使用指针来切割区间。
本题之中，left的左边一定都是0，right右边一定都是2，但是这里的交换需要分情况考虑：
-
如果动指针p指向的元素是0：那么直接和left的元素互换，并且left和p都往后走一位。
这种情况下，p为什么敢向后走：因为p一开始指向的是0，那么left++，p++，这个时候左边都只有一个0，符合left左边都是0，left和p之间都不是0和2（实际上是放1的区间，只是现在区间无值）
-
如果p指向的元素是2：那么和right的元素互换，但是只有right往前走一位。
我们是从左到右判断，而右边的数字我们还没有遍历过，不知道交换回来的是0还是1，那么这个时候p不可以往后走，而是要留在原地判断。所以right–
-
如果p指向的元素是1，那么直接不做处理，p往后走一位就好了。
class Solution {
public void sortColors(int[] nums) {
int left = 0, right = nums.length-1;
int p=0;
while(p<=right){
if(nums[p]==2) {
swap(nums,p,right);
right--;
}else if(nums[p]==0){
swap(nums,p,left);
p++;
left++;
}else{
p++;
}
}
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
9. 链表之中是否有环？入环点的位置？
这个题乍看和6是一样的，实际上第一步判断其是否有环也的确可以使用相同做法。但是第二部分，求入环点这一步对于fast这个指针的循环退出条件就有所不同了。
如何求入环点：
假设fast和slow第一次遇到，那么这个时候fast一定是已经将环走了一圈，slow还没有走完。那么就以这个点为例，设从链表头到入环点的距离是a，从入环点到相遇的距离，也就是slow在环里走过的距离是b，slow还没有走完的距离是c。那么可知：
b+c = 环长，而且fast走的距离是b走的距离的2倍，且fast走的距离是b走的距离+环长。那么就可以得到：
2(a+b)=a+b+b+c
从而得到a=c。
那么，只要让fast从头开始走，slow从相遇点开始走，当slow走了c，到了入环点的时候，fast刚好也走到入环点，二者相遇，直接返回即可。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
fast = head;
while(fast!=null && fast.next!=null){
if(fast==slow) return fast;
fast = fast.next;
slow = slow.next;
}
}
}
return null;
}
}
