当前位置：网站首页>Yyds dry goods inventory leetcode question set 751 - 760

Yyds dry goods inventory leetcode question set 751 - 760

2022-07-06 19:25:00 【Brother daze who loves learning】

LeetCode Exercise set
Some questions may be skipped directly , Brush before tidying up leetcode

752. Open the turntable lock

You have a turntable lock with four round pulleys . Every wheel has 10 A digital ： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ . Each wheel can rotate freely ： For example, put ‘9’ Turn into ‘0’,‘0’ Turn into ‘9’ . Each rotation can only rotate one digit of a wheel .

The initial number of locks is ‘0000’ , A string representing the number of four dials .

list deadends Contains a set of death figures , Once the number of dials is the same as any element in the list , This lock will be permanently locked , Can't be rotated again .

character string target Represents a number that can be unlocked , You need to give the minimum number of rotations , If you can't unlock it anyway , return -1.

 Example  1:

 Input ：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
 Output ：6
 explain ：
 The possible moving sequence is  "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
 Be careful  "0000" -> "0001" -> "0002" -> "0102" -> "0202"  Such a sequence cannot be unlocked ,
 Because when it comes to  "0102"  The lock will be locked .
 Example  2:

 Input : deadends = ["8888"], target = "0009"
 Output ：1
 explain ：
 Just rotate the last bit in reverse once  "0000" -> "0009".
 Example  3:

 Input : deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
 Output ：-1
 explain ：
 Unable to rotate to target number and not locked .
 Example  4:

 Input : deadends = ["0000"], target = "8888"
 Output ：-1
 

     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.

Tips ：

Death list deadends The length range of is [1, 500].
Target number target Not in deadends In .
Every deadends and target The number of strings in will be in 10,000 A possible situation ‘0000’ To ‘9999’ Produced in .

class Solution {
      public int openLock(String[] deadends, String target) {
        final List<String> deals = Arrays.asList(deadends);
        if (deals.contains("0000")) return -1;

        final List<String> options = new ArrayList<>(); //  Reach the target number  8  Status 
        // Each person counts the possibility of turning left and right 
        for (int i = 0; i < 4; i++) {
            char[] cs = target.toCharArray();
            char c = cs[i];
            cs[i] = (char) ((c - 48 + 1) % 10 + 48);
            options.add(new String(cs));
            cs[i] = (char) ((c - 48 + 9) % 10 + 48);
            options.add(new String(cs));
        }

        options.removeAll(deals); //  Remove the death number from the reachable number 
        if (options.isEmpty()) return -1; //  Reach the target number  8  All States return directly in the death number 

        int step = Integer.MAX_VALUE;
        for (String option : options) { //  Judge the shortest rotation times in the reachable state 
            int curStep = 1;
            char[] cs = option.toCharArray();
            for (int i = 0; i < 4; i++) {
                int num = cs[i] - 48; // '0'  by  48  Reduce implicit conversions 
                if (num > 5) curStep += 10 - num; //  Judge positive rotation , Reverse 
                else curStep += num;
            }
            step = Math.min(curStep, step); //  Record the minimum number of rotations 
        }
        return step;
    }
}

     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.
31.
32.
33.

753. Crack the safe

There's a safe that needs a password to open . The password is n digit , Every bit of the code is k Bit sequence 0, 1, …, k-1 One of them .

You can enter the password as you like , The safe will automatically remember the last n An input , If the match , You can open the safe .

for instance , Suppose the password is “345”, You can type “012345” To open it , It's just that you typed in 6 Characters .

Please return the shortest string that can open the safe .

Example 1:

Input : n = 1, k = 2
Output : “01”
explain : "10" You can also open the safe .

Example 2:

Input : n = 2, k = 2
Output : “00110”
explain : “01100”, “10011”, “11001” You can open the safe, too .

Tips ：

n The range is [1, 4].
k The range is [1, 10].
k^n The most likely is 4096.

PS：
Should say no , Baidu translation is better than this

class Solution {
   public static final int[] MASK = {0, 1, 10, 100, 1000};
    public String crackSafe(int n, int k) {
        M = MASK[n];
        StringBuilder sb = new StringBuilder();
        Hierholzer(0, k, new BitSet(), sb);
        for (int i = 0; i < n - 1; i++) sb.append(0);
        return sb.toString();
    }

