LeetCode 90子集Ⅱ&91解码方法

叁歲伎倆 2022-12-30 14:50 155阅读 0赞

> **微信搜一搜**：`bigsai` 专注于Java、数据结构与算法，**一起进大厂不迷路！**  
> **算法文章题解全部收录在github仓库[bigsai-algorithm][],求star！**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 79单词搜索&80删除排序数组中的重复项Ⅱ&81.搜索旋转排序数组Ⅱ][LeetCode 79_80_81.]  
> [LeetCode 86分割链表&87扰乱字符串][LeetCode 86_87]  
> [LeetCode 88合并两个有序数组&89格雷编码][LeetCode 88_89]

## 子集Ⅱ ##

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

**分析：**  
这道题和上道求子集不同的是这里面可能会出现重复的元素。我们需要在结果中过滤掉重复的元素。

首先，子集问题无疑是使用回溯法求得结果，首先分析如果序列没有重复的情况，我们会借助一个boolean\[\]数组标记使用过的元素和index表示当前的下标，在进行回溯的时候我们只向后进行递归并且将枚举到的那个元素boolean\[index\]置为true(回来的时候复原)。每次递归收集boolean\[\]数组中true的元素为其中一个子集。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]  
而有重复元素的处理上，和前面全排列的处理很相似，首**先进行排序**，然后在进行递归处理的时候遇到相同元素只允许从第一位连续使用而不允许跳着使用，具体可以参考这张图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]

实现代码为：

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请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[bigsai-algorithm]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 79_80_81.]: https://bigsai.blog.csdn.net/article/details/110734770
[LeetCode 86_87]: https://bigsai.blog.csdn.net/article/details/111356921
[LeetCode 88_89]: https://bigsai.blog.csdn.net/article/details/111412194
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/16f1a8866b2042649fbee5b82a00638f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/17cefbfce35544daa6210338c87dd36e.png
[image-20201114211553660]: /images/20221120/156588c7d4d145c5af4f121c894a4c0a.png