LeetCode(字节10日)-0716

这篇具有很好参考价值的文章主要介绍了LeetCode(字节10日)-0716。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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]

我们只要确定了 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(65)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(51)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(50)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(51)
  • 【python与数据结构】(leetcode算法预备知识)

    笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 1.数字类型: 整数(int):表示整数值,例如 1、-5、100。 浮点数(float):表示带有小数部分的数字,例如 3.14、-0.5、2.0。 复数(complex):表示实部和虚部的复数,例如 2+3j。 2.布尔类型(bool): 表示真(True)或假(

    2024年02月08日
    浏览(38)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(40)
  • 【算法与数据结构】518、LeetCode零钱兑换 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题的硬币是无数的,因此本题可以抽象成一个完全背包问题。完全背包和01背包的不同之处在于完全背包式从前往后遍历的。在本题的完全背包问题中,amount代表背包的最大重量

    2024年01月23日
    浏览(43)
  • 【算法与数据结构】63、LeetCode不同路径 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :参考【算法与数据结构】62、LeetCode不同路径的题目,可以发现本题仅仅是多了障碍物。我们还是用动态规划来做。有障碍物的地方无法到达,因此路径数量为0,只需要将障碍物位

    2024年02月02日
    浏览(53)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只

    2024年02月12日
    浏览(43)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题的思路很简单,本质上就是遍历每一个节点,然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做,参考这两篇文章,【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包