leetcode 算法题 Star

2020-03-26 本文已影响0人 Zak1

一趟结束后能够确定一个元素的最终位置的排序方法有：简单选择排序、快速排序、冒泡排序、堆排序
稳定性定义：排序前后两个相等的数相对位置不变，则算法稳定。

数据结构 search insert delete
数组 O(n)，有序数组折半查找是O(lgn) O(n) O(n)
双向链表 O(n) O(1) O(1)
排序二叉树 O(lgn) O(lgn) O(lgn)
哈希表（n与槽数m成正比）O(1) O(1) O(1)

快速排序算法:

public static int[] qsort(int arr[],int start,int end) {        
    int pivot = arr[start];        
    int i = start;        
    int j = end;        
    while (i<j) {            
        while ((i<j)&&(arr[j]>pivot)) {                
            j--;            
        }            
        while ((i<j)&&(arr[i]<pivot)) {                
            i++;            
        }            
        if ((arr[i]==arr[j])&&(i<j)) {                
            i++;            
        } else {                
            int temp = arr[i];                
            arr[i] = arr[j];                
            arr[j] = temp;            
        }        
    }        
    if (i-1>start) arr=qsort(arr,start,i-1);        
    if (j+1<end) arr=qsort(arr,j+1,end);        
    return arr;    
}

归并排序(左右分治)：

    /**
     * 归并排序
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    /**
     * 对lr范围内进行左右分别排序，使中点左右两边都有序
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void process(int[] arr, int l, int r) {
        if (l == r) return;
        int mid = (l + r) / 2;

        process(arr, l, mid);
        process(arr, mid + 1, r);
        merge(arr, l, r);
    }

    /**
     * 使用辅助数组对已经左右拍好序的数组进行整体排序
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void merge(int[] arr, int l, int r) {
        int[] helpArr = new int[r - l + 1];
        int mid = (r + l) / 2;
        int p = l;
        int q = mid + 1;
        int index = 0;
        while (p <= mid && q <= r) {
            helpArr[index++] = arr[p] < arr[q] ? arr[p++] : arr[q++];
        }
        //左右一定有一个越界
        while (p <= mid) {
            helpArr[index++] = arr[p++];
        }
        while (q <= r) {
            helpArr[index++] = arr[q++];
        }
        if (helpArr.length >= 0) System.arraycopy(helpArr, 0, arr, l, helpArr.length);
    }

归并排序的*Master公式=T(N)=a*T(N/b)+O(N^d)==T(N)=2T(N/2)+O(N) **

大顶堆：(根节点的关键字既大于等于左子树的关键字值，同时也大于等于右子树的关键字值)
小顶堆：(根结点的键值是所有堆结点键值中最小者)

典例

4的幂：

这个题和“2的幂”“3的幂”一样，有不用循环和递归就能直接判断的方法，同样十分巧妙，属于二进制/位运算的应用。
4的幂的数，都是这样的数：100、10000、1000000……（4、16、64）
观察规律，可以发现 4的幂 需要满足以下条件：
最高位是 1，其余都为 0；
最高位的 1 应该在奇数位上，比如：100 的 1 在 第三位上；
那么对应的判断方法为：
用 num & (num-1) 可以判断条件1，比如：100(4) & 011(3) == 0，结果为 0 说明符合条件1；
是否在奇数位可以用 0xaaaaaaaa 判断，16 进制的 a 是 1010，比如：0100(4) & 1010(a) == 0，结果为 0 说明最高位 1 在奇数位上；

 public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && ((n & 0x55555555) == n);
        
        //        if (n<0) return false; 
        //        if ((n&(n-1))!=0) return false; 判断是否位2的幂次方
        //        return (n & 0x55555555) == n;   判断1是否在奇数位上
        
    }

两个数相乘：

    public static String multiply2(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] res = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int LowPos = i + j + 1;
                int highPos = i + j;
                int temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + res[LowPos];
                res[LowPos] = (temp) % 10;
                res[highPos] += temp / 10; //这里高位不要取mod
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i : res) {
            if (!(sb.length() == 0) && i == 0) sb.append(i);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

二叉树的公共祖先：
- 最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
  
  例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
  
  [图片上传失败...(image-2faa57-1585194160478)]

class Solution {
    /*
    算法思想,当递归到的节点为p1或p2时候,则将该节点向上传递,
    使其父节点变成其本身,如果一个节点下方没有p1/p2,则向上传递null,使父节点为null,
    当左右节点分别是p1,p2时则说明该节点是目标节点，向上传递,
    该目标节点对应的兄弟节点经过递归后一定为null(因为兄弟节点的子节点中不存在p1/p2只能向上传递null),    最终目标顶点传递至根节点。
    */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p1, TreeNode p2) {
      if (root == null || root == p1 || root == p2) return root;
        TreeNode left = lowestCommonAncestor(root.left, p1, p2);
        TreeNode right = lowestCommonAncestor(root.right, p1, p2);
        if (left == null && right == null) return null;
        if (left == null || right == null) return left == null ? right : left;
        return root;
    }
}

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))",
"(()())",
"(())()",
"()(())",
"()()()"]

 public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generate(res, "", 0, 0, n);
        return res;
    }
  
    //count1统计“(”的个数，count2统计“)”的个数
    public void generate(List<String> res, String ans, int count1, int count2, int n) {
        if (count1 > n || count2 > n) return;
        if (count1 == n && count2 == n) res.add(ans);
        /*核心点: count1>=count2 ,
        从左往右添加,只有满足左边括号数量>=右边括号时候,
        才能够满足题意,否则会出现括号不匹配的情况
        */
        if (count1 >= count2) {
            generate(res, ans + "(", count1 + 1, count2, n);
            generate(res, ans + ")", count1, count2 + 1, n);
        }
    }

