Villay's Leetcode brush record - Moment For Technology

The maximum product of word lengths

Given an array of strings words, calculate the maximum value of the product of the lengths of two strings words[I] and words[j] when they do not contain the same characters. Assume that the string contains only English lowercase letters. Returns 0 if there is no pair of strings that do not contain the same character.

Input: words = [abcw “, “” baz”, “foo”, “bar”, “fxyz”, “abcdef”]

Output: 16

Explanation: These two words are “abCW “, “fxyz”. They do not contain the same characters and the product of lengths is the largest.
Input: words = [” a “, “ab”, “ABC”, “d”, “CD” and “BCD”, “abcd”]

Output: 4

Explanation: These two words are “ab” and “CD”.
Enter: words = [” A “,” AA “,” AAA “,” aAAA “]

Output: 0

Explanation: There are no such two words.

var maxProduct = function (words) {
    let len = words.length;
    let max = 0;
    let bits = new Array(len).fill(0);

    // Construct binary values for each word
    for(let i = 0; i < len ; i ++) {let word = words[i];
        for(let j = 0; j < word.length; j++) { bits[i] |=1 << (word[j].charCodeAt() - 97);
           // Place the existing letter in the binary bit value of 1}}for(let i = 0; i < len ; i++) {for(let j = 0; j < i ; j++) {if((bits[i] & bits[j]) === 0) {
                The & operation computes the maximum length if there are no identical letters
                max = Math.max(max,words[i].length * words[j].length)
            }
        }
    }
   return max;
}
Copy the code

The maximum depth of a binary tree

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node. Note: Leaf nodes are nodes that have no child nodes.

Given a binary tree [3,9,20,null,null,15,7] returns its maximum depth of 3.

const maxDepth = (root) = > {
  if(root == null) return 0
  const queue = [root]
  let depth = 1;
  while(queue.length) {
      // The number of nodes in the current layer
      const levelSize = queue.length
      // List the nodes of the current layer one by one
      for(let i = 0; i<levelSize; i++) {// The node that is currently listed
          const cur = queue.shift()
          // The left and right child nodes are added to the column
          if(cur.left) queue.push(cur.left)
          if(cur.right) queue.push(cur.right)  
      }
      // All nodes at the current layer are listed. If the queue is not empty, the node at the next layer is listed. Depth + 1
      if(queue.length) depth++
  }
  return depth
}
Copy the code

Binary addition

Given two 01 strings A and B, compute their sum and output it as a binary string. The input is a non-empty string containing only the digits 1 and 0.

Input: a = “11”, b = “10” output: “101”
Input: a = “1010”, b = “1011” output: “10101”

Each string consists only of the character '0' or '1'. 1 <= a.length, b.length <= 10^4 Strings that are not "0" do not contain leading zeros.

var addBinary = function (a,b) {
    return (BigInt('0b' + a) + BigInt('0b' + b)).toString(2)}Copy the code

palindrome

Given an integer x, return true if x is a palindrome integer; Otherwise, return false. Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Input: x = 121 Output: true
Input: x = -121 Output: false
Interpretation: Read from left to right as -121. Read from right to left, 121-. So it’s not a palindrome number.
Input: x = 10 Output: false
Interpretation: Read from right to left as 01. So it’s not a palindrome number.
Enter: x = -101
Output: false

/ * * * *@param {*} x 
 * @returns * / 
var isPalindrome = function(x) {
    return x === Number(x.toString().split(' ').reverse().join(' '))}Copy the code

The two together

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

Enter nums = [2,7,11,15], target = 9
Output: [0, 1]
Because nums[0] + nums[1] == 9, return [0, 1]
Enter: nums = [3,2,4], target = 6
Output: [1, 2]
Enter: nums = [3,3], target = 6
Output: [0, 1]

/ * * * *@param {*} nums 
 * @param {*} target 
 * @returns * /
var twoSum = function (nums,target) {
    let len = nums.length;
    / / create a MAP
    const MAP = new Map(a);// The first element is stored in the hash table because there must be no element before it
    MAP.set(nums[0].0)
    for(let i = 1; i<len; i++) {// Extract shared
    let other = target - nums[i]
    // Determine whether the condition is met and return the corresponding subscript
    if(MAP.get(other) ! = =undefined) return [MAP.get(other),i]
    // Store those that do not match the hash table
    MAP.set(nums[i],i)
    }
}

Copy the code

Take a coin

There are n stacks of coins on the table, and the amount of each stack is stored in the array Coins. We can choose any pile at a time, take one or two of the coins, and find the minimum number of times to use up the strong deduction.

Input: (4, 2, 1)
Output: 4
Explanation: The first pile of force deduction coins need to take at least 2 times, the second pile need to take at least 1 times, the third pile need to take at least 1 times, a total of 4 times can be taken.
Input:,3,10 [2]
Output: 8

Limit: 1 <= N <= 4 1 <= coins[I] <= 10

