LeetCode: problem solving of the 160th weekly match

5238. Finding the positive integer solution of a given equation

subject

In this paper, we give a function f(x, y) and an objective result z. please calculate the equation f(x,y) == z all possible positive integer pairs X and y.
The given function is strictly monotonic, that is to say:
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined as follows:

You can return the result pairs that meet the conditions in any order.

Example

Example 1:

Example 2:

Title Solution

Simple problem: solve by force, just traverse all situations

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 1 ; i <= 1000 ; i ++){
            for(int j = 1 ; j <= 1000; j++){
                int d = customfunction.f(i,j);
                if(d > z) break;
                else if(d == z) {
                    List<Integer> l = new ArrayList<>();
                    l.add(i);
                    l.add(j);
                    res.add(l);
                }
            }
        }
        return res;
    }
}

5239. Cyclic code arrangement

subject

Here are two integers, N and start. Your task is to return any (0,1,2,... , 2^n-1), and meet the following requirements:

• p[0] = start
• The binary representation of p[i] and p[i+1] is only one bit different
• The binary representations of p[0] and p[2^n -1] are also only one bit different

Tips:

• 1 <= n <= 16
• 0 <= start < 2^n

Example

Example 1:

Example 2:

Title Solution

Medium difficulty.
Search was used in the game, timeout ╮ (╯ (╯) system ╭.
In fact, this is a rule problem. You can search for the generation rule of gray code (????????)??. Here is just the rule I used: Gray code of n-bit can be generated by gray code of n-1 bit.
For example:
2-digit Gray Code:
00 01 11 10
3-digit Gray Code:
000 001 011 010 110 111 101 100
There are the following rules:
The first four numbers of 3-digit gray codes are 2-digit gray codes.
The last four numbers 110 111 101 100 are the inverse 2-bit gray code (10 11 01 00) with 1.
This can generate n-bit gray codes.
It's easy to do that the topic requires starting as the first number, because gray code is a ring, traverse n as gray code, find start, and move the position forward.

class Solution {
    static boolean flag = false;
    public List<Integer> circularPermutation(int n, int start) {

        flag = false;
        int m  = 1 << n;
        int i,j;
        List<Integer> l = new ArrayList<>(m);
        List<Integer> ans = new ArrayList<>(m);
        ans.add(0);
        ans.add(1);
        for(i = 2 ; i <= n ; i ++){
            int size = ans.size();
            for(j = size - 1 ; j >= 0; j --)
                ans.add(ans.get(j) + (1 << ( i - 1)));
        }
        for( i = 0 ; i < ans.size(); i ++)
            if(ans.get(i) == start) break;
        for(j = i ; j <ans.size(); j ++) l.add(ans.get(j));
        for(j = 0 ; j < i; j ++)  l.add(ans.get(j));
        return l;
    }
}

5240. Maximum length of concatenated string

subject

Given a string array arr, string s is a string obtained by connecting a certain subsequence string of arr. if every character in s only appears once, then it is a feasible solution.
Please return the longest of all possible solutions s.

Example

Example 1:

Example 2:

Example 3:

Tips:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] contains only lowercase letters

Title Solution

Medium question: DFS lists all cases and finds the maximum length that meets the requirements.
There should be more time-consuming and less complex algorithms.

class Solution {
    public int maxLength(List<String> arr) {
        List<String> ans = new ArrayList<>();
        dfs(arr,0, arr.size(),"", ans);
        Collections.sort(ans, (a,b) ->{
            return - a.length()+b.length();
        });
        int d = 0 , i = 0 , len = 0;
        for(String s: ans){
            int []a = new int[30];
            len = s.length();
            for(i = 0 ; i < len ; i ++)
                if(a[s.charAt(i) - 'a'] == 1) break;
                else a[s.charAt(i) - 'a'] =  1;
            if(i == len) {
                d = len;
                break;
            }
        }
        return d;
    }
    
    public void dfs(List arr ,int i,int n , String s, List ans){
        if(i == n){
            ans.add(s);
            return ;
        }
        dfs(arr,i + 1,n,s, ans);
        dfs(arr,i + 1,n,s + arr.get(i) , ans);
    }
}

5241. Tiling

subject

You are the foreman of a construction team. According to the requirements of the designer, you are going to decorate a house with unique design style.
The living room of the house is n x m in size, and to maintain a minimalist style, the floor needs to be covered with as few square tiles as possible.
Suppose that the size of square tiles is unlimited, and the side length is an integer.
Please help the designer to figure out how many square tiles are needed at least?

Example

Title Solution

I didn't work out the difficult questions.
After reading the master's answer, I used to hit the watch and learned (... •˘˘˘... )
There is also a wide search method.

class Solution {
        public int tilingRectangle(int n, int m) {
        int[] a1 = {1};
        int[] a2 = {2,1};
        int[] a3 = {3,3,1};
        int[] a4 = {4,2,4,1};
        int[] a5 = {5,4,4,5,1};
        int[] a6 = {6,3,2,3,5,1};
        int[] a7 = {7,5,5,5,5,5,1};
        int[] a8 = {8,4,5,2,5,4,7,1};
        int[] a9 = {9,6,3,6,6,3,6,7,1};
        int[] a10 = {10,5,6,4,2,4,6,5,6,1};
        int[] a11 = {11,7,6,6,6,6,6,6,7,6,1};
        int[] a12 = {12,6,4,3,6,2,6,3,4,5,7,1};
        int[] a13 = {13,8,7,7,6,6,6,6,7,7,6,7,1};

        int[][] a = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13};
        int mx = Math.max(n, m) - 1;
        int mi = Math.min(n, m) - 1;

        return a[mx][mi];
    }
}