山西省旅游网站建设分析ps怎么做网站图片

当前位置： 首页 > news >正文

山西省旅游网站建设分析,ps怎么做网站图片,wordpress怎么修改模板,报纸网站建设对于二分题#xff0c;其实就是设定一个中间值 mid, 然后通过这个值进行一个判断 check(mid)#xff0c; 通过这个函数的返回值#xff0c;判断将不可能的一半剪切掉#xff1b; 在刷题的时候需要注意主要是两部分#xff0c;check 函数的定义以及边界的选择#xff08;…对于二分题其实就是设定一个中间值 mid, 然后通过这个值进行一个判断 check(mid) 通过这个函数的返回值判断将不可能的一半剪切掉 在刷题的时候需要注意主要是两部分check 函数的定义以及边界的选择等号的选择以及最后是 return left 还是 right 这次主要是 LC 的二分专题里面的简单题基本都是比较显性的提示了 check 函数的构建比方说直接找出某个值而难题一般都是 check 函数比较难想的这个时候就需要经验了 广义上只要是排好序局部排序只要是找某个值大部分都可以考虑用二分这样复杂度可以降低很多 对于边界我的循环结束条件是 left right 因为如果要多记很多模板怕会出问题所以退出条件基本都按这个然后无论是那种模块都基于这个结束条件来判断这样可以把问题收缩都循环里的判定的 check 函数多做了就会发现端倪 然后关于退出之后 left 还是 right 这个是具体问题具体分析由于我的结束判定条件是 leftright 所以如果没用中间返回那么必然存在 left right 的时候这个时候根据判定条件就知道 right 在 left 的前面而到底是左逼近还是右逼近都比较好判断了因为这个时候已经退出去了left 和 right 所代表的 check 的状态也是显而易见的那么看题目要求什么给什么即可 对于二分我觉得这个专题就基本足够了简单居多难题也有两个如果是第一次学习二分那么按照专栏的三个模板去记忆也 ok 别人的经验终归是适合别人自己做题最重要是把握住自己的节奏记忆自己最熟悉的那个点强行模仿别人反而落了下乘 当然那个男人那么强我的做题就是模仿的他慢慢大佬的解法就是我自己的节奏了毕竟模仿多了其实就是自己的了除了算法其他的工程化学习也是一样的 那么周末快乐下周开 dp 吧毕竟这个听有意思的。 模板 1 目标值是一个固定的 target在二分过程中需要不断的判断如果成功就返回对应的值否则直接返回失败的值返回值如果是向下取返回 right如果向上取则返回 left还有可能返回一个特定给的失败值 var search function (fn, target) {let left 最小值,right 最大值;while (left right) {// 取 mid 值const mid ((right - left) 1) left;//这里的 fn 可能是函数也可能只是数组取值反正就是可以取得一个值去跟 target 比较const temp fn(mid);if (temp target) return mid;if (temp target) {left mid 1;} else {right mid - 1;}}return 没有精确匹配后的值; };

