算法题目整合

文章目录

  • 121. 小红的区间翻转
  • 142. 两个字符串的最小 ASCII 删除总和
  • 143. 最长同值路径
  • 139.完美数
  • 140. 可爱串
  • 141. 好二叉树

121. 小红的区间翻转

小红拿到了两个长度为 n 的数组 a 和 b,她仅可以执行一次以下翻转操作:选择a数组中的一个区间[i, j],(i != j),将它们翻转。例如,对于 a = [2,3,4,1,5,6],小红可以选择左闭右闭区间[2,4],数组 a 则变成[2,3,5,1,4,6]。

小红希望操作后 a 数组和 b 数组完全相同。请你告诉小红有多少种操作的方案数。

初始 a 数组和 b 数组必定不相同。
输入描述

第一行输入一个正整数 n,代表数组的长度;
第二行输入 n 个正整数 ai; 
第三行输入 n 个正整数 bi。
输出描述
选择区间的方案数。

输入示例

4
1 2 3 1
1 3 2 1

输出示例

2

提示信息

数据范围
1 ≤ n, ai ,bi ≤ 103
在示例中:
将 1 2 3 1 中的 2 3 进行翻转,得到 1 3 2 1。
将 1 2 3 1 整个进行翻转,得到 1 3 2 1。
所以最终结果是 2。

思路:考虑先找到满足条件的最大left索引和最小right索引,然后进行循环:每次循环left–,right++,如果说A[left]==B[right],说明翻转后还是相同,直到两者不等,那么此时就可以break了。

import java.util.*;
class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int len = scanner.nextInt();int[] A = new int[len], B = new int[len];for(int i = 0; i < len; i++){A[i] = scanner.nextInt();}for(int i = 0; i < len; i++){B[i] = scanner.nextInt();}System.out.println(cal(A, B, len));}private static int cal(int[] A, int[] B, int len){int start = 0, end = len - 1;//定位到A与B第一个不相同的地方,这个时候需要考虑进行翻转了while(A[start] == B[start]){start++;}while(A[end] == B[end]){end--;}//找到满足条件的最大left索引和最小right索引int left = start, right = end;while(left <= end && right >= start){if(A[left] != B[right])  return 0;left++;right--;}int res = 1;int l = start - 1, r = end + 1;//进行循环while(l >= 0 && r < len){if(A[l] != B[r]){break;}else{res++;}l--;r++;}return res;}
}

142. 两个字符串的最小 ASCII 删除总和

题目描述

给定两个字符串 s1 和 s2(0 <= s1.length, s2.length <= 1000),返回使两个字符用相等所需删除字符的 ASCLL 值的最小和。 
s1 和 s2 由小写英文字母组成。

输入描述

输入共两行,每行一个字符串。

输出描述

输出一个正整数,表示使两个字符用相等所需删除字符的 ASCLL 值的最小和。

输入示例

sea
eat

输出示例

231

提示信息

解释:在“sea”中删除“s”并将"s”的值(115)加入总和。 
在"eat”中删除“t“并将116 加入总和。 
结束时,两个字符串相等,115+116 =231 就是符合条件的很小和。

