LeetCode 90子集Ⅱ&91解碼方法

語言: CN / TW / HK

時間 2020-12-27 00:01:34 bigsai

主題:

微信搜一搜：bigsai 專注於Java、資料結構與演算法，一起進大廠不迷路！
演算法文章題解全部收錄在github倉庫bigsai-algorithm,求star！
關注回覆進群即可加入力扣打卡群，歡迎划水。近期打卡：
LeetCode 79單詞搜尋&80刪除排序陣列中的重複項Ⅱ&81.搜尋旋轉排序陣列Ⅱ
LeetCode 86分割連結串列&87擾亂字串
 LeetCode 88合併兩個有序陣列&89格雷編碼

子集Ⅱ

給定一個可能包含重複元素的整數陣列 nums，返回該陣列所有可能的子集（冪集）。

說明：解集不能包含重複的子集。

示例:

輸入: [1,2,2]
輸出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

分析：
這道題和上道求子集不同的是這裡面可能會出現重複的元素。我們需要在結果中過濾掉重複的元素。

首先，子集問題無疑是使用回溯法求得結果，首先分析如果序列沒有重複的情況，我們會藉助一個boolean[]陣列標記使用過的元素和index表示當前的下標，在進行回溯的時候我們只向後進行遞歸併且將列舉到的那個元素boolean[index]置為true(回來的時候復原)。每次遞迴收集boolean[]陣列中true的元素為其中一個子集。
在這裡插入圖片描述
而有重複元素的處理上，和前面全排列的處理很相似，首先進行排序，然後在進行遞迴處理的時候遇到相同元素只允許從第一位連續使用而不允許跳著使用，具體可以參考這張圖：

實現程式碼為：

class Solution {
   
   
    public List<List<Integer>> subsetsWithDup(int[] nums) {
   
   
		 Arrays.sort(nums);
		 boolean jud[]=new boolean[nums.length];
		 List<List<Integer>> valueList=new ArrayList<List<Integer>>();
		 dfs(nums,-1,valueList,jud);
		return valueList;

	    }

	private void dfs(int[] nums, int index, List<List<Integer>> valueList, boolean[] jud)   {
   
   
		// TODO Auto-generated method stub
		List<Integer>list=new ArrayList<Integer>();
		for(int i=0;i<nums.length;i++)
		{
   
   
			if (jud[i]) {
   
   
			   list.add(nums[i]);
			}
		}
		valueList.add(list);
		for(int i=index+1;i<nums.length;i++)
		{
   
   
			if((i==0)||(nums[i]!=nums[i-1])||(i>0&&jud[i-1]&&nums[i]==nums[i-1]))
			{
   
   
				jud[i]=true;
				dfs(nums, i, valueList,jud);
				jud[i]=false;
			}
		}
	}
}

解碼方法

一條包含字母 A-Z 的訊息通過以下方式進行了編碼：

'A' -> 1
'B' -> 2
...
'Z' -> 26

給定一個只包含數字的非空字串，請計算解碼方法的總數。

題目資料保證答案肯定是一個 32 位的整數。

示例 1：

輸入：s = "12"
輸出：2
解釋：它可以解碼為 "AB"（1 2）或者 "L"（12）。

示例 2：

輸入：s = "226"
輸出：3
解釋：它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

輸入：s = "0"
輸出：0
示例 4：

輸入：s = "1"
輸出：1

示例 5：

輸入：s = "2"
輸出：1

提示：

1 <= s.length <= 100
s 只包含數字，並且可能包含前導零。

分析
本題是個動態規劃的題，轉移方程不是很難但是需要考慮的點比較多。[a-z]之間的字串。dp[]表示狀態轉移陣列，有以下狀態需要考慮：

(1) xx10 xx20 結尾只能 xx (J) 和 xx（T）這種轉換 dp[i]=dp[i-2]
(2) xx40 等數字大於20且%10==0的數字不可能組合返回 0
(3) xx01-xx09 分解為x(x0)1-x(x0)9 dp[i]=dp[i-1]
(4) xx27 等大於26分解為xx(2)(7) 那麼dp[i]=dp[i-1]
(5) xx25等其他數字可能分解為xx(2)(5)或者xx(25)

實現程式碼為：

class Solution {
   
   
    public int numDecodings(String s) {
   
   
       if(s.length()==0||s.charAt(0)=='0')
            return  0;
        char chS[]=s.toCharArray();
        int dp[]=new int[chS.length+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<chS.length+1;i++)
        {
   
   
            int value=(chS[i-2]-'0')*10+(int)(chS[i-1]-'0');
            if(value==10||value==20)
                dp[i]=dp[i-2];
            else if(value%10==0)
                return  0;
            else if(value>26||value<10)
                dp[i]=dp[i-1];
            else
                dp[i]=dp[i-1]+dp[i-2];
        }
        return  dp[chS.length];
    }
}

原創不易，bigsai請你幫兩件事幫忙一下:

star支援一下，您的肯定是我在平臺創作的源源動力。
微信搜尋「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關注、咱們下次再見！

本文同步分享在部落格“Big sai”（CSDN）。
如有侵權，請聯絡 [email protected] 刪除。
本文參與“OSC源創計劃”，歡迎正在閱讀的你也加入，一起分享。

「其他文章」