標題

• • 串聯所有單詞得字串
  • 下一個排列

維護真的不易，如有幫助還請點贊關注，關注公眾號bigsai回復進群即可加入打卡。

串聯所有單詞得字串

題目描述：

給定一個字符串 s 和一些長度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯形成的子串的起始位置。
注意子串要與 words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮 words 中單詞串聯的順序。

示例 1：

輸入：
s = “barfoothefoobarman”,
words = [“foo”,“bar”]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 “barfoo” 和 “foobar” 。
輸出的順序不重要, [9,0] 也是有效答案。

示例 2：

輸入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
輸出：[]

分析：
這題講真還是挺有技巧和方案的，刷這道題也花了不少心思，需要考慮的點也稍微多一點。題意就是要找到字符串s的某個字串可以由words中所有單詞組成。返回滿足匹配s子串的首位編號。

遞歸法：
從處理的方式上理論是可以使用遞歸的，但是由于層數太多并且個別比較特殊的數據可能導致爆棧TL。這里就有個教訓：

主要當時沒仔細讀題，沒有在意每個單詞長度都相同所以以為是搜索題，后來仔細看題之后才發現問題。

普通哈希法(滑動窗口)
對于有些人叫啥滑動窗口啥稀奇古怪的漂亮名稱，這里我就簡稱為Hash法。如何去分析和處理這個問題呢？我們可以看看一些重要的條件：

• words中所有單詞長度都相同
• 必須使用所有words中的單詞一次

也就是說在進行匹配的時候可以根據單詞進行匹配。

但每個字符串進行判斷的時候，可以進行分割成若干單詞數判斷。

用兩個HashMap儲存單詞數即可，存儲途中進行判斷如果有不滿足直接停止。如果能跑到最后說明可以添加這個標記。

具體實現的代碼為：

public List<Integer> findSubstring(String s, String[] words) {List<Integer>value=new ArrayList<Integer>();Map<String, Integer>map=new HashMap<String, Integer>();for(int i=0;i<words.length;i++){int num=map.getOrDefault(words[i], 0);map.put(words[i], num+1);}int wordlen=words[0].length();int len=words[0].length()*words.length;StringBuilder sBuilder=new StringBuilder(" ");sBuilder.append(s.substring(0, len-1));for(int i=0;i<s.length()-len+1;i++){sBuilder.deleteCharAt(0);sBuilder.append(s.charAt(i+len-1));int num=0;//統計總共滿足的單詞數量Map<String, Integer>map2=new HashMap<String, Integer>();//map2.putAll(map);int index=0;while (index<len) {String team=sBuilder.substring(index,index+wordlen);int number=map2.getOrDefault(team, 0);//次數map2.put(team, number+1);if(number+1>map.getOrDefault(team, 0))break;index+=wordlen;}if(index==len)value.add(i);}return value; }

Hash滑動窗口優化
可以發現在上面所涉及的的滑動處理中每次都需要重新計算當前字符串的HashMap情況并重新匹配。這樣就有很多已經匹配的情況就浪費了。

所以就需要優化來去掉重復的計算，首先要將字符串分成單詞長度的組數來分別計算。

然后每組在詳細進行的時候需要兩個指針動態向右表示區間匹配。而Map通常不需要每次都刷新可以重新利用。一個坐標j代表開頭一個index表示當前結尾。

你可能會遇到以下幾種情況：

• 遇到新單詞不存在，此時j和index都移動到單詞后重新開始，且儲存的動態map需要clear；

• 遇到的單詞存在，但是多了，需要將j右移一直到消除這個多余單詞，同時修改動態map。

• 正常情況，疊加匹配更新index和map。

上面步驟完成之后，如果j+len==index那么就說明完成匹配，添加此個編號。但在此同時，可以判斷下個單詞是否與當前首單詞相等，如果相等直接更新對應j和index順便加入結果集中，不過不需要更新動態的map。

有了上述優化的思路，就可以碼代碼了。注意細節實現，前開后閉等等，具體代碼為：

public List<Integer> findSubstring(String s, String[] words) {List<Integer>value=new ArrayList<Integer>();//返回的結果Map<String, Integer>map=new HashMap<String, Integer>();//統計單詞個數for(String team:words)//進行統計{int num=map.getOrDefault(team, 0);map.put(team, num+1);}int wordlen=words[0].length();//單個單詞的長度int len=words[0].length()*words.length;//總長度for(int i=0;i<wordlen;i++)//分組分別進行{int j=i,index=j;Map<String, Integer>map2=new HashMap<String, Integer>();while (j<=s.length()-len&&index+wordlen<=s.length()) {String word=s.substring(index,index+wordlen);int num=map2.getOrDefault(word, 0);map2.put(word, num+1);if(!map.containsKey(word))//不包含該元素，直接跳過{j=index+wordlen;map2.clear(); }else if(map.get(word)<num+1)//元素存在但次數過多{String teamstr="";while (!(teamstr=s.substring(j,j+wordlen)).equals(word)) {//找到第一個不相等得map2.put(teamstr, map2.get(teamstr)-1);j+=wordlen;}map2.put(teamstr, map2.get(teamstr)-1);j+=wordlen;}index+=wordlen;if(index==j+len){value.add(j);while (index+wordlen<=s.length()&&s.substring(j, j+wordlen).equals(s.substring(index, index+wordlen))) {value.add(j+wordlen);j+=wordlen;index+=wordlen;} String teamstr=s.substring(j,j+wordlen);map2.put(teamstr, map2.get(teamstr)-1);j+=wordlen;}}}return value; }

下一個排列

題目描述：
實現獲取下一個排列的函數，算法需要將給定數字序列重新排列成字典序中下一個更大的排列。

如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列）。

必須原地修改，只允許使用額外常數空間。

以下是一些例子，輸入位于左側列，其相應輸出位于右側列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

分析：
是不是和全排列有點像，但是又不是全排列。是需要找到下一個字典序。
分析數列你會發現以下兩個規律：

首先從右往左交換第一個正序：

• 例如1 2 3 5 4 交換3和4成為1 2 4 5 3.

其次根據交換的區間內，從右向左(雙重循環)交換逆序對：

• 例如上述變成1 2 4 3 5；

具體實現的時候，注意位置編號等問題。具體代碼為：

public void nextPermutation(int[] nums) {boolean jud=false;int i,j=0;for( i=nums.length-2;i>=0;i--){for( j=nums.length-1;j>i;j--){if(!jud&&nums[i]<nums[j]){int team=nums[i];nums[i]=nums[j];nums[j]=team;jud=true;break;}}if(jud)break;}if(jud)for(int k=nums.length-1;k>i;k--){for(int m=k-1;m>i;m--){if(nums[k]<nums[m]){int team=nums[k];nums[k]=nums[m];nums[m]=team;}}}int team;if(!jud)for( i=0;i<nums.length/2;i++){team=nums[i];nums[i]=nums[nums.length-1-i];nums[nums.length-1-i]=team;}}

好啦，本次打卡就到這里啦，更多精彩歡迎關注bigsai,回復進群加入打卡，回復bigsai獲取珍藏pdf資源。

總結

以上是生活随笔為你收集整理的LeetCode 30串联所有单词的子串31下一个排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。