Two questions a day T37

Two questions a day T37

algorithm

LeetCode T1095. Find the target value in the mountain array[1]

description

An array of integers numsin addition to the two figures, other figures appear twice. Please write a program to find these two numbers that only appear once. The required time complexity is O(n), and the space complexity is O(1).

This is an interactive question)

Give you a mountainArr array, please return the smallest subscript index value that can make mountainArr.get(index) equal to target.

If there is no such subscript index, please return -1.

What is an array of mountains? If the array A is an array of mountains, it satisfies the following conditions:

First , A.length >= 3

Second , under the condition of 0 <i <A.length-1, there is i such that:

A[0] <A[1] <... A[i-1] <A[i] A[i]> A[i+1]> ...> A[A.length-1]

You will not be able to directly access the mountain array, you must get the data through the MountainArray interface:

MountainArray.get(k)-will return the element with index k in the array (subscript starts from 0) MountainArray.length()-will return the length of the array

note:

Submissions with more than 100 calls to MountainArray.get will be considered incorrect answers. In addition, any solution that attempts to circumvent the judging system will result in the disqualification of the competition.

analysis

It is much clearer in two steps:

1. Find the peak value 2. Divide it into left and right parts according to the peak value, first find the left side in two, and then look at the left side without looking at the right

Code

/**
 * @param {number} target
 * @param {MountainArray} mountainArr
 * @return {number}
 */
var findInMountainArray = function (target, mountainArr) {
 //Find the peak
  let left = 0
  let right = mountainArr.length()-1
  let mid = left + ((right-left) >> 1)
  while (left <= right) {
    if (mountainArr.get(mid) <mountainArr.get(mid + 1)) {//When mid is less than the right, it means that the peak is on the right, and continue to search on the right
      left = mid + 1
    } else {//Otherwise on the left, continue to search on the left
      right = mid-1
    }
    mid = left + ((right-left) >> 1)
  }
 //After performing the binary search above, left is the subscript of the peak

 //Two search in two segments according to the peak value
  let res = -1
  res = binarySearch(mountainArr, 0, left, target, true)
  res === -1 && (res = binarySearch(mountainArr, left, mountainArr.length()-1, target, false))
  return res
};
/**
* @param {MountainArray} mountainArr
* @param {number} left
* @param {number} right
* @param {number} target
* @param {Boolean} isUp
* @return {number} 
*/
function binarySearch(mountainArr, left, right, target, isUp) {
  let mid = left + ((right-left) >> 1)//Get the middle index
  while (left <= right) {
    let midValue = mountainArr.get(mid)
    if (midValue === target) return mid//Find and return directly  
    if (midValue <target) {
      isUp? left = mid + 1: right = mid-1//Use isUp to distinguish positive order or descending order
    } else {
      isUp? right = mid-1: left = mid + 1
    }
    mid = left + ((right-left) >> 1)
  }
  return -1
}

front end

What are the shortcomings of Object.defineProperty in Vue's reactive principle? Why is Proxy used in Vue3.0 and Object.defineProperty is abandoned?

1. Object.defineProperty cannot monitor the changes of the array subscript, which leads to adding elements through the array subscript and cannot respond in real time; 2. Object.defineProperty can only hijack the properties of the object, which requires each object and each property to be traversed. If the attribute value is an object, it needs to be traversed in depth. Proxy can hijack the entire object and return a new object. 3. Proxy can not only proxy objects, but also proxy arrays. It can also proxy dynamically added attributes.

Proxy has the following two advantages;

Can hijack the entire object and return a new object. There are 13 hijacking operations

References

[1]1095. Find the target value in the mountain array: https://leetcode-cn.com/problems/find-in-mountain-array/

Reference: https://cloud.tencent.com/developer/article/1664384 Two questions a day T37-Cloud + Community-Tencent Cloud