BFS:

[图片上传失败...(image-26fb97-1585194160478)]

# 广度遍历
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}


def BFS(graph, s):
    queue = []  # 使用动态数组作队列
    queue.append(s)
    seen = set()
    while (len(queue) > 0):
        vertex = queue.pop(0) # 每次取队列中的第一个再进行添加
        seen.add(s)
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)


BFS(graph, "A")

DFS

# 深度遍历
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}


def DFS(graph, s):
    queue = []  # 使用动态数组作栈
    queue.append(s)
    seen = set()
    seen.add(s)
    parent = {s: None} # <子节点:父节点>
    while (len(queue) > 0):
        vertex = queue.pop()
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                parent[w] = vertex
                queue.append(w)
                seen.add(w)
        print(vertex)
    return parent

if __name__ == "__main__":
    print (DFS(graph,"A"))

使用BFS求最短路径(Dijkstra)：

[图片上传失败...(image-a1078d-1585194160478)]

import heapq # 权限比队列
import math
graph = {
    "A": {"B": 5, "C": 1},
    "B": {"A": 5, "C": 2},
    "C": {"A": 1, "B": 2, "D": 4},
    "D": {"B": 1, "C": 4, "E": 3, "F": 6},
    "E": {"C": 8, "D": 3},
    "F": {"D": 6}
}


def init_distance(graph, s):
    distance = {s: 0}
    for vertex in graph.keys():
        if vertex != s:
            distance[vertex] = math.inf
    return distance


def dijkstra(graph, s):
    pqueue = []  # prorityqueue 具有权重比的队列，权重高的排前面
    heapq.heappush(pqueue, (0, s))
    seen = set()
    parent = {s: None}
    distance = init_distance(graph, s)

    while(len(pqueue) > 0):
        pair = heapq.heappop(pqueue)
        dist = pair[0]  # 取出来的点到s的距离
        vertex = pair[1]
        seen.add(vertex)

        nodes = graph[vertex].keys()
        for w in nodes:
            if w not in seen:
                if dist+graph[vertex][w] < distance[w]: 
                    distance[w] = dist+graph[vertex][w]
                    heapq.heappush(pqueue, (dist+graph[vertex][w], w))
                    parent[w] = vertex
    return parent, distance


