Daily question brushing record (16)

The first question is : The finger of the sword Offer 46. Translate numbers into strings

LeetCode: The finger of the sword Offer 46. Translate numbers into strings

describe :
Given a number , We translate it as a string according to the following rules ：0 Translate into “a” ,1 Translate into “b”,……,11 Translate into “l”,……,25 Translate into “z”. A number may have more than one translation . Please program a function , Used to calculate how many different translation methods a number has .

Their thinking :

1. Dynamic programming problem solving
2. state F(i) : Before presentation i How many different translations are there for numbers
3. State transition equation :
   • When for the first i A digital , When translating alone , F(i) = F(i-1)
   • When for the first i A digital , When you can combine translation , F(i) = F(i-2)
   • Finally, add the two together .
4. The initial state : F(0) = 1;
5. Return results : F(len)

Code implementation :

class Solution {
    
    public int translateNum(int num) {
    
        String str = num+"";
        int[] dp = new int[str.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= str.length() ; i++) {
    
            dp[i] = dp[i-1];
            if(i>1) {
    
                String s = str.substring(i-2,i);
                //  Only satisfaction  [10,25] To translate 
                if(s.compareTo("10") >= 0 && s.compareTo("25") <= 0) {
    
                    dp[i] += dp[i-2] ;
                }
            }
        }
        return dp[str.length()];
    }
}

The second question is : The finger of the sword Offer 47. The greatest value of gifts

LeetCode: The finger of the sword Offer 47. The greatest value of gifts

describe :
In a m*n There is a gift in every space of the chessboard , Every gift has a certain value （ Value greater than 0）. You can start from the top left corner of the chessboard to get the gifts in the grid , And move right or down one space at a time 、 Until you reach the bottom right corner of the chessboard . Given the value of a chessboard and its gifts , Please calculate the maximum value of gifts you can get ？

Their thinking :

1. Here we use dynamic programming to solve the problem .
2. state F(i,j) : Indicates arrival (i,j) when , Maximum gift value
3. State transition equation :
   • i = 0 , j = 0 => F(i,j) = grid[i][j]
   • i = 0 , j != 0 => F(i,j) = grid[i][j] + F(i,j-1)
   • i != 0, j=0 => F(i,j) = grid[i][j] + F(i-1,j)
   • i!=0,j!=0 => F(i,j) = grid[i][j] + Max(F(i-1,j) , F(i,j-1))
4. The initial state : dp[0][0] = gird[0][0]
5. Return results : dp[gird.length-1][gird[0].length-1]

Code implementation :

class Solution {
    
    public int maxValue(int[][] grid) {
    
        int[][] dp = new int[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++) {
    
            for(int j = 0; j < grid[0].length; j++) {
    
                if(i==0 && j==0) dp[i][j] = grid[i][j];
                else if(i==0) dp[i][j] = grid[i][j] + dp[i][j-1];
                else if(j==0) dp[i][j] = grid[i][j] + dp[i-1][j];
                else dp[i][j] = grid[i][j] + Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

Third question : The finger of the sword Offer 49. Ugly number

LeetCode: The finger of the sword Offer 49. Ugly number

describe :
We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .

Their thinking :

1. It can be seen here as 3 A sequence of numbers
2. by 2 Factor of : 2, 4, 6, 8,10, …
3. by 3 Factor of : 3, 6, 9, 12, 15, …
4. by 5 Factor of : 5, 10, 15, 20, 25, …
5. Every time you get the minimum, you have to put it into the array , Just go , Pay attention to duplicates

Code implementation :

class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] dp = new int[n];
        dp[0] = 1;
        int x2 = 0;
        int x3 = 0;
        int x5 = 0;
        for(int i = 1; i < n; i++) {
    
            int tmp = Math.min(dp[x2]*2,Math.min(dp[x3]*3,dp[x5]*5));
            if(tmp == dp[x2] * 2) x2++;
            if(tmp == dp[x3] * 3) x3++;
            if(tmp == dp[x5] * 5) x5++;
            dp[i] = tmp;
        }
        return dp[n-1];
    }
}

Fourth question : The finger of the sword Offer 53 - I. Look up numbers in the sort array I

LeetCode: The finger of the sword Offer 53 - I. Look up numbers in the sort array I

describe :
Count the number of times a number appears in the sort array .

Their thinking :

1. Here we use the binary search method
2. First, find... Through dichotomy , Find and appear target The right border of
3. Then search by two points , Find and appear target The left border .
4. Finally back to Right border - Left boundary - 1
5. By controlling nums[mid] <= target still < target To find the boundary

Code implementation :

class Solution {
    
    public int search(int[] nums, int target) {
    
        int left = 0;
        int right = nums.length-1;
        //  Find the right boundary  rightIndex
        while(left <= right) {
    
            int mid = left + (right - left) / 2;
            //  Finding the right boundary requires control  <=
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        int rightIndex = left;
        left = 0;
        right = nums.length-1;
        //  Find the left boundary  leftIndex
        while(left <= right) {
    
            int mid = left + (right - left) / 2;
            //  There is no need to control to find the left boundary  <=
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        int leftIndex = right;
        return rightIndex-leftIndex-1;
    }
}

Fifth question : The finger of the sword Offer 56 - I. The number of occurrences of numbers in an array

LeetCode: The finger of the sword Offer 56 - I. The number of occurrences of numbers in an array

describe :
An integer array nums Except for two numbers , The other numbers appear twice . Please write a program to find out these two numbers that only appear once . The required time complexity is O(n), The space complexity is O(1).

Their thinking :

1. First, XOR all the numbers in the array
2. The number obtained is the XOR result of the two numbers of the result
3. Then go from right to left , Find the first one as 1 Number of digits , by 1, It means that the two numbers are inconsistent
4. Then according to this 1 The location of , Queue array nums, division
   • If nums[i] & This number is 0, Just divide into groups .
   • If nums[i] & This number is 1, Just divide into groups .
5. Finally, let both groups do XOR , The last remaining number of each group , It's the result .
   

Code implementation :

class Solution {
    
    public int[] singleNumbers(int[] nums) {
    
        int tmp = 0;
        for(int num : nums) {
    
            tmp ^= num;
        }
        int index = 1;
        while( (tmp & index) == 0) {
    
            index <<= 1;
        }
        int res1 = 0;
        int res2 = 0;
        for(int num : nums) {
    
            if((num & index) == 0) {
    
                res1 ^= num;
            }else{
    
                res2 ^= num;
            }
        }
        return new int[]{
    res1,res2};
    }
}

Sixth question : The finger of the sword Offer 56 - II. The number of occurrences of numbers in an array II

LeetCode: The finger of the sword Offer 56 - II. The number of occurrences of numbers in an array II

describe :
In an array nums Except that a number appears only once , The other numbers appear three times . Please find the number that only appears once .

Their thinking :

1. Here, first of all, all numbers are converted into binary form ,
2. Then add up the numbers on each digit
3. The final number . Make every mold 3
4. The result you get is the result you need
   

Code implementation :

class Solution {
    
    public int singleNumber(int[] nums) {
    
        int[] by = new int[32];
        //  Here we add each bit 
        for(int num : nums) {
    
            for(int i = 0; i < 32; i++) {
    
                by[i] += (num >> i & 1) == 1 ? 1 : 0;
            }
        }
        int res = 0;
        for(int i = 0; i < 32; i++) {
    
            //  Take the mold for each ,  And become  2 ^ i Power ,  here 1<<i That's the effect .
            res += (1<<i) * (by[i] % 3);
        }
        return res;
    }
}