目錄

一、單詞拆分?

二、環繞字符串中唯一的子字符串

雙指針-三數之和

ArrayList(Arrays.asList(array))

四、四數之和（思路和三數之和一樣，只是多了一層循環）

---

一、單詞拆分?

1.狀態表示

dp[i]:到達i位置結尾，能否被dict拆分

最難的我認為到現在為止就是選擇狀態如何表示

dp[i]:[0,i]區間內的字符串，能否被字典中的單詞拼接而成

2.狀態轉移方程

設置j為i位置位置最后一個單詞的第一個字母

那么dp[i]->dp[j-1]==true&&s[j,i]這個字符串在dict之中

3.初始化

dp[0]=s[0]在dict中,就是true。

dp[m+1]:直接擴大一個格子，這樣他就不需要考慮邊界

我們可以讓s這個字符串前面加一個空格

這樣字符串就會往后挪動一個空格

4.順序是

從左到右

5.返回值

dp[n]

優化：既然可以有重復，重復可以一直使用，那么可以人工把這個dict中去重放到set中，這樣，重復的問題就可以不用去考慮了

簡單來說，包頭不包尾巴。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> hash=new HashSet(wordDict);int m=s.length();  boolean []dp=new boolean[m+1];//加一個占位符，可以處理下標的映射關系s=" "+s;dp[0]=true;//遍歷從1開始，是因為不去考慮邊界條件區域
//dp[i]:[0,i]區間內的字符串，能否被字典中的單詞拼接而成
//設置j為i位置位置最后一個單詞的第一個字母，i+1的原因是往后推了一個格子。
//--的原因是什么呢？他這個過程，我認為像是找最后一個單詞的第一個字母是什么，所以才會有--的原因，是因為--從最后開始遍歷去尋找
//另外，他那個sub是包頭不包尾巴，所以說那個需要到i+1,但是實際也就是j-ifor(int i=1;i<=m;i++){for(int j=i;j>=1;j--){if(dp[j-1]&& hash.contains(s.substring(j,i+1))){dp[i]=true;//假如有一個方式匹配成功了，那么就不需要別的方式了，可以直接跳出break;}}}
return dp[m];}
}

二、環繞字符串中唯一的子字符串

1.狀態表示

dp[i]:到達i為止，有dp[i]個非空字符串在base中存在過

2.狀態轉移方程

假如說連接的情況只有兩種

一種是后面減去前面的等于一

第二種就是前面的是z后面的是a相差25

假如她這個連接不起來，就是自然的單獨一個

這個時候我已經看第二個實例：在想一個問題，可不可以把它放到set里面去重，假如去重來會怎么樣？但是我又想到一個問題，假如去重了，那么假如這種abcdefghigklmnopqrstuvwxyza ，一圈之后還有個a，怎么辦，那么這樣就不能使用傳統意義上的去重，不妨使用數組（26個字母，就26個容量），然后去更新數組的值，假如a[0]==xx,那么下次在第n次的時候會再次到達，a[0]更新到最大值。

雙指針-三數之和

三數之和：采用雙指針的操作。

class Solution {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>>ret=new ArrayList<>();int m=nums.length;Arrays.sort(nums);for(int i=0;i<m;){int left=i+1,right=m-1;int a=nums[i];while(left<right){if(nums[left]+nums[right]<-a){left++;}else if(nums[left]+nums[right]>-a){right--;}else{
//Arrays.asList():這個方法是什么意思呢？
//這個方法的意思是將數組轉化成List集合的方法。也就是說把數組這個三個元素裝入List集合里面
//（1）該方法適用于對象型數據的數組（String、Integer...）//（2）該方法不建議使用于基本數據類型的數組（byte,short,int,long,float,double,boolean）
//這個方法是使用包裝類(Integer等)//（3）該方法將數組與List列表鏈接起來：當更新其一個時，另一個自動更新//（4）不支持add()、remove()、clear()等方法ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
//縮小區間繼續尋找left++;right--;
//對于去重：left是往右走，那么就是他和上一個看是不是一樣的。while(left<right&&nums[left]==nums[left-1])left++;
//right是往左走，他和右邊那個是不是一樣。while(left<right&&nums[right]==nums[right+1])right--;}}//本身的i也需要去去重，i<m，如果i和前一個i-1一樣，那么就去再次去重i++;while(i<m && nums[i]==nums[i-1])i++;}return ret;
}
}

因為left+right已經不可能會出現小于0的情況

其次我們要熟悉兩個方法

我本是對JAVA的集合方面不是很熟系，所以我會在下面再去寫一些我不熟悉的東西

List<List<Integer>>ret=new ArrayList<>();

Arrays.asList:這個方法，只推薦用于遍歷，而不推薦進行刪改等操作，它是把數組元素轉換成集合，這種方法，你在修改他的時候，也會影響到原先的數組，所以推薦是（不去用它刪除，只去遍歷）

ArrayList(Arrays.asList(array))

與?Arrays.asList?方法一樣，我們還可以使用?ArrayList<>(Arrays.asList(array))?來從 Array 創建一個 List。

但是，與上面的方法不一樣的是，使用這個方法創建的 List 是一個從老的 Array 中數據拷貝過來的，這個新的 List 與老的 Array 不相干，對新 List 中數據的操作不會影響到老的 Array 中的數據。

使用這種方法創建的 List 是可以對 List 中的元素進行添加和刪除操作的。

https://www.cnblogs.com/huyuchengus/p/15132032.html

一個關于ArrayList(Array.asList(array))和普通的Array.asList()的區別

四、四數之和（思路和三數之和一樣，只是多了一層循環）

class Solution {public  static List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>>ret=new ArrayList<>();int m=nums.length;Arrays.sort(nums);for(int i=0;i<m;){for(int j=i+1;j<m;){int left=j+1;int right=m-1;long n=(long)target-nums[i]-nums[j];while(left<right){if(nums[left]+nums[right]>n){right--;}else if(nums[left]+nums[right]<n){left++;}else{ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[i], nums[j], nums[right])));left++;right--;while (nums[left] == nums[left - 1] && left < right) left++;while (nums[right] == nums[right + 1] && left < right) right--;}}j++;while(j<m&&nums[j]==nums[j-1]&&j<m){j++;}}i++;while(i>0&&i<m&&nums[i]==nums[i-1])i++;}return ret;
}}

這里使用long是為了處理一組數據，因為int的數值有一定范圍，所以不可以用int去承載那么多的數，所以使用long

這里我還要講一個

if ?

else if

else

是說假如if不成立，看else if成不成立，但假如說if成立的情況下，這層循環結束，開始下一次循環，不執行下面邏輯的判斷