• 算法记录 & 牛客网 & leetcode刷题记录


    常用算法模板

    堆排序

    小顶堆:每次都把最大的调整到根部,最后把最大的放在数组末尾,最终形成的堆根部是最小的
    大顶堆:每次都把最小的调整到根部,最后把最小的放在数组末尾,最终形成的堆根部是最大的

    在优先队列里,

    //小顶堆,top的时候返回元素最小的那个
    priority_queue <int,vector<int>,greater<int> > q;
    //大顶堆,top的时候返回元素最大的那个
    priority_queue <int,vector<int>,less<int> >q;
    ``
    
    
    堆排序每次调整成大顶/小顶堆后,把堆顶元素放到数组末尾,然后继续调整大顶/小顶堆
    ```cpp
    class HeapSort {
    public:
    	void heapSort(vector<int>& arr) {
    		if (arr.size() == 0) {
    			return;
    		}
    		int len = arr.size();
    		// 构建大顶堆,这里其实就是把待排序序列,变成一个大顶堆结构的数组
    		buildMaxHeap(arr, len);
     
    		// 交换堆顶和当前末尾的节点,重置大顶堆
    		for (int i = len - 1; i > 0; i--) {
    			swap(arr, 0, i);
    			len--;
    			heapify(arr, 0, len);
    		}
    	}
     
    	void buildMaxHeap(vector<int>& arr, int len) {
    		// 从最后一个非叶节点开始向前遍历,调整节点性质,使之成为大顶堆
    		for (int i = (int)floor(len / 2) - 1; i >= 0; i--) {
    			heapify(arr, i, len);
    		}
    	}
     
    	void heapify(vector<int>& arr, int i, int len) {
    		// 先根据堆性质,找出它左右节点的索引
    		int left = 2 * i + 1;
    		int right = 2 * i + 2;
    		// 默认当前节点(父节点)是最大值。
    		int largestIndex = i;
    		if (left < len && arr[left] > arr[largestIndex]) {
    			// 如果有左节点,并且左节点的值更大,更新最大值的索引
    			largestIndex = left;
    		}
    		if (right < len && arr[right] > arr[largestIndex]) {
    			// 如果有右节点,并且右节点的值更大,更新最大值的索引
    			largestIndex = right;
    		}
     
    		if (largestIndex != i) {
    			// 如果最大值不是当前非叶子节点的值,那么就把当前节点和最大值的子节点值互换
    			swap(arr, i, largestIndex);
    			// 因为互换之后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整。
    			heapify(arr, largestIndex, len);
    		}
    	}
     
    	void swap (vector<int>& arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    插入排序

    插入排序其实是冒泡排序的反向,插入排序从数组第二个元素开始,每加入一个元素,都将其和前面已有的元素进行比较,然后不断调整位置。

    void insertionSort(vector<int> & data) {
    	for (int i = 1; i < data.size(); i++) {
    		for (int j = i; j >= 1; j--) {
    			if (data[j] < data[j - 1]) {
    				int tmp = data[j];
    				data[j] = data[j - 1];
    				data[j - 1] = tmp;
    			}
    		}
    	}
    	return;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    快速排序

    原理:每次随机将数组中的一个数,放到他指定的排序后的位置。
    比如,把一个数A,放到数组的位置i,那么[0,i-1]的位置都是比A小的数,[i+1,size-1]都是比A大的数

    class Solution {
    public:
        void qsort(vector<int>& nums,int start,int end,int k){
        int size=nums.size();
        int i=start,j=end,base=nums[start];
        if(size<=0) return;
        
        
        while(i<j){
            while(nums[j]<=base && i<j){
                j--;    
            }
            
            if(i<j) nums[i]=nums[j];
            
            while(nums[i]>=base && i<j) i++;
            
            if(i<j) nums[j]=nums[i];
         }
        
         
         nums[i]=base;
        
        if(i+1>k) qsort(nums,start,i-1,k);
        else if(i+1==k) return ;
        else qsort(nums,i+1,end,k);
    }
        
        int findKthLargest(vector<int>& nums, int k) {
            int size=nums.size();
            qsort(nums,0,size-1,k);
            return nums[k-1];
        }
        
        
        
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    二叉树

    JZ55 二叉树的深度

    关键词:二叉树、深度优先遍历、递归


    自己写的笨蛋方法:

    /*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        int max_depth = 0;
        int now_depth = 0;
        int TreeDepth(TreeNode* pRoot) {
            if(pRoot == NULL){
                return max_depth;
            }
            this->now_depth++;
            if(now_depth>max_depth){
                max_depth=now_depth;
            }
            this->TreeDepth(pRoot->left);
            this->TreeDepth(pRoot->right);
            this->now_depth--;
            return max_depth;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    优秀解答:

    1. 递归解法
    class Solution {
    public:
    	int TreeDepth(TreeNode* pRoot){
    	    if(!pRoot) return 0 ;
                return max(1+TreeDepth(pRoot->left), 1+TreeDepth(pRoot->right));
    	}
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    1. BFS解法
    import java.util.Queue;
    import java.util.LinkedList;
    
    public class Solution {
    	public int TreeDepth(TreeNode pRoot)
        {
        	if(pRoot == null){
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(pRoot);
            int depth = 0, count = 0, nextCount = 1;
            while(queue.size()!=0){
                TreeNode top = queue.poll();
                count++;
                if(top.left != null){
                    queue.add(top.left);
                }
                if(top.right != null){
                    queue.add(top.right);
                }
                if(count == nextCount){
                    nextCount = queue.size();
                    count = 0;
                    depth++;
                }
            }
            return depth;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    回溯

    其实回溯就是递归

    解题的时候,如果遇到给的函数参数不够,可以另自己起一个函数

    JZ12 矩阵中的路径

    我的答案

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 
         * @param matrix char字符型vector> 
         * @param word string字符串 
         * @return bool布尔型
         */
        int now=0;
        bool flag = false;
        stack<int*> s;
        vector<vector<bool>> v;
        bool hasPath(vector<vector<char> >& matrix, string word) {
            // write code here
            if(matrix.size()==0 || word.size()==0 || matrix[0].size()==0){
                return false;
            }
            
            if(now == 0){
                v.resize(matrix.size(), vector<bool>(matrix[0].size()));
            }
            
            if(word[now] == '\0'){
                flag=true;
                return flag;
            }
            if(now ==0){
                for(int i = 0;i<matrix.size();i++){
                    for(int j=0; j<matrix[0].size();j++){
                        if(flag){
                            break;
                        }
                        if(matrix[i][j]==word[now]){
                            now++;
                            int arr[2]={i,j};
                            s.push(arr);
                            v[i][j] = true;
                            if(hasPath(matrix, word)){
                                 return flag;  
                            }
                            s.pop();
                            now--;
                            v[i][j]=false;
                        }
                    }
                }
            }
            else{
                int* arr = s.top();
                int i = arr[0];
                int j = arr[1];
                
                if(i!=0 &&  matrix[i-1][j] == word[now] && v[i-1][j]!=true){
                    now++;
                    int tmp[2] = {i-1, j};
                    s.push(tmp);
                    v[i-1][j]= true;
                    if(hasPath(matrix, word)){
                        return flag;
                    }
                    v[i-1][j]= false;
                    s.pop();
                    now--;
                }
                if(i!=matrix.size()-1 &&  matrix[i+1][j] == word[now] && v[i+1][j]!=true){
                    now++;
                    int tmp[2] = {i+1, j};
                    s.push(tmp);
                    v[i+1][j]= true;
                    if(hasPath(matrix, word)){
                        return flag;
                    }
                    v[i+1][j]= false;
                    s.pop();
                    now--;
                }
                if(j!=matrix[0].size()-1 &&  matrix[i][j+1] == word[now] && v[i][j+1]!=true){
                    now++;
                    int tmp[2] = {i, j+1};
                    s.push(tmp);
                    v[i][j+1]= true;
                    if(hasPath(matrix, word)){
                        return flag;
                    }
                    v[i][j+1]= false;
                    s.pop();
                    now--;
                }
                if(j!=0 &&  matrix[i][j-1] == word[now] && v[i][j-1]!=true){
                    now++;
                    int tmp[2] = {i, j-1};
                    s.push(tmp);
                    v[i][j-1]= true;
                    if(hasPath(matrix, word)){
                        return flag;
                    }
                    v[i][j-1]= false;
                    s.pop();
                    now--;
                }
                
                
            }
            return flag;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108

    高分答案

    import java.util.*;
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 
         * @param matrix char字符型二维数组 
         * @param word string字符串 
         * @return bool布尔型
         */
        public boolean hasPath (char[][] board, String word) {
            // write code here
                  int  length1=board[0].length;//列数
          int  length2=board.length;//行数
            for(int i =0; i<length2;i++){
                for(int j=0;j<length1;j++){
                    if(board[i][j]==word.charAt(0))
                     if(dfs(board,i,j,word,0))
                        return true;
                        
                   
                }
            }
            return false;
        }
    
        public boolean dfs(char[][] board,int i, int j, String word, int u){
          int  length1=board[0].length;//列数
          int  length2=board.length;//行数
            //失败:先判断边界值
            if(i<0||i>=length2||j<0||j>=length1||board[i][j]!=word.charAt(u)){
                return false;
            }
            //成功:遍历到最后一个
            if(u==word.length()-1)
                return true;
            //覆盖原来防止重复
            char temp = board[i][j];
            board[i][j]= '#';
            //递归调用
            boolean res = dfs(board,i-1,j,word,u+1) || dfs(board,i+1,j,word,u+1) || dfs(board,i,j-1,word,u+1)
            || dfs(board,i,j+1,word,u+1) ;
            //递归结束
            board[i][j]= temp;
            return res;
            
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    总结:
    回溯刚开始都要判断结束 && 判断边界 && 判断条件

    接下来再调用自己。

    有没有走过可以先覆盖原来的,之后回溯出来的时候再写回原来的
    (这样就避免了还要自己初始化一个数组判断是否走过)

    二分查找、排序

    二分诀窍:

    1. 找到二分开始的位置
    2. 找到二分前进的方向

    关于左开右闭,左闭右开,左闭右闭
    【玩转二分查找Ⅰ】左闭右闭型,左开右闭型,左闭右开型(动图演绎)

    核心是,中间值的取法不同 以及 while循环内部的判断方式不同


    Leetcode-148 排序链表

    leetcode-排序列表题目详情
    总结:使用归并排序
    链表找到中间位置:是用一个快指针,一个慢指针。

    卡了很久的一个点:

    if(first_pointer == nullptr) 
    	return second_pointer 
    else
    	return first_pointer
    
    • 1
    • 2
    • 3
    • 4

    这是错误的,因为忽略了 first_pointer和second_pointer都有值的情况

    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(head == nullptr || head->next==nullptr){
                return head;
            } 
    
            ListNode* first_pointer=head;
            ListNode* second_pointer=head->next;
            
            // 找到中间的位置
            while((second_pointer!=nullptr) && (second_pointer->next!=nullptr) ){
                first_pointer = first_pointer->next;
                second_pointer = second_pointer->next;
                if(second_pointer->next != nullptr){
                    second_pointer = second_pointer->next;
                }
            }
    
            
            ListNode* next_pointer = first_pointer->next;
            first_pointer->next =nullptr;
            head = sortList(head);
            next_pointer = sortList(next_pointer);
            
            return Merge(head,next_pointer);
        }
    
        ListNode* Merge(ListNode* first_pointer, ListNode* second_pointer){
            ListNode* head;
            ListNode* tick;
            if(first_pointer == nullptr){
                return second_pointer;
            }
            if(second_pointer == nullptr){
                return first_pointer;
            }
    
            if(first_pointer->val < second_pointer->val){
                head=first_pointer;
                tick=first_pointer;
                first_pointer = first_pointer->next;
            }
            else{
                head=second_pointer;
                tick=second_pointer;
                second_pointer = second_pointer->next;
            }
    
            while(first_pointer!=nullptr && second_pointer!=nullptr){
                if(first_pointer->val < second_pointer->val){
                    tick->next= first_pointer;
                    first_pointer = first_pointer->next;
                    tick = tick->next;
                }
                else{
                    tick->next = second_pointer;
                    second_pointer = second_pointer->next;
                    tick = tick->next;
                }
            }
    
            if(first_pointer==nullptr){
                tick->next =second_pointer;
    
            }
            else{
                tick->next=first_pointer;
            }
    
            return head;
    
        }
    
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    BM18 二维数组中的查找

    矩阵中,行和列都是递增,那么可以找左下,或者右上的元素开始。
    复杂度:O(n+m)

    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int r = array.size();
            if(r == 0){
                return false;
            }
            int col = array[0].size();
            if(col == 0){
                return false;
            }
            int i = 0, j =col-1;
            
            while(i<=r-1 && j>=0 ){
                if(array[i][j] == target){
                    return true;
                }
                else if(array[i][j] >target){
                    j--;
                }
                else if(array[i][j]<target){
                    i++;
                }
                 
            }
                
            return false;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    BM19寻找峰值

    复杂度O(logn)
    思想: 上坡一定有波峰,下坡不一定有波峰

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 
         * @param nums int整型vector 
         * @return int整型
         */
        int findPeakElement(vector<int>& nums) {
            // write code here
            int right = nums.size()-1;
            int left = 0;
            while(left<right){
                int mid = (left+right)/2;
                if(nums[mid]>nums[mid+1]){
                    right = mid;
                }
                else{
                    left = mid+1;
                }
            }
            return right;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    295. 数据流的中位数

    295.数据流的中位数

    思想: 维护两个堆,一个大顶堆(堆顶是最大的元素),一个是小顶堆(堆顶是最小的元素)。

    每个堆都存储一半的元素,大顶堆的元素总是小于等于小顶堆的元素。

    那么中位数就可以通过大顶堆堆顶和小顶堆堆顶元素来判断。

    class MedianFinder {
    public:
    	// 小顶堆,堆顶是最小的元素
        priority_queue<int, vector<int>, greater<int>> big;
    	// 大顶堆,堆顶是最大的元素
        priority_queue<int, vector<int>, less<int>> small;
        MedianFinder() {
        }
        
        void addNum(int num) {
            big.push(num);
            
            small.push(big.top());
            big.pop();
            if(small.size()>big.size()){
                big.push(small.top());
                small.pop();
            }
        }
        
        double findMedian() {
            if(big.size() == small.size()){
                return (big.top() +small.top())/2.0; 
            }
            else{
                return big.top();
            }
        }
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder* obj = new MedianFinder();
     * obj->addNum(num);
     * double param_2 = obj->findMedian();
     */
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    动态规划

    所以在DP的实践中很重要的就是递推关系边界条件
    1. 边界条件
    所谓边界条件就是最简单的情况。
    2. 递推关系
    所谓递推关系就是如果你已经知道这么多,再多给你一个,你怎么得到。
    (状态转移方程)

    状态定义、状态转移方程


    DP5 连续子数组最大和

    状态定义: array[i] 表示数组连续到下标为i为止的连续数组最大和
    (注意区别于整个数组的连续数组最大和, 或者说 array[i]代表以第 i 个数结尾的子数组最大连续和)
    状态转移方程: state[i] = max(state[i-1]+array[i], array[i])
    因为最终求的是整个数组的最大值,所以要使用max_num来存储最大值

    #include
    using namespace std;
    int main(){
        int n;
        cin>>n;
        vector<int> array(n, 0);
        vector<int> state(n,INT_MIN);
        
        cin>>array[0];
        state[0] = array[0];
        int max_num = array[0];
        
        for(int i=1;i<n;i++){
            cin>>array[i];
            state[i] = max(state[i-1]+array[i],array[i]);
            
            max_num = max(max_num,state[i]);
        }
        
        cout<<max_num<<endl;
        return 0;  
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    664. Strange Printer(奇怪的打印机)

    题解

    class Solution {
    public:
        int strangePrinter(string s) {
            int size = s.size();
            if(size == 0){
                return 0;
            }
            vector<vector<int>> v(size, vector<int>(size, INT_MAX));
            
            for(int i=size-1;i>=0;i--){
                for(int j=i;j<=size-1;j++){
                    // 分开打印
                    v[i][j] = ((i==j)? 1: 1+v[i+1][j]);
                    
                    for(int k=i+1;k<j;k++){
                        if(s[i] == s[k]){
                            v[i][j] = min(v[i][j], v[i+1][k]+v[k+1][j]);
                        }
                    }
                    if(s[i] == s[j] && i!=j){
                        v[i][j] = min(v[i][j], v[i+1][j]);
                    }
                }
            }
            return v[0][size-1];
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    BM80 买卖股票的最好时机(一)

    这种买入必须在卖出前面的,即当前位置的值只和前面有关的,非常适合于一次遍历

    class Solution {
    public:
        /**
         * 
         * @param prices int整型vector 
         * @return int整型
         */
        int maxProfit(vector<int>& prices) {
            // write code here
            int min_price = INT_MAX;
            int profit = 0;
            int size = prices.size();
            
            for(int i=0;i<size;i++){
                profit = max(profit, prices[i] - min_price);
                min_price = min(min_price,prices[i]);
                
            }
            return profit;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    BM81 买卖股票的最好时机(二)

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         * 计算最大收益
         * @param prices int整型vector 股票每一天的价格
         * @return int整型
         */
        int maxProfit(vector<int>& prices) {
            // write code here
            int profit = 0;
             
            for(int i =1; i<prices.size();i++){
                int tmp = prices[i] -prices[i-1];
                if(tmp>0){
                    profit+=tmp;
                }
            }
             
            return profit;
             
             
             
        }
    };
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    BM82 买卖股票的最好时机(三)

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         * 计算最大收益
         * @param prices int整型vector 股票每一天的价格
         * @return int整型
         */
        int maxProfit(vector<int>& prices) {
            // write code here
            int dp0 = 0;
            int dp1 = -prices[0];
            int dp2 = 0;
            int dp3 = -prices[0];
            int dp4 = 0;      
            for(int i=1;i<prices.size();i++){
                int dp0_0 = dp0;
                int dp1_1 = max(dp1, dp0 - prices[i]);
                int dp2_2 = max(dp2, dp1 + prices[i]);
                int dp3_3 = max(dp3, dp2 - prices[i]);
                int dp4_4 = max(dp4, dp3 + prices[i]);
                dp0 = dp0_0;
                dp1 = dp1_1;
                dp2 = dp2_2;
                dp3 = dp3_3;
                dp4 = dp4_4;
    //             dp0 = dp0;
    //             dp1 = max(dp1, dp0 - prices[i]);
    //             dp2 = max(dp2, dp1 + prices[i]);
    //             dp3 = max(dp3, dp2 - prices[i]);
    //             dp4 = max(dp4, dp3 + prices[i]);
            }   
            return dp4;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    329. 矩阵中的最长递增路径

    leetcode 329 矩阵中的最长递增路径

    方法1: DFS + 动态规划

    class Solution {
    public:
        vector<vector<int>> directions{{0,-1},{0,1},{1,0},{-1,0}};
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int row_num = matrix.size();
            if(row_num == 0){
                return 0;
            }
            int col_num = matrix[0].size();
            if(col_num == 0){
                return 0;
            }
    
            vector<vector<int>> memo(row_num, vector<int>(col_num , 0));
    
            int max_length = 0;
    
            for(int i= 0; i<row_num;i++){
                for(int j=0;j<col_num;j++){
                    max_length = max(max_length, dfs(matrix, i, j, memo));
                }
            }
            return max_length;
        }
    
        int dfs(vector<vector<int>>& matrix, int row, int col, vector<vector<int>>& memo){
            if(memo[row][col] !=0){
                return memo[row][col];
            }
    
            memo[row][col]++;
    
            for(int i=0;i<directions.size();i++){
                    int new_row = directions[i][0] + row;
                    int new_col = directions[i][1] + col;
    
                    if(new_row >=0 && new_col>=0 && new_row<memo.size() && new_col < memo[0].size()){
                        if(matrix[new_row][new_col] > matrix[row][col]){
                            memo[row][col] = max(memo[row][col], 
                                                 dfs(matrix, new_row, new_col, memo)+1);
                        }
                    }
    
                
            }
            
            return memo[row][col];
    
        }
    
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    方法2:拓扑排序 + 动态规划
    注意,这里是从出度为0的

    class Solution {
    public:
    
        vector<vector<int>> dirs = {{0,-1},{0,1}, {1,0},{-1,0}};
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if (matrix.size() == 0 || matrix[0].size() == 0) {
                return 0;
            }
    
            int row_num = matrix.size();
            int col_num = matrix[0].size();
            vector<vector<int>> outdegrees(row_num, vector<int>(col_num, 0));
            queue<pair<int,int>> q;
    
    
            for(int i=0; i<row_num; i++){
                for(int j=0; j<col_num; j++){
                    for(int dir=0;dir<dirs.size();dir++){
                        int newRow = i+dirs[dir][0];
                        int newCol = j+dirs[dir][1];
    
                        if(newRow>=0 && newCol>=0 && newRow<row_num && newCol < col_num && matrix[i][j] < matrix[newRow][newCol]){
                            outdegrees[i][j]++;
                        }
                    }
                   
                }
            }
    
            for(int i=0;i<row_num;i++){
                for(int j=0;j<col_num;j++){
                     if(outdegrees[i][j] == 0){
                        q.push(pair<int,int>(i,j));
                    }
                }
            }
    
            int ans =0;
    
            //BFS
            while(!q.empty()){
                ans++;
                int tmp_size = q.size();
                for(int _=0;_<tmp_size;_++){
                    pair<int, int> e = q.front();
                    q.pop();
    
                    int row = e.first;
                    int col = e.second;
    
                    for(int dir=0;dir<dirs.size();dir++){
                        int newRow = row + dirs[dir][0];
                        int newCol = col + dirs[dir][1];
    \
                        if(newRow>=0 && newCol>=0 && newRow<row_num && newCol < col_num && matrix[row][col] > matrix[newRow][newCol]){
                            outdegrees[newRow][newCol]--;
                            if(outdegrees[newRow][newCol] == 0){
                                q.push(pair<int, int>(newRow, newCol));
                            }
                        }
                        
                    }
                }
            }
            return ans;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
  • 相关阅读:
    Vue 2 进入、离开和列表过渡
    ubuntu 多版本cmake共存的终极方法
    Shell-01Shell初相识
    langchain:Prompt在手,天下我有
    计算机专业毕业设计项目推荐09-个人医疗系统(Spring+Js+Mysql)
    【RTOS训练营】上节回顾、内部机制、中断管理和晚课提问
    微软出品自动化神器Playwright,不用写一行代码(Playwright+Java)系列(二) 之脚本的录制及调试详解
    EventLoop事件循环机制
    白噪声,有色噪声的定义、特性及其MATLAB仿真
    iview表格实现的编辑和expand功能
  • 原文地址:https://blog.csdn.net/crabstew/article/details/123119585