LC 121. 买卖股票的最佳时机

股票问题系列通解

LC 122. 买卖股票的最佳时机 II

股票问题系列通解

LC 123. 买卖股票的最佳时机 III

股票问题系列通解

LC 131. 分割回文串

  1. class Solution {
  3.     List<List<String>> results = new ArrayList<>();
  4.     List<String> result = new ArrayList<>();
  5.     String s;
  7.     public List<List<String>> partition(String s) {
  8.         this.s = s;
  9.         backtracking(0);
  10.         return results;
  11.     }
  13.     public void backtracking(int startIndex) {
  14.         if (startIndex == s.length()) {
  15.             results.add(new ArrayList<>(result));
  16.             return;
  17.         }
  19.         for (int i = startIndex; i < s.length(); i++) {
  20.             if (judge(s, startIndex, i)) {
  21.                 result.add(s.substring(startIndex, i + 1));
  22.             } else {
  23.                 continue;
  24.             }
  25.             backtracking(i + 1);
  26.             result.remove(result.size() - 1);
  27.         }
  28.     }
  30.     public boolean judge(String s, int l, int r) {
  32.         boolean empty = s.isEmpty();
  33.         if (empty == true) {
  34.             return true;
  35.         }
  37.         while (l <= r) {
  38.             if (s.charAt(l) != s.charAt(r)) {
  39.                 return false;
  40.             }
  41.             l++;
  42.             r--;
  43.         }
  44.         return true;
  45.     }
  46. }

LC 135. 分发糖果

回溯 + 备忘录的话，严重超内存

  1. class Solution {
  3.     int[] ratings;
  4.     int minSum = Integer.MAX_VALUE;
  6.     public int candy(int[] ratings) {
  7.         this.ratings = ratings;
  8.         backTracking(-1, 0, 0);
  9.         return minSum;
  10.     }
  12.     // num 表示下标为 index 的孩子的糖果数量
  13.     // sum 表示下标为 index 及之前的孩子的糖果总数量
  14.     public void backTracking(int index, int num, int sum) {
  15.         if (index == ratings.length - 1) {
  16.             if (sum < minSum) {
  17.                 minSum = sum;
  18.             }
  19.             return;
  20.         }
  22.         for (int i = 1; i <= ratings.length; i++) {
  23.             if (index >= 0) {
  24.                 int temp = ratings[index + 1] - ratings[index];
  25.                 if (temp > 0 && i <= num) {
  26.                     i = num + 1;
  27.                 } else if (temp < 0 && i >= num) {
  28.                     break;
  29.                 }
  30.             }
  31.             backTracking(index + 1, i, sum + i);
  32.         }
  33.     }
  34. }

LC 188. 买卖股票的最佳时机 IV

股票问题系列通解