Kennem's Blog
  • 🏠主页
  • 🔍搜索
  • 📚文章
  • ⏱时间轴
  • 🔖标签
  • 🗂️分类
  • 🙋🏻‍♂️关于
主页 📚文章

💻技术

Java20天速成——进阶课程(3)

Java20天速成——进阶课程(3) 文件操作 File对象 常用方法 public static void main(String[] args) { // 创建File对象,表示文件test.txt的绝对路径 File f1 = new File("D:/JAVA/JavaSeProMax/file-io-app/src/com/showguan/FileDemo/test.txt"); // 创建File对象,表示文件夹JavaSeProMax的绝对路径 File f2 = new File("D:/JAVA"); // 创建File对象,表示不存在的文件路径t.txt File f3 = new File("D:/JAVA/t.txt"); // 输出文件f1的长度(字节数) System.out.println(f1.length()); // 输出文件夹f2的长度,由于f2表示文件夹,而不是文件,因此返回值没有意义 System.out.println(f2.length()); // 输出文件f3的长度,由于文件路径不存在,因此返回0 System.out.println(f3.length()); // 检查文件f3是否存在,返回false,因为文件路径不存在 System.out.println(f3.exists()); // 创建File对象,表示相对路径下的文件test.txt // 相对路径默认从当前工程的根目录开始寻找,因此文件路径不存在 File f4 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\test.txt"); // 检查文件f4是否存在,返回false,因为文件路径不存在 System.out.println(f4.exists()); // 输出文件f4的长度,由于文件路径不存在,因此返回0 System.out.println(f4.length()); } public static void main(String[] args) { // 创建File对象,表示相对路径下的文件test.txt File f1 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\test.txt"); // 创建File对象,表示文件夹file-io-app的路径 File f2 = new File("file-io-app"); // 检查文件f1是否存在,返回true,因为文件路径存在 System.out.println(f1.exists()); // 检查f1是否表示一个文件,返回true System.out.println(f1.isFile()); // 检查f1是否表示一个文件夹,返回false System.out.println(f1.isDirectory()); // 检查f2是否表示一个文件夹,返回true System.out.println(f2.isDirectory()); // 获取文件f1的名称,输出test.txt System.out.println(f1.getName()); // 获取文件f1的长度(字节数) System.out.println(f1.length()); // 获取文件f1最后修改时间 long time = f1.lastModified(); // 格式化最后修改时间并输出 SimpleDateFormat sdf = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss"); System.out.println(sdf.format(time)); // 获取文件f1的路径(创建时使用的路径),输出相对路径file-io-app\src\com\showguan\FileDemo\test.txt System.out.println(f1.getPath()); // 获取文件f1的绝对路径,输出完整的绝对路径 System.out.println(f1.getAbsolutePath()); } 创建文件、目录 import java.io.File; import java.io.IOException; public static void main(String[] args) throws IOException { // 创建File对象,表示新文件test2.txt的路径 File f1 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\test2.txt"); // 创建新文件test2.txt,如果文件不存在则创建并返回true,否则返回false System.out.println(f1.createNewFile()); // 创建File对象,表示新文件夹aaa的路径 File f2 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\aaa"); // 创建新文件夹aaa,如果文件夹不存在则创建并返回true,否则返回false System.out.println(f2.mkdir()); // 创建File对象,表示新文件夹路径a\b\c File f3 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\a\\b\\c"); // 创建新文件夹路径a\b\c,如果路径中的文件夹不存在则递归创建,创建成功返回true,否则返回false System.out.println(f3.mkdirs()); // 删除文件test2.txt,删除成功返回true,否则返回false System.out.println(f1.delete()); // 删除文件夹a,由于文件夹非空,因此删除失败返回false File f4 = new File("file-io-app\\src\\com\\showguan\\FileDemo\\a"); System.out.println(f4.delete()); } public static void main(String[] args) { // 遍历方法,只能遍历一级文件 File f1 = new File("D:\\JAVA"); // 获取D:\JAVA目录下的所有一级文件名 String[] names = f1.list(); // 遍历打印所有一级文件名 for (String name : names) { System.out.println(name); } // 获取D:\JAVA目录下的所有一级文件对象 File f2 = new File("D:\\JAVA"); // 获取D:\JAVA目录下的所有一级文件对象 File[] files = f2.listFiles(); // 遍历打印所有一级文件对象的绝对路径 for (File file : files) { System.out.println(file.getAbsoluteFile()); } // 尝试获取不存在的目录的一级文件对象,返回null File f3 = new File("D:\\JAVA1"); System.out.println(f3.listFiles()); // null // 尝试获取非文件夹的一级文件对象,返回null File f4 = new File("D:\\JAVA\\test1"); // 因为f4代表的路径不是文件夹,因此listFiles()返回null File[] files4 = f4.listFiles(); System.out.println(Arrays.toString(files4)); // null } 递归查找 public static void main(String[] args) throws IOException { searchFile(new File("D:\\文档"), "23暑期青训营笔记"); // 调用搜索文件的方法 } /** * 递归搜索指定目录下的文件,并打印找到的文件的绝对路径,并使用系统默认程序打开该文件。 * @param dir 要搜索的目录 * @param fileName 要搜索的文件名 * @throws IOException 如果发生I/O错误 */ public static void searchFile(File dir, String fileName) throws IOException { // 如果目录为空、不存在或者是文件,则直接返回 if(dir==null || !dir.exists() || dir.isFile()){ return ; } // 获取目录下的所有文件和子目录 File[] files = dir.listFiles(); // 如果目录下存在文件 if(files!=null && files.length>0){ // 遍历目录下的所有文件和子目录 for (File file : files) { // 如果是文件 if(file.isFile()){ // 判断文件名是否包含指定的文件名 if(file.getName().contains(fileName)){ System.out.println("找到了!" + file.getAbsoluteFile()); // 打印找到的文件的绝对路径 Runtime runtime = Runtime.getRuntime(); runtime.exec(file.getAbsolutePath()); // 使用系统默认程序打开该文件 return; // 找到文件后直接返回 } }else{ // 如果是目录,则递归调用搜索文件的方法 searchFile(file, fileName); } } } } 递归删除 public static void main(String[] args) throws IOException { File file = new File("D:\\JAVA\\test1\\test"); // 要删除的目录的路径 deleteDir(file); // 调用删除目录的方法 } /** * 递归删除目录及其所有子目录和文件。 * @param dir 要删除的目录 */ public static void deleteDir(File dir){ // 如果目录为空或者不存在,则直接返回 if(dir==null || !dir.exists()){ return ; } // 如果是文件,则直接删除并返回 if(dir.isFile()){ dir.delete(); return; } // 获取目录下的所有文件和子目录 File[] files = dir.listFiles(); // 如果目录为空,则直接返回 if(files==null){ return; } // 遍历目录下的所有文件和子目录 for (File file : files) { if(file.isFile()){ // 如果是文件,则直接删除 file.delete(); } deleteDir(file); // 递归删除子目录 } dir.delete(); // 删除当前目录 } 字符集 UTF-32 ...

2024-04-19 · 17 分钟 · 8234 字 · updated: 2024-04-19 · ShowGuan

LeetCode笔记

LeetCode笔记 目标:2500分 HOT100 301. 删除无效的括号 题目大意: 给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 ...

2024-04-17 · 26 分钟 · 12788 字 · updated: 2024-10-06 · ShowGuan

Linux

Linux Linux文件系统 FHS3.0(File system Hierarchy Standard) / etc 配置文件 bin 必要命令 usr 二级目录 home 家目录 var 动态数据 VFS虚拟文件系统 内核层抽象出通用的文件系统接口 支持文件、网络、特殊文件系统 ...

2024-04-17 · 17 分钟 · 8433 字 · updated: 2024-04-17 · ShowGuan

LeetCode每日一题(202404)

每日一题(202404) 2009. 使数组连续的最少操作数 题意:给定一个可能有重复元素的数组,可以修改数组中值为任意其他值,问使数组连续的最小操作数。 思路:由于只能改动元素,所以最后的元素个数不变,去重后,枚举每个值作为左端点,则右端点为nums[i]+n-1, 用双指针计算在区间内的元素个数即为可以保留的数字,其他数字修改元素值填满空隙即可。 ...

2024-04-17 · 12 分钟 · 5983 字 · updated: 2024-04-22 · ShowGuan

LeetCode每日一题(202404)

每日一题(202404) 2009. 使数组连续的最少操作数 题意:给定一个可能有重复元素的数组,可以修改数组中值为任意其他值,问使数组连续的最小操作数。 思路:由于只能改动元素,所以最后的元素个数不变,去重后,枚举每个值作为左端点,则右端点为nums[i]+n-1, 用双指针计算在区间内的元素个数即为可以保留的数字,其他数字修改元素值填满空隙即可。 ...

2024-04-17 · 11 分钟 · 5131 字 · updated: 2024-04-22 · ShowGuan

剑指Offer

剑指Offer 数据流中的中位数 用两个堆模拟, 左边大顶堆,右边小顶堆,则两个堆顶是最中间的数字。 添加数字时: 如果输入的是第奇数个(比如第一个,则N初始化为0,插入后N为1,代表一共有一个数字),则先插入大顶堆,然后把堆顶插入小顶堆。保证小顶堆的任意一个值都比大顶堆大。 同样,如果输入的是第偶数个(第二个),则先插入小顶堆,然后将小顶堆最小值插入大顶堆。同样是保证小顶堆的任意一个值都比大顶堆大。 至于先插入哪一个堆是没有关系的,只要保证交替插入不同的堆即可,并且要确保边界问题(比如在奇数个元素的中位数, 只有一个数据时应返回先插入的堆顶值, 否则堆为空会报错)。 ...

2024-04-17 · 5 分钟 · 2475 字 · updated: 2024-04-22 · ShowGuan

LeetCode Hot 100 精练🥸(1)

LeetCode Hot 100 精练🥸(1) 记忆中的东西一定会消退,真正留下的才是学到的,一定要及时回顾。 题目表 (序号) 标题 (1) 160. 相交链表 (2) 236. 二叉树的最近公共祖先 (3) 234. 回文链表 (4) 739. 每日温度 (5) 226. 翻转二叉树 (6) 221. 最大正方形 (7) 215. 数组中的第K个最大元素 (8) 208. 实现 Trie (前缀树) (9) 207. 课程表 (10) 206. 反转链表 (11) 200. 岛屿数量 (12) 198. 打家劫舍 (13) 169. 多数元素 (14) 238. 除自身以外数组的乘积 (15) 155. 最小栈 (16) 152. 乘积最大子数组 (17) 148. 排序链表 (18) 146. LRU 缓存 (19) 142. 环形链表 II (20) 141. 环形链表 (21) 139. 单词拆分 (22) 136. 只出现一次的数字 (23) 647. 回文子串 (24) 128. 最长连续序列 (25) 124. 二叉树中的最大路径和 (26) 322. 零钱兑换 (27) 494. 目标和 (28) 461. 汉明距离 (29) 448. 找到所有数组中消失的数字 (30) 438. 找到字符串中所有字母异位词 (31) 437. 路径总和 III (32) 416. 分割等和子集 (33) 406. 根据身高重建队列 (34) 399. 除法求值 (35) 394. 字符串解码 (36) 347. 前 K 个高频元素 (37) 338. 比特位计数 (38) 337. 打家劫舍 III (39) 121. 买卖股票的最佳时机 (40) 312. 戳气球 (41) 309. 买卖股票的最佳时机含冷冻期 (42) 301. 删除无效的括号 (43) 300. 最长递增子序列 (44) 297. 二叉树的序列化与反序列化 (45) 287. 寻找重复数 (46) 283. 移动零 (47) 279. 完全平方数 (48) 253. 会议室 II (49) 240. 搜索二维矩阵 II (50) 239. 滑动窗口最大值 (51) 22. 括号生成 (52) 49. 字母异位词分组 (53) 48. 旋转图像 (54) 46. 全排列 (55) 42. 接雨水 (56) 39. 组合总和 (57) 543. 二叉树的直径 (58) 34. 在排序数组中查找元素的第一个和最后一个位置 (59) 33. 搜索旋转排序数组 (60) 32. 最长有效括号 (61) 31. 下一个排列 (62) 538. 把二叉搜索树转换为累加树 (63) 23. 合并 K 个升序链表 (64) 560. 和为 K 的子数组 (65) 21. 合并两个有序链表 (66) 20. 有效的括号 (67) 19. 删除链表的倒数第 N 个结点 (68) 17. 电话号码的字母组合 (69) 15. 三数之和 (70) 11. 盛最多水的容器 (71) 10. 正则表达式匹配 (72) 5. 最长回文子串 (73) 4. 寻找两个正序数组的中位数 (74) 3. 无重复字符的最长子串 (75) 2. 两数相加 (76) 79. 单词搜索 (77) 114. 二叉树展开为链表 (78) 621. 任务调度器 (79) 617. 合并二叉树 (80) 105. 从前序与中序遍历序列构造二叉树 (81) 104. 二叉树的最大深度 (82) 102. 二叉树的层序遍历 (83) 101. 对称二叉树 (84) 98. 验证二叉搜索树 (85) 96. 不同的二叉搜索树 (86) 94. 二叉树的中序遍历 (87) 85. 最大矩形 (88) 84. 柱状图中最大的矩形 (89) 1. 两数之和 (90) 78. 子集 (91) 76. 最小覆盖子串 (92) 75. 颜色分类 (93) 72. 编辑距离 (94) 70. 爬楼梯 (95) 581. 最短无序连续子数组 (96) 64. 最小路径和 (97) 62. 不同路径 (98) 56. 合并区间 (99) 55. 跳跃游戏 (100) 53. 最大子数组和 (1)160. 相交链表 题目大意: ...

2024-04-17 · 20 分钟 · 9650 字 · updated: 2025-12-20 · ShowGuan

Java20天速成——进阶课程(2)

Java20天速成——进阶课程(2) 正则表达式 符号 含义 举例 [] 匹配方括号内的任一字符 [abc] ^ 匹配除指定字符外的任意字符 [^abc] && 匹配两个字符集的交集,需作为整体出现 [a-z&&m-p] . 匹配除换行符外的任意字符 a.b (匹配 “a” 后接任意字符,再接 “b”) \ 转义字符,用于匹配特殊字符 \\d \\d 匹配数字 0-9 \\d+ \\D 匹配非数字字符 \\D+ \\s 匹配空白字符 \s匹配空格、制表符、换行符等等 \\S 匹配非空白字符 \\S+ (匹配非空白字符序列) \\w 匹配单词字符 [a-zA-Z_0-9] \\W 匹配非单词字符 [^\w] * 匹配前面的元素零次或多次,即可有可无 a*b (匹配 “b”、“ab”、“aab”、等等) ? 匹配前面的元素零次或一次,即可有可无 colou?r (匹配 “color” 或 “colour”) () 分组,将其中的字符视为一个单元 a(bc)+ \f 匹配换页符 \f | `|` | 或,用于匹配多个模式中的任意一个 | `ab\|AB` | public static void method1() { // 给定的字符串包含了电话号码和邮箱地址的信息 String data = " 来黑马程序员学习Java,\n" + " 电话:1866668888,18699997777\n" + " 或者联系邮箱:boniu@itcast.cn,\n" + " 座机电话:01036517895,010-98951256\n" + " 邮箱:bozai@itcast.cn,\n" + " 邮箱:dlei0009@163.com,\n" + " 热线电话:400-618-9090 ,400-618-4000,4006184000,4006189090"; // 定义正则表达式来匹配电话号码和邮箱地址 String regex = "(1[3-9]\\d{9})|" + "(0\\d{2,9}-?\\d{7,18})|" // 匹配固定电话号码,包括区号和分机号 + "(\\w{2,}@\\w{2,20}(\\.\\w{2,10}){1,2})|" // 匹配邮箱地址 + "(400-?\\d{3,7}-?\\d{3,7})"; // 匹配400电话号码,包括可能的分机号 // 编译正则表达式 Pattern pattern = Pattern.compile(regex); // 创建匹配器对象 Matcher matcher = pattern.matcher(data); // 循环查找匹配项并打印 while(matcher.find()){ String res = matcher.group(); // 获取匹配到的字符串 System.out.println(res); } } String s1 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴"; System.out.println(s1.replaceAll("\\w+", "-")); String s2 = "我我我喜欢编编编编编编编编编编编编程程程"; System.out.println(s2.replaceAll("(.)\\1+", "$1")); String s3 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴"; String[] names = s3.split("\\w+"); System.out.println(Arrays.toString(names)); 异常 Error: 代表的系统级别错误(属于严重问题), 也就是说系统一旦出现问题,sun公司会把这些问题封装成Error对象给出了,即Error是Sun公司自己用的,而不是给程序员用的 ...

2024-04-16 · 24 分钟 · 11670 字 · updated: 2024-04-15 · ShowGuan

LeetCode周赛240414

LeetCode第 393 场周赛 第三题3116. 单面值组合的第 K 小金额 题目大意: 给定一个整数数组coins表示不同面额的硬币,另给定一个整数k。你有无限量的每种面额的硬币,但是,你不能组合使用不同面额的硬币。要求返回使用这些硬币能制造的第kth小金额。 ...

2024-04-16 · 3 分钟 · 1109 字 · updated: 2024-04-16 · ShowGuan

Java20天速成——进阶课程(1)

进阶课程(1) OOP static 静态, 可以修饰成员变量,成员方法 成员变量按照有无static修饰,分为两种 类变量 : 有static修饰,属于类,在计算机里只有一份,会被类的全部对象共享 实例变量(对象的变量):无static修饰,属于每个对象 // 类变量推荐赋值方式 Student.name = "Java"; // 不推荐赋值方式 Student s1 = new Student(); s1.name = "True Java"; Student s2 = new Student(); s2.name = "False Java"; System.out.println(s2.name); //False Java System.out.println(Student.name); //False Java // 成员变量 s1.age = 25; s2.age = 15; System.out.println(s1.age); //25 System.out.println(s2.age); //15 //User类 public static int number; public User(){ number+=1; //类中访问自己的变量可以不写 User(). } //Test类 public static void main(String[] args) { User u1 = new User(); User u2 = new User(); User u3 = new User(); System.out.println(User.number); //3 } 类方法:有static修饰的成员方法,属于类。 实例方法:无static修饰的成员方法,属于对象 //Student double score; public static void printHelloWorld(){ System.out.println("Hello World"); System.out.println("Hello World"); } public void printPass(){ System.out.println("成绩:" + (score >= 60 ? "及格" : "不及格")); } //Test Student.printHelloWorld();//Hello World Hello World Student s = new Student(); s.score = 100; s.printPass(); //成绩:及格 类方法的常见应用案例 类方法最常见的应用场景是做工具类 工具类:工具类中的方法都是一些类方法,每个方法都是用来完成一个功能的,工具类是给开发人员共同使用的 ...

2024-04-15 · 23 分钟 · 11232 字 · updated: 2024-04-15 · ShowGuan

Java20天速成——基础课程

JAVA 20天速成 有志者事竟成 没有全身心的投入和检验,是学不到东西的。 自欺欺人和眼高手低毫无作用。 JAVA背景信息 JAVA是一门高级编程语言。 ...

2024-04-15 · 24 分钟 · 11926 字 · updated: 2024-10-12 · ShowGuan

Acwing算法学习

Acwing算法学习 [TOC] 第一章 课上:学思想 课下:背代码 题目,一道题写好几遍 理解没有任何意义,体力活+脑力活 记忆力 毅力/自制力 沉下心背东西 快速排序算法模板 —— 模板题 AcWing 785. 快速排序 分治 ...

2024-04-09 · 28 分钟 · 13857 字 · updated: 2024-04-09 · ShowGuan

算法笔记(二)——数据结构(Python实现)

算法笔记(二)——数据结构(Python实现) 数据结构 单链表 N = int(1e5+10) e=[0]*N ne=[0]*N head=-1 idx=1 def insert(x): global idx, head e[idx]=x ne[idx]=head head=idx idx+=1 def add(k, x): global idx e[idx]=x ne[idx]=ne[k] ne[k]=idx idx+=1 def remove(k): global idx, head if k==0: head = ne[head] else: ne[k]=ne[ne[k]] n = int(input()) for _ in range(n): s = input().split() op=s[0] if op=='H': insert(int(s[1])) elif op=='I': add(int(s[1]), int(s[2])) else: remove(int(s[1])) i=head while i!=-1: print(e[i], end=' ') i=ne[i] 双链表 N = int(1e5+10) e=[0]*N l=[0]*N r=[0]*N idx=0 def init(): global idx r[2]=1 l[1]=2 idx=3 def insert(k, x): global idx e[idx]=x l[idx]=k r[idx]=r[k] l[r[k]]=idx r[k]=idx idx+=1 def remove(k): l[r[k]]=l[k] r[l[k]]=r[k] init() m=int(input()) for _ in range(m): s=input().split() if s[0]=='L': x=int(s[1]) insert(2,x) elif s[0]=='R': x=int(s[1]) insert(l[1],x) elif s[0]=='D': k=int(s[1])+2 remove(k) elif s[0]=='IL': k=int(s[1])+2 x=int(s[2]) insert(l[k],x) elif s[0]=='IR': k=int(s[1])+2 x=int(s[2]) insert(k,x) i=2 while i!=0: if i==2 or i==1: i=r[i] continue print(e[i],end=" ") i=r[i] 栈 N = int(1e5+10) # 假设N的值为100 stk = [0] * N tt = 0 # 向栈顶插入一个数 tt += 1 stk[tt] = x # 从栈顶弹出一个数 tt -= 1 # 栈顶的值 stk[tt] # 判断栈是否为空 if tt > 0: pass 队列 N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = -1 # 向队尾插入一个数 tt += 1 q[tt] = x # 从队头弹出一个数 hh += 1 # 队头的值 q[hh] # 判断队列是否为空 if hh <= tt: pass N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = 0 # 向队尾插入一个数 q[tt] = x tt += 1 if tt == N: tt = 0 # 从队头弹出一个数 hh += 1 if hh == N: hh = 0 # 队头的值 q[hh] # 判断队列是否为空 if hh != tt: pass 单调栈 tt = 0 stk = [0] * (n + 1) for i in range(1, n + 1): while tt and check(stk[tt], i): tt -= 1 stk[tt + 1] = i tt += 1 单调队列 n = 10 # 假设n的值为10 hh = 0 tt = -1 q = [0] * n for i in range(n): while hh <= tt and check_out(q[hh]): hh += 1 while hh <= tt and check(q[tt], i): tt -= 1 q[tt + 1] = i tt += 1 N = int(1e6+10) q=[0 for _ in range(N)] n,k=map(int, input().split()) a=[0]+[int(x) for x in input().split()] hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] >= a[i]: tt-=1 tt+=1 q[tt]=i if i >= k: print(a[q[hh]], end=" ") print() hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] <= a[i]: tt-=1 tt+=1 q[tt]=i if i>=k: print(a[q[hh]], end=" ") KMP m = len(p) # 假设p为模板串,长度为m n = len(s) # 假设s为模式串,长度为n ne = [0] * (m + 1) # 初始化ne数组 # 求Next数组 j = 0 for i in range(2, m + 1): while j and p[i] != p[j + 1]: j = ne[j] if p[i] == p[j + 1]: j += 1 ne[i] = j # 匹配 j = 0 for i in range(1, n + 1): while j and s[i] != p[j + 1]: j = ne[j] if s[i] == p[j + 1]: j += 1 if j == m: j = ne[j] # 匹配成功后的逻辑 n = int(input()) p = ' ' + input() m = int(input()) s = ' ' + input() ne = [0]*(n+1) j = 0 for i in range(2, n+1): while j and p[i]!=p[j+1]: j = ne[j] if p[i]==p[j+1]: j += 1 ne[i] = j j = 0 res = [] for i in range(1, m+1): while j and s[i]!=p[j+1]: j = ne[j] if s[i]==p[j+1]: j += 1 if j==n: res.append(i-j) j = ne[j] print(*res, sep=' ') Z函数 def z_function(s): n = len(s) z = [0] * n l, r = 0, 0 for i in range(1, n): if i <= r and z[i - l] < r - i + 1: z[i] = z[i - l] else: z[i] = max(0, r - i + 1) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] - 1 > r: l = i r = i + z[i] - 1 return z Tire N = 100010 son = [[0] * 26 for _ in range(N)] cnt = [0] * N idx = 0 # 0号点既是根节点,又是空节点 # son[][]存储树中每个节点的子节点 # cnt[]存储以每个节点结尾的单词数量 # 插入一个字符串 def insert(s): global idx p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: idx += 1 son[p][u] = idx p = son[p][u] cnt[p] += 1 # 查询字符串出现的次数 def query(s): p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: return 0 p = son[p][u] return cnt[p] 马拉车(字符串回文串算法) class Solution: # 推荐教学视频 :https://www.bilibili.com/video/BV1Sx4y1k7jG/?spm_id_from=333.337.search-card.all.click&vd_source=a4a2b56f746715b34521bfb853094cf4 def longestPalindrome(self, s: str) -> str: s = '#' + '#'.join(list(s)) + '#' n = len(s) p = [0]*n #每个点的 最长回文字串 能到的 两侧长度 c, r = 0, 0 # 右边能到达最远的蘑菇的位置 和 其最右边能达到的位置 for i in range(n): if i<=r: p[i] = min(r-i, p[c + c-i]) # 由已知条件得到当前位置能达到的最大右侧距离( 需要取min(镜像位置的值, 当前最大蘑菇能覆盖到的最大值) ) while i+p[i]+1 < n and s[i-p[i]-1] == s[i+p[i]+1]: p[i]+=1 if p[i]+i > r: r = p[i] + i c = i ma = max(p) idx = p.index(ma) return s[idx-ma+1:idx+ma+1:2] 并查集 N = 1000005 # 假设N的值为1000005 p = [0] * N # 初始化p数组 # 返回x的祖宗节点 def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] ''' 非递归写法 def find(x): while p[x]!=x: p[x] = p[p[x]] x = p[x] return x ''' # 初始化,假定节点编号是1~n for i in range(1, n + 1): p[i] = i # 合并a和b所在的两个集合 p[find(a)] = find(b) 维护size信息 ...

2024-04-09 · 15 分钟 · 7176 字 · updated: 2024-04-09 · ShowGuan

算法笔记(三)——图论(Python实现)

算法笔记(三)——图论(Python实现) 图论 树的存储 邻接矩阵 # 创建一个二维列表表示邻接矩阵 n = 10 # 顶点数量 g = [[0] * n for _ in range(n)] # 添加一条边a->b def add_edge(a, b): g[a][b] = 1 # 初始化 g = [[0] * n for _ in range(n)] 邻接表 # 创建一个列表表示邻接表 n = 10 # 顶点数量 h = [-1] * n e = [0] * n ne = [0] * n idx = 0 # 添加一条边a->b def add_edge(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 h = [-1] * n 树和图的存储 # 邻接表表示的图 N = 100010 # 根据具体需求设置合适的最大节点数量 # 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点 h = [-1] * N # 存储边的目标节点 e = [0] * N # 存储下一条边的索引 ne = [0] * N # 边的索引 idx = 0 # 添加一条边a->b def add(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 for i in range(N): h[i] = -1 树和图的遍历 DFS def dfs(u): st[u] = True i = h[u] while i!=-1: j = e[i] if not st[j]: dfs(j) i = ne[i] BFS from collections import deque q = deque() st[1] = True q.append(1) while q: t = q.popleft() i = h[t] while i!=-1: j=e[i] if not st[j]: st[j] = True q.append(j) i=ne[i] 拓扑排序 from sys import stdin from collections import deque input = lambda:stdin.readline().strip() def topsort(): q = deque() res = [] for i in range(1, n+1): if ind[i]==0: res.append(i) q.append(i) while q: u = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append(v) res.append(v) return res n = int(input()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(1, n+1): a = list(map(int, input().split())) for j in range(len(a)-1): g[i].append(a[j]) ind[a[j]]+=1 res = topsort() print(*res, sep=' ') 奖金 from sys import stdin from collections import deque def topsort(): res = [] q = deque() ans = 0 for i in range(1, n+1): if ind[i]==0: res.append(i) q.append((i, 100)) ans += 100 while q: u, m = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append((v, m+1)) res.append(v) ans += m+1 if len(res)==n: print(ans) else: print("Poor Xed") n, m = map(int, input().split()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) ind[a] += 1 g[b].append(a) topsort() LCA def lca(x,y): if dep[x] < dep[y]: x,y = y,x d = dep[x]-dep[y] while d: # 循环直到深度差为 0 v = d & -d # 获取 d 的最低位的 1 所在的位置 i = v.bit_length() - 1 # 计算最低位的位置索引 x = fa[i][x] # 将节点 x 上移到和节点 y 同一深度 d -= v # 更新深度差 if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] # 初始化深度以及父节点信息 dep[x]=dep[val]+1 dep[y]=dep[val]+1 fa[0][x] = val fa[0][y] = val for k in range(K-1): fa[k+1][x] = fa[k][fa[k][x]] # 自己的第2^(1+1)级父亲即为 自己的第2^(1)级父亲 的第2^(1)级父亲 fa[k+1][y] = fa[k][fa[k][y]] 祖孙询问 from sys import stdin from collections import deque, defaultdict from math import inf K = 17 N = int(4*10e4) + 10 dep = [inf]*(N) fa = [[0]*N for _ in range(K)] def bfs(): dep[0] = 0; dep[root] = 1 q = deque([root]) while q: u = q.popleft() for v in g[u]: if dep[v] > dep[u] + 1: dep[v] = dep[u] + 1 q.append(v) fa[0][v] = u for k in range(1, K-1): fa[k][v] = fa[k-1][fa[k-1][v]] def lca(x, y): if dep[x] < dep[y]: x, y = y, x d = dep[x] - dep[y] while d: v = d & -d i = v.bit_length() - 1 x = fa[i][x] d -= v if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] n = int(input()) g = defaultdict(list) for i in range(n): a, b = map(int, input().split()) if b==-1: root = a else: g[a].append(b) g[b].append(a) bfs() # print(dep) m = int(input()) for i in range(m): x, y = map(int, input().split()) res = lca(x, y) if res == x and res != y: print(1) elif res == y and res != x: print(2) else: print(0) 最短路 单元最短路 ...

2024-04-09 · 17 分钟 · 8077 字 · updated: 2024-04-09 · ShowGuan

算法笔记(四)——数学(Python实现)

算法笔记(四)——数学(Python实现) 数学 试除法判定质数 def check(x): # 判定 if x<2: return False for i in range(2, int(x**0.5)+1): if x%i==0: return False return True n = int(input()) for i in range(n): x = int(input()) if check(x): print("Yes") else: print("No") 试除法分解质因数 def get(x): #分解 for i in range(2, int(x**0.5)+1): if x%i==0: cnt=0 while x%i==0: x//=i cnt+=1 print(i, cnt, sep=' ') if x>1: print(x, 1, sep=' ') n = int(input()) for i in range(n): x = int(input()) get(x) print() 线性筛法求素数 N = int(1e6+10) primes = [] st = [False]*N def get(n): for i in range(2, n+1): if not st[i]: primes.append(i) for j in range(len(primes)): if i*primes[j]>n: break st[i*primes[j]]=True if i%primes[j]==0: break n = int(input()) get(n) print(len(primes)) 朴素筛法求素数 N = 1000005 # 根据需要修改 primes = [] # 存储所有素数 st = [False] * N # st[x]存储x是否被筛掉 # 筛素数函数 def get_primes(n): global primes global st for i in range(2, n + 1): if not st[i]: primes.append(i) for j in range(i, n + 1, i): st[j] = True # Example usage: # get_primes(100) # print(primes) 试除法求所有约数 def get(x): res = [1] for i in range(2, int(x**0.5)+1): if x%i==0: res.append(i) if i!=x//i: res.append(x//i) if x>1: res.append(x) return sorted(res) n = int(input()) for i in range(n): x = int(input()) res = get(x) print(*res) 约数个数和约数之和 如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1) 约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck) 约数之和 题目大意:给定两个自然数 A 和 B,定义 S 为 A*B 的所有约数之和。求 S mod 9901 的值。 ...

2024-04-09 · 4 分钟 · 1837 字 · updated: 2024-04-09 · ShowGuan
« 上一页  下一页  »
© 2026 Kennem's Blog · Powered by Hugo & PaperMod
👤 Visitors: 👀 Views: