This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Arrange the array to the smallest number

Offer 45. Arrange the array to the smallest number

Difficulty: Medium

Topic: leetcode-cn.com/problems/ba…

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

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

Answer key

For example [10, 2], suppose a= 10, b = 2, then a+b = “102”, b+a= “210”, to splice into the smallest number, then:

  • If a plus b is less than b plus a, then BA is greater than AB, and A should be to the left of B

  • If a plus b is less than b plus a, then AB is greater than BA, and A should be to the right of B

So a is to the left of B, and you can see that we can sort this out.

Method 1 built-in function

/ * * *@param {number[]} nums
 * @return {string}* Convert an array to a string after sorting it. * /
var minNumber = function(nums) {
	return nums.sort((a, b) = > 
    (' ' + a + b) - (' ' + b + a)
  ).join(' '); 
};
Copy the code
  • Time complexity: O(NlogNNlogNNlogN), sort uses quicksort
  • Space complexity: O(111)

Method two fast row

Avoid being beaten to death by the interviewer

function quickSort(array, start, end) {
  if (end - start < 1) return;
  const target = array[start];
  let l = start;
  let r = end;
  while (l < r) {
    while (l < r && array[r] + target >= target + array[r]) {
      r--;
    }
    array[l] = array[r];
    while (l < r && array[l] + target < target + array[l]) {
      l++;
    }
    array[r] = array[l];
  }
  array[l] = target;
  quickSort(array, start, l - 1);
  quickSort(array, l + 1, end);
  return array;
}
var minNumber = function (nums) {
  if (nums.length < 2) return String(nums);
  // Convert nums to an array of strings
  return quickSort(nums.map(String), 0, nums.length - 1).join("");
}
Copy the code
  • Time complexity: O(NlogNNlogNNlogN)
  • Space complexity: O(111)

Translate numbers into strings

46. Translate numbers into strings

Difficulty: Medium

Topic: leetcode-cn.com/problems/ba…

Given a number, we translate it as a string using the following rules: 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

0 <= num < 2^31

Answer key

Method one dynamic programming

Ideas:

Dp [I] is defined as the number of methods for the number of I before translation, and dp[0] is set to 1 for the number of 0 before translation to meet the needs of dynamic programming.

The transfer equation of this problem is:


d p [ i ] = { d p [ i – 1 ] . s t r [ i ] and s t r [ i – 1 ] Cannot compose a character d p [ i – 1 ] + d p [ i – 2 ] s t r [ i ] and s t r [ i – 1 ] The ability to compose a character Dp = \ [I] the begin {cases} dp] [I – 1, \quad\quad\quad\quad\quad \ STR [I] and STR [I −1] cannot combine a single character \\ dp[i-1]+dp[i-2]\quad STR [I] and STR [I −1] can combine a single character \end{cases} 
/ * * *@param {number} num
 * @return {number}* /
var translateNum = function (num) {
  const str = num.toString();
  const len = str.length;
  const dp = new Array(len + 1);
  dp[0] = 1, dp[1] = 1;
  for (let i = 2; i < len + 1; i++) {
    const temp = Number(str[i - 2] + str[i - 1]);
    if (temp >= 10 && temp <= 25) {
      dp[i] = dp[i - 1] + dp[i - 2];
    } else {
      dp[i] = dp[i - 1]; }}return dp[len];
};
Copy the code
  • Time complexity: O(NNN), where N is the number of state transitions
  • Space complexity: O(NNN), the space complexity can be further optimized. Instead of using the dp array to store the results, use two variables to store the DP item. The optimization is as follows:
var translateNum = function (num) {
  const str = num.toString();
  let pre = 1,
    cur = 1;
  for (let i = 2; i < str.length + 1; i++) {
    const temp = Number(str[i - 2] + str[i - 1]);
    if (temp >= 10 && temp <= 25) {
      const t = cur; // save the previous state, i.e. Dp [i-1]
      cur = pre + cur; // dp[i] = dp[i - 2] + dp[i - 1]
      pre = t; Dp [i-2] = dp[i-1];
    } else {
      pre = cur; Dp [i-1] = dp[i-1]; // Update dp[i-2] to dp[i-1]}}return cur;
};
Copy the code
  • Time complexity: O(NNN), where N is the number of state transitions
  • Space complexity: O(111)

Method two numbers mod

Ideas:

  • Using the remainder operation num%10 and the integer operation num / 10, we can obtain the digits of the number num. .
  • The traversal operation from right to left is realized by the way of complementation and integration.

The transfer equation is:


d p [ i ] = { d p [ i + 1 ] . t m p ∈ [ 0 . 10 ) ∪ ( 25 . 99 ] d p [ i + 1 ] + d p [ i + 2 ] t m p ∈ [ 10 . 25 ] Dp = \ [I] the begin dp {cases} [I + 1), \quad\quad\quad\quad\ TMP \in [0,10]\ cup (25,99]\ dp[I +1]+dp[I +2]\quad TMP \in [10,25]\end{cases} 
var translateNum = function (num) {
  let a = 1,
    b = 1,
    x, y = num % 10; // b comes after A, y comes after x
  while (num) {
    num = Math.floor(num / 10);
    x = num % 10;
    let tmp = 10 * x + y; // TMP represents the two-digit number from right to left for judgment
    let c = (tmp >= 10 && tmp <= 25)? a + b : a; b = a; a = c; y = x; }return a;
};
Copy the code
  • Time complexity: O(NNN)
  • Space complexity: O(111)

Method three DFS

This problem can be abstracted as a tree model, which is to find the total number of paths from the root node to the leaf node of a binary tree.

var translateNum = function (num) {
  const str = num.toString();

  const dfs = (str, pos) = > { Pos is used to point to a character
    let len = str.length;
    if (pos >= len - 1) return 1;
    const temp = Number(str[pos] + str[pos + 1]);
    if (temp >= 10 && temp <= 25) {
      return dfs(str, pos + 1) + dfs(str, pos + 2);
    }
    return dfs(str, pos + 1);
  }

  return dfs(str, 0);
}
Copy the code
  • Time complexity: O(2N2^N2N). When this method recursively, repeated subtrees will be generated, so we can optimize it.
  • Space complexity: O(NNN)

DFS + Memorandum

Duplicate subtrees are generated in DFS. If we encounter duplicate subtrees on the right side of the priority recursion left subtree, there is no need to recalculate. Therefore, we need to write down the calculated results in a memo and use them directly when we come across them. Here we use map as a memo.

var translateNum = function (num) {
  const str = num.toString();
  const len = str.length;
  const map = new Map(a); map.set(len -1.1); // The parent of the leaf node, whose POS points to the last one
  map.set(len, 1); // The value of the leaf node

  const dfs = (str, pos, map) = > {
    if (map.get(pos)) return map.get(pos); // If there is a repetition, play the repetition directly.
    const temp = Number(str[pos] + str[pos + 1]);
    if (temp >= 10 && temp <= 25) {
      map.set(pos, dfs(str, pos + 1, map) + dfs(str, pos + 2, map));
    } else {
      map.set(pos, dfs(str, pos + 1, map));
    }
    return map.get(pos);
  }

  return dfs(str, 0, map);
}
Copy the code
  • Time complexity: O(NNN)
  • Space complexity: O(NNN)

Practice every day! The front end is a new one. I hope I can get a thumbs up