parent, distance = dijkstra(graph, "A")
print(parent)
print(distance)

两个数之间的所有数相与：

public static int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while (n != m) {
            n >>= 1;
            m >>= 1;
            count++;
        }
        return n << count;
    }

最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

//dp[i][j]为以[i][j]为右下角坐标的最长正方形边长
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix==null||matrix.length==0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1' && (i == 0 || j == 0)) {
                    dp[i][j] = 1;
                }else if (matrix[i][j] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
                res = Math.max(dp[i][j] * dp[i][j], res);
            }
        }
        return res;
    }
}

LeetCode 395题：至少有K个重复字符的最长子串

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:
输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

题解(递归+分治)：

class Solution {
      public int longestSubstring(String s, int k) {
          if (s.length() < k) return 0;
          return countLongestSubstring(s.toCharArray(), 0, s.length() - 1, k);
      }
      private int countLongestSubstring(char[] chars, int l, int r, int k) {
          int[] count = new int[26];
          for (int i = l; i <= r; i++) {
              count[chars[i] - 'a']++;
          }
          //使得左右指针所在位置的字符满足条件(两指针之间仍然可能存在不满足条件的字符)
          while (r - l + 1 >= k && count[chars[l] - 'a'] < k) l++;
          while (r - l + 1 >= k && count[chars[r] - 'a'] < k) r--;
            //当筛选完毕后如果长度不满足K则返回0
          if (r - l + 1 < k) return 0;
         
          //对初筛满足条件的子串进行遍历，出现不满足条件的字符，以字符为分割，左右继续递归查询，直到满足所有的count[chars[i] - 'a']都>=K则 返回  r - l + 1
          for (int i = l; i < r; i++) {
              if (count[chars[i] - 'a'] < k) {
                  return Math.max(countLongestSubstring(chars, l, i - 1, k), countLongestSubstring(chars, i + 1, r, k));
              }
          }
          return r - l + 1;
      }
  }

计算完全二叉树的节点个数并且且时间复杂度小于O(N)
[图片上传失败...(image-86a6b8-1585194160478)]

lcs 最长公共子串：

[图片上传失败...(image-9fb531-1585194160478)]

