每日两题 T37
算法
LeetCode T1095. 山脉数组中查找目标值[1]
描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
这是一个 交互式问题 ）
给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1]
你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始） MountainArray.length() - 会返回该数组的长度
注意：
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
分析
分作两步就清晰好多了:
1.把峰值找出來2.按峰值把其分为左右两部分，先二分查找左边，左边没有再看右边
代码
/**
* @param {number} target
* @param {MountainArray} mountainArr
* @return {number}
*/
var findInMountainArray = function (target, mountainArr) {
// 一 查找峰值
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)) { // 当mid小于右边的时,说明峰值在右边, 继续在右边查找
left = mid + 1
} else { // 否则在左边, 继续在左边查找
right = mid - 1
}
mid = left + ((right - left) >> 1)
}
// 执行完上边的二分查找 left 就是峰值的下标了
// 二 根据峰值分两段 二分查找
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) // 获取中间索引
while (left <= right) {
let midValue = mountainArr.get(mid)
if (midValue === target) return mid // 找到直接返回
if (midValue < target) {
isUp ? left = mid + 1 : right = mid - 1 //用 isUp 区分正序还是降序
} else {
isUp ? right = mid - 1 : left = mid + 1
}
mid = left + ((right - left) >> 1)
}
return -1
}前端
Vue 的响应式原理中 Object.defineProperty 有什么缺陷？为什么在 Vue3.0 采用了 Proxy，抛弃了 Object.defineProperty？
1.Object.defineProperty无法监控到数组下标的变化，导致通过数组下标添加元素，不能实时响应；2.Object.defineProperty只能劫持对象的属性，从而需要对每个对象，每个属性进行遍历，如果，属性值是对象，还需要深度遍历。Proxy可以劫持整个对象，并返回一个新的对象。3.Proxy不仅可以代理对象，还可以代理数组。还可以代理动态增加的属性。
Proxy有以下两个优点;
可以劫持整个对象，并返回一个新对象 有13种劫持操作
References
[1] 1095. 山脉数组中查找目标值: https://leetcode-cn.com/problems/find-in-mountain-array/