ChengYue's Cat

🍉 基础类型题目

🍉 链表

141. 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 只有 0 或者 1 个节点直接返回false
        if(head == NULL || head->next == NULL) return false;

        // 注意这里节点的初始化slow = head; fast = head->next
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != slow){
            if(fast==nullptr || fast->next==nullptr) return false;
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }
};

🍉 双指针

165. 比较版本号

🍉 贪心算法

334.递增的三元子序列

解法一：

//为了找到递增的三元子序列，first 和 second 应该尽可能地小，此时找到递增的三元子序列的可能性更大
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int len = nums.size();
        if(len < 3) return false;

        int min = nums[0], max = INT_MAX;

        for(int i=1; i<len; i++){
            if(nums[i] > max) {
                return true;
            }
            else if(nums[i] > min) {
                max = nums[i];
            }
            else {
                min = nums[i];
            }
        }
        return false;
    }
};

解法二：

//维护两个数组left_min, right_max, left_min[i]为 i 左侧的最小值，right_max[i] 为 i 右侧的最大值。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int len=nums.size();
        
        vector<int> left_min(len, 0);
        left_min[0] = nums[0];
        vector<int> right_max(len, 0);
        right_max[len-1] = nums[len-1];
        // 维护数组 left_min
        for(int i=1; i < len; i++) {
            left_min[i] = min(left_min[i-1], nums[i]);
        }
        // 维护数组 right_max
        for(int j=len-2; j>=0; j--) {
            right_max[j] = max(right_max[j+1], nums[j]);
        }
        for(int k=1; k<len-1; k++){
            if(nums[k]>left_min[k-1] && nums[k] <right_max[k+1]) return true;
        }
        return false;
    }
};

🍉 动态规划

300.最长递增子序列

解法一：完全基于动态规划

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        // 定义dp数组并初始化
        vector<int> dp(len, 1);
        // 更新dp数组
        for(int i=1; i<len; i++) {
            for(int j=0; j<i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int k=0; k <len; k++){
            if(dp[k] > res) res = dp[k];
        }
        return res;
    }
};

解法二：动态规划+二分查找

This site is open source. Improve this page.