var minCount = function(coins) {
    let sum = 0;
    for(let i = 0; i < coins.length ; i ++) {if(coins[i] % 2! = =0 ) {
            sum = sum + ((coins[i] + 1) / 2)}else if (coins[i] % 2= =0) {
            sum = sum + ((coins[i] / 2))}}}var minCount = function(coins) {
    coins[0] = Math.ceil(coins[0] / 2)
    return coins.reduce((p, c) = > p + Math.ceil(c / 2))};var minCount = function (arr) {
    var num = 0;
    arr.forEach(element= > {
      num += Math.ceil(element / 2)});return num;
  };
Copy the code

The sum of two arrays in a sorted array

Given an array of integers in ascending order numbers, find two numbers that add up to the target number. The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 0, so the answer array should be 0 <= answer[0] < answer[1] < numbers. Length. Assume that only one pair of qualified numbers exists in the array, and the same number cannot be used twice.

Type: numbers = [1,2,4,6,10] target = 8
Output: [1, 3]
Explanation: The sum of 2 and 6 equals the target number 8. So index1 is equal to 1, index2 is equal to 3.
Enter: numbers = [2,3,4], target = 6
Output: [0, 2]
Type: numbers = [-1,0], target = -1
Output: [0, 1]

var twoSum = function (numbers,target) {
    let left = 0, right = numbers.length - 1;
    while (left < right ) {
        const sum = numbers[left] + numbers[right]
        if(sum == target) {
            return [left,right]
        } else if(sum < target) {
            left ++
        } else {
            right --
        }
    }
    return[]}console.log(twoSum([1.2.4.6.10].11))
Copy the code

The number of 1’s in the first n digit binary

Given a non-negative integer n, count the number of 1s in the binary representation of each number between 0 and n and output an array.

Enter: n = 2
Output:,1,1 [0]
Explanation:
0 — > 0
1 — — > 1
2 –> 10
Enter n = 5
Output:,1,1,2,1,2 [0]
Explanation:
0 — > 0
1 — — > 1
2 –> 10
3 –> 11
4 – – > 100
5 – – > 101

var countBits = function (n) {
    let res = [] // The number of 1s used to store each number
    for(let i = 0; i <= n; i++ ) {// Run the loop one by one
        let num = i 
        let L = 0 // This variable counts the number of 1s
        while(num) {
            num = num & (num - 1) 
            L ++
        }
        res.push(L)
    }
    return res
}
console.log(countBits(6))
Copy the code

Coin change

Description: Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1

Example 1:
Enter: Coins = [1, 2, 5], amount = 11
Output: 3
11 = 5 + 5 + 1
Example 2:
Enter: Coins = [2], amount = 3
Output: 1

const coinChange = function(coins,amout) {
    // Used to save the minimum number of coins corresponding to each target total
    const f = [];
    // Define what you know ahead of time
    f[0] = 0;
    // Iterate over the total number of coins in the interval [1,amout]
    for(let i = 1; i <= amout; i++) {
        // The value is the minimum, so we set it to infinity to ensure that it will always be updated by smaller values
        f[i] = Infinity;
        // Loop over the denomination of each available coin
        for(let j = 0; j < coins.length; j ++) {// If the coin denomination is less than the target amount, then the problem is true
            if(i - coins[j] >= 0) {
                // State transition equation
                f[i] = Math.min(f[i],f[i-coins[j]] + 1); }}}// If the target total is infinite for the due solution, then it means that none of the eligible coins are available to update it
    if(f[amout] === Infinity) {
        return -1;
    }
    // If there is a solution, return the content of the solution directly
    return f[amout];
}
console.log(coinChange([1.2.5].22))
Copy the code

Valid palindromes

Given a string s, verify that s is a palindrome string. Only alphanumeric characters are considered. In this case, the empty string is defined as a valid palindrome string.

Input: s = “A man, A plan, A canal: Panama”
Output: true,
Explanation: “Amanaplanacanalpanama” is a palindrome string
Enter: s = “race a car”
Output: false
Explanation: “raceacar” is not a palindrome string

var isPalindrome = function(s) {
    s = s.toLowerCase()
    let arr = ' '
    for(var key of s) {
        if(/[A-Za-z0-9]/.test(key)) {
            arr += key
        }
    }
    let left = 0
    let right = arr.length - 1
    while(left < right) {
        if(arr[left] ! == arr[right]) {return false
        }
        left ++
        right --
    }
    return true
}
Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Villay’s Leetcode brush record

The maximum product of word lengths

The maximum depth of a binary tree

Binary addition

palindrome

The two together

Take a coin

The sum of two arrays in a sorted array

The number of 1’s in the first n digit binary

Coin change

Valid palindromes

Villay’s Leetcode brush record

The maximum product of word lengths

The maximum depth of a binary tree

Binary addition

palindrome

The two together

Take a coin

The sum of two arrays in a sorted array

The number of 1’s in the first n digit binary

Coin change

Valid palindromes

Related Posts

Mobx implements permission state management

Reveal front-end storage

9 lines of code to copy the content to the clipboard