1. 二分查找 var search function (nums, target) {const len nums.length;if (!len) return -1;let left 0,right len - 1;while (left right) {const mid ((right - left) 1) left;if (nums[mid] target) return mid;if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1; };
2. x 的平方根 // 69. x 的平方根 var mySqrt function (x) {let left 0,right x;while (left right) {const mid ((right - left) 1) left;const sqrt mid * mid;if (sqrt x) return mid;if (sqrt x) {left mid 1;} else {right mid - 1;}}// 向下取整return right; };
3. 猜数字大小 分析 这里内置一个函数 guess(n), 返回值是 -1 0 1, -1 是 targt 值更小 var guessNumber function (n) {let left 1,right n;while (left right) {const mid ((right - left) 1) left;if (guess(mid) 0) return mid;if (guess(mid) 0) {// 这个时候 mid pickleft mid 1;} else {right mid - 1;}} };// 自己模拟一下这个 guess 函数吧 – 假定第二个参数就是目标猜的数字我们可以用它来初始化默认是5 function guess(num, pick 5) {if (num pick) return 0;if (pick num) return -1;if (pick num) return 1; } 参考视频传送门
4. 排列硬币 分析 这里求的是一个左侧极值的二分法是向右逼近的二分累计值算法是小学数学题 sum (firstend)*count/2每次取中间层数求出到这个层数需要的币数 sum然后和目标值 n 比较如果刚好符合直接返回这里可以收缩到左侧判定条件中如果 count 比较少则 left 要提到 mid1,否则 right 要提到 mid-1由于最后要返回的是最逼近 n 的层数所以判断一下当 left right 情况如果小于 n则 left mid1这个时候 right 符合要求所以跳出循环后返回的是 right时间复杂度O(logN) var arrangeCoins function (n) {let left 0,right n;while (left right) {const mid left ((right - left) 1);// mid 层的时候满的硬币数const sum ((1 mid) * mid) / 2;if (sum n) return mid;if (sum n) {left mid 1;} else {right mid - 1;}}return right; };
5. 搜索旋转排序数组 分析 已知原始数组 nums 是生序排序的且数组中的值不一样的入参的 nums 是在某个下标 k 的作用下发生了重置使得 nums 现在是先升序数组 [k,len-1]然后断裂后再一个升序数组[0,k-1]这是一个局部排好序的数组所以可以用二分处理,返回的是 target 值的下标或者 -1所以每次都用排好序的一半来作为判断依据如果在排好序这边则删除另外反之亦然时间复杂度 O(logn) var search function (nums, target) {let left 0,right nums.length - 1;while (left right) {const mid ((right - left) 1) left;if (nums[mid] target) return mid;if (nums[mid] nums[left]) {// [left,mid] 是有序的if (nums[left] target target nums[mid]) {// target 在[left , mid) 中right mid - 1;} else {left mid 1;}} else {// [mid,right] 是有序的if (nums[mid] target target nums[right]) {// target 在mid , right] 中left mid 1;} else {right mid - 1;}}}return -1; }; 模板 2 – 需要用到邻居值判断 相比于模板 1模板 2 中不是仅有一个符合条件值而是一系列值我们需要找到符合要求的那个 极值比方说是符合条件的最大值/第一个值 等 var search function (fn) {let left 最小值,right 最大值;while (left right) {// 取 mid 值const mid ((right - left) 1) left;//这里的 fn 可能是函数也可能只是数组取值反正就是可以取得一个值去跟 target 比较const bool fn(mid);if (bool) {// 成功了要向还没成功的地方寻找right mid - 1;} else {left mid 1;}}return 特定的值; };
6. 第一个错误的版本 分析 这里要找出的是第一个错误版本而整理版本排列是 正常 - 错误所以这里是根据错误向左逼近如果是错误版本 right 指针不断往左如果是正常版本left 指针不断往右当左右指针相交时如果是错误版本right 继续往左到达正常区这个时候 left 就是第一个错误版本了时间复杂度 O(logn) var solution function (isBadVersion) {return function (n) {let left 1,right n;while (left right) {const mid ((right - left) 1) left;if (isBadVersion(mid)) {// 如果是错误版本right mid - 1;} else {left mid 1;}}return left;}; };
7. 寻找峰值 分析 已知多峰的时候只需返回一个即可那么就是直接做二分判断即可两侧边缘值也可以是峰值,因为题目给了两侧是 -Infinity犹豫已经存在整体区域外的最低点所以只要找到一个局部下降区域那么局部上升区域中肯定存在峰值 var findPeakElement function (nums) {nums[-1] nums[nums.length] -Infinity; // 设置边界值这样保证在边缘的时候也只需要两个值就能判极值let left 0,right nums.length - 1;while (left right) {const mid ((right - left) 1) left;// 找出一个有峰值的区间if (nums[mid] nums[mid 1]) {// [mid,right] 局部下降而[-1,mid] 是局部上升的比较有一个最低值right mid - 1;} else {left mid 1;}}return left; };
8. 寻找旋转排序数组中的最小值 分析 这里其实就是找谷值注意的是这里的值互不相等且局部单增 所以可以加一个辅助条件 nums[-1] nums[len] infinite,这样能保证谷值在边缘也能直接找到 注意这里返回的是最小值而不是最小坐标 注意取得 mid 值之后将 mid 与 right 的值比较只会出现两种情况
   如果 nums[mid]nums[right] 则 mid 和 right 重合或 mid 在 right 之后且单增这个时候无论是在第一个单增区间还是第二个谷点都在 mid 之钱所以 right mid-1 var findMin function (nums) {let len nums.length;nums[-1] nums[len] Infinity;let left 0,right len - 1;while (left right) {const mid ((right - left) 1) left;if (nums[mid - 1] nums[mid] nums[mid] nums[mid 1])return nums[mid]; //谷值if(nums[mid]nums[right]){// [mid,right] 单增// 注意这个等号为啥要加可以考虑一下如果 left 和 right 相等时对应的 mid 也是这个点那么是让 right 走还是让 left 走这里我们最后返回值是 left,所以让 right 走一步结束战斗right mid-1}else{left mid1}}return nums[left]; };
9. 寻找旋转排序数组中的最小值 II 和 153. 寻找旋转排序数组中的最小值 类似但是由于值可以重复无法直接判断单增区间所以想办法将右侧与 mid 相等的值先删除掉这个时候剩下的不同值可以与 153 题一样做处理了 var findMin function(nums) {const len nums.lengthnums[-1] nums[len] Infinitylet left 0,right len-1while(leftright){const mid ((right-left)1) left// 将右侧与 mid 同值的值删掉while(nums[right] nums[mid] rightmid){right – }// 由于存在重复值所以拐点值右侧可以是直线而不一定是单增if(nums[mid-1]nums[mid] nums[mid]nums[mid1]) return nums[mid]if(nums[mid]nums[right]){// 上一题这里的等号是当 left 和 right 重合时的特殊情况// 现在由于值可能重复所以不能直接判断出 [mid,right] 是递增的区间了所以要先为右侧相同的值进行删减然后再进行即可right mid-1}else{left mid1}}return nums[left] }; 模板3 在排序数组中查找元素的第一个和最后一个位置 分析 正常查找 target 值直到找到左侧第一个如果没有找到则直接返回 [-1,-1]如果找到了左侧的 target 值这个时候以左侧 left 为起点再进行一次二分求右侧第一个 target 值最后返回即可时间复杂度 O(logn) var searchRange function(nums, target) {if(!nums) return [-1,-1]let left 0,right nums.length-1let ret []// 找左节点while(leftright){const mid ((right-left)1) leftif(nums[mid]target){left mid1}else{right mid-1}}if(nums[left]! target) return [-1,-1]// 找右节点let l left,r nums.length-1while(lr){const mid ((r-l)1) lif(nums[mid]target){r mid-1}else{l mid1}}return [left,r] };
10. 找到 K 个最接近的元素 分析 先找出 arr 中值最靠近 x 左侧的下标值 – 如果有等于 x 的就取 x 没有就取最靠近的前一个然后开始向两边扩散找接近 x 的前 k 个值时间复杂度 O(log(n)) var findClosestElements function (arr, k, x) {let l 0,r arr.length - 1;while (l r) {const mid ((r - l) 1) l;if (arr[mid] x) {r mid - 1;} else {l mid 1;}}// 这个时候 r 是左侧最靠近 x 的值下标l 是右侧最靠近 x 的值let lIndex r,rIndex l; // 防止混淆let ret [];while (k–) {let isLeft true;if (lIndex 0 rIndex arr.length) {isLeft x - arr[lIndex] arr[rIndex] - x;} else if (rIndex arr.length) {isLeft false;}if (isLeft) {ret.unshift(arr[lIndex]);lIndex–;} else {ret.push(arr[rIndex]);rIndex;}}return ret; }; 其他练习题
11. Pow(x, n) 分析 直接将 n 进行拆分然后递归求值 – 然后超时了因为很多值都是重复的然后就是快速迭代我们 2 - 4 -16值得注意的是这里 n 的取值是 [-231,231-1] 本来没啥事但是吧你将 n 转成正数再执行, 那么 n 1 就有事了一旦 n 是 -2^31,那么第一次递归的时候 recursion 的 n 就是负数了所以要用 或者用数学的方法时间复杂度 O(logn) var myPow function (x, n) {const recursion (n) {if (n 0) return 1;// const y recursion(n 1);const y recursion(Math.floor(n / 2));return n % 2 ? y * y * x : y * y;};return n 0 ? 1 / recursion(-n) : recursion(n); };console.log(myPow(2.1, 3)); console.log(myPow(2, -2));
12. 有效的完全平方数 /** * 分析 * 1. 概念若 x*x y 则 y 是完全平方数 */ var isPerfectSquare function (num) {let left 0,right num;while (left right) {const mid ((right - left) 1) left;const temp mid * mid;if (temp num) return true;if (temp num) {right mid - 1;} else {left mid 1;}}return false; };
13. 寻找比目标字母大的最小字母 分析: 注意 这道题应该改成给定一个排好序的字符数组找出处 target 所在位置的下一个字母且该数组首尾衔接 – 即如果给定的 target 在数组最后则下一个就是首字母字母先转成 UniCode 编码然后用 编码大小来进行比较注意这里只有小写字母所以 left right 值也是有了这是个奇葩的设定[‘a’,‘c’],‘z’ , 如果按照真正 charCode 比较数组中没有比 ‘z’ 大的这里这能说是顺序遍历数组后在 target 之后的第一个元素时间复杂度: O(logN) var nextGreatestLetter function(letters, target) {const targetIndex target.charCodeAt()let left 0,right numbers.length-1while(left right){const mid ((right-left) 1) leftif(letters[mid].charCodeAt()targetIndex){// 只要是符合的都返回往左走知道走不了right mid-1}else{left mid1}}if(leftnumbers.length) return letters[0]return letters[left]};
14. 两个数组的交集 分析 先为 nums1 和 nums2 排序然后遍历其中一个数组另外一个数组做二分查找最后得到结果这里直接取nums1 做遍历实际可以找个长度少的遍历长度大的做二分这样查找过程的时间复杂度即为 O(nlogm), 其中 nm但是由于做了排序实际的时间复杂度是 mlogm m 是大的那个长度 var intersection function (nums1, nums2) {const l1 nums1.length,l2 nums2.length;if (!l1 || !l2) return [];// 先排序nums1.sort((a, b) a - b);nums2.sort((a, b) a - b);const ret [];for (let i 0;il1;i) {if(i0 nums1[i-1] nums1[i]) continue // 重复值跳过const n nums1[i];let left 0,right l2-1;while (left right) {const mid ((right - left) 1) left;if (nums2[mid] n) {ret.push(n);break;}if (nums2[mid] n) {right mid - 1;} else {left mid 1;}}}return ret };
15. 两个数组的交集 II 直接用 map 将其中一个数组的值映射保存起来然后遍历另外的数组每一次匹配成功则map 的值减一ret 数组 push 上这个值直到 map 中的这个值为 0则这个值在两个数组中的最大公约数达到不再进行 push 咯时间复杂度 O(nm) , 空间复杂度 O(n) 其中 n 可以是小的那个数组的不同值长度 var intersect function (nums1, nums2) {const map new Map(); //将长数组的值存储一份for (let item of nums2) {if (map.has(item)) {map.set(item, map.get(item) 1);} else {map.set(item, 1);}}let ret [];for(let item of nums1){if(!!map.get(item)){map.set(item,map.get(item)-1)ret.push(item)}}return ret; };
16. 两数之和 II - 输入有序数组 分析 numbers 是升序数组找出 n1n2 target , 返回 n1,n2 对应的下标值 [i1,i2] – 注意下标值从 1 开始每个输入只有唯一的输出值时间复杂度 nlogn var twoSum function (numbers, target) {for (let i 0; i numbers.length-1; i) {const temp target - numbers[i];let l i 1,r numbers.length - 1;while (l r) {const mid ((r - l) 1) l;if (numbers[mid] temp) return [i 1, mid 1];if (numbers[mid] temp) {left mid 1;} else {right mid - 1;}}} };
17. 寻找重复数 分析 给定长度为 n1 的 nums里面的值都是 1-n, 本题中只有一个值是重复的找出这个值注意这里只是表明重复的只有一个值但是这个值重复多少次并没有说明所以不能用简单的异或二进制处理但是我们可以选定以 mid 值然后判断小于等于 mid 值 count如果 count 超出了 mid 证明在 [1,mid] 中至少有一个值重复了这个时候可以砍掉右侧部分当 left 和 right 相等之后即找到了唯一重复的值因为这个时候左右两侧的值都不服要求就只有这个了时间复杂度 O(nlohn), 空间复杂度 1 var findDuplicate function (nums) {let left 1,right nums.length - 1; // 值是 1 - nwhile (left right) {const mid ((right - left) 1) left;const count nums.reduce((prev, cur) (cur mid ? prev 1 : prev), 0); // 小于等于 count 的值if (count mid) {// 如果 [1,mid] 这个数组满值的情况才只有 mid 个现在 count 如果比这个还大证明重复的值在这里面right mid;} else {left mid 1;}}return left; }; 4.寻找两个正序数组的中位数 分析 已知两个有序数据求中位数 和求第 k 小没啥区别根据两个数组的大小将题转成求第 k 小的题目这题使用二分没能直接过判定条件边界很多最后放弃直接用二分处理掉了 var findMedianSortedArrays function (nums1, nums2) {const n nums1.length,m nums2.length;let sum n m; // 如果是偶数取两个值 prev,cur ,取中间值let k (sum 1) / 2; // 可以是非整数let cur;while (k 1) {if (!nums1.length) {cur nums2.shift();} else if (!nums2.length) {cur nums1.shift();} else {if (nums1[0] nums2[0]) {cur nums1.shift();} else {cur nums2.shift();}}k–;}let next;if (k ! 0) {// 这里用 ?? 而不是用 || , 是因为判断 nums[0] 是否为 undefined而如果是 0 的时候取 0 而非切换到 Infinity;next Math.min(nums1[0] ?? Infinity, nums2[0] ?? Infinity);return (cur next) / 2;}return cur; };
18. 分割数组的最大值 分析 切分数组 nums使得切割后数组和最大的那个值最小 – 子数组是连续的也就是尽可能按照总和均匀的将值分配到每一个数组中且每个数组中最少有一个值,所以最小值应该就是 max(nums[i]), 最大值是 sum(nums)设计一个函数 check(max), 判断是否能切割出 m 个连续子数组且值小于等于 max如果可以证明这个是一个较大值可以继续向左侧逼近找到一个更小的值如果不可以证明这个值 max 偏小了需要求的值在右侧.这里最需要注意的是切割的子组件是连续的同时每一个数组至少有一个值只要捋清楚 check 这个函数基本就能每次都切掉一半直接拿到最后值了 var splitArray function (nums, m) {// 先找到 left 和 rightlet left 0,right 0;for (let num of nums) {left Math.max(num, left);right num;}// 切割最大值不超过 max 的数组如果切出来的数组数量少于 m则证明可以切得更新发挥 true// 如果切除来的数组数量超出了 m, 证明只且 m 组的时候最小值要超出 max 了返回 falsefunction check(max) {let ret 0,sum 0;let i 0;while (i nums.length) {sum nums[i];if (sum max) {// 一旦超出 max则分组结束sum 重新设置为 nums[i]ret;sum nums[i];}i}// 如果最后还有剩单独成团ret sum ? ret 1 : ret;return retm}while (left right) {const mid ((right - left) 1) left;if (check(mid)) {// 如果能找到向左逼近 – right 最后得到的是一个不成功的值因为只要成功它就要发生改变right mid - 1;} else {// left 最终出去的时候肯定代表一个成功的值left mid 1;}}return left;};