102. 二叉树的层序遍历

  2. class Solution {
  3.     public List<List<Integer>> levelOrder(TreeNode root) {
  4.         List<List<Integer>> result = new ArrayList<>();
  5.         if(root==null){
  6.             return result;
  7.         }
  8.         Queue<TreeNode> queue = new LinkedList<>();
  9.         queue.add(root);
  10.         while (!queue.isEmpty()){
  11.             List<Integer> list = new ArrayList<>();
  12.             int size = queue.size();
  13.             for(int i=0;i<size;i++){
  14.                 TreeNode node = queue.poll();
  15.                 list.add(node.val);
  16.                 if(node.left!=null){
  17.                     queue.add(node.left);
  18.                 }
  19.                 if(node.right!=null){
  20.                     queue.add(node.right);
  21.                 }
  22.             }
  23.             result.add(list);
  24.         }
  25.         return result;
  26.     }
  27. }

121. 买卖股票的最佳时机

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices==null || prices.length==0){
  4.             return 0;
  5.         }
  6.         // 第i天股票状态为j时的最大利润：j=0表示不持有股票，j=1表示持有股票
  7.         int[][] dp = new int[prices.length][2];
  8.         // 不持有股票
  9.         dp[0][0] = 0;
  10.         // 持有股票
  11.         dp[0][1] = -prices[0];
  12.         for(int i=1;i<prices.length;i++){
  13.             // 不持有股票:上一天就不持有股票，上一天持有股票今天卖出
  14.             dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
  15.             // 持有股票:上一天就持有股票，上一天不持有股票今天买入（只能一次买入一次卖出，因此不是dp[i-1][0]-prices[i]）
  16.             dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
  17.         }
  18.         return dp[prices.length-1][0];
  19.     }
  20. }

20. 有效的括号