思路:动态规划:记 d p [ i ] [ j ] dp[i][j] dp[i][j]为str1到str2最小 ASCII 删除总和,于是有转移方程
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] , i f s t r 1 [ i − 1 ] = = s t r 2 [ j − 1 ] d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + s t r 1 ( i − 1 ) , d p [ i ] [ j − 1 ] + s t r 2 ( j − 1 ) ) dp[i][j]=dp[i-1][j-1],\quad if\quad str1[i-1]==str2[j-1] \\ dp[i][j] =min(dp[i-1][j]+str1(i-1),dp[i][j-1]+str2(j-1)) dp[i][j]=dp[i1][j1],ifstr1[i1]==str2[j1]dp[i][j]=min(dp[i1][j]+str1(i1),dp[i][j1]+str2(j1))
还有边界条件
d p [ 0 ] [ 0 ] = 0 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + s t r 1 ( i − 1 ) d p [ 0 ] [ j ] = d p [ 0 ] [ j − 1 ] + s t r 2 ( j − 1 ) dp[0][0]=0 dp[i][0]=dp[i-1][0]+str1(i-1)\\ dp[0][j]=dp[0][j-1]+str2(j-1) dp[0][0]=0dp[i][0]=dp[i1][0]+str1(i1)dp[0][j]=dp[0][j1]+str2(j1)
然后空间优化方面,由于 d p [ i ] [ j ] dp[i][j] dp[i][j]只与 d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] dp[i-1][j],dp[i][j-1],dp[i-1][j-1] dp[i1][j]dp[i][j1]dp[i1][j1]有关,所以可以优化成一维数组。
d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]就是 d p [ j ] dp[j] dp[j]
d p [ i ] [ j ] dp[i][j] dp[i][j]就是 d p [ j ] dp[j] dp[j]
d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j1]就是 d p [ j − 1 ] dp[j-1] dp[j1]
d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]就需要先利用 p r e v prev prev记录 d p [ i − 1 ] [ 0 ] dp[i-1][0] dp[i1][0],再在内层循环时用 t e m p temp temp记录 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]

import java.util.*;
class Main{public static void main (String[] args) {Scanner scanner = new Scanner(System.in);String str1 = scanner.next();String str2 = scanner.next();System.out.println(AsciiSum(str1, str2));}private static int AsciiSum(String str1, String str2){int m = str1.length();int n = str2.length();int[] dp = new int[n + 1];for(int j = 1; j <= n; j++){dp[j] = dp[j - 1] + str2.charAt(j - 1);}for(int i = 1; i <= m; i++){int prev = dp[0];dp[0] += str1.charAt(i - 1);for(int j = 1; j <= n; j++){int temp = dp[j];if(str1.charAt(i - 1) == str2.charAt(j - 1)){dp[j] = prev;}else{dp[j] = Math.min(dp[j] + str1.charAt(i-1),dp[j-1]+str2.charAt(j-1));}prev = temp;}}return dp[n];}
}

143. 最长同值路径

题目描述

给定一个二叉树的 root ,返回最长的路径的长度,这个路径中的每节点具有相同值。
这条路径可以经过也可以不经过根节点。两个节点之间的路径长度 由它们之间的边数表示。 
树的节点数的范围是 [0,10^4] -1000 <= Node.val <= 1000
树的深度将不超过 18 层

输入描述

输入共两行,第一行是一个整数 n,表示第二行的字符串数。
第二行包含 n 个字符串,空格隔开,数字的字符串代表该节点存在,并且值为数字,null 代表是一个空结点。

输出描述

输出一个正整数,代表最长路径长度。

输入示例

7
5 4 5 1 1 null 5

输出示例

2

在这里插入图片描述这题有两个难点,第一个自然就是找到最长路径长度,但另一个难点是如何构造需要的二叉树,所以这个问题可以拆成两个部分:

  1. 根据输入构建二叉树
  2. 根据二叉树找到最长路径长度
    上面两点分别对应了deSerialize方法和dfs方法,两个方法本身并不算复杂,只不过需要熟练掌握队列的使用。
import java.util.*;
class Main{static int max;public static void main (String[] args) {max = 0;Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();String str = sc.nextLine();TreeNode root = deSerialize(str);dfs(root);System.out.println(max);}private static int dfs(TreeNode node){if(node == null)  return 0;int cur = 0, res = 0, left = dfs(node.left), right = dfs(node.right);int left1 = 0, right1 = 0;if(node.left != null && node.val == node.left.val){left1 = left + 1;}if(node.right != null && node.val == node.right.val){right1 = right + 1;}max = Math.max(max, left1 + right1);return Math.max(left1, right1);}private static TreeNode deSerialize(String s){String[] vals = s.split(" ");TreeNode root = new TreeNode(Integer.parseInt(vals[0]));Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int i = 1;while(!queue.isEmpty()){TreeNode node = queue.poll();if(i < vals.length && !vals[i].equals("null")){node.left = new TreeNode(Integer.parseInt(vals[i]));queue.offer(node.left);}i++;if(i < vals.length && !vals[i].equals("null")){node.right = new TreeNode(Integer.parseInt(vals[i]));queue.offer(node.right);}i++;}return root;}
}
class TreeNode{TreeNode left;TreeNode right;int val;TreeNode(){}TreeNode(int val){this.val = val;}
}

