855学习记录算法刷题$Day$-$3$——炎泽汐$de$ Blog

环形链表 2

---

     快慢指针，相遇有环，遇后快停，慢头同走，相遇入口；

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *f = head, *s = head;
        while(f && f -> next){
            f = f -> next -> next;
            s = s -> next;
            if(f == s){
                while(s != head){
                    s = s -> next;
                    head = head -> next;
                }
                return head;
            }
        };
        return NULL;
    }
};

乘积最大子数组

---

      以第 i 个数结尾的最大乘积要么是以 i-1 结尾的最小乘积乘 i、要么是以 i-1 结尾的最大乘积乘 i、要么是自身；

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int a, b, ans, ta, tb;
        a = b = ans = nums[0];
        for(int i = 1; i < n; i++){
            ta = a, tb = b;
            a = max(nums[i], max(ta * nums[i], tb * nums[i]));
            b = min(nums[i], min(ta * nums[i], tb * nums[i]));
            ans = max(a, ans);
        }
        return ans;
    }
};

完全平方数

---

     完全背包问题；

class Solution {
public:
    int numSquares(int n) {
        int m = sqrt(n);
        vector<int> DP(n + 1, 10001);
        DP[0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(j >= i * i){
                    DP[j] = min(DP[j], DP[j - i * i] + 1);
                }
            }
        }
        return DP[n];
    }
};

买卖股票的最佳时期含冷冻期

---

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] -= prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
    }
};

戳气球

---

     经典区间 DP；

class Solution {
public:
    vector<int> arr;
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        int dp[n + 1][n + 1];
        memset(dp, 0, sizeof(dp));

        arr.clear();
        arr.push_back(1);
        for(int i = 0; i < n; i++){
            arr.push_back(nums[i]);
        }
        arr.push_back(1);

        for(int i = 1; i <= n; i++){
            dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1];
        }
        for(int i = 1; i < n; i++){
            int a = dp[i][i] + arr[i - 1] * arr[i + 1] * arr[i + 2];
            int b = dp[i + 1][i + 1] + arr[i - 1] * arr[i] * arr[i + 2];
            dp[i][i + 1] = max(a, b);
        }

        for(int len = 3; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int l = i, r = i + len - 1;
                int a = arr[l - 1] * arr[l] * arr[r + 1] + dp[l + 1][r];
                int b = arr[l - 1] * arr[r] * arr[r + 1] + dp[l][r - 1];
                dp[l][r] = max(a, b);
                for(int k = l + 1; k < r; k++){
                    int temp = dp[l][k - 1] + dp[k + 1][r];
                    temp += arr[l - 1] * arr[k] * arr[r + 1];
                    dp[l][r] = max(dp[l][r], temp);
                }
            }
        }
        return dp[1][n];
    }
};