# algorithm **Repository Path**: xliang99/algorithm ## Basic Information - **Project Name**: algorithm - **Description**: 算法学习 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-09-20 - **Last Updated**: 2025-07-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## 知识点 1. 位运算 - 左移：<<，移动后右侧补0 - 无符号右移：>>>，移位后高位补0 - 有符号右移：>>，移位后高位用符号位补 - 按位与：&，全1为1，有0为0 - 按位或：|，有1为1，全0为0 - 按位异或：^，相同为0，不同为1，无进位相加 - a^a = 0 - a^0= a - 按位取反：~，1变0，0变1 - 提取出二进制中最右侧的1：a & -a a & (~a + 1) 2. 二叉树 - 满二叉树：除了最后一层节点外，每一层的所有节点都有两个子节点 - 完全二叉树：要么是满的，要么是从左到右在依次变满的路上，左子树的高度最多比右子树的高度大1 - 二叉搜索树：在整棵树上，对于任意一颗子树，它的左子树上的最大值一定小于该子树根节点，它的右子树上的最小值一定大于该子树根节点 - 平衡二叉树：是一颗高度平衡的二叉搜索树，在整棵树上，对于任意一颗子树，它的左右子树的高度差不超过1 - 红黑树：弱平衡二叉搜索树 + 每个节点要么是黑的，要么是红的 + 根节点是黑的 + 如果一个节点是红的，则它的两个子节点都是黑的 + 每个叶节点都是黑的 - 堆：是完全二叉树，也是平衡二叉树 - 前缀树 3. 动态规划 - 记忆化搜索，缓存法 - 尝试模型：从左到右尝试模型、范围尝试模型、样本对应模型 4. ## 题目 1. 一个数组中有一种数出现了奇数次，其它数都出现了偶数次，找到并打印这种数 2. 一个数组中有两种数出现了奇数次，其它数都出现了偶数次，找到并打印这两种数 3. 一个数组中有一种数出现了K次，其它数都出现了M次，已知M > 1, K < M，找到出现了K次的数，要求额外的空间复杂度为O(1)，时间复杂度为O(N) 4. 等概览随机数 - 等概率生成0~N随机数 - 给定1-5等概率随机函数，加工出1~7等概率随机函数 - 给定a~b等概率随机函数，加工出c~d等概率随机函数 - 把不等概率随机函数变成等概率随机函数 - 使用等概率随机函数生成随机数组 5. 基本排序 - 冒泡排序 - 选择排序 - 插入排序 - 希尔排序 - 基数排序 - 计数排序 - 桶排序 - 快速排序，荷兰国旗问题（小于的放左边，大于的放右边，等于的放中间），作为快排的一个子问题 - 归并排序 6. 在有序数组中找到num 7. 在有序数组中找到>=num最左的位置 8. 在有序数组中找到<=num最右的位置 9. 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回 10. 实现单链表、双链表 11. 实现栈：使用数组、使用单链表、使用双链表 12. 实现队列、双端队列：使用数组、使用单链表、使用双链表 13. 实现带有getMin功能的栈 14. 反转单链表、反转双链表 15. K个节点的组内逆序调整，给定一个单链表的头节点head，和一个正数k，实现k个节点的小组内部逆序，如果最后一组不够k个就不调整 16. 使用两个栈实现队列 17. 使用两个队列实现栈 18. 两个链表相加 - 给定两个链表的头节点head1和head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表 - 例子 4 -> 3 -> 6 2 -> 5 -> 3，返回 6 -> 8 -> 9， 解释 634 + 352 = 986 19. 两个有序链表的合并 - 给定两个有序链表的头节点head1和head2 - 返回合并之后的大链表，要求依然有序 - 例子 1 -> 3 -> 3 -> 5 -> 7 2 -> 2 -> 3 -> 3-> 7 - 返回 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7 20. 合并多个有序链表，https://leetcode.com/problems/merge-k-sorted-lists 21. 输入链表头节点，奇数长度返回中点，偶数长度返回上中点 22. 输入链表头节点，奇数长度返回中点，偶数长度返回下中点 23. 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个 24. 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个 25. 给定一个单链表的头节点head，请判断该链表是否为回文结构 26. 给定一个单链表的头节点head，给定一个整数n，将链表按n划分成左边n 27. 单链表相交问题 - 给定两个可能有环也可能无环的单链表，头节点head1和head2 - 请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交返回null - 要求如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1) 28. 能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉？ 29. 链表复制 - 单链表节点结构： - int value;Node next; Node rand; - rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null - 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制 - 返回复制的新链表的头节点，要求时间复杂度O(N)，额外空间复杂度O(1) 30. 归并排序非递归实现，A005中实现 31. 快速排序非递归实现，A005中实现 32. 给定一个数组arr，求数组的小和 - 在数组中，一个数左边比它小的数的总和叫该数的小和 - 所有数的小和累加起来叫数组的小和 33. 给定一个数组arr，求数组的降序对的总数量 - 在数组中任何一个前面的数a，和任何一个后面的数b，如果(a,b)是降序的就称为降序对 34. 给定数组arr，对于数组中任何一个数num，求有多少个（后面的数*2）依然小于num，返回总个数 35. 给定一个没有重复元素的有序数组arr和一个正整数k，请打乱该数组，要求打乱后的数组如果从新排好序每个元素移动的距离不能超过k 36. 给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在[lower，upper]范围上，https://leetcode.com/problems/count-of-range-sum 37. 实现堆 38. 已知一个几乎有序的数组，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，k相对于数组的长度来说是比较小的，请选择一个合适的排序策略，对这个数组进行排序 39. 线段最大重合问题 - 给定很多线段，每个线段都有两个数start、end，表示线段的开始位置和结束位置，左右都为闭区间 - 线段的开始和结束位置一定都是整数值 - 线段的重合区域的长度必须大于等于1 - 返回线段最多重合区域中包含了几条线段 40. 抽奖问题，在每个事件到来时都给购买次数最多的前k名用户颁奖 - 给定一个整型数组arr，一个布尔类型数组op，两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作，一对arr[i]、op[i]代表一个事件 - op[i] == true表示用户购买了一件商品，false表示退货了一件商品 - 得奖规则 + 如果某个用户购买商品数为0，但是又发送了退货事件，则认为该事件无效，得奖名单和上一个事件发生后一致 + 某用户发生购买商品事件，购买数+1，发生退货事件，购买数-1 + 每次都是最多k个用户得奖，可以小于k，k作为参数传入 + 得奖系统分为得奖区和候选区，任何用户只要购买数>0一定在这个区域中的一个 + 购买数最大的前k名用户进入得奖区 + 如果候选区购买最多的用户已经足以进入得奖区，则将替换得奖区中购买数最少的那个替换，如果最少的有个多个就替换最早进入得奖区的用户，如果候选区中购买最多的有多个，则机会给最早进入候选区的用户 + 候选区和得奖区是两套时间，从得奖区出来进入候选区则将得奖区时间删除，反之亦然 + 如果用户购买数为0，则从得奖区和候选区出来，时间全删除 - 遍历这两个数组，遍历一步得到一个得奖名单 41. 二叉树的先序、中序、后序遍历，递归序 42. 判断两颗树是否相同，https://leetcode.com/problems/same-tree 43. 判断一棵树是否是镜面树，https://leetcode.com/problems/symmetric-tree 44. 返回一棵树的最大深度，https://leetcode.com/problems/maximum-depth-of-binary-tree 45. 用先序数组和中序数组重建一棵树，https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 46. 二叉树按层遍历并收集节点，https://leetcode.com/problems/binary-tree-level-order-traversal-ii 47. 在二叉树上能否组成路径和，https://leetcode.com/problems/path-sum 48. 在二叉树上收集所有达标的路径和，https://leetcode.com/problems/path-sum-ii 49. 判断二叉树是否是平衡二叉树，https://leetcode.com/problems/balanced-binary-tree 50. 判断二叉树是否是搜索二叉树 51. 判断二叉树是不是满二叉树 52. 给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小 53. 给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点 54. 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离 55. 给定一棵二叉树的头节点head，和另外两个节点a和b，返回a和b的最低公共祖先 56. 求二叉树的最大宽度 57. 二叉树的序列化和反序列化 58. N叉树如何通过二叉树来序列化、并完成反序列化，https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree 59. 折纸问题 - 把一段纸条竖着放在桌子上，然后荣纸条的下边向上方对折1次，压出折痕后展开，此时折痕是凹下去的 - 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有3条折痕，从上到下依次是下折痕、下折痕和上折痕 - 给定一个输入参数N，代表纸条从下边向上方连续对折N次，从上到下打印折痕的方向 60. 给定二叉树中某个节点，返回该节点的后继节点，节点结构：value、left、right、parent 61. 求派对的最大快乐值 - 员工信息：快乐值：int happy； 下属：List subordinates - 公司的每个员工都符合类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树 - 树的头节点是公司唯一的老板，除老板之外的每个员工都有唯一的直接上级 - 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外每个员工都有一个或多个直接下级 - 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则： + 如果某个员工来了，那么这个员工的所有直接下级都不能来 + 派对的整体快乐值是所有到场员工快乐值的累加 + 你的目标是让派对的整体快乐值尽量大 - 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。 62. 给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中字典序最小的结果 63. 点灯问题 - 给定一个字符串str，只由'X'和'.'两种字符构成 - 'X'表示墙，不能放灯，也不需要点亮；'.'表示居民点，可以放灯，需要点亮 - 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮 - 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯 64. 切分金条问题 - 一块金条切成两半，是需要花费和长度数值一样的铜板 - 比如长度为20的金条，不管怎么切都要花费20个铜板，一群人想整分整块金条，怎么分最省铜板? - 例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。 - 如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板 - 但如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板 - 输入一个数组，返回分割的最小代价 65. 会议室问题 - 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲，给你每一个项目开始的时间和结束的时间 - 你来安排宣讲的日程，要求会议室进行的宣讲的场次最多，返回最多的宣讲场次 66. 项目收益问题 - 输入正数数组costs、正数数组profits、正数K和正数M - costs[i]表示i号项目的花费 - profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) - K表示你只能串行的最多做k个项目 - M表示你初始的资金 - 说明：每做完一个项目，马上获得的收益，可以支持你去做下一个项目，不能并行的做项目。 - 输出：最后获得的最大钱数 67. 一群朋友中，有几个不相交的朋友圈，https://leetcode.com/problems/friend-circles 68. 岛问题（递归解法 + 并查集解法 + 并行解法） - 给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量 69. 图的宽度优先遍历 70. 图的深度优先遍历 71. 三种方式实现图的拓扑排序 72. 最小生成树算法Kruskal，用并查集实现 73. 最小生成树算法Prim，用堆实现 74. 单元最短路径算法Dijkstra，用加强堆 75. 机器人从M移动到K位置的方法数 - 假设有排成一行的N个位置记为1~N，N一定大于或等于2 - 开始时机器人在其中的M位置上(M一定是1~N中的一个) - 如果机器人来到1位置，那么下一步只能往右来到2位置； - 如果机器人来到N位置，那么下一步只能往左来到N-1位置； - 如果机器人来到中间位置，那么下一步可以往左走或者往右走； - 规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种 - 给定四个参数 N、M、K、P，返回方法数 76. 纸牌博弈问题 - 给定一个整型数组arr，代表数值不同的纸牌排成一条线 - 玩家A和玩家B依次拿走每张纸牌 - 规定玩家A先拿，玩家B后拿 - 但是每个玩家每次只能拿走最左或最右的纸牌 - 玩家A和玩家B都绝顶聪明 - 请返回最后获胜者的分数 77. 背包问题 - 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值 - 给定一个正数bag，表示一个载重bag的袋子，装的物品不能超过这个重量 - 返回能装下的最大价值 78. 数字转字符问题 - 规定1和A对应、2和B对应、3和C对应...26和Z对应 - 那么一个数字字符串比如"111”就可以转化为："AAA"、"KA"和"AK" - 给定一个只有数字字符组成的字符串str，返回有多少种转化结果 79. 贴纸问题 - 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文 - arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来 - 返回需要至少多少张贴纸可以完成这个任务 - 例子：str= "babac"，arr = {"ba","c","abcd"} - ba + ba + c 3 abcd + abcd 2 abcd+ba 2 80. 最长公共子序列长度 - 给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度 - 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k” - 最长公共子序列是“123456”，所以返回长度6 81. 最长回文子序列长度 - 给定一个字符串str，返回这个字符串的最长回文子序列长度 - 比如 ： str = “a12b3c43def2ghi1kpm” - 最长回文子序列是“1234321”或者“123c321”，返回长度7 82. 象棋棋盘走马问题 - 整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置 - 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域 - 给你三个 参数 x，y，k - 返回“马”从(0,0)位置出发，必须走k步 - 最后落在(x,y)上的方法数有多少种? 83. 咖啡机问题 - 给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间 - 给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡 - 只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯 - 每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发 - 假设所有人拿到咖啡之后立刻喝干净， - 返回从开始等到所有咖啡机变干净的最短时间 - 三个参数：int[] arr、int N，int a、int b 84. 最小距离累加和问题 - 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角 - 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和 - 返回最小距离累加和 85. 货币问题 - arr是货币数组，其中的值都是正数。再给定一个正数aim。 - 每个值都认为是一张货币， - 即便是值相同的货币也认为每一张都是不同的， - 返回组成aim的方法数 - 例如：arr = {1,1,1}，aim = 2 - 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2 - 一共就3种方法，所以返回3 86. 货币问题2 - arr是货币数组，其中的值都是正数。再给定一个正数aim。 - 每个值都认为是一张货币， - 认为值相同的货币没有任何不同， - 返回组成aim的方法数 - 例如：arr = {1,2,1,1,2,1,2}，aim = 4 - 方法：1+1+1+1、1+1+2、2+2 - 一共就3种方法，所以返回3 87. 货币张数问题 - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。 - 每个值都认为是一种面值，且认为张数是无限的。 - 返回组成aim的方法数 - 例如：arr = {1,2}，aim = 4 - 方法如下：1+1+1+1、1+1+2、2+2 - 一共就3种方法，所以返回3 88. 醉汉存活问题 - 给定5个参数，N，M，row，col，k - 表示在N*M的区域上，醉汉Bob初始在(row,col)位置 - Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位 - 任何时候Bob只要离开N*M的区域，就直接死亡 - 返回k步之后，Bob还在N*M的区域的概率 89. 打怪兽问题 - 给定3个参数，N，M，K - 怪兽有N滴血，等着英雄来砍自己 - 英雄每一次打击，都会让怪兽流失[0~M]的血量 - 到底流失多少？每一次在[0~M]上等概率的获得一个值 - 求K次打击之后，英雄把怪兽砍死的概率 90. 货币数问题 - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。 - 每个值都认为是一种面值，且认为张数是无限的。 - 返回组成aim的最少货币数 91. 正数裂开问题 - 给定一个正数n，求n的裂开方法数， - 规定：后面的数不能比前面的数小 - 比如4的裂开方法有： - 1+1+1+1、1+1+2、1+3、2+2、4 92. 数组集合累加和问题 - 给定一个正数数组arr， - 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近 - 返回最接近的情况下，较小集合的累加和 93. 数组集合累加和问题2 - 给定一个正数数组arr，请把arr中所有的数分成两个集合 - 如果arr长度为偶数，两个集合包含数的个数要一样多 - 如果arr长度为奇数，两个集合包含数的个数必须只差一个 - 请尽量让两个集合的累加和接近 - 返回最接近的情况下，较小集合的累加和 94. N皇后问题 - N皇后问题是指在N*N的棋盘上要摆N个皇后， - 要求任何两个皇后不同行、不同列， 也不在同一条斜线上 - 给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1 - n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0 - n=8，返回92 95. 窗口内最大值或最小值更新结构的实现 - 假设一个固定大小为W的窗口，依次划过arr， - 返回每一次滑出状况的最大值 - 例如，arr = [4,3,5,4,3,3,6,7], W = 3 - 返回：[5,5,5,4,6,7] 96. 数组中达标子数组问题 - 给定一个整型数组arr，和一个整数num - 某个arr中的子数组sub，如果想达标，必须满足：sub中最大值 – sub中最小值 <= num， - 返回arr中达标子数组的数量 97. 加油站的良好出发点问题 98. 货币张数问题 - arr是货币数组，其中的值都是正数。再给定一个正数aim。 - 每个值都认为是一张货币， - 返回组成aim的最少货币数 - 因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了 99. 单调栈实现 100. 子数组最大值问题 - 给定一个只包含正数的数组arr，arr中任何一个子数组sub， - 一定都可以算出(sub累加和 )* (sub中的最小值)是什么， - 那么所有子数组中，这个值最大是多少？ 101. 给定一个非负数组arr，代表直方图，返回直方图的最大长方形面积 102. 给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的最大子矩形内部有多少个1（面积） 103. 给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量 104. 给定一个数组arr，返回所有子数组最小值的累加和 105. 斐波那契数列的矩阵快速幂模型，斐波那契数列矩阵乘法方式的实现 106. 台阶方法数问题，一个人可以一次往上迈1个台阶，也可以迈2个台阶，返回迈上N级台阶的方法数 107. 奶牛生小牛问题 - 第一年农场有1只成熟的母牛A，往后的每年： - 每一只成熟的母牛都会生一只母牛 - 每一只新出生的母牛都在出生的第三年成熟 - 每一只母牛永远不会死 - 返回N年后牛的数量 108. 达标的字符串 - 给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串 - 如果某个字符串，任何0字符的左边都有1紧挨着，认为这个字符串达标 - 返回有多少达标的字符串 109. 用1*2的瓷砖，把N*2的区域填满，返回铺瓷砖的方法数 110. KMP算法：给定两棵二叉树的头节点head1和head2，返回head1中是否有某个子树的结构和head2完全一样 111. KMP算法：判断str1和str2是否互为旋转字符串 112. Manacher算法：给定一个字符串str，只能在str的后面添加字符，想让str整体变成回文串，返回至少要添加几个字符 113. 不要用任何比较判断，返回两个数中较大的数 114. 给定一个参数N，返回1!+2!+3!+4!+…+N!的结果 115. 打印n层汉诺塔从最左边移动到最右边的全部过程（递归+非递归实现） 116. 打印一个字符串的全部子序列 117. 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列 118. 打印一个字符串的全部排列 119. 打印一个字符串的全部排列，要求不要出现重复的排列 120. 给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数