致自己: 努力,去想去的地方。每日1题。
2020/9/20 20:30:21
- problem3 早餐组合
Start Time: 22:00:45
End Time: 22:41:41
time: 41min
Try: 3次
Status: AC
solve: 有趣的题目,之前做过,但思路记得不清楚了。一直以来对于取模的题目,很不熟练。测了三次用例后,一次提交error,才想到取模的问题。
staple记录主食价格,drinks记录饮料价格,数组numFood[i]先表示主食价格不超过i的种类。
priceStaple用来标识当前的饮料价格是否溢出,priceStaple>0的话, 则numFood[priceStaple]则表示当前的饮料与priceStaple构成的主食价格不超过x的种类数。
code:
class Solution {
public int breakfastNumber(int[] staple, int[] drinks, int x) {
int[] numFood = new int[x+1];
int ret = 0;
for(int i=0; i<staple.length; i++){
if(staple[i]<x){
numFood[staple[i]] =numFood[staple[i]]+1;
}
}
for(int i=2; i<x;i++){
numFood[i] += numFood[i-1];
}
int priceStaple = 0;
for(int i=0; i<drinks.length; i++){
priceStaple = x - drinks[i];
if(priceStaple<=0)
continue;
ret = (ret+numFood[priceStaple])%1000000007;
}
return (ret%1000000007);
}
}
- problem2 子集
Start Time: 20:32:02
End Time: 21:01:02
Try: 1
time: 29
Status:AC
solve: 很典型的回溯。看着熟悉,之前做过,又忘了。
code:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
//方法1:
backTrack(ret, new ArrayList<>(), nums, 0);
//方法2:
// ret.add(new ArrayList<>());
// List<Integer> tmp = new ArrayList<>();
// for(int i=0;i<nums.length;i++){
// int len = ret.size();
// for(int j=0;j<len;j++){
// tmp = new ArrayList<>(ret.get(j));
// tmp.add(nums[i]);
// ret.add(tmp);
// }
// }
return ret;
}
void backTrack(List<List<Integer>> ret, List<Integer> temp, int[] nums, int start){
ret.add(new ArrayList(temp));
for(int i=start;i<nums.length;i++){
temp.add(nums[i]);
backTrack(ret, temp, nums, i+1);
temp.remove(temp.size()-1);
}
}
}
2020/9/2 0:21:28
- problem1旋转图像
Start Time: 0:25:24
End Time: 0:50:10
Try:
time:
Status: 没做。
2020/9/1 23:10:12
- problem0预测赢家
Try:1
time:
Status:AC
模板备忘