京东网站建设设计框架图,太原最新新闻消息,网站为什么要seo?,小程序开发制作费用167. 两数之和 II - 输入有序数组 输入#xff1a;numbers [2,7,11,15], target 9 输出#xff1a;[1,2]。 解释#xff1a;2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 解题思路#xff1a;首先散列表可以直接秒了#xff0c;双指针也秒了 二分…167. 两数之和 II - 输入有序数组 输入numbers [2,7,11,15], target 9 输出[1,2]。 解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 解题思路首先散列表可以直接秒了双指针也秒了 二分法是这里面性能不好的一种做法nlog(n),得遍历后找其他两个O(n)
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {for(int i0, jnumbers.size()-1;ij;i){int l i1,r j;int mid;while(lr){mid (lr1)/2;if(numbers[i]numbers[mid]target)rmid-1;else lmid;}if(numbers[i]numbers[l]target)return {i1,l1};}return {};}
};240. 搜索二维矩阵 II 解题思路双指针秒了ij从左下角开始搜索二维矩阵I 是拍平二维数组然后二分这题应该也是考虑如何拍平 278. 第一个错误的版本 你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
这里也可以二分分从这以后的版本都是错误从这以前的版本可能正确的直接使用二分法模板一
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left0;int rightn;int mid0;while(leftright){mid (right - left) / 2 left; if(isBadVersion(mid)){rightmid;}elseleftmid1;}return left;}
};300. 最长递增子序列 输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4 。
class Solution {
public:int lengthOfLIS(vectorint nums) { int ans1;int nnums.size();vectorintdp(n,1);for(int i0;in;i){for(int j0;ji;j){if(nums[i]nums[j]){dp[i]max(dp[i],dp[j]1);if(ansdp[i])ansdp[i];}}}return ans;}};349. 两个数组的交集 输入nums1 [1,2,2,1], nums2 [2,2] 输出[2] 611. 有效三角形的个数 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 658. 找到 K 个最接近的元素 输入arr [1,2,3,4,5], k 4, x 3 输出[1,2,3,4]