139.完美数

题目描述

小红定义一个数为“完美数”,当且仅当该数仅有一个非零数字。例如 5000, 4, 1, 10, 200 都是完美数。 小红拿到了一个大小为 n(2 <= n <= 2000)的数组 a,她希望选择数组中的两个元素(1 <= a[i] <= 10^9),满足它们的乘积为完美数。 小红想知道,共有多少种不同的取法?

输入描述

第一行输入一个整数 n,表示数组大小。 第二行输入 n 个整数,整数之间用空格隔开,表示数组中的元素。

输出描述

输出一个整数,表示取法个数。

输入示例

4
25 2 1 16

输出示例

3

提示信息

25 * 2 = 50; 2 * 1 = 2; 25 * 16 = 400。

难度不大,将long来存储乘积结果并用String来进行0的判断是关键。

import java.util.*;
class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int res = 0;int n = sc.nextInt();long[] nums = new long[n];for(int i = 0; i < n; i++){nums[i] = sc.nextInt();}for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){long ans = nums[i] * nums[j];if(isValid(ans))  res++;}}System.out.println(res);}private static boolean isValid(long ans){String s = String.valueOf(ans);for(int i = 1; i < s.length(); i++){if(s.charAt(i) != '0'){return false;}}return true;}
}

140. 可爱串

题目描述

我们定义子序列为字符串中可以不连续的一段,而子串则必须连续。
例如 rderd 包含子序列 "red”,且不包含子串"red”,因此该字符串为可爱串。 小红想知道,长度为 n(3 <= n <= 10 ^ 5)的、仅由 'r''e''d' 三种字母组成的字符串中,有多少是可爱串?答案请对 10 ^ 9 + 7 取模。

输入描述

输入共一行,包含一个正整数 n

输出描述

输出一个正整数,代表可爱串的数量

输入示例

4

输出示例

3

提示信息

"reed"、"rerd"、"rded"
import java.util.*;public class Main{static long MOD = (long) (1e9 + 7);public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();long[] dp1 = new long[n + 1];long[] dp2 = new long[n + 1];long[] dp3 = new long[n + 1];// 可爱串的个数 = 包含“red”子序列的方案个数 - 包含“red”子串的方案个数// dp1[i]表示长度为i的包含“red”子串的方案个数for (int i = 3; i <= n; i++) {dp1[i] = (3 * dp1[i - 1] + pow(3,i - 3) - dp1[i - 3] + MOD) % MOD;}// dp2[i]表示长度为i的包含“re”子序列的方案个数for (int i = 2; i <= n; i++) {dp2[i] = ((2 * dp2[i - 1]) + (i - 1) * pow(2, i - 2) + MOD) % MOD;}// dp3[i]表示长度为i的包含“red”子序列的方案个数for (int i = 3; i <= n; i++) {dp3[i] = (3 * dp3[i - 1] + dp2[i - 1] + MOD) % MOD;}System.out.println(dp3[n] - dp1[n]);}private static long pow(long x, long n) {long res = 1;while (n > 0) {if ((n & 1) == 1) {  // 如果 n 是奇数res = res * x % MOD;}x = x * x % MOD;n >>= 1;  // n 右移一位,相当于除以 2}return res;}
}

141. 好二叉树

题目描述

小红定义一个二叉树为“好二叉树”,当且仅当该二叉树所有节点的孩子数量为偶数(0 或者 2)。 
小红想知道,n(1<= n <=3000)个节点组成的好二叉树,共有多少种不同的形态? 
答案请对 10 ^ 9 + 7 取模。

输入描述

输入一个正整数 n

输出描述

输出一个正整数,代表好二叉树的数量

输入示例

5

输出示例

2

思路:动态规划,一个二叉树除了根节点可以分为左子树和右子树,设分别有 j j j个和 k − j k-j kj个,其中 k = i − 1 k=i-1 k=i1 j j j遍历每一个奇数即可。