//lrc 最长公共子串
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        for (int i = 0; i < text1.length(); i++) {
            for (int j = 0; j < text2.length(); j++) {
                boolean b = text1.charAt(i) == text2.charAt(j);
                if (i != 0 && j != 0) {
                    if (b) dp[i][j] = dp[i - 1][j - 1] + 1;
                    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } else {
                    if (b) dp[i][j] = 1;
                    else {
                        if (i == 0 && j == 0) continue;
                        if (i == 0) dp[i][j] = dp[i][j - 1];
                        else dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[text1.length() - 1][text2.length() - 1];
    }

更优解法：

 public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }

LIS 最长上升子序列：

 //给定一个无序的整数数组，找到其中最长上升子序列的长度。
 
 class Solution {
    public int lengthOfLIS(int[] nums) {
         if (nums.length == 0) return 0;
         int[] dp = new int[nums.length];
         dp[0] = 1;
         for (int i = 1; i < nums.length; i++) {
             int tempMax = 0;
             for (int j = i - 1; j >= 0; j--) {
                 if (nums[i] > nums[j]) {
                     tempMax = Math.max(tempMax, dp[j]);
                 }
             }
             dp[i] = tempMax + 1;
         }
         int res = 0;
         for (int i : dp) {
             if (i > res) res = i;
         }
         return res;
     }
 }

lcs 712 两个字符串的最小ascll删除和：

 //最大公共子串 且 要求这些公共子串的 ascii 值最大。    
 public int minimumDeleteSum(String s1, String s2) {
         int sum = 0;
         for (int i = 0; i < s1.length(); i++) sum += s1.charAt(i);
         for (int i = 0; i < s2.length(); i++) sum += s2.charAt(i);
         if (s1.length() == 0 || s2.length() == 0) return sum;
         int[][] dp = new int[s1.length() + 1][s2.length() + 1];
         int max_lcs_sum = 0;
         for (int i = 1; i <= s1.length(); i++) {
             for (int j = 1; j <= s2.length(); j++) {
                 if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                     dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                 } else {
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                 }
                 max_lcs_sum = Math.max(dp[i][j], max_lcs_sum);
             }
         }
         return sum - 2 * max_lcs_sum;
     }

279 完全平方数:

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

        //最小值公式f(n)=常数i+j*j (需要满足条件i-j*j>=0,不能越界)
    //而f(j*j)=1
    //所以f(n)=f(i)+f(j*j)=f(i)+1
    //bfs遍历所有可能的i j组合
    //取每次遍历的最小值情况
    //dp[i]=Math.min(dp[i],dp[i-j*j]+dp[j*j]);
    
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            //默认的每个数都是由全部1组成
            dp[i] = i;
            //bfs操作
            for (int j = 0; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

376,摆动序列（线性DP）

    
public int wiggleMaxLength(int[] nums) {
        if(nums.length<2) return nums.length;
        int low = 1;
        int high = 1;
        for (int i = 1; i < nums.length; i++) {
            //起始位高低位都为1.
            //保证了在连续上升/下降的情况下 high/low 不会重复递增，
            //在上升情况中，只要没有发生坡度中断，则high对应的low不会发生改变。那么high位就不会发生改变。
            if (nums[i] > nums[i - 1]) high = low+1;
            if (nums[i] < nums[i - 1]) low  = high+1;
        }
        return Math.max(low, high);
    }

汉诺塔问题(每次移动顶部的，并且不能大压小)

public void hanoti(int N,String from,String to,String help){
    if(N==1) System.out.println("Move 1 from" + from + "to" +to );
    else{
        hanoti(N-1,from,help,to);
        System.out.println("Move"+N+"from" + from + "to" +to );
        hanoti(N-1,help,to,from);
    }
}

502题IPO

public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        IpoNode[] ipoNodes = new IpoNode[Profits.length];
        PriorityQueue<IpoNode> MinCostHeap = new PriorityQueue<>(comparingInt(o -> o.cost));
        PriorityQueue<IpoNode> MaxProfitHeap = new PriorityQueue<>(comparingInt(o -> -o.profit));
        for (int i = 0; i < ipoNodes.length; i++) {
            ipoNodes[i] = new IpoNode(Capital[i], Profits[i]);
            MinCostHeap.add(ipoNodes[i]);
        }
        for (int i = 0; i < k; i++) {
            while (MinCostHeap.size() > 0 && MinCostHeap.peek().cost <= W) MaxProfitHeap.add(MinCostHeap.poll());
            if (MaxProfitHeap.size() > 0) W += MaxProfitHeap.poll().profit;
        }
        return W;
    }

class IpoNode {
    public int cost;
    public int profit;

    public IpoNode(int cost, int profit) {
        this.cost = cost;
        this.profit = profit;
    }
}

1277 统计全为1的正方形子矩阵：

核心在于加上每次的边长
因为当出现长的边长,说明以该右下角为正方形几个新的小正方形也同时出现了,
比如3, res+3意味着加了边长为3和边长为2和边长为1这三个正方形。

class Solution {
    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && (i == 0 || j == 0)) {
                    dp[i][j] = 1;
                } else if (matrix[i][j] == 1) {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
                //直接将每一个正方形的边长加上来
                res += dp[i][j];
            }
        }
        return res;
    }
}

