100121. Find Words Containing Character
给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。
请你返回一个 下标数组 ，表示下标在数组中对应的单词包含字符 x 。
注意 ，返回的数组可以是 任意 顺序。
测试样例：
输入：words = ["leet","code"], x = "e"
输出：[0,1]
解释：
"e" 在两个单词中都出现了："leet" 和 "code" 。所以我们返回下标 0 和 1 。
解答：暴力寻找。
class Solution {
public List<Integer> findWordsContaining(String[] words, char x) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < words.length; ++i) {
if (isContain(words[i], x)) {
res.add(i);
}
}
return res;
}
private boolean isContain(String w, char c) {
for (int i = 0; i < w.length(); ++i) {
if (w.charAt(i) == c) return true;
}
return false;
}
}100138. Maximize Area of Square Hole in Grid
给你一个网格图，由 n + 2 条 横线段 和 m + 2 条 竖线段 组成，一开始所有区域均为 1 x 1 的单元格。
所有线段的编号从 1 开始。
给你两个整数 n 和 m 。
同时给你两个整数数组 hBars 和 vBars 。
- hBars 包含区间 [2, n + 1] 内 互不相同 的横线段编号。
- vBars 包含 [2, m + 1] 内 互不相同的 竖线段编号。
如果满足以下条件之一，你可以 移除 两个数组中的部分线段：
- 如果移除的是横线段，它必须是 hBars 中的值。
- 如果移除的是竖线段，它必须是 vBars 中的值。
请你返回移除一些线段后（可能不移除任何线段），剩余网格图中 最大正方形 空洞的面积，正方形空洞的意思是正方形 内部 不含有任何线段。
测试样例：
输入：n = 2, m = 1, hBars = [2,3], vBars = [2]
输出：4
解释：
左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2,3] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。
解答：这题纯粹恶心人，题目又臭又长。注意是一开始段都在，只有数组内的段可以去除。排序寻找横竖最长空档，然后取min平方。
class Solution {
public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
int n1 = max(n, hBars), n2 = max(m, vBars);
int res = Math.min(n1, n2);
return res * res;
}
private int max(int n, int[] bars) {
Arrays.sort(bars);
int res = 0;
for (int i = 0; i < bars.length; ++i) {
int st = bars[i] - 1;
int tmp = bars[i];
for (int j = i + 1; j < bars.length; ++j) {
if (bars[j] == bars[j - 1] + 1) {
tmp = bars[j];
} else {
break;
}
}
res = Math.max(res, tmp + 1 - st);
}
return res;
}
}100133. Minimum Number of Coins for Fruits
你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动：
- 如果你花费 price[i] 购买了水果 i ，那么接下来的 i 个水果你都可以免费获得。
注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。
请你返回获得所有水果所需要的 最少 金币数。
测试样例
输入：prices = [3,1,2]
输出：4
解释：
你可以按如下方法获得所有水果：
- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。
- 免费获得水果 3 。
注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。购买所有水果需要最少花费 4 个金币。
解答：标准动态规划，范围也很少。暴力运算。
class Solution {
public int minimumCoins(int[] prices) {
int len = prices.length;
long[] dp = new long[len + 1];
for (int i = prices.length - 1; i >= 0; --i) {
int jump = i + 2, t = Math.min(prices.length, jump + i);
dp[i] = Integer.MAX_VALUE;
for (int j = i + 1; j <= t; ++j) {
dp[i] = Math.min(dp[i], dp[j] + prices[i]);
}
}
return (int)dp[0];
}
}100135. Find Maximum Non-decreasing Array Length
给你一个下标从 0 开始的整数数组 nums 。
你可以执行任意次操作。每次操作中，你需要选择一个 子数组 ，并将这个子数组用它所包含元素的 和 替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。
请你返回执行任意次操作以后，可以得到的 最长非递减 数组的长度。
子数组 指的是一个数组中一段连续 非空 的元素序列。
测试样例
输入：nums = [5,2,2]
输出：1
解释：
这个长度为 3 的数组不是非递减的。
我们有 2 种方案使数组长度为 2 。
第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。
第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。
这两种方案中，数组最后都不是 非递减 的，所以不是可行的答案。
如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。
所以答案为 1 。
解答：不会做，先搬运一个大佬解法。
class Solution {
public int findMaximumLength(int[] nums) {
int len = nums.length;
int ret=0;
long[] sum = new long[len + 1];
for (int i = 0; i < len; ++i){
sum[i + 1] = sum[i] + nums[i];
}
long[] mSum=new long[len+1];
mSum[0] = nums[0];
int t=0;
int[] choice = new int[len];
choice[0]=-1;
int[] si= new int[len+1];
long[] sv= new long[len+1];
si[0] = -1; sv[0] = 0;
int cs=0;int tt=0;
for (int i=0;i<len;i++){
while (t<=cs&&sum[i+1]>=sv[t]){
t++;
}
t--;
mSum[i]=sum[i+1]-sum[si[t]+1];
choice[i]=si[t];
long nv=sum[i+1]+mSum[i];
while (nv<sv[cs]){
cs--;
}
cs++;sv[cs]=nv;si[cs]=i;
// System.out.println(i+" "+t+" "+mSum[i]);
}
t= len - 1;
while (t!=-1){
ret++;t=choice[t];
}
return ret;
}
}