leetcode题目解析（191101）
标签：leetcode
Leetcode 287：寻找重复数
题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例
输入: [1,3,4,2,2]，输出: 2
输入: [3,1,3,4,2]，输出: 3
解题思路
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int findDuplicate(vector<int>& nums) { int len = nums.size(); if (len < 1) return -1; int slow = nums[0]; int fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } int res = 0;//从开头开始，与慢指针相遇 while (res != slow) { slow = nums[slow]; res = nums[res]; } return res; } |
代码性能
Leetcode 287：寻找重复数
题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例
输入: [1,3,4,2,2]，输出: 2
输入: [3,1,3,4,2]，输出: 3
解题思路
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int findDuplicate(vector<int>& nums) { int len = nums.size(); if (len < 1) return -1; int slow = nums[0]; int fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } int res = 0;//从开头开始，与慢指针相遇 while (res != slow) { slow = nums[slow]; res = nums[res]; } return res; } |
代码性能
Leetcode 300：最长上升序列
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int lengthOfLIS(vector<int>& nums) { vector<int> inseq;; for(int i = 0;i < nums.size();i++){ auto it = std::lower_bound(inseq.begin(),inseq.end(),nums[i]); if(it == inseq.end()){ inseq.push_back(nums[i]); } else *it = nums[i]; } return inseq.size(); } |
代码性能
