左神算法之中级提升班(9)
目录
【案例1】
【题目描述】
【思路解析】
【代码实现】
【案例2】
【题目描述】
【思路解析 平凡解技巧 从业务中分析终止条件 重点】
【代码实现】
【案例3】
【题目描述】
【思路解析】
【案例4】
【题目描述】
【思路解析】
【代码实现】
【动态规划代码】
【案例5】
【题目描述】【很重要】【编辑距离问题】
【思路解析】
【代码实现】
【案例6】
【题目描述】
【思路解析】
【代码实现】
【案例1】
【题目描述】
【思路解析】
因为它数字的范围只能为1 - n,然后数组范围0 - n-1,所以说如果没有缺失值的话,每个i位置应该放i + 1,所以我们直接对每个数组完成这个操作,让每个i位置尽可能放i+1,如果有些位置不是i+1,则这些位置就是缺失值,遍历打印即可 。
【代码实现】
/*** @ProjectName: study3* @FileName: Ex1* @author:HWJ* @Data: 2023/7/31 9:48*/
public class Ex1 {public static void main(String[] args) {int[] arr = {1, 3, 4, 3};printNumberNoInArray(arr);}public static void printNumberNoInArray(int[] arr){if (arr == null || arr.length == 0){return;}for (int i : arr) {modify(i, arr);}for (int i = 0; i < arr.length; i++) {if (arr[i] != i + 1){System.out.println(i + 1);}}}// 这里实现让每个i位置上尽可能方i+1public static void modify(int value, int[] arr){while(arr[value - 1] != value){int tmp = arr[value - 1];arr[value - 1] = value;value = tmp;}}}
【案例2】
【题目描述】
【思路解析 平凡解技巧 从业务中分析终止条件 重点】
这道题容易想到使用暴力递归来解决,但限制条件只有一个cur == end,不足以作为basecase,需要补充限制条件,因为end和start均为偶数,且end > > start ,所以有一个只用点赞到达end的平凡解,如果高于这个花费的解,直接不考虑。
从业务中分析,因为他有一个私聊是可以-2,然后在递归中,它有一个分支可能一直在-2,导致无法到达end,所以限制条件增加一个为start已经小于0停止。
从业务中分析,他有一个*2的方式,但是总有一次*2可以使他第一次比b大,此时如果再次*2就会花费更多的私聊钱,再分析再次*2会大于2*b,所以增加一个限制条件start不能大于 2 * b;
【代码实现】
/*** @ProjectName: study3* @FileName: Ex2* @author:HWJ* @Data: 2023/7/31 10:39*/
public class Ex2 {public static void main(String[] args) {System.out.println(getMinMoney(3, 100, 1, 2, 6));}public static int getMinMoney(int x, int y, int z, int start, int end) {int limitCoin = ((end - start) / 2) * x;int limitAim = end * 2;return process(x, y, z, start, end, 0, limitCoin, limitAim);}// preMoney代表当前已经花了多少钱// limitCoin代表平凡解所需要花费的钱币// limitAim 代表当前start的上界public static int process(int x, int y, int z, int start, int end, int preMoney, int limitCoin, int limitAim) {if (start == end) {return preMoney;}if (start < 0) {return Integer.MAX_VALUE;}if (preMoney > limitCoin) {return Integer.MAX_VALUE;}if (start > limitAim) {return Integer.MAX_VALUE;}int p1 = process(x, y, z, start + 2, end, preMoney + x, limitCoin, limitAim);int p2 = process(x, y, z, start * 2, end, preMoney + y, limitCoin, limitAim);int p3 = process(x, y, z, start - 2, end, preMoney + z, limitCoin, limitAim);return Math.min(p1, Math.min(p2, p3));}}
【案例3】
【题目描述】
【思路解析】
可以通过后面关联矩阵生成一个图,然后从末尾H开始做一个图的宽度优先遍历,每个节点实现一个哈希表,然后哈希表里面维护当花费天数增加时,收益一定增加,然后每个节点就得到了它独自的哈希表,然后最后将所有哈希表汇总,这样就得到了所有完成方式。然后最后根据限制天数来查表即可。最后这里也可以用大根堆来做,只有小于限制天数的值才加入,然后里面根据收益大小来维护大根堆。两个方式都差不多。
【案例4】
【题目描述】
【思路解析】
因为& | ^ 这几个运算都是二元运算,则表达式长度应该为奇数且大于1,满足奇数位上只有0或1,偶数位上只有&、|或^运算符,如果不满足此规则的字符串直接返回0.
然后对于组合就有如下定义,对于每一个确定的表达式组合应有确定的括号,对于不同的括号填充,则认为不同的组合方式。括号可以认为是进行运算时的顺序规定,不一定真的要在字符串上填充括号。
【代码实现】
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex4* @author:HWJ* @Data: 2023/9/11 14:21*/
public class Ex4 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();boolean desire = input.nextBoolean();if (!check(str)){System.out.println(0);}else {char[] charArray = str.toCharArray();int ans = count(charArray, 0, charArray.length - 1, desire);System.out.println(ans);}}public static boolean check(String str){// 因为 | & ^ 运算都是二元运算,所以有效字符串长度应该为奇数,并且奇数位是 1 或者 0, 偶数位是 二元运算符if (str.length() % 2 == 0 || str.length() == 1){return false;}char[] charArray = str.toCharArray();for (int i = 0; i < charArray.length; i+=2) {if (charArray[i] != '0' && charArray[i] != '1'){return false;}}for (int i = 1; i < charArray.length; i+=2) {if (charArray[i] != '|' && charArray[i] != '&' && charArray[i] != '^'){return false;}}return true;}public static int count(char[] chars, int L, int R, boolean desire) {if (L == R) {if (chars[L] == '0') {return desire ? 0 : 1;} else {return desire ? 1 : 0;}}int res = 0;for (int i = L + 1; i < R; i += 2) {if (desire) {switch (chars[i]) {case '&':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);break;case '|':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;case '^':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;}} else {switch (chars[i]) {case '|':res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);break;case '&':res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;case '^':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);break;}}}return res;}
}
【动态规划代码】
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex4_2* @author:HWJ* @Data: 2023/9/11 15:10*/
public class Ex4_2 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();boolean desire = input.nextBoolean();int ans = dp(str, desire);System.out.println(ans);}public static boolean check(String str) {// 因为 | & ^ 运算都是二元运算,所以有效字符串长度应该为奇数,并且奇数位是 1 或者 0, 偶数位是 二元运算符if (str.length() % 2 == 0 || str.length() == 1) {return false;}char[] charArray = str.toCharArray();for (int i = 0; i < charArray.length; i += 2) {if (charArray[i] != '0' && charArray[i] != '1') {return false;}}for (int i = 1; i < charArray.length; i += 2) {if (charArray[i] != '|' && charArray[i] != '&' && charArray[i] != '^') {return false;}}return true;}public static int dp(String str, boolean desire) {if (!check(str)) {return 0;}int N = str.length();char[] charArray = str.toCharArray();int[][] tMap = new int[N][N];int[][] fMap = new int[N][N];for (int i = 0; i < N; i += 2) {tMap[i][i] = charArray[i] == '1' ? 1 : 0;fMap[i][i] = charArray[i] == '1' ? 0 : 1;}for (int row = N - 3; row >= 0; row -= 2) {for (int col = row + 2; col < N; col += 2) {for (int i = row + 1; i < N; i += 2) {switch (charArray[i]) {case '&':tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];break;case '|':tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];break;case '^':tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];break;}switch (charArray[i]) {case '&':fMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];fMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];break;case '|':fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];break;case '^':fMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];break;}}}}if (desire) {return tMap[0][N - 1];} else {return fMap[0][N - 1];}}
}
【案例5】
【题目描述】【很重要】【编辑距离问题】
【思路解析】
这里可以使用dp动态规划,来进行寻找最小代价。
这里的i和j表示str1使用i个字符,完成str2的j个字符
分为以下情况
(1)str1使用i-1个字符完成str2的j-1个字符,再将str1第i个字符替换为str2第j个字符,如果相等就可以剩去替换的过程
(2)str1使用i-1个字符完成str2的j个字符,再将str1第i个字符删去
(3) str1使用i个字符完成str2的j-1个字符,再添加str2的第j个字符
则str1使用i个字符,完成str2的j个字符的最小使用,则为上面的最小值
【代码实现】
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex5* @author:HWJ* @Data: 2023/9/11 15:01*/
public class Ex5 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str1 = input.next();String str2 = input.next();int add = input.nextInt();int del = input.nextInt();int replace = input.nextInt();int ans = dp(str1, str2, add, del, replace);System.out.println(ans);}public static int dp(String str1, String str2, int add, int del, int replace){int N1 = str1.length();int N2 = str2.length();int[][] map = new int[N1 + 1][N2 + 1];for (int i = 1; i <= N2; i++) {map[0][i] = i * add;}for (int i = 1; i <= N1; i++) {map[i][0] = i * del;}for (int i = 1; i <= N1; i++) {for (int j = 1; j <= N2; j++) {// 这里的i和j表示str1使用i个字符,完成str2的j个字符// 分为以下情况// (1)str1使用i-1个字符完成str2的j-1个字符,再将str1第i个字符替换为str2第j个字符,如果相等就可以剩去替换的过程// (2)str1使用i-1个字符完成str2的j个字符,再将str1第i个字符删去// (3) str1使用i个字符完成str2的j-1个字符,再添加str2的第j个字符// 则str1使用i个字符,完成str2的j个字符的最小使用,则为上面的最小值map[i][j] = map[i - 1][j] + del;map[i][j] = Math.min(map[i][j], map[i][j - 1] + add);map[i][j] = Math.min(map[i][j], map[i][j - 1] + str1.charAt(i - 1) == str2.charAt(j - 1) ? 0 : replace);}}return map[N1][N2];}}
【案例6】
【题目描述】
【思路解析】
建立一个每个字符的词频表,然后从当前位置开始遍历每一个字符,经历一个字符就词频减1,当出现某个字符词频为0时,就在所有经历过的字符中,选择一个字典序最小的字符,然后删去除了他其他相同的字符,并删去在他之前的字符。直到所有字符的词频都为1.
【代码实现】
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex6* @author:HWJ* @Data: 2023/9/11 16:14*/
public class Ex6 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();String s = delete(str);System.out.println(s);}public static String delete(String str){if (str.length() <= 1){return str;}// 这里假设字符的ascii码值最大为256;int[] map = new int[256];int max = 1;for (int i = 0; i < str.length(); i++) {map[str.charAt(i)] += 1;max = Math.max(max, map[str.charAt(i)]); }if(max == 1){return str;}else {for (int i = 0; i < str.length(); i++) {map[str.charAt(i)] -= 1;if (map[str.charAt(i)] == 0){int min = Integer.MAX_VALUE;int index = -1;for (int j = 0; j <= i; j++) {min = Math.min(min, str.charAt(j));index = min == str.charAt(j) ? j : index;}return String.valueOf(str.charAt(index)) +delete(str.substring(index + 1).replace(String.valueOf(str.charAt(index)), ""));}}}return "";}
}
相关文章:

左神算法之中级提升班(9)
目录 【案例1】 【题目描述】 【思路解析】 【代码实现】 【案例2】 【题目描述】 【思路解析 平凡解技巧 从业务中分析终止条件 重点】 【代码实现】 【案例3】 【题目描述】 【思路解析】 【案例4】 【题目描述】 【思路解析】 【代码实现】 【动态规划代码】…...

SmartNews 基于 Flink 的 Iceberg 实时数据湖实践
摘要:本文整理自 SmartNews 数据平台架构师 Apache Iceberg Contributor 戢清雨,在 Flink Forward Asia 2022 实时湖仓专场的分享。本篇内容主要分为五个部分: SmartNews 数据湖介绍基于 Icebergv1 格式的数据湖实践基于 Flink 实时更新的数据…...
websocket请求通过IteratorAggregate实现流式输出
对接国内讯飞星火模型,官方文档接口采用的是websocket跟国外chatgpt有些差异。 虽然官网给出一个简单demo通过while(true),websocket的receive()可以实现逐条接受并输出给前端,但是通用和灵活度不高。不能兼容现有项目框架的流式输出。故模仿…...
《C和指针》笔记28:可变参数和stdarg宏
可变参数列表可以通过宏来实现,这些宏定义于stdarg.h头文件,它是标准库的一部分。这个头文件声明了一个类型va_list和三个宏——va_start、va_arg和va_end 。我们可以声明一个类型为va_list的变量,与这几个宏配合使用,访问参数的值…...

Matlab论文插图绘制模板第114期—带图形标记的图
之前的文章中,分享了Matlab带线标记的图: 带阴影标记的图: 带箭头标记的图: 进一步,分享一下带图形标记的图,先来看一下成品效果: 特别提示:本期内容『数据代码』已上传资源群中&…...
Python:用于有效对象管理的单例模式
1. 写在前面 在本文中,我们将介绍一种常用的软件设计模式 —— 单例模式。 通过示例,演示单例创建,并确保该实例在整个应用程序生命周期中保持一致。同时探讨它在 Python 中的目的、益处和实际应用。 关键点: 1、单例模式只有…...

【TCP】滑动窗口、流量控制 以及拥塞控制
滑动窗口、流量控制 以及拥塞控制 1. 滑动窗口(效率机制)2. 流量控制(安全机制)3. 拥塞控制(安全机制) 1. 滑动窗口(效率机制) TCP 使用 确认应答 策略,对每一个发送的数…...
Xilinx FPGA管脚约束语法规则(UCF和XDC文件)
文章目录 1. ISE环境(UCF文件)2. Vivado环境(XDC文件) 本文介绍ISE和Vivado管脚约束的语句使用,仅仅是管脚和电平状态指定,不包括时钟约束等其他语法。 ISE使用UCF文件格式,Vivado使用XDC文件&…...

服务网格和CI/CD集成:讨论服务网格在持续集成和持续交付中的应用。
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
代码随想录训练营第56天|583.两个字符串的删除操作,72.编辑距离
代码随想录训练营第56天|583.两个字符串的删除操作,72.编辑距离 583.两个字符串的删除操作文章思路代码 72.编辑距离文章思路代码 总结 583.两个字符串的删除操作 文章 代码随想录|0583.两个字符串的删除操作 思路 如果不按照编辑距离考虑的话,只需要…...
【JDK 8-Lambda】3.1 Java高级核心玩转 JDK8 Lambda 表达式
一、 什么是函数式编程 ? 二、 什么是lambda表达式? 1. 先看两个示例 A.【创建线程】 B.【数组排序-降序】 2. lambda表达式特性 A. 使用场景(前提): B. 语法 (params) -> expression C. 参数列表 D. 方法体 F. 好处 一、 什么是函数式编…...

【C#】XML的基础知识以及读取XML文件
最近在学读取文件 目录 介绍特点结构XML的语法规则XML 命名规则 C#操作XML新建读取第一种第二种第三种 读取属性 介绍 XML (可扩展标记语言,eXtensible Markup Language) 是一种标记语言,它被设计用来传输和存储数据。 特点 可扩展性:由于…...
Immutable.js简介
引子 看一段大家熟悉的代码 const state {str: wwming,obj: {y: 1},arr: [1, 2, 3] } const newState stateconsole.log(newState state) // truenewState和state是相等的 原因: 由于js的对象和数组都是引用类型。所以newState的state实际上是指向于同一块内存…...
C语言进阶教程(位操作和进制数的表示)
文章目录 前言一、左移和右移二、清除对应的位为0和设置对应的位为11.设置对应的位为12.清除对应的位为0 三、进制数的表示四、& ^ | ~总结 前言 本篇文章给大家讲解一下C语言中的位操作,在嵌入式中位操作是经常需要使用的,那么下面就让我们来学习一…...

Loguru:功能强大、简单易用的Python日志库
文章目录 Loguru:Python的日志库安装 Loguru基本用法配置 Loguruadd() 语句remove() 语句设置日志文件保留日志的等级设置控制台日志显示等级Loguru:Python的日志库 Loguru 是一个功能强大、简单易用的日志库,可以让 Python 的日志记录变得更加轻松。它提供了丰富的功能和配…...

idea之maven的安装与配置
我们到maven的官网里下载maven,地址:https://maven.apache.org/download.cgi下载完成后解压即可配置环境变量 此电脑–>右键–>属性–>高级系统设置–>环境变量–>系统变量(S)–>新建一个系统变量 变量名&…...

【最新面试问题记录持续更新,java,kotlin,android,flutter】
最近找工作,复习了下java相关的知识。发现已经对很多概念模糊了。记录一下。部分是往年面试题重新整理,部分是自己面试遇到的问题。持续更新中~ 目录 java相关1. 面向对象设计原则2. 面向对象的特征是什么3. 重载和重写4. 基本数据类型5. 装箱和拆箱6. …...
面试:经典问题解决思路
1. 秒杀系统架构 参考:秒杀系统架构优化思路 2. 如何防止订单重复提交 重复提交原因: 一种是由于用户在短时间内多次点击下单按钮,或浏览器刷新按钮导致。另一种则是由于Nginx或类似于SpringCloud Gateway的网关层,进行超时重试造成的。 方案…...

CG MAGIC分享3ds Max卡顿未保存处理方法有哪些?
3ds Max进行建模、渲染这一系列过程中,大家使用中都会遇到各种原因导致软件卡顿或崩溃是很常见的情况。 可以说卡机没关系,可是卡顿发生时,如果之前的工作没有及时保存,可能会导致数据的丢失和时间的浪费。这就是最让人烦躁的了&…...
[python 刷题] 238 Product of Array Except Self
[python 刷题] 238 Product of Array Except Self 题目: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guar…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...