当前位置：网站首页>LeetCode 1079. 活字印刷

LeetCode 1079. 活字印刷

2022-06-23 18:35:00 【51CTO】

LeetCode 1079. 活字印刷_活字印刷

想看更多算法题，可以扫描上方二维码关注我微信公众号“数据结构和算法”，截止到目前我已经在公众号中更新了500多道算法题，其中部分已经整理成了pdf文档，截止到目前总共有1000多页（并且还会不断的增加），可以在公众号中回复关键字“pdf”即可下载。

LeetCode 1079. 活字印刷_sed_02

回溯算法解决

这题实际上是让求输入的字符可以组成多少种不同的组合。之前也讲过很多种类似这样的题

《391，回溯算法求组合问题》《448，组合的几种解决方式》《451，回溯和位运算解子集》

但不同的是前面几道题字符出现的顺序是不会变的，比如第451题，他的子集有123，但不能有321。但这题不一样，输入AAB，他的序列中，A可以在B的前面也可以在B的后面。那么这道题使用回溯算法该怎么解，我们就以示例1为例来画个图看一下

LeetCode 1079. 活字印刷_回文算法_03
前面介绍的几个组合的回溯算法，因为结果不能有重复的（比如[1，3]和[3，1]被认为是重复的结果），所以每次选择的时候都只能从前往后选。但这题中子集[A，B]和[B，A]被认为是两种不同的结果，所以每次都要从头开始选择，因为每个字符只能被使用一次，所以如果使用之后下次就不能再使用了，这里可以使用一个数组visit来标记有没有被使用。

但这里有个难点就是怎么过滤掉上面图中灰色的部分（也就是重复的部分）。举个例子，比如ABBCD，如果我们选择了第1个B，那么剩余的字符就变成了ABCD，这个时候我们再选择第2个B是可以的。但如果我们没选择第1个B，直接选择第2个B，那么剩余的字符就是ABCD，和上面重复了。所以代码大致是这样的

在前面讲《450，什么叫回溯算法，一看就会，一写就废》的时候，回溯算法的模板也被多次提及

       
       private 
       
       void 
       
       backtrack(
       
       "原始参数") {
       
       //终止条件(递归必须要有终止条件)
       
       if (
       
       "终止条件") {
       
       //一些逻辑操作（可有可无，视情况而定）
       
       return;
       
    }
       
       for (
       
       int 
       
       i 
       
       = 
       
       "for循环开始的参数"; 
       
       i 
       
       < 
       
       "for循环结束的参数"; 
       
       i
       
       ++) {
       
       //一些逻辑操作（可有可无，视情况而定）
       
       //做出选择
       
       //递归
       
       backtrack(
       
       "新的参数");
       
       //一些逻辑操作（可有可无，视情况而定）
       
       //撤销选择
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

最后来看下这题的最终代码

       
       public 
       
       int 
       
       numTilePossibilities(
       
       String 
       
       tiles) {
       
       char[] 
       
       chars 
       
       = 
       
       tiles.
       
       toCharArray();
       
       //先排序，目的是让相同的字符挨着，在下面计算的时候好过滤掉重复的
       
       Arrays.
       
       sort(
       
       chars);
       
       int[] 
       
       res 
       
       = 
       
       new 
       
       int[
       
       1];
       
       backtrack(
       
       res, 
       
       chars, 
       
       new 
       
       boolean[
       
       tiles.
       
       length()], 
       
       tiles.
       
       length(), 
       
       0);
       
       return 
       
       res[
       
       0];
       
}
       
       private 
       
       void 
       
       backtrack(
       
       int[] 
       
       res, 
       
       char[] 
       
       chars, 
       
       boolean[] 
       
       used, 
       
       int 
       
       length, 
       
       int 
       
       index) {
       
       //如果没有可以选择的就返回
       
       if (
       
       index 
       
       == 
       
       length)
       
       return;
       
       //注意，这里的i每次都是从0开始的，不是从index开始
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       length; 
       
       i
       
       ++) {
       
       //一个字符只能选择一次，如果当前字符已经选择了，就不能再选了。
       
       if (
       
       used[
       
       i])
       
       continue;
       
       //过滤掉重复的结果
       
       if (
       
       i 
       
       - 
       
       1 
       
       >= 
       
       0 
       
       && 
       
       chars[
       
       i] 
       
       == 
       
       chars[
       
       i 
       
       - 
       
       1] 
       
       && 
       
       !
       
       used[
       
       i 
       
       - 
       
       1])
       
       continue;
       
       //选择当前字符，并把它标记为已选择
       
       used[
       
       i] 
       
       = 
       
       true;
       
       res[
       
       0]
       
       ++;
       
       //选择一个字符，就多了一种结果
       
       //下一分支继续递归
       
       backtrack(
       
       res, 
       
       chars, 
       
       used, 
       
       length, 
       
       index 
       
       + 
       
       1);
       
       //使用完之后再把它给复原。
       
       used[
       
       i] 
       
       = 
       
       false;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

这里还可以换一种写法，先统计每个字符的数量，然后再使用，代码如下。原理都类似，但他不需要去重，因为这里根本不可能出现重复的。

       
       public 
       
       int 
       
       numTilePossibilities(
       
       String 
       
       tiles) {
       
       char[] 
       
       chars 
       
       = 
       
       tiles.
       
       toCharArray();
       
       //统计每个字符的数量
       
       int[] 
       
       count 
       
       = 
       
       new 
       
       int[
       
       26];
       
       for (
       
       char 
       
       c : 
       
       chars)
       
       count[
       
       c 
       
       - 
       
       'A']
       
       ++;
       
       int[] 
       
       res 
       
       = 
       
       new 
       
       int[
       
       1];
       
       backtrack(
       
       res, 
       
       count);
       
       return 
       
       res[
       
       0];
       
}
       
       private 
       
       void 
       
       backtrack(
       
       int[] 
       
       res, 
       
       int[] 
       
       arr) {
       
       //遍历所有的字符
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       26; 
       
       i
       
       ++) {
       
       //如果当前字符使用完了再查找下一个
       
       if (
       
       arr[
       
       i] 
       
       == 
       
       0)
       
       continue;
       
       //如果没使用完就继续使用，然后把这个字符的数量减1
       
       arr[
       
       i]
       
       --;
       
       //使用一个字符，子集数量就会多一个
       
       res[
       
       0]
       
       ++;
       
       backtrack(
       
       res, 
       
       arr);
       
       //当前字符使用完之后，把它的数量还原
       
       arr[
       
       i]
       
       ++;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

总结

前面也介绍过很多关于回溯算法的题，回溯算法有个大致的模板，只要掌握这个模板，然后对于不同的题在稍加修改，基本上都能做的出来。

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_4774266/5412484

当前位置：网站首页>LeetCode 1079. 活字印刷

LeetCode 1079. 活字印刷

回溯算法解决

总结

边栏推荐

猜你喜欢

随机推荐