【算法刷题日记之本手篇】连续最大和与判断回文

举报
未见花闻 发表于 2022/07/31 22:25:16 2022/07/31
【摘要】 本篇文章介绍来自牛客试题广场的两道题题解,分别为【连续最大和】和【判断回文】,展示语言java。

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解,分别为【连续最大和】和【判断回文】,展示语言java。

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创!
📆首发时间:🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《数据结构与算法》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!

⭐️连续最大和⭐️

🔐题目详情

描述

一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000),表示一共有n个元素 第二行为n个数,即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:

所有连续子数组中和最大的值。

示例1

输入:

3
-1 2 1

输出:

3

题目链接:连续最大和

💡解题思路

基本思路: 动态规划

解题思路:
本题需要我们去求一段连续子序列的最大连续和,我们可以考虑动态规划,假设有一数组arr,长度为n,下标为i
做动态规划题,有三个步骤:

  • 状态定义
  • 确定初始状态
  • 确定状态转移方程

类似与数学推理,我们要相信,人可能会欺骗我,生活可能会欺骗我,但是数学永远不会欺骗我们,所以在下面进行推理的时候,只要你推理过程没有问题,要坚信你得到的推理表达式是正确的,如果你得到的状态转移方程有问题,你就要想想,你状态定义的是否为题目直接所求,你的初始状态是否正确,你的推理逻辑是否严密。

下面我们来进行推导:

状态定义: 我们定义 f [ i ] f[i] 表示以 i i 下标元素结尾的最大连续子序列和。
确定初始状态: i = 0 i=0 时, f [ 0 ] = a r r [ 0 ] f[0]=arr[0]
转态转移方程: 遍历到 i i 下标的元素的时候,你有两种选择,一是在原来序列上加上这一个元素,此时的序列和为 f [ i 1 ] + a r r [ i ] f[i-1]+arr[i] ,另外的一种选择就是放弃之前的序列,从当前元素开始新的序列,此时序列和为 a r r [ i ] arr[i] ,我们要选择哪一种呢?很明显,我们选择序列和更大的那一个,因此状态转移方程也就出来了。

f [ i ] = m a x ( f [ i 1 ] + a r r [ i ] , a r r [ i ] ) f[i]=max(f[i-1]+arr[i], arr[i])

再次回到我们的题目,题目让我们求最大连续子序列的和,我们状态转移方程求的是以i下标元素结尾的连续子序列最大和,因此整个数组的连续子序列最大和,就是从i下标元素结尾的最打连续子序列和中最大的那一个,即所求得f[n]数组中最大的元素。

🔑源代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //转态定义:定义f[i]表示以i作为结尾下标的元素的最大序列和
        //初始状态确定:当i=0时,最大元素和为f[0] = arr[0]
        //状态转移方程f[i] = Max(f[i - 1] + arr[i], arr[i])
        int[] f = new int[n];
        f[0] = arr[0];
        //ans用来求最大子连续序列和
        int ans = arr[0];
        for (int i = 1; i < n; i++) {
            int curval = f[i - 1] + arr[i];
            f[i] = curval > arr[i] ? curval : arr[i];
            
            //如果当前以i结尾的最大序列和比ans大,则更新,否则不更新
            ans = f[i] > ans ? f[i] : ans;
        }
        System.out.println(ans);
    }
}

🌱总结

本题为简单动态规划推理题,重点是要学会如何进行状态定义,如何确定初始状态值,如何推导状态转移方程。
类似题:
53. 最大子数组和
509. 斐波那契数
剑指 Offer 10- II. 青蛙跳台阶问题
118. 杨辉三角
119. 杨辉三角 II
121. 买卖股票的最佳时机
70. 爬楼梯
1137. 第 N 个泰波那契数

升级题:
剑指 Offer II 088. 爬楼梯的最少成本

⭐️判断回文⭐️

🔐题目详情

“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串,生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求,帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如:
A = “aba”,B = “b”。这里有4种把B插入A的办法:
* 在A的第一个字母之前: “baba” 不是回文
* 在第一个字母‘a’之后: “abba” 是回文
* 在字母‘b’之后: “abba” 是回文
* 在第二个字母’a’之后 “abab” 不是回文
所以满足条件的答案为2

输入描述:

每组输入数据共两行。 第一行为字符串A 第二行为字符串B 字符串长度均小于100且只包含小写字母

输出描述:

输出一个数字,表示把字符串B插入字符串A之后构成一个回文串的方法数

示例1

输入:

aba
b

输出:

2

💡解题思路

基本思路: 模拟构造+判断回文
解题思路:
不妨设题目中的A字符串为str1B字符串为str2,首先我们考虑每一个位置,str2插入str1指定位置构造字符串,然后判断这个构造的字符串是否回文即可,如果为回文字符串,计数器加1即可。

对于判断回文,很简单,就是将字符串逆置,在于源字符串比较,如果相同,那这个字符串就是回文字符串。

🔑源代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        
        int ans = 0;
        int n = str1.length();
        for (int i = 0; i <= n; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(str1.substring(0, i));
            sb.append(str2);
            sb.append(str1.substring(i, n));
            String rs1 = sb.toString();
            String rs2 = sb.reverse().toString();
            if (rs1.equals(rs2)) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

🌱总结

本题为字符串模拟题,基本思路就是构造str2插入str1字符串每一个位置情况的字符串,然后判断回文并计数即可。
类似题:
125. 验证回文串
剑指 Offer II 027. 回文链表

升级题:
剑指 Offer II 020. 回文子字符串的个数

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200