【算法题解】

文章目录

  • day4_26
    • 最长回文子串
          • 思路:
          • 代码:
    • **DP30** **买卖股票的最好时机(一)**
          • 思路:贪心
          • 代码:
    • 过河卒
          • 思路:动态规划---路径类
          • 代码:

day4_26

https://www.nowcoder.com/questionTerminal/12e081cd10ee4794a2bd70c7d68f5507

最长回文子串

在这里插入图片描述

思路:

空间扩展算法

1.枚举中心位置的时候,要考虑回文串长度的奇偶性

  • 奇数,枚举的数在中心,left,right在两边去扩展
  • 偶数,left在i的位置上,right在i的右边,进行扩展

2.如何计算长度

​ right-left-1

代码:
    public int getLongestPalindrome(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int left = i - 1;
            int right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            ans = Math.max(ans,right-left-1);
            left = i;
            right = i+1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            ans = Math.max(ans,right-left-1);
        }
        return ans;
    }

DP30 买卖股票的最好时机(一)

https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb?tpId=230&tqId=39767&ru=/exam/oj

在这里插入图片描述

思路:贪心

1.用一个变量来表示,当前位置的前驱最小值

2.每输入一个数,更新当前的最小利润

3.跟新最小值

代码:
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ret = 0;
        int x = 0;
        int prevMin = in.nextInt();
        for (int i = 1; i < n; i++) {
            x = in.nextInt();
            ret = Math.max(ret,x-prevMin);
            prevMin = Math.min(prevMin,x);
        }
        System.out.println(ret<0?0:ret);
    }

过河卒

https://ac.nowcoder.com/acm/problem/16708

在这里插入图片描述

思路:动态规划—路径类

1.状态表示:dp[i] [j] 表示从00位置出发,到达ij位置,一共有多少种方法。

2.状态转移方程:dp[i] [j] = dp[i-1] [ j] +dp[i] [j-1]

3.如果是马所能到达的位置,就为0

4.初始化: dp表规模(n+2)*(m+2).dp[0] [1]==1 || dp[1] [0] ==1

5.填表:dp[n+1] [m+1];

代码:
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        int[][] dp = new int[n + 2][m + 2];
        dp[0][1] = 1;
        x += 1;
        y += 1;
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                if (i != x && j != y && Math.abs(i - x) + Math.abs(j - y) == 3 || (i == x && j == y)) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        System.out.println(dp[n+1][m+1]);
    }

点击移步博客主页,欢迎光临~

偷cyk的图

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

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

相关文章

生命周期评估(LCA)Simapro软件应用与碳足迹分析

各企事业单位&#xff1a; SimaPro以系统和透明的方式轻松建模和分析复杂的生命周期&#xff0c;通过确定供应链中每个环节的热点&#xff0c;从原材料的提取到制造&#xff0c;分销&#xff0c;使用和处置&#xff0c;衡量所有生命周期阶段的产品和服务对环境的影响。SimaPro是…

又重新搭了个个人博客

哈喽大家好&#xff0c;我是咸鱼。 前段时间看到一个学弟写了篇用 Hexo 搭建博客的教程&#xff0c;心中沉寂已久的激情重新被点燃起来。&#xff08;以前搞过一个个人网站&#xff0c;但是因为种种原因最后不了了之&#xff09; 于是花了一天时间参考教程搭了个博客网站&…

广工电工与电子技术实验报告-8路彩灯循环控制电路

实验代码 module LED_water (clk,led); input clk; output [7:0] led; reg [7:0] led; integer p; reg clk_1Hz; reg [7:0] current_state, next_state; always (posedge clk) begin if(p25000000-1)begin …

JVM(Jvm如何管理空间?对象如何存储、管理?)

Jvm如何管理空间&#xff08;Java运行时数据区域与分配空间的方式&#xff09; ⭐运行时数据区域 程序计数器 程序计数器&#xff08;PC&#xff09;&#xff0c;是一块较小的内存空。它可以看作是当前线程所执行的字节码的行号指示器。Java虚拟机的多线程是通过时间片轮转调…

Flutter 从 Assets 中读取 JSON 文件:指南 [2024]

在本教程中&#xff0c;我们将探讨如何从 Flutter 项目中的 asset 中读取 JSON 文件。您将找到详细的解释、实际示例和最佳实践&#xff0c;使您的 JSON 文件处理顺利高效。那么&#xff0c;让我们深入了解 Flutter 和 JSON 的世界吧&#xff01; 从 asset 中读取 JSON 文件 …

RTK负载(4K可见光+高分热成像+超广角+激光测距)四光AI智能识别跟踪吊舱技术详解

无人机光电吊舱的RTK负载&#xff08;4K可见光高分热成像超广角激光测距&#xff09;AI智能识别跟踪吊舱技术是一种高度集成和先进的无人机观测系统。系统结合了无人机的飞行能力和光电吊舱的多功能传感器&#xff0c;通过集成RTK&#xff08;实时动态差分定位&#xff09;技术…

WebGL开发框架比较

WebGL开发框架提供了一套丰富的工具和API&#xff0c;使得在Web浏览器中创建和操作3D图形变得更加容易。以下是一些流行的WebGL开发框架及其各自的优缺点。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.Three.js 优点&#xff1a…

WoodMart主题下载:为您的电商网站带来自然而优雅的购物体验

在电子商务的激烈竞争中&#xff0c;一个设计精良、用户友好的在线商店是吸引和保留客户的关键。WoodMart主题&#xff0c;作为一款专为Shopify平台设计的高级主题&#xff0c;以其自然美学和强大的功能&#xff0c;帮助您的商店在众多竞争对手中脱颖而出。 [WoodMart主题的核…

运行游戏提示dll文件丢失,分享多种有效的解决方法

在我们日常频繁地利用电脑进行娱乐活动&#xff0c;特别是畅玩各类精彩纷呈的电子游戏时&#xff0c;常常会遭遇一个令人困扰的问题。当我们满怀期待地双击图标启动心仪的游戏程序&#xff0c;准备全身心投入虚拟世界时&#xff0c;屏幕上却赫然弹出一条醒目的错误提示信息&…

【书生浦语第二期实战营学习作业笔记(二)】

书生浦语第二期实战营学习作业&笔记(二) 操作文档&#xff1a;https://github.com/InternLM/Tutorial/blob/camp2/helloworld/hello_world.md 基础作业 &#xff1a; 使用 InternLM2-Chat-1.8B 模型生成 300 字的小故事&#xff1a; 八戒部署&#xff08;笔记&#xff0…

基于灰狼算法的综合能源系统多时间尺度优化调度(附matlab程序)

0.代码链接 基于灰狼算法的综合能源系统多时间尺度优化调度&#xff08;MATLAB程序&#xff09;资源-CSDN文库 1.简述 对于冷、热、电联供综合能源系统优化问题&#xff0c;为了提高可再生能源利用率&#xff0c;故以弃风、弃光量最小和综合能源系统运行经济性为优化目标&…

mac配置maven

在 macOS 上配置 Maven 也相对简单。以下是一种常用的方法&#xff1a; 1. 安装maven **下载 Maven&#xff1a;**首先&#xff0c;你需要从 Maven 官网&#xff08;https://maven.apache.org/download.cgi&#xff09;下载最新版本的 Maven。你可以选择二进制压缩包&#xf…

redis常用数据结构

redis常用数据结构 Redis 底层在实现下面数据结构的时候&#xff0c;会进行特定的优化&#xff0c;来达到节省时间/空间的效果。 内部结构 String raw&#xff08;最基本的字符串&#xff09;&#xff0c;int&#xff08;实现计数功能&#xff0c;当value为整数的时候会用整…

JPEG图像常用加密算法简介

JPEG图像加密算法 目前&#xff0c;JPEG图像加密算法可以分成异或加密、置乱加密和置乱与异或组合加密。下面对这三种加密方式进行阐述。 (1) 异或加密 文献[1]提出了一种基于异或加密的JPEG图像的RDH-EI方案。该算法通过对AC系数的ACA和图像的量化表进行流密码异或&#xf…

Feign功能详解、使用步骤、代码案例

简介&#xff1a;Feign是Netflix开发的声明式&#xff0c;模板化的HTTP客户端&#xff0c;简化了HTTP的远程服务的开发。Feign是在RestTemplate和Ribbon的基础上进一步封装&#xff0c;使用RestTemplate实现Http调用&#xff0c;使用Ribbon实现负载均衡。我们可以看成 Feign R…

经典的免费wordpress模板

这款经典的免费WordPress模板以鲜艳的红色为主调&#xff0c;充满了活力与热情。设计简洁而现代&#xff0c;适合各种类型的项目网站。模板采用响应式设计&#xff0c;确保在不同设备和屏幕尺寸上都能呈现出完美的视觉效果。 红色象征着激情、活力和自信&#xff0c;这款模板…

ubuntu子系统密码忘记了,怎么办?

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

18种WEB常见漏洞:揭秘网络安全的薄弱点

输入验证漏洞: 认证和会话管理漏洞: 安全配置错误: 其他漏洞: 防范措施: Web 应用程序是现代互联网的核心&#xff0c;但它们也容易受到各种安全漏洞的影响。了解常见的 Web 漏洞类型&#xff0c;对于开发人员、安全测试人员和普通用户都至关重要。以下将介绍 18 种常见的 …

HttpClient工具类编写

HttpClient 介绍 HttpClient是Apache Jakarta Common下的一个子项目&#xff0c;它提供了一个高效的、最新的、功能丰富的支持HTTP协议的客户端编程工具包。它支持HTTP协议最新的版本和建议&#xff0c;并实现了Http1.0和Http1.1协议。 HttpClient具有可扩展的面向对象的结构…

电脑壁纸怎么设置?简单3步,让你的电脑桌面变得更合心意

电脑壁纸是我们每天在电脑上工作和娱乐时不可或缺的一部分。一张精美的电脑壁纸&#xff0c;既能提升我们的工作效率&#xff0c;也能为我们带来愉悦的心情。无论是静谧的自然风光、抽象的艺术设计&#xff0c;还是心动的明星照片&#xff0c;都可以在电脑壁纸的世界里找到自己…