左神算法之中级提升班(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…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
Windows 下端口占用排查与释放全攻略
Windows 下端口占用排查与释放全攻略 在开发和运维过程中,经常会遇到端口被占用的问题(如 8080、3306 等常用端口)。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口,帮助你高效解决此类问题。 一、准…...