題目一

給定三個字符串str1、str2和aim， 如果aim包含且僅包含來自str1和str2的所有字符，而且在aim中屬于str1的字符 之間保持原來在str1中的順序，屬于str2的字符之間保持原來在str2中的順序，那么稱aim是str1和str2的交錯組成。實現一個函數，判斷aim是 否是str1和str2交錯組成
[舉例] str1="AB"， str2="12"。 那么"AB12"、"A1B2"、 "A12B"、 "1A2B"和"1AB2"等都是str1和str2的交錯組成
?

雙指針法只能用在沒有重復值的情況?如果有重復值?雙指針法就不再適用了

首先如果長度不一致的話?aim!=str1+str2的時候?直接過濾掉

dp[i][j]?是str1 0....i和str2 0....j?能否交錯組成aim 0.....i+j

basecase的話?第一行還算好找?第一列也是??

經典字符串考慮?不要的情況?dp[0]位置全是str1一個字符都不要?不過這么做之后確實簡單了不少?要不basecase就夠喝一壺了

所以?相等就是可以?不等就是不行

然后dp[i][j]依賴于?它的前一個格子和上一個格子

就是你新加入了一個字符?那么我們就看這個新加的字符和aim對應位置的字符是否相同

因為是交錯組成?假如說前面已經是兩個字符串交錯組成而來的話那我們只需要看最新的位置

if(s3.length()!=s1.length()+s2.length()) {return false;}char [] aim = s3.toCharArray();char [] chars1 = s1.toCharArray();char [] chars2 = s2.toCharArray();int length1 = chars1.length;int length2 = chars2.length;boolean [][] dp = new boolean [length1+1][length2+1];dp[0][0] = true;for(int i = 1;i<=length1;i++) {if(chars1[i-1]!=aim[i-1]) {break;}dp[i][0] = true;  }for(int i = 1;i<=length2;i++) {if(chars2[i-1]!=aim[i-1]) {break;}dp[0][i] = true;  }for(int i = 1;i<=length1;i++) {for(int j = 1;j<=length2;j++) {if ((chars1[i - 1] == aim[i + j - 1] && dp[i - 1][j])|| (chars2[j - 1] == aim[i + j - 1] && dp[i][j - 1])) {dp[i][j] = true;}}}return dp[length1][length2];}

題目二

給定一個無序數組arr.如果只能再一個子數組上排序 返回如果讓arr整體有序，需要排序的最短子數組長度
無論中間的有序數組有多長?邊上有元素無序都不行?所以我們看兩側不用排的有多少?

public static int [] getMinLength(int[] arr) {if (arr == null || arr.length < 2) {return new int [] {-1,-1};}int N = arr.length;int leftno = -1;int max = arr[0];int righton = -1;int min = arr[N-1];for(int i = 1;i<N;i++) {if(max > arr[i]) {leftno = i-1;break;}max = arr[i];}for(int i = N-2;i>=0;i--) {if(min<arr[i]) {righton = i+1;break;}min = arr[i];}return new int [] {leftno,righton};}

我剛開始是這么寫的?但是只是兩邊有序是不行的?例如 1,2,3......?1,2,3? 這樣的?就是錯的??

從后往前找?找到最前面一個無序的?從前往后找?找最后一個無序的?這樣才對?這樣找出來的才是最邊上的無序的

第三題

讀題都得讀一會?

要注意我們要求的是整個數組的最小組成和?不是某個子數組的不可組成和?只要一個子數組可以組成?那么整體就可以組成

做一個dp數組?dp[i][j]?表示數組0...i的累加和能否得到j

啊?填第一列?肯定能?我一個不要?不就是累加和0

dp[i][j]? 它依賴于dp[i-1][j-arr[i]]? 如果只用i-1個元素?就能湊出j-arr[i]的話?那么我們再加上一個元素?就能湊出j

或者?dp[i-1][j]?如果四個元素都能推出j?那五個元素也能推出?我不要新的元素不就得了

所以這個格子的位置是?可不可以推出?而不是等不等于

可以有可以的推法被?可以是包含等于的?所以我們又有了個依賴dp[i-1][j]

既然我有 0....i了?那我就可以湊出任何一個位置的?累加和可不可以得到某個值(其實用不上?只要最后一行?所有元素都要能推出什么值)

然后我們拿最后一行?也就是說我們用所有元素?可以推出什么不可以推出什么

啊?所以最開始我們求sum的時候把min和一起求了?后面還有用(max不用求?就是sum)

public static int  unformedSum(int[] arr) {if (arr == null || arr.length == 0) {return 1;}int N = arr.length;int Min = Integer.MAX_VALUE;int sum = 0;for (int i : arr) {Min = Math.min(Min,i);sum+=i;}boolean [][] dp = new boolean [N][sum+1];for(int i = 1;i<N;i++) {dp[i][0] = true;}for(int i = 0;i<N;i++) {for(int j = 1;j<sum+1;j++) {dp[i][j] = dp[i-1][j]||((j-arr[i]>=0)?dp[i-1][j-arr[i]]:false);}}for (int j = min; j <= sum; j++) {if (!dp[N - 1][j]) {return j;}}return sum + 1;}

那么升級版的問題怎么解

整數數組永遠包含1?也就是最小不可組成和永遠要從2開始算

先把整個數組從小到大排序

定義一個變量?range?含義是1.....range的數都可求

a是一個遍歷數組的指針

如果a<=range+1

那么就?range =?range+a?舉個例子 a = 5?range = 20?也就是說range<=20的所有數都能求出來?那么就必然存在 20+5 19+5 18+5 +17+5?讓它把21到25填好

如果a>range+1

a = 50； range = 30? 50>31?前面的一堆玩意都湊不出來31?你比31還大?那更湊不出來了?第一個出現的大于就是最小不可求

為啥是range+1?當a==range+1 的時候? 假如說a = 5?range = 4?這個時候? 9完全可以通過之前的方式得出?如果a要是再大一點呢 6 a = 6?range仍等于4?那么4通過累加就無法得到5了?他們就缺了?這個東西本質是要求?range的最大范圍要和a是相鄰的?才能嚴格的推出每一個值

4 5?相鄰?中間沒有真空期是前面的累加不出來?加上后面的更累加不出來?range后面這個數?要一個數加上a才能累加出來?如果a本身就比這個大?那家多少都累加不出來

public static int unformedSum3(int[] arr) {if (arr == null || arr.length == 0) {return 0;}Arrays.sort(arr); // O (N * logN)int range = 1;// arr[0] == 1for (int i = 1; i != arr.length; i++) {if (arr[i] > range + 1) {return range + 1;} else {range += arr[i];}}return range + 1;}