This is the 22nd day of my participation in the August More Text Challenge

Offer 45. Arrange the array to the smallest number

The title

Enter an array of non-negative integers, concatenate all the numbers in the array into a number, and print the smallest number that can be concatenated.

Example 1:

Input: [10,2] output: "102"Copy the code

Example 2:

Input: [3,30,34,5,9] output: "3033459"Copy the code

Tip:

  • 0 < nums.length <= 100

Description:

  • The output can be quite large, so you need to return a string instead of an integer
  • Concatenated numbers may have leading zeros, and the final result does not need to remove the leading zeros

Methods a

Sorting:

Custom collation:

  • If the concatenated string x + y > y + x, then x is “greater than” y;
  • If x+y

Proof:

The string xy < yx, yz < zy, we need to prove that xz < zx. X = x * 10^b + y (x * 10^a + x) x = x * 10^b + y (x * 10^a + x) X * 10^b + y < y * 10^a + x x (10^ b-1) < y (10^ a-1) x/(10^ a-1) < y/(10^ b-1) Y/(10^ b-1) < z/(10^ c-1)  x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1) x / (10^a - 1) < z / (10^c - 1) x (10^c - 1) < z (10^a - 1) x * 10^c + Z < z * 10^a + x can be deduced xz < zx, the transitivity is provedCopy the code
class Solution { public String minNumber(int[] nums) { String[] ss = new String[nums.length]; for (int i = 0; i < nums.length; i ++ ) ss[i] = String.valueOf(nums[i]); Arrays.sort(ss, (a, b)->{ String s1 = a + b, s2 = b + a; return s1.compareTo(s2); }); // StringBuilder StringBuilder res = new StringBuilder(); for (String s : ss) res.append(s); return res.toString(); }}Copy the code

46. Translate numbers into strings

The title

Given a number, we translate it as a string as follows: 0 to “a”, 1 to “b”… 11 translated as “L”… 25 translates as “Z”. A number can have multiple translations. Program to implement a function that calculates how many different ways a number can be translated.

Example 1:

Input: 12258 Output: 5 Explanation: 12258 has 5 different translations, which are "bCCFI "," bwFI ", "BCZI "," MCFI "and "mzi"Copy the code

Tip:

  • 0 <= num < 231

Methods a

Recursive:

  • Will be given the numbernumThe digits in each of the digits are deducted and stored in the set; And then we recurse;
  • The number at each position is zero0 ~ 9, so there must be a letter that matches, and then recurse to the next digit
  • If you do the one-digit recursion in the previous step, you can also try two-digit recursion to determine if the two digits are less than 26, that is, if there is a letter match, then recurse, recursive entry+ 2Indicates that the next bit is matched;
  • When the number of bits of the input parameter is equal to the size of the set, it indicates the number of all matches, schemes+ 1
class Solution {
​
    int res = 0;
    List<Integer> nums = new ArrayList<>();
    public int translateNum(int num) {
​
        while(num != 0) {
            nums.add(num % 10);
            num /= 10;
        }
​
        Collections.sort(nums, (a, b)->{
            return -1;
        });
​
        dfs(0);
        
        return res;
    }
    void dfs(int u) {
​
        if (u == nums.size()) {
            res ++;
            return;
        }
        dfs(u + 1);
        
        if (u < nums.size() - 1) {
            int t1 = nums.get(u), t2 = 0;
            t2 = nums.get(u + 1);
            int t = t1 * 10 + t2;
            if (t < 26 && nums.get(u) != 0) 
                dfs(u + 2);
        }
        
    }
}
Copy the code

Method 2

Dynamic programming:

  • f[i]Said beforeiBit translation scheme, the value is expressed as the maximum
  • Transfer equation: NoiThe bits can go from the first placei-1,i-2The bits are shifted,i-1It must be transferable,i-2We need to judge
class Solution { public int translateNum(int num) { List<Integer> nums = new ArrayList<>(); while(num ! = 0) { nums.add(num % 10); num /= 10; } Collections.sort(nums, (a, b)->{ return -1; }); if (nums.size() <= 1) return 1; int[] f = new int[nums.size() + 1]; f[0] = f[1] = 1; for (int i = 2; i <= nums.size(); i ++ ) { f[i] = f[i - 1]; if (nums.get(i - 1) + nums.get(i - 2) * 10 < 26 && nums.get(i - 2) ! = 0) f[i] += f[i - 2]; } return f[nums.size()]; }}Copy the code