当前位置: 首页>后端>正文

leetcode 算法题 Star

  • 一趟结束后能够确定一个元素的最终位置的排序方法有: 简单选择排序、快速排序、冒泡排序、堆排序

  • 稳定性定义:排序前后两个相等的数相对位置不变,则算法稳定。

  • 数据结构 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;
      }
      

https://www.xamrdz.com/backend/3mq1940028.html

相关文章: