代码随想录算法训练营第31天|● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

文章目录

  • 理论基础
  • 分发饼干
    • 思路:
    • 代码:
  • 摆动序列
    • 思路一 贪心算法:
      • 代码:
    • 思路二:动态规划(想不清楚)
      • 代码:
  • 最大子序和
    • 思路:
      • 代码:

理论基础

贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。

不用花心思去研究其规律, 没有思路就立刻看题解。

基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。

学完贪心之后再去看动态规划,就会了解贪心和动规的区别

分发饼干

添加链接描述
在这里插入图片描述

思路:

在这里插入图片描述

从代码中可以看出我用了一个 index 来控制饼干数组的遍历,遍历饼干并没有再起一个 for 循环,而是采用自减的方式,这也是常用的技巧。

有的同学看到要遍历两个数组,就想到用两个 for 循环,那样逻辑其实就复杂了。

代码:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = s.length-1;//饼干的下标
        int res=0;
        for(int i=g.length-1;i>=0;i--){// 循环判断
            if(start>=0&&s[start]>=g[i]){
                res++;
                start--;
            }
        }
        return res;
    }
}

摆动序列

在这里插入图片描述

思路一 贪心算法:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

代码:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int count = 1;//默认最右边是峰值
        for (int i = 0; i < nums.length-1; i++) {
            //得到当前差值
            curDiff = nums[i+1] - nums[i];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

思路二:动态规划(想不清楚)

在这里插入图片描述

代码:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        int dp[][] = new int[nums.length][2];

        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.length; i++){
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;

            for (int j = 0; j < i; j++){
                if (nums[j] > nums[i]){
                    // i 是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]){
                    // i 是波峰
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }

最大子序和

在这里插入图片描述

思路:

在这里插入图片描述

在这里插入图片描述

代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for(int i=0;i<nums.length;i++){
            count+=nums[i];//?来判断是否结果是负数
            sum=Math.max(sum,count);// 取区间累计的最大值(相当于不断确定最大子序终止位置)
            if(count<0){//重置起始位置
                count=0;
            }
        }
        return sum;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/390275.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Android Jetpack Compose 沉浸式状态栏的实现

目录 概述效果展示代码实现总结 概述 说到沉浸式状态栏&#xff0c;很多小伙伴可能不太熟悉&#xff0c;其实让Android的状态栏的颜色和APP的主题颜色相同&#xff0c;给人感觉状态栏和APP就是一体的。沉浸式的状态栏让页面看起来更舒服&#xff0c;实现沉浸式状态栏也很简单&…

精品jsp+ssm基于Java的疫苗接种管理系统

《[含文档PPT源码等]精品jspssm基于Java的疫苗接种管理系统[包运行成功]》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功&#xff01; 使用技术&#xff1a; 开发语言&#xff1a;Java 框架&#xff1a;ssm 技术&#xff1a;JSP JDK版…

2024年!PyCharm快捷键大全

收藏&#xff01;PyCharm快捷键大全 工欲善其事必先利其器&#xff0c;PyCharm 是最popular的Python开发工具&#xff0c;它提供的功能非常强大&#xff0c;是构建大型项目的理想工具之一&#xff0c;如果能挖掘出里面实用技巧&#xff0c;能带来事半功倍的效果。 本文主要向大…

PLC_博图系列☞FBD

PLC_博图系列☞FBD 文章目录 PLC_博图系列☞FBD背景介绍FBD优势局限性 FBD 元素 关键字&#xff1a; PLC、 西门子、 博图、 Siemens 、 FBD 背景介绍 这是一篇关于PLC编程的文章&#xff0c;特别是关于西门子的博图软件。我并不是专业的PLC编程人员&#xff0c;也不懂电路…

Linux程序地址空间

引言 以下为示意草图 下面以代码验证一下&#xff1a; 1 #include<stdio.h> 2 #include<stdlib.h>3 …

C++数据结构与算法——双指针法

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月&#xff0c;主要利用代码随想录来学习&#xff0c;刷题使用力扣网站&#xff0c;不定时更…

Flutter 动画(显式动画、隐式动画、Hero动画、页面转场动画、交错动画)

前言 当前案例 Flutter SDK版本&#xff1a;3.13.2 显式动画 Tween({this.begin,this.end}) 两个构造参数&#xff0c;分别是 开始值 和 结束值&#xff0c;根据这两个值&#xff0c;提供了控制动画的方法&#xff0c;以下是常用的&#xff1b; controller.forward() : 向前…

【开源】在线办公系统 JAVA+Vue.js+SpringBoot+MySQL

目录 1 功能模块1.1 员工管理模块1.2 邮件管理模块1.3 人事档案模块1.4 公告管理模块 2 系统展示3 核心代码3.1 查询用户3.2 导入用户3.3 新增公告 4 免责声明 本文项目编号&#xff1a; T 001 。 \color{red}{本文项目编号&#xff1a;T001。} 本文项目编号&#xff1a;T001。…

前端vue3实现本地及在线文件预览(含pdf/txt/mp3/mp4/docx/xlsx/pptx)

一、仅需实现在线预览&#xff0c;且文件地址公网可访问 &#xff08;一&#xff09;微软office免费预览&#xff08;推荐&#xff09; 支持doc/docx/xls/xlsx/ppt/pptx等多种office文件格式的免费预览 //示例代码//​在https://view.officeapps.live.com/op/view.aspx?src…

骨传导耳机是什么?如何选择骨传导耳机不会踩雷?

骨传导耳机是利用骨传导技术研发而成一种新型蓝牙耳机&#xff0c;其传声方式很独特&#xff0c;不通过空气传导&#xff0c;而是通过人体骨骼来传递声音。 详细传声原理请看下图&#xff1a; 随着骨传导耳机逐渐热门&#xff0c;如何选购耳机成为了问题&#xff0c;下面跟大家…

计算机设计大赛 深度学习YOLO图像视频足球和人体检测 - python opencv

文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络4 Yolov5算法5 数据集6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习YOLO图像视频足球和人体检测 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非…

1_opencv3环境搭建与测试

之前2020年5月写过一次&#xff0c;时隔3年多&#xff0c;有机会再重新写一次。相比之前&#xff0c;应该是有一点儿进步的。之前是使用默认安装路径&#xff0c;所以无需配置共享库的搜索路径。这次是自定义安装路径&#xff0c;略有区别。随着写程序的时间增长&#xff0c;编…

Dockerfile 常用指令

1、FROM 指定base镜像。 2、Docker history 显示镜像的构建历史&#xff0c;也就是Dockerfile的执行过程。 Missing 表示无法获取IMAGE ID&#xff0c;通常从Docker Hub下载的镜像会有这个问题。 3、调试Dockerfile&#xff0c;使用sudo docker run -it XXXX&#xff0c;XXXX…

036-安全开发-JavaEE应用第三方组件Log4j日志FastJson序列化JNDI注入

036-安全开发-JavaEE应用&第三方组件&Log4j日志&FastJson序列化&JNDI注入 #知识点&#xff1a; 1、JavaEE-组件安全-Log4j 2、JavaEE-组件安全-Fastjson 3、JavaEE-基本了解-JNDI-API 演示案例&#xff1a; ➢Java-三方组件-Log4J&JNDI ➢Java-三方组件-Fa…

【开源】SpringBoot框架开发大学生相亲网站

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询会员4.2 查询相亲大会4.3 新增留言4.4 查询新闻4.5 新增新闻 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的大学生相亲网站&#xff0c;包含了会员管理模块、新闻管…

炬芯ATS2819 soundbar音响系统开发完全手册

加我微信hezkz17,可申请加入数字音频系统研究开发交流答疑群,赠送音频项目核心开发资料 ATS2819音响系统开发完全手册 1 硬件原理实现 图1 硬件原理框图 2 SOC ATS2819介绍 3 E800 板子项目实物…

黑群晖一键修复:root、AME、DTS、转码、CPU型号等

食用方法&#xff1a;SSH连接群晖使用临时root权限执行 AME3.x激活补丁 只适用于x86_64的&#xff1a;DSM7.x Advanced Media Extensions (AME)版本3.0.1-2004、3.1.0-3005 激活过程需要下载官方的解码包&#xff0c;过程较慢&#xff0c;耐心等待。。。 DSM7.1和7.2的AME版…

【前端设计】炫酷导航栏

欢迎来到前端设计专栏&#xff0c;本专栏收藏了一些好看且实用的前端作品&#xff0c;使用简单的html、css语法打造创意有趣的作品&#xff0c;为网站加入更多高级创意的元素。 html <!DOCTYPE html> <html lang"en"> <head><meta charset&quo…

Java 和 JavaScript 的奇妙协同:语法结构的对比与探索(中)

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

家人们,比赛打完了

啊&#xff0c;终于打完一场比赛了&#xff0c;但还有三场…… 先看看我的战绩&#xff1a; 共八题&#xff0c;AC6题&#xff0c;总共3902分&#xff0c;3.7k人参加&#xff0c;第980名 来看看第一&#xff1a; A8题&#xff0c;我只有2题没做出&#xff0c;相差4000多分&am…
最新文章