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源創計劃”，歡迎正在閲讀的你也加入，一起分享。

「其他文章」