A Code

151. Best Time to Buy and Sell Stock III int maxProfit ( vector < int > &prices) { // write your code here // DP //好吧，还是要整理DP思路先。 //状态 f[i][j] 前i-th element 最多交易j次的收益。 //转移：在第i-th 元素看，分情况： //1, day i 没有交易: f[i][j] = f[i - 1][j]. //2, day i 有交易。1) 第i - 1天没有卖: f[i][j] = f[i - 1][j - 1] + max(0, prices[i- 1] - prices[i - 2); // 2) 第i - 1天卖了: f[i][j] = p[i - 1][j] + diff; //需要第二个状态: 表示在第i天卖了这个特定条件下，最多交易j次的收益p[i][j],实际上就是上面f[i][j]里的case2. // 站在第i天，第i天卖了：p[i][j] = max(f[i - 1][j - 1] + max(0, prices[i - 1] - prices[i - 2]), p[i-1][j] + diff; //iniial, 都是0. const int n = prices.size(); if (n == 0 ){ return 0 ; } //vector<vector<int>> f(n + 1, vector<int>(3, 0)); //vector<vector<int>> p(n + 1, vector<int>(3, 0)); vector < int > f( 3 , 0 ); vector ...

public : /** * @param matrix: matrix, a list of lists of integers * @param target: An integer * @return: a boolean, indicate whether matrix contains target */ bool searchMatrix ( vector < vector < int >> &matrix, int target) { // write your code here // binary search 1，先找比target小的最大的值 2，然后在这一行内找。复杂度是O(log(m) + log(n)) const int m = matrix.size(); if (m == 0 ){ return false ; } const int n = matrix[ 0 ].size(); if (target < matrix[ 0 ][ 0 ]){ return false ; } if (target > matrix[m - 1 ][n - 1 ]){ return false ; } int start = 0 ; int end = m - 1 ; int row = 0 ; while (start + 1 < end){ int mid = start + (end - start) / 2 ; if (matrix[mid][ 0 ] == target){ return true ; } else if (matrix[mid][ 0 ] <...

36. Reverse Linked List II Unfollow Description 中文 English Reverse a linked list from position m to n. Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: 1->2->3->4->5->NULL, m = 2 and n = 4, Output: 1->4->3->2->5->NULL. Example 2: Input: 1->2->3->4->NULL, m = 2 and n = 3, Output: 1->3->2->4->NULL. ListNode * reverseBetween (ListNode * head, int m, int n) { // write your code here if (head == NULL || head->next == NULL ){ return head; } if (m == n){ return head; } ListNode *dummy = new ListNode( 0 ); dummy->next = head; ListNode *copy = dummy; for ( int i = 0 ; i < m - 1 ; i++){ dummy = dummy->next; } ...

162. Set Matrix Zeroes void setZeroes ( vector < vector < int >> &matrix) { // write your code here //用第一行和第一列存 有0的列 和 有 0的行 //先判断记录第一行，第一列里面是否有0，有0的话全行，全列后面变0. const int m = matrix.size(); if (m == 0 ){ return ; } const int n = matrix[ 0 ].size(); int firstRow = 0 , firstCol = 0 ; for ( int j = 0 ; j < n; j++){ if (matrix[ 0 ][j] == 0 ){ firstRow = 1 ; break ; } } for ( int i = 0 ; i < m; i++){ if (matrix[i][ 0 ] == 0 ){ firstCol = 1 ; break ; } } for ( int i = 1 ; i < m; i++){ for ( int j = 1 ; j < n; j++){ if (matrix[i][j] == 0 ){ matrix[i][ 0 ] = 0 ; matrix[ 0 ][j] = 0 ; } } } for ( int i = 1 ;...