当前位置：网站首页>LeetCode 1079. movable-type printing

LeetCode 1079. movable-type printing

2022-06-23 19:28:00 【51CTO】

LeetCode 1079. movable-type printing _ movable-type printing

Want to see more algorithm problems , You can scan the QR code above to follow my wechat official account “ Data structures and algorithms ”, Up to now, I have been in the official account Updated 500 Multiple algorithm problems , Some of them have been sorted into pdf file , Up to now, there are a total of 1000 Multi page （ And it will continue to increase ）, You can reply to keywords in the official account “pdf” You can download it. .

LeetCode 1079. movable-type printing _sed_02

Backtracking algorithm solves

This question is actually how many different combinations of input characters can be formed . I've talked about many similar problems before

《391, Backtracking algorithm for combinatorial problems 》《448, Combined solutions 》《451, Backtracking and bit operations solve subsets 》

But the difference is that the order of the characters in the previous questions will not change , For example 451 topic , His subset is 123, But there can be no 321. But the question is different , Input AAB, In his sequence ,A Can be in B It can also be in front of B Behind . So how to solve this problem using backtracking algorithm , Let's take an example 1 Let's draw a picture for example

LeetCode 1079. movable-type printing _ Palindrome algorithm _03
Several combination backtracking algorithms introduced earlier , Because the results can't be repeated （ such as [1,3] and [3,1] It is considered to be the result of repetition ）, So every time you choose, you can only choose from the past . But this problem subset [A,B] and [B,A] It is considered to be two different results , So choose from the beginning every time , Because each character can only be used once , So if you use it, you can't use it next time , You can use an array here visit To mark whether it has been used .

But the difficulty here is how to filter out the gray part in the above figure （ That's the repetitive part ）. for instance , such as ABBCD, If we choose the second 1 individual B, Then the rest of the characters become ABCD, At this time, we will choose the second 2 individual B Yes. . But if we don't choose the second 1 individual B, Choose the second one directly 2 individual B, Then the remaining characters are ABCD, It's repeated above . So the code looks like this

Let's talk about 《450, What is a backtracking algorithm , As soon as we see it , As soon as you write it, it's useless 》 When , The template of backtracking algorithm has been mentioned many times

       
       private 
       
       void 
       
       backtrack(
       
       " Original parameters ") {
       
       // Termination conditions ( Recursion must have a termination condition )
       
       if (
       
       " Termination conditions ") {
       
       // Some logic operations （ not essential , As the case may be ）
       
       return;
       
    }
       
       for (
       
       int 
       
       i 
       
       = 
       
       "for The parameters at the beginning of the loop "; 
       
       i 
       
       < 
       
       "for Parameters at the end of the loop "; 
       
       i
       
       ++) {
       
       // Some logic operations （ not essential , As the case may be ）
       
       // Make a choice 
       
       // recursive 
       
       backtrack(
       
       " New parameters ");
       
       // Some logic operations （ not essential , As the case may be ）
       
       // Unselect 
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

Finally, let's look at the final code of this problem

       
       public 
       
       int 
       
       numTilePossibilities(
       
       String 
       
       tiles) {
       
       char[] 
       
       chars 
       
       = 
       
       tiles.
       
       toCharArray();
       
       // Prioritize , The goal is to have the same characters next to , In the following calculation, we can filter out the duplicate 
       
       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 there is nothing to choose from, return to 
       
       if (
       
       index 
       
       == 
       
       length)
       
       return;
       
       // Be careful , there i Every time from 0 At the beginning , Not from index Start 
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       length; 
       
       i
       
       ++) {
       
       // A character can only be selected once , If the current character has been selected , You can't choose any more .
       
       if (
       
       used[
       
       i])
       
       continue;
       
       // Filter out duplicate results 
       
       if (
       
       i 
       
       - 
       
       1 
       
       >= 
       
       0 
       
       && 
       
       chars[
       
       i] 
       
       == 
       
       chars[
       
       i 
       
       - 
       
       1] 
       
       && 
       
       !
       
       used[
       
       i 
       
       - 
       
       1])
       
       continue;
       
       // Select the current character , And mark it as selected 
       
       used[
       
       i] 
       
       = 
       
       true;
       
       res[
       
       0]
       
       ++;
       
       // Choose a character , One more result 
       
       // The next branch continues recursion 
       
       backtrack(
       
       res, 
       
       chars, 
       
       used, 
       
       length, 
       
       index 
       
       + 
       
       1);
       
       // Restore it after use .
       
       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.

Here can also be written in another way , First count the number of each character , And then use , The code is as follows . The principle is similar , But he doesn't have to be heavy , Because there's no possibility of repetition here .

       
       public 
       
       int 
       
       numTilePossibilities(
       
       String 
       
       tiles) {
       
       char[] 
       
       chars 
       
       = 
       
       tiles.
       
       toCharArray();
       
       // Count the number of each character 
       
       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) {
       
       // Traverse all the characters 
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       26; 
       
       i
       
       ++) {
       
       // If the current character is used up, look for the next 
       
       if (
       
       arr[
       
       i] 
       
       == 
       
       0)
       
       continue;
       
       // If it's not used up, keep using it , And then subtract the number of characters 1
       
       arr[
       
       i]
       
       --;
       
       // Use one character , The number of subsets will be one more 
       
       res[
       
       0]
       
       ++;
       
       backtrack(
       
       res, 
       
       arr);
       
       // After the current character is used , Restore the number of it 
       
       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.

summary

I have also introduced many problems about backtracking algorithm , The backtracking algorithm has a general template , Just master this template , And then for different questions in slightly modified , Basically, it can be done .

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/174/202206231833090564.html

当前位置：网站首页>LeetCode 1079. movable-type printing

LeetCode 1079. movable-type printing

Backtracking algorithm solves

summary

边栏推荐

猜你喜欢

随机推荐