    public int M;
    public void Hierholzer(int n, int k, BitSet bs, StringBuilder sb) {
        bs.set(n);
        int tail = n % 10;
        n = (n % M) * 10;
        for (int i = 0; i < k; i++, n++) {
            if (!bs.get(n)) Hierholzer(n, k, bs, sb);
        }
        sb.append(tail);
    }
 
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

754. The number at the end of the line

On an infinite number axis , You are standing 0 The location of . End at target The location of .

Every time you choose to move left or right . The first n Secondary mobility （ from 1 Start ）, You can go n Step .

Return to the minimum number of moves required to reach the destination .

Example 1:

Input : target = 3
Output : 2
explain :
First move , from 0 To 1 .
Second move , from 1 To 3 .
Example 2:

Input : target = 2
Output : 3
explain :
First move , from 0 To 1 .
Second move , from 1 To -1 .
The third move , from -1 To 2 .
Be careful :

target Is in [-10^9, 10^9] Nonzero integers in the range .

class Solution {
      public int reachNumber(int target) {
        int sum = 0;
        int c = 0;
        target = Math.abs(target);
        // The number that must be taken is less than the target number to cycle 
        // And the number of walks minus the target number , It's even , It can be flipped to 
                // For example 
        // If it is an even number of steps , You can go left 1 Right walk 2 Right walk 3 Right walk 4 That's it 8
        //  If it is normal, it is 1+2+3+4=10
        while(sum < target || (sum-target)%2!=0){
            c ++;
            sum += c;
        }
        return c;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

756. Pyramid transformation matrix

Now? , We use some squares to build a pyramid . Each square is represented by a string containing only one letter .

The stacking rules of using triples to represent pyramids are as follows ：

For three tuples (A, B, C) ,“C” For the top box , square “A”、“B” As squares “C” The left of the next floor 、 Right sub block . If and only if (A, B, C) Are allowed triples , Before we can pile it up .

At the beginning , The base of a given pyramid bottom, Use a string to represent . A list of allowed triples allowed, Each triplet has a length of 3 String representation of .

If it can be piled from the base to the spire, it will return true, Otherwise return to false.

 Example  1:

 Input : bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
 Output : true
 analysis :
 Can be stacked into such a pyramid :
    A
   / \
  G   E
 / \ / \
B   C   D

 Because it conforms to ('B', 'C', 'G'), ('C', 'D', 'E')  and  ('G', 'E', 'A')  Three rules .
 Example  2:

 Input : bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
 Output : false
 analysis :
 Can't pile all the way to the spire .
 Be careful ,  Image allowed  (A, B, C)  and  (A, B, D)  Such triples , among  C != D.
 

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

Be careful ：

bottom The length range of is [2, 8].
allowed The length range of is [0, 200].
The marking letter range of the box is {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}.

class Solution {
   public boolean pyramidTransition(String bottom, List<String> allowed) {
        if(allowed==null||allowed.size()==0)return false;
        HashMap<String,List<String>> dir=new HashMap<>(16);
        for(String str:allowed)
        {
            String head=str.substring(0,2);
            String ch=str.substring(2,3);
            if(dir.containsKey(head))
            {
                dir.get(head).add(ch);
            }
            else
            {
                List<String>p=new ArrayList<>();
                p.add(ch);
                dir.put(head,p);
            }
        }
        return(dfs(bottom, "",dir));
    }
    static boolean dfs(String last,String now,HashMap<String,List<String>> dir){
        if(last.length()==2&&now.length()==1) {
            return true;
        }
        if(now.length()==last.length()-1){
            return dfs(now,"",dir);
        }
        int start=now.length();int end=now.length()+2;
        List<String> p=dir.get(last.substring(start, end));
        if(p==null) return false;
        for (int i = 0; i < (p).size(); i++) {
            if(dfs(last,now+p.get(i),dir)) {
                return true;
            }
        }
        return 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.
31.
32.
33.
34.
35.
36.
37.
38.
39.

757. Set the intersection size to at least 2

An integer interval [a, b] ( a < b ) It's about starting from a To b All consecutive integers of , Include a and b.

Give you a set of integer intervals intervals, Please find a minimum set S, bring S Elements and intervals in intervals Every integer interval in has at least 2 Elements intersect .

Output this minimal set S Size .

Example 1:

Input : intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Output : 3
explain :
Consider the set S = {2, 3, 4}. S And intervals All four intervals in have at least 2 Intersecting elements .
And this is S In the smallest case , So we export 3.
Example 2:

Input : intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
Output : 5
explain :
The smallest set S = {1, 2, 3, 4, 5}.
Be careful :

intervals The length range of is [1, 3000].
intervals[i] The length is 2, Left respectively 、 Right border .
intervals[i][j] The value of is [0, 10^8] Range of integers .

class Solution {
       public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]){
                    return o2[0]-o1[0];
                }
                return o1[1]-o2[1];
            }
        });
        
        int[] rec = {-1,-1};
        int res=0;
        for(int[] is : intervals){
            if(is[0]<=rec[0]){
                continue;
            }else if(is[0] <= rec[1]){
                res++;
                rec[0] = rec[1];
            }else{
                rec[0] = is[1]-1;
                res+=2;
            }
            rec[1] = is[1];
        }
        return res;
    }
}

     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.