894,所有可能的满二叉树

    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        if(N % 2 == 0){
            return res;
        }
        if(N == 1){
            res.add(new TreeNode(0));
            return res;
        }
        //对每个奇数
        //一个奇数拆成两个奇数+1
        for(int i = 1; i < N; i += 2){
            List<TreeNode> lt = allPossibleFBT(i);
            List<TreeNode> rt = allPossibleFBT(N - 1 - i);
            //每种可能性都加进来
            for(TreeNode l : lt){
                for(TreeNode r : rt){
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }

1079 活字印刷：

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

分而治之

23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

 public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        if (lists.length == 2) return mergeTwoListNode(lists[0], lists[1]);
        int mid = lists.length / 2;
        ListNode[] leftArr = new ListNode[mid];
        ListNode[] rightArr = new ListNode[lists.length - mid];
        for (int i = 0; i < lists.length; i++) {
            if (i < mid) {
                leftArr[i] = lists[i];
            } else {
                rightArr[i - mid] = lists[i];
            }
        }
        //左右分治，最终变成两个listNode合并
        return mergeTwoListNode(mergeKLists(leftArr), mergeKLists(rightArr));
    }
    //递归合并两个ListNode
    public ListNode mergeTwoListNode(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode cur;
        if (l1.val < l2.val) {
            cur = l1;
            cur.next = mergeTwoListNode(l1.next, l2);
        } else {
            cur = l2;
            cur.next = mergeTwoListNode(l1, l2.next);
        }
        return cur;
    }

不用加减乘除做加法：
- a+b==> (a&b)<<1+a^b
- (异或就相当于没有进位的加法，而&就是寻找进位，<<1左移动1是表明与的值为进位在二进制加法中向前一位)
- ```
  //当a==0的时候说明没有进位
 public int add(int a, int b) {
         if(a==0) return b;
         return add((a&b)<<1,b^a);
     }
```

动态规划

lc 264 丑数三指针：

    public int nthUglyNumber(int n) {
        if (n == 0) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        int l_2 = 0, l_3 = 0, l_5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[l_2] * 2, Math.min(dp[l_3] * 3, dp[l_5] * 5));
            if (dp[i] == dp[l_2] * 2) l_2++;
            if (dp[i] == dp[l_3] * 3) l_3++;
            if (dp[i] == dp[l_5] * 5) l_5++;
        }
        return dp[n - 1];
    }

lc 309 最佳买卖股票世纪含冷冻期：

# sold rest hold 分别表示在该price 所持有的收益
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sold=0
        rest=0
        hold=-2147383648
        for price in prices:
            pre_sold=sold
            # 今天卖出的的收益
            sold=hold+price
            # 当天是否买入，前一天的持有与之前的冷冻期收益减掉price
            hold = max(hold, rest - price);
            #当天冷冻,取之前的冷冻的那天值和前一天pre_sold的比较值,保证了冷冻一定是在上次销售之后
            rest = max(rest, pre_sold);
        
        return max(sold,rest)

lc123 最佳买卖股票，次数限制：

   public int maxProfit(int[] prices) {
     if (prices == null || prices.length < 2) return 0;
     int[][][] dp = new int[prices.length+1][3][2];
     //base case
     for (int i = 0; i < 3; i++) {
         dp[0][i][0] = 0;
         dp[0][i][1] = Integer.MIN_VALUE;
     }
     for (int i = 1; i <= prices.length; i++) {
         for (int j = 1; j < 3; j++) {
             dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i-1]);
             dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j-1][0] - prices[i-1]);
         }
     }
     return dp[prices.length][2][0];
 }

lc309 股票买卖，含冷冻期：

    public int maxProfit(int[] prices) {
      if(prices==null||prices.length==0) return 0;
      int[][] dp = new int[prices.length][2];
      dp[0][0] = 0;
      dp[0][1] = -prices[0];
      for (int i = 1; i < prices.length; i++) {
          if (i == 1) dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
                                                                            //-2表示相邻那天不能交易
          else dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
          dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      }
      return dp[prices.length - 1][0];
  }

迭代实现中序遍历：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
    }
    return res;
}

leetcode 算法题 Star

典例

分而治之

动态规划

猜你喜欢

热点阅读