2809. 使數組和小于等于 x 的最少時間

思路：

1. 獲取兩個列表的長度n，并初始化一個二維數組f，用于存儲最優解。
2. 定義一個二維數組nums，用于存儲輸入的兩個列表中的元素，并按照第二列元素進行排序。
3. 使用動態規劃的方法，通過遍歷nums數組，計算最優解。其中，f[i][j]表示將前i個元素分配到j個集合中時的最大總和。通過比較f[i-1][j]和f[i-1][j-1]+a+b*j的大小，更新f[i][j]。
4. 計算兩個列表中所有元素的和，分別存儲在s1和s2中。
5. 遍歷0至n的范圍，判斷是否滿足條件s1 + s2 * j - f[n][j] <= x，若滿足則返回j。
6. 若沒有滿足條件的j值，則返回-1

class Solution {public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {int n = nums1.size();int[][] f = new int[n + 1][n + 1]; // 定義二維數組f，用于存儲最優解int[][] nums = new int[n][0]; // 定義二維數組nums，用于存儲輸入的兩個列表中的元素for (int i = 0; i < n; ++i) {nums[i] = new int[] {nums1.get(i), nums2.get(i)}; // 將輸入的兩個列表中的元素按照相同的索引放入nums數組中}Arrays.sort(nums, Comparator.comparingInt(a -> a[1])); // 根據nums數組中第二列的元素進行排序for (int i = 1; i <= n; ++i) {for (int j = 0; j <= n; ++j) {f[i][j] = f[i - 1][j]; // 初始化f[i][j]為f[i-1][j]if (j > 0) { // 當j大于0時，進行以下操作int a = nums[i - 1][0], b = nums[i - 1][1];f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + a + b * j); // 更新f[i][j]，取當前值與f[i-1][j-1]+a+b*j的較大值}}}int s1 = 0, s2 = 0;for (int v : nums1) {s1 += v; // 計算nums1列表中所有元素的和，存儲在s1中}for (int v : nums2) {s2 += v; // 計算nums2列表中所有元素的和，存儲在s2中}for (int j = 0; j <= n; ++j) {if (s1 + s2 * j - f[n][j] <= x) { // 判斷是否滿足條件 s1 + s2 * j - f[n][j] <= xreturn j; // 返回滿足條件的j值}}return -1; // 若沒有滿足條件的j值，則返回-1}
}

2788. 按分隔符拆分字符串

思路：

1. 對于每個單詞，使用一個可變字符串 StringBuilder 來構建拆分后的單詞。初始時，可變字符串為空。
2. 遍歷每個單詞的每個字符，如果遇到指定的分隔符，就將可變字符串中的字符構成一個新的單詞，并將其添加到結果列表中。然后清空可變字符串，準備構建下一個單詞。
3. 如果遇到的不是分隔符，則將當前字符添加到可變字符串中。
4. 最后，如果可變字符串非空，則說明最后一個單詞還沒有添加到結果列表中，因此需要將其添加到結果列表中。
5. 返回拆分后的結果列表。

//2788. 按分隔符拆分字符串public List<String> splitWordsBySeparator(List<String> words, char separator) {// 創建一個新的字符串列表，用于存儲拆分后的結果List<String> res = new ArrayList<>();// 遍歷原始字符串列表中的每個單詞for (String word : words) {// 創建一個可變字符串，用于構建拆分后的單詞StringBuilder sb = new StringBuilder();// 獲取當前單詞的長度int length = word.length();// 遍歷當前單詞的每個字符for (int i = 0; i < length; i++) {// 獲取當前字符char c = word.charAt(i);// 如果當前字符是分隔符if (c == separator) {// 如果可變字符串不為空，則將其添加到結果列表中，并清空可變字符串if (sb.length() > 0) {res.add(sb.toString());sb.setLength(0);}} else {// 如果當前字符不是分隔符，則將其添加到可變字符串中sb.append(c);}}// 如果可變字符串不為空，則將其添加到結果列表中if (sb.length() > 0) {res.add(sb.toString());}}// 返回拆分后的字符串列表return res;}

410. 分割數組的最大值

思路：二分查找+貪心

利用二分查找法和貪心算法來求解將數組分割為m個非空連續子數組，使得每個子數組的和的最大值最小

1. 首先，我們需要確定二分查找的左右邊界。左邊界left初始化為數組中的最大值，右邊界right初始化為數組所有元素的總和。
2. 然后，我們使用二分查找法在左右邊界之間查找滿足條件的最小子數組和。
3. 在每次迭代中，我們計算中間值mid，然后調用check函數判斷以mid為目標值是否能將數組nums分割成不超過m個子數組。如果能，則將右邊界更新為mid，因為我們要尋找更小的子數組和。如果不能，則將左邊界更新為mid + 1，因為mid不滿足條件，我們需要嘗試更大的值。
4. 當左邊界left不小于右邊界right時，二分查找結束，最終的結果即為左邊界的值。
5. 最后，返回左邊界的值作為最小子數組和。

public int splitArray(int[] nums, int m) {int left = 0, right = 0;// 初始化左右邊界for (int i = 0; i < nums.length; i++) {right += nums[i];if (left < nums[i]) {left = nums[i];}}// 使用二分查找法尋找最小的子數組和while (left < right) {int mid = (right - left) / 2 + left;if (check(nums, mid, m)) {right = mid;} else {left = mid + 1;}}// 返回最小的子數組和return left;
}public boolean check(int[] nums, int x, int m) {int sum = 0;int cnt = 1;// 統計滿足條件的子數組個數for (int i = 0; i < nums.length; i++) {if (sum + nums[i] > x) {// 當前元素加上之后超過了目標值，需要分割出一個新的子數組cnt++;sum = nums[i];} else {// 將當前元素加入到當前子數組中sum += nums[i];}}// 判斷最終的子數組個數是否小于等于目標個數return cnt <= m;
}

在check函數中，遍歷數組nums，累加元素值到sum變量中，如果累加和超過了目標值x，則說明當前子數組和超過了目標值，需要分割出一個新的子數組，同時將子數組計數cnt增加1，并將sum重置為當前元素值。如果累加和未超過目標值，則將當前元素加入到當前子數組中。

最后，判斷最終的子數組個數cnt是否小于等于目標個數m，如果是則返回true，否則返回false。

通過不斷調整二分查找的左右邊界，可以找到滿足條件的最小子數組和

點擊移步博客主頁，歡迎光臨~