121. 买卖股票的最佳时机(简单)
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]<min)min = prices[i];
else if(prices[i]-min>res)res = prices[i]-min;
}
return res;
}
}
213. 打家劫舍 II(中等)
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n<=2)return Arrays.stream(nums).max().getAsInt();
int dp0[] = new int[n-1]; // 取 0
int dp[] = new int[n]; // 不取 0
dp0[0] = nums[0];
dp0[1] = Math.max(nums[0],nums[1]);
dp[1] = nums[1];
dp[2] = Math.max(nums[1],nums[2]);
for(int i=2;i<n-1;i++){
int j = i+1;
dp0[i] = Math.max(dp0[i-1],dp0[i-2]+nums[i]);
dp[j] = Math.max(dp[j-1],dp[j-2]+nums[j]);
}
return Math.max(dp0[n-2],dp[n-1]);
}
}
剑指 Offer 38. 字符串的排列(中等)
注意:需要使用 set 过滤掉重复集合,例如 aab 的全排列
//15:18 15:29 15:35
class Solution {
public Set<String> res;
public String[] permutation(String s) {
res = new HashSet<>();
int n = s.length();
boolean visit[] = new boolean[n];
dfs("",n,visit,s);
String ans[] = new String[res.size()];
List<String> res0 = res.stream().collect(Collectors.toList());
for(int i=0;i<res0.size();i++)
ans[i] = res0.get(i);
return ans;
}
public void dfs(String str,int cnt,boolean[] visit,String s){
if(cnt==0){
res.add(str.toString());
return ;
}
for(int i=0;i<s.length();i++){
if(visit[i])continue;
visit[i] = true;
dfs(str+s.charAt(i),cnt-1,visit,s);
visit[i] = false;
}
}
}
剑指 Offer II 010. 和为 k 的子数组(中等)
思路:乍一看是滑动窗口,但是发现可以是负数,窗口失效,则考虑双层 for 循环,之后看题解发现可以使用前缀和+哈希表优化
// 思路:双 for 枚举
class Solution {
public int subarraySum(int[] nums, int k) {
int left = 0,right = 0,sum = nums[0],cnt=0;
int n = nums.length;
for(int i=0;i<n;i++){
sum = nums[i];
if(sum==k)cnt++;
for(int j=i+1;j<n;j++){
sum+=nums[j];
if(sum==k)cnt++;
}
}
return cnt;
}
}
前缀和思路:pre 记录累加的值,那么k = pre[j] - pre[i]文章来源:https://www.toymoban.com/news/detail-578976.html
我们只要确定了 pre[j] 就可以确定pre[i] ,就剩下找一下有没有 pre[i]这个值,有几个文章来源地址https://www.toymoban.com/news/detail-578976.html
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> mp = new HashMap<>();
int cnt = 0, pre = 0;
mp.put(0,1);
for(int num:nums){
pre += num;
if(mp.containsKey(pre-k)){
cnt += mp.get(pre-k);
}
mp.put(pre,mp.getOrDefault(pre,0)+1);
}
return cnt;
}
}
到了这里,关于LeetCode(字节10日)-0716的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!