import java.util.*;
class Main{static long MOD = (long)(1e9 + 7);public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();long[] dp = new long[3001];dp[1] = dp[3] = 1;for(int i = 5; i <= n; i += 2){for(int j = 1, k = i - 1; j < k; j += 2){dp[i] += (dp[j] * dp[k-j]) % MOD;dp[i] %= MOD;}}System.out.println(dp[n]);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot集成MQTT实现交互服务通信

引言 本文是springboot集成mqtt的一个实战案例。 gitee代码库地址&#xff1a;源码地址 一、什么是MQTT MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传输协议&#xff09;&#xff0c;是一种基于发布/订阅&#xff08;publish/subscribe&…

教大模型学数学,总共分几步?

大模型那么聪明&#xff0c;为什么数学题总是做不对、做不会&#xff1f; 从答高考数学卷难及格到普通数字比大小出错&#xff0c;大模型总算让大家觉得并非“无所不能”。这一方面让普通人开心&#xff0c;毕竟讲到AI取代人类看起来为时尚早&#xff0c;而另一方面&#xff0…

Autosar RTE配置-Assembly和Delegation的使用-基于ETAS软件

文章目录 前言Assembly和Delegation的含义Delegation的使用Assembly的使用总结 前言 RTE中的Compostion内部的SWC之间的连接使用Assembly Connector进行连接。这样的连接一般都是一个SWC的Pport对应另一个SWC的Rport。而Autosar软件中往往不只一个Composition(一般可以以核的数…

Android Toast

Toast Toast是Android常用的简单控件&#xff0c;主要用来进行简短的信息提示&#xff0c;如图1所示。 图1 Toast效果图 Toast的基本用法很简单&#xff0c;不需要设置layout&#xff0c;只需要在程序中调用即可。Toast调用makeText()方法设置需要显示的界面、显示的内容、显…

【计算机网络】学习指南及导论

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️计算机网络】 文章目录 前言我们为什么要学计算机网络&#xff1f;计算机网络概述计算机网络的分类按交换技术分类按使用者分类按传输介质分类按覆盖网络分类按覆盖网络分类 局域网的连接方式有线连接…

Lua基础知识入门

1 基础知识 标识符&#xff1a;标识符的定义和 C语言相同&#xff1a;字母和下划线_ 开头&#xff0c; 下划线_ 大写字母一般是lua保留字&#xff0c; 如_VERSION 全局变量&#xff1a;默认情况下&#xff0c;变量总是认为是全局的&#xff0c;不需要申明&#xff0c;给一个变…

河南萌新联赛2024第(一)场:河南农业大学

A.造数 题目&#xff1a; 链接&#xff1a;https://ac.nowcoder.com/acm/contest/86639/A 思路&#xff1a; 签到题&#xff0c;特判如果n0&#xff0c;输出0&#xff0c;如果n1或2&#xff0c;输出1&#xff1b;while循环&#xff0c;首先如果n%2!0&#xff0c;那么s&…

基于Web的特产美食销售系统的设计与实现

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…

Spring Web MVC(常用的注解@RequestMapping,@RequestParam,@RequestBody等)

一、Spring MVC spring的启动类 启动类是看这个 SpringBootApplication 注解&#xff0c;而不是 类的名字 这个注解在哪&#xff0c;哪个类就是启动类 1.MVC思想 举例 二、Spring MVC mvc 是一种思想&#xff0c;而spring mvc是对mvc思想的一种实现。全称是 spring web mvc…

笔记 2 : 课本第 3 章开始,记录 arm 的汇编指令的格式

&#xff08;13&#xff09; 介绍 arm 中的第一个汇编指令的用法 mov &#xff1a; &#xff08;14&#xff09;立即数的概念&#xff1a; &#xff08;15&#xff09; 汇编中的移位写法&#xff1a; 举例 &#xff1a; &#xff08;16&#xff09; 学习一个新的指令 cmp &a…

【大型实战】企业网络实验(华为核心交换、ESXI7.0vmware虚拟机、DHCP中继、服务端网络及用户端网络配置)

需求 实验 vmware网络配置&#xff08;企业内部一般为ESXI&#xff09; 这样服务器虚拟机使用192.168.200.X网段才能与用户侧互通 vmware虚拟机配置&#xff08;DHCP服务器网络配置&#xff09; 打开网络管理页面 nmtui重置一下网络连接&#xff08;重启网卡&#xff09; …

ubuntu24.04 linux bcm94352hmb 无线网卡(带蓝牙功能)无法连接蓝牙设备的解决办法

ubuntu24.04 linux bcm94352hmb 无线网卡&#xff08;带蓝牙功能&#xff09;无法连接蓝牙设备的解决办法 问题描述 小本是自己换装的bcm94352hmb&#xff0c;现在跑不动黑苹果了&#xff0c;换装ubuntu&#xff0c;该网卡在黑苹果上和windows上都能正常工作&#xff0c;到了…

Go语言中的并发

简单介绍go中的并发编程. 涉及内容主要为goroutine, goroutine间的通信(主要是channel), 并发控制(等待、退出). 想查看更多与Go相关的内容, 可以查看我的Go编程栏目 Goroutine 语法 在一个函数调用前加上go即可, go func(). 语法很简单, 可以说是并发写起来最简单的程序语言…

Mongodb多键索引中索引边界的混合

学习mongodb&#xff0c;体会mongodb的每一个使用细节&#xff0c;欢迎阅读威赞的文章。这是威赞发布的第93篇mongodb技术文章&#xff0c;欢迎浏览本专栏威赞发布的其他文章。如果您认为我的文章对您有帮助或者解决您的问题&#xff0c;欢迎在文章下面点个赞&#xff0c;或者关…

linux进程——概念理解与PCB

前言&#xff1a;本篇讲解Linux进程概念相关内容。 操作系统被称为计算机世界的哲学&#xff0c; 可以见得操作系统的知识并不好理解。 对于这篇进程概念的讲解&#xff0c; 博主认为&#xff0c; 如果没有一些前置知识的话&#xff0c;里面的有些概念并不好理解。 但是如果学习…

TDesign组件库日常应用的一些注意事项

【前言】Element&#xff08;饿了么开源组件库&#xff09;在国内使用的普及率和覆盖率高于TDesign-vue&#xff08;腾讯开源组件库&#xff09;&#xff0c;这也导致日常开发遇到组件使用上的疑惑时&#xff0c;网上几乎搜索不到其文章解决方案&#xff0c;只能深挖官方文档或…

防溺水预警系统引领水域安全新篇章

一、系统概述 随着人们对水域活动的需求增加&#xff0c;溺水事故频发&#xff0c;给人们的生命安全带来了严重威胁。然而&#xff0c;如今&#xff0c;一项创新科技正在以强大的功能和无限的潜力引领着水域安全的新篇章。智能防溺水预警系统&#xff0c;作为一种集成了智能感知…

文心一言:如何备考软考架构师

提问&#xff1a;软考高级:架构师指导&#xff0c;有哪些考点、重点考点有哪些&#xff1f;需要如何备考&#xff1f;案例分析题如何做&#xff1f;论文如何写&#xff1f; 文心一言回答1700字如下&#xff1a; 针对软考高级架构师的考试&#xff0c;以下是对考点、重点考点、备…

MongoDB自学笔记(三)

一、前文回顾 上一篇文章中我们学习了更新操作&#xff0c;以及讲解了部分的更新操作符&#xff0c;今天我们继续学习剩余的更新操作符。 二、更新操作符 1、$rename 语法&#xff1a;{ $rename: { < field1 >: < newName1 >, < field2 >: < newName2…

JDK、JRE、JVM的区别java的基本数据类型

说一说JDK、JRE、JVM的区别在哪&#xff1f; JDK&#xff1a; Java Delopment kit是java工具包&#xff0c;包含了编译器javac&#xff0c;调试器&#xff08;jdb&#xff09;以及其他用于开发和调试java程序的工具。JDK是开发人员在开发java应用程序时候所需要的的基本工具。…