Leetcode – Binary search & divide-and-conquer

1. Find the leftmost key in an array of repeating elements

var binarySearch(nums, key) {
	let left = 0, right = nums.length - 1;
  
  while(left < right) {
    let mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] >= key) {
      right = mid;
    } else {
      left = mid + 1; }}return left;
}
Copy the code

2,The square root of x

Implement the int SQRT (int x) function.

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

var mySqrt = function(x) {
  if (x <= 1) return x;

  let left = 1, right = x;

  while(left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    const value = mid ** 2;

    if (value === x) {
      return mid;
    } else if (value > x) {
      right = mid - 1;
    } else {
      left = mid + 1; }}return right;
};
Copy the code

3,Find the smallest letter larger than the target letter

You are given a sorted list of letters, containing only lowercase Letters. Given another target letter, look for the smallest letter in the sequence list that is larger than the target letter.

In comparison, the letters appear in a circular order. Here’s an example:

If the target letter is target = ‘z’ and the character list is letters = [‘a’, ‘b’], the answer returns ‘a’.

var nextGreatestLetter = function(letters, target) {
  const n = letters.length;
  if (target >= letters[n - 1]) {
    return letters[0];
  }

  let left = 0, right = n - 1;

  while(left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (letters[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1; }}return letters[left];
};
Copy the code

4,The first incorrect version

You are a product manager, currently leading a team to develop a new product. Unfortunately, the latest version of your product did not pass the quality test. Since each version is based on the previous version, all versions after the incorrect version are incorrect.

Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

You can tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

var solution = function(isBadVersion) {
  / * * *@param {integer} n Total versions
     * @return {integer} The first bad version
     */
  return function(n) {
    let left = 0, right = n;

    while(left <= right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (isBadVersion(mid)) {
        right = mid - 1;
      } else {
        left = mid + 1; }}return left;
  };
};
Copy the code

5,Find the minimum value in the rotation sort array

Given an array of length N, sorted in ascending order, rotated 1 to n times, the input array is obtained. For example, the original array nums = [0,1,2,4,5,6,7] might be changed to: If you rotate it four times, you get [4,5,6,7,0,1,2] and if you rotate it seven times, you get [0,1,2,4,5,6,7] Array [a [0], a [1], a [2],… and a [n – 1]] array to the result of the rotation a [a] [n – 1, a [0], a [1], a [2],… and a [n – 2]].

You are given an array nums with different element values. It was originally an array sorted in ascending order and rotated several times as described above. Find and return the smallest element in the array.

var findMin = function(nums) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else{ right = mid; }}return nums[left];
};
Copy the code

6,Finds the first and last position of an element in a sorted array

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

If no target value exists in the array, return [-1, -1].

var searchRange = function(nums, target) {
  const left = findLeft(nums, target);
  const right = findLeft(nums, target + 1) - 1;
  if (left < nums.length && nums[left] === target) {
    return [left, right];
  }
  return [-1, -1];
};


function findLeft(nums, target) {
  const n = nums.length;
  if (target > nums[n - 1]) return n;

  let left = 0, right = nums.length - 1;

  while(left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1; }}return right;
} 
Copy the code

7,Design priorities for operational expressions

Given a string containing a number and an operator, add parentheses to the expression and change its precedence to produce a different result. You need to give the results of all possible combinations. Valid operation symbols include +, -, and *.

var diffWaysToCompute = function(expression) {
  const n = expression.length;
  const res = [];
  const value = Number(expression);
  if (!isNaN(value)) return [value];

  for (let i = 0; i < n; i++) {
    const char = expression[i];
    let leftArr = [], rightArr = [];
    if (char === '+' || char === The '-' || char === The '*') {
      leftArr = diffWaysToCompute(expression.substring(0, i));
      rightArr = diffWaysToCompute(expression.substring(i + 1, n));
    }

    for (let x of leftArr) {
      for (let y of rightArr) {
        switch(char) {
          case '+':
            res.push(x + y);
            break;
          case The '-':
            res.push(x - y);
            break;
          case The '*':
            res.push(x * y);
            break; }}}}return res;
};
Copy the code