leetcode题目解析(191101)

Leetcode 287:寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例

输入: [1,3,4,2,2],输出: 2

输入: [3,1,3,4,2],输出: 3

解题思路

代码实现

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

解题思路

代码实现

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。

代码实现

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();
    }

代码性能

复杂度配图

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注