算法经典题型

整理几个经典题型。

双指针

11.盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0,right = height.size() - 1;
        int ret = min(height[left],height[right]) * (right  - left);
        while(left < right){
            ret = max(ret, min(height[left],height[right])*(right-left));
            if (height[left] <= height[right]){
                left++;
            }else{
                right --;
            }
        }
        return ret;
    }
};

19.删除链表的倒数第N个节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

209.长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums)
    {
        int n = nums.size();
        int ans = INT_MAX;
        int left = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            while (sum >= s) {
                ans = min(ans, i + 1 - left);
                sum -= nums[left++];
            }
        }
        return (ans != INT_MAX) ? ans : 0;
    }
};

并查集

DFS

BFS

动态规划

70.爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        int ret = 0;
        vector <int> dp(n+1);
        if (n < 2){
            return 1;
        }else {
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
        }
        return dp[n];
    }
};

53.最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), ret = nums[0];
        vector <int> dp(n);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++){
            if(nums[i]>nums[i]+dp[i-1])
                dp[i]=nums[i];
            else
                dp[i]=nums[i]+dp[i-1];
            if(ret<dp[i]) 
                ret=dp[i]; 
        }
        return ret;
    }
};

63.不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        vector <int> ret(m);

        if (obstacleGrid[0][0] == 0){
            ret[0] = 1;
        }else{
            ret[0] = 0;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    ret[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    ret[j] += ret[j - 1];
                }
            }
        }

        return ret[m - 1];
    }
};

91.解码方法

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        int pre = 1, curr = 1;//dp[-1] = dp[0] = 1
        for (int i = 1; i < s.size(); i++) {
            int tmp = curr;
            if (s[i] == '0')
                if (s[i - 1] == '1' || s[i - 1] == '2') curr = pre;
                else return 0;
            else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6'))
                curr = curr + pre;
            pre = tmp;
        }
        return curr;
    }

};

堆栈