- 博客(216)
- 收藏
- 关注
RSS订阅原创 字典树3.输出频率前k的单词（字典树+treemap）
这个list简直了，很厉害。import java.util.*;public class Main { public static void main(String[] argc){ String[] reviews={"i love python and cpp", "i love java", "i love python more than go but go is nice as well", "python is great", "i love cpp", "i
2021-04-12 18:55:23
279
原创 双指针8.采购方案
在数组中选两个数字达到目的选两个数字如果是目标和，则可以直接移动指针，如果是一个小于等于目标和的数，则在lo到hi符合条件时，hi-lo个数都可以符合条件。class Solution { public int purchasePlans(int[] nums, int target) { Arrays.sort(nums); int lo=0; int hi=nums.length-1; int res=0; wh
2021-04-06 12:26:45
178
原创 森林中的兔子
有一个数组，其中是兔子说和它一样的有几只，相同的兔子说的一定相同，但说的相同的不一定是相同的兔子，因为不是所有的兔子都说话了，求最少的兔子数量。可以用贪心来求，将数组排序，如果此时为arr[i]，则有这种兔子的数量应该为arr[i]+1,那么可以跳过arr[i]+1这么多只兔子（如果后面数组也为arr[i]的话）和arr[i]不一样的话那就另外算。class Solution { public int numRabbits(int[] cs) { Arrays.sort(cs)
2021-04-06 11:45:06
170
原创 字符串可否拆成字典树中的单词
已知一个非空的字符串和一个包括非空字符的字典list，查找字符串可否根据空格被拆为list中的一个或者多个单词。1.首先第一反应是暴力/回溯，因为就是选字符串中的每个字母要不要，每次dfs都遍历此时的字符串，当此时的字符串前缀发现在字典中有，则dfs剩下的子串，否则一直往前，到最后都没有就返回false，如果在开始发现已经把字符串遍历完了，则返回true。但这样每个字符都要遍历，复杂度为O（nn）2.备忘录：记忆化回溯，把后缀的字符串结果保存到备忘录中，当需要调用的时候就直接返回值。3.动态规划用d
2021-04-05 21:23:45
106
原创 遍历3寻找重复子树653
寻找一颗二叉树中的重复子树，并且把重复子树加到一个list中，同一个子树只要加1次，所以遍历所有节点，然后将以它为根节点的子树加到map中，如果此时这个节点有一次，则把它加到结果列表中，如果有0次，则加到map中，超过1次就不处理。class Solution { Map<String,Integer> map=new HashMap<String,Integer>(); List<TreeNode> res=new ArrayList<TreeN
2021-04-04 14:32:12
59
原创 字符串-＞树 3.重建二叉树（已知中序后序）106
class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } public TreeNode build(int[] inorder, int lo1,int hi1,int[] postorder,int lo2,int hi2
2021-04-04 12:45:58
74
原创 递归6.最大二叉树654
利用递归来一层层的建造class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return core(nums,0,nums.length-1); } public TreeNode core(int[] nums,int lo,int hi){ if(lo>hi)return null; int maxIndex=-1;
2021-04-04 10:29:25
60
原创 有序链表转换二叉搜索树109
class Solution { public TreeNode sortedListToBST(ListNode head) { if(head==null)return null; return create(head,null); } public TreeNode create(ListNode left,ListNode right){ if (left == right) { return null
2021-04-03 23:08:04
64
原创 重排链表143
把链表排成l1 ln l2 ln-1的形式 需要把1,2,3,4,5,6 变成1,6,2,5,3,4相当于先找到链表中点，然后将后半段反转如果一开始为1,2,3,4,5,6则现在得到 1,2,3 和6,5,4 则进行归并即可。class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode
2021-04-03 22:01:03
62
原创 排序链表148
使用归并class Solution { public ListNode sortList(ListNode head) { if(head==null || head.next==null)return head; ListNode fast=head; ListNode slow=head; while(fast.next!=null && fast.next.next!=null){ fa
2021-04-03 21:50:46
53
原创 分割链表86
记得要最后把cur2的结尾清除为nullclass Solution { public ListNode partition(ListNode head, int x) { ListNode head1=new ListNode(); ListNode cur1=head1; ListNode head2=new ListNode(); ListNode cur2=head2; ListNode cur=head;
2021-04-03 21:16:47
75
原创 求链表长度
public class string{ public static void main(String[] argc){ ListNode n1=new ListNode(1); ListNode n2=new ListNode(2); ListNode n3=new ListNode(3); ListNode n4=new ListNode(4); ListNode n5=new ListNode(5);
2021-04-03 20:33:58
196
原创 k个一组翻转链表25
可以分析得到，如果递归的反转前k个，然后以k+1个节点为起点再次递归可以反转下k个，然后将这两个过程结合起来，如果不足的话需要保持原样。然后实现一个反转两个端点已知的链表，其实就是原来是cur到null停止，现在是到第二个端点停止。只不过最后一个点没连起来需要手动练一下。在区间a到b反转k个链表，for循环来判断此时的循环有没有k个元素，没有则直接返回。如果有的话反转a到b，这里都不用返回节点，因为a和b都是没变的，只不过换了个位置。但这里不需要反转b，反转的是一个左闭右开的区间。/** * Def
2021-04-03 17:17:42
72
原创 组合1.无重复元素
利用begin结束条件为满足条件就这class Solution { List<List<Integer>> res =new ArrayList<List<Integer>>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { if(candidates.length==0){
2021-04-02 01:48:07
89
原创 回溯问题总结--一道笔试题的折磨加顿悟
今天是2021.4.2日，笔试携程的一道题的时候出现大问题，明明思路是对的，就是过不了，于是不开心了一天，一直在思考是哪里的问题，现在忽然发现哦，茅塞顿开，按照这个思路来做，再有回溯的题不会我是猪。回溯主要用来在一颗解空间树上求哪种拥有想要的效果。其实就是解决子序列问题的，子序列问题的暴力解就是回溯。在一排列组合的大树中，要哪个元素不要哪个元素，其实总结起来就很简单，三种情况。一定要画出解空间树的图来，才能确定怎么来回溯。排列第一种是排列，也就是所有的元素都得要，只不过排的顺序不同，它用的方法是
2021-04-02 01:41:07
104
原创 加油站134
有一个环路上有N个加油站gas[i]表示其中第i个加油站的油量，然后cost表示下个i开往i+1个加油站需要耗费的代价。求从哪个加油站出发的时候可以走完全程。简单的思路就是遍历每一个加油站，然后遍历找到下一个能去的地方，因为是一个环形的，所以可以算下标的时候对n取余，因为此时每一个地点都要去，所以如果从0开始到i结束，0到i之间的任何一个地方都无法到i之后，可以直接跳过，所以可以记录一个可到达的最远地方cnt。进入循环之后算出此时的可到达目标j，然后把去下个地方的代价和此地的补充加上，如果发现代价大于
2021-04-01 15:40:18
73
原创 滑动窗口--字符串排列 567
给定s1和s2两个字符串，判断s2是否包含s1的排列，也就是s1是不是s2的子串。这里其实用固定窗口的滑动窗口就可以，不过这样也可以写，只不过条件要写成end-start==l1，不是while循环了。class Solution { int[] map1=new int[26]; int[] map2=new int[26]; public boolean checkInclusion(String s1, String s2) { if(s1.length()
2021-03-27 11:13:10
63
原创 图1.所有可能的路径
有两种表现形式，第一种是邻接矩阵，是一个二维布尔数组，表示节点x和y是否相邻；第二种是临界表，表示每个节点的邻居节点，好处是占用空间少，但缺点是无法快速判断两个节点是否相邻。遍历图和树一样，只不过因为图可能是有环的，所以需要一个visited数组来表示是否遍历过这个节点,而树直接判断是不是null就可以dfs（）｛针对这个节点的操作。判断是否到终点if（visited[s]）return；visited[s]=true；for（TreeNode neighbor：gragh.neighbors
2021-03-27 08:38:07
283
原创 组合4.1到9中和为n的k个数的组合
画出解空间树，可以发现是一个组合问题，而且递归中不能重复之前的数。所以用begin，传入i+1当递归的begin。结束就利用target就可以判断。class Solution { List<List<Integer>> res=new ArrayList<List<Integer>>(); public List<List<Integer>> combinationSum3(int k, int n) {
2021-03-26 22:07:06
83
原创 组合3.组合77
组合，画出图来就可以确定。关键是它的元素在一次递归中不能重复，所以传入i+1.class Solution { List<List<Integer>> res=new ArrayList<List<Integer>>(); public List<List<Integer>> combine(int n, int k) { if(n==0 || k>n){ return
2021-03-26 21:52:18
70
原创 组合2.有重复元素
有重复元素的话就不能再递归中重复选择了。画出解空间图，可以发现在选择列表中仍然需要跳过重复元素，所以需要排序，而且因为是组合，所以选择列表的起点仍然应该是begin。那怎么避免在递归中跳过重复元素呢，在组合中利用的是used数组，如果发现没有使用过，说明跳出了上次的递归，这次可以使用了。而组合利用的是begin来限制选择列表中可以选择的元素，在递归中反而可以用，因为要把此时的i传进去来当递归的begin，所以递归可选择的范围是更大的，但是在这个题中，一个数字也不能选多次，所以应该传入的是i+1所以如果此
2021-03-26 21:35:55
147
原创 组合1.无重复元素
找出一个和为target的元素组合。元素可以重复使用还是一样画出解空间树。这个和前面的区别就是选择列表少了很多，第二个数就不能选第一个数了，所以用一个begin可以标识出此时的列表 开始选择下标。还有就是此时的判断条件需要改变，因为现在不是到树的底部就结束，而是target到0结束，所以如果到了负数，则直接返回即可，因为再往下肯定大于target了。class Solution { List<List<Integer>> res =new ArrayList<Li
2021-03-26 21:12:05
84
原创 排列2.有重复数字
全排列（有重复数字）和无重复数字时候一样，画出解空间树，发现这种在遍历的时候仍然是一样的，只不过列表空间在发现重复的时候需要跳过，怎么发现重复呢，可以进行排序，然后和前一个比就可以。但是它递归路径中是不用跳过的，所以判断是否跳过时候就需要判断这个是在进行列表的迭代还是递归。一个很巧妙的方法就是看used数组，如果此时前一个值是false，说明已经递归完了，这个是遍历，就可以跳过。如果不是，则不跳过。class Solution { List<List<Integer>>
2021-03-26 21:01:27
191
原创 java中String作为参数传递终极解决
今天我遇到一个问题就是string的传值问题，它虽然是一个引用数据类型，但是却和基本数据类型一样无法被改变，我看到网上的很多解释都很离谱，比如说很多解释说String要看成和Integer一样的包装类，看成 是char[]的包装类，所以和其一样无法被改变？？？真的好离谱我经过自己的思考， 想到了正确的解释。对于函数的参数传值问题，分为三种。第一种为传值，也就是把此时的值复制一份。一般是基本数据类型。java，c++，c。第二种为传引用，一般是C++或者C中的传&a，可以直接改变值。第三种为
2021-03-25 23:27:16
1295
1
原创 打家劫舍2--解决环形数组的方法
还是给一个数组，只不过他们是首尾相连的，求最大数。则就是第一个要考虑最后一个和第一个之间的关系他们之间有三种关系，全不被抢，选其中一个抢。其实只要选后两种就行了。所以调用两次方法，分别算有没有最后一个和有最后一个两种情况。比较其最大值。class Solution { public int rob(int[] nums) { if(nums.length==1)return nums[0]; return Math.max(core(Arrays.copyOf
2021-03-14 19:53:20
217
原创 打家劫舍1
给一个数组，我是一个小偷，目的是偷到最多的钱，规则是偷的时候一家偷完之后下一家不能再偷，否则会触发警报，则求可以偷到最多的钱。求最值，使用动态规划，可以用dp[i]表示0到i可以偷到最多的钱，则返回最后一个dp值即可。dp[i]=dp[i-1]或者是dp[i-2]加num[i]，这两个中最大的一个。初值是dp[0]=0,dp[1]=num[0],dp[2]=max(num[1]+dp[0],dp[1])则多设置一个值很重要。class Solution { public int rob(i
2021-03-14 19:44:24
81
原创 一维数组字符串5.KMP
首先kmp算法就是找子串的位置，普通做法其实不能用滑动窗口来做，因为一个子串比较不是在一个字符串中找，而是两个字符串，比较失败需要退回，所以每个字符串失败之后还要退回到原来的位置，这种做法效率很低，kmp就是利用有限状态机来指定这个字符串往哪返回而不是返回原来第一个位置的下一个（其实类似动态规划）。所以对于每一个模式字符串p，会创造一个属于它的dp数组，它决定了这次比较字符该往哪走。dp[i][j]表示从p的i位置的字符如果碰到了j这个字符（256长度的ascii码）该往哪走。所以在比较的时候，原字符串不会
2021-03-13 18:22:20
60
原创 跳跃游戏2
一定可以到达最后，求到达最后需要的最短步数。这个题用动态规划也可以做，但时间很久。想一下其实没有必要算每一个地方可以到达的所有地方求最少，只要选一个最远的即可，也就是在一个位置能跳到的最远地方中选一个能跳最远的。用i来进行迭代表示现在的位置，res表示总的步数，max表示全局可以到达的最远位置（主要由i来更新），end表示此时可以到达的最远距离，也就是不用再跳一步已经可以到的最远距离。什么时候更新步数呢，就是当i等于end的时候需要再跳一步。记得是跳到最后一个就够了，所以直接不用遍历最后一个。cla
2021-03-11 15:56:41
51
原创 区间调度2.用最少的箭引爆气球
给了一些区间，求最少的弓箭可以引爆所有气球，也就是求最少有多少个不重叠的区间，和区间调度非常像。只不过边界也算重叠。为了保证不超过int的范围后points1-points2无法进行，所以直接改成比大小class Solution { public int findMinArrowShots(int[][] points) { if(points.length==0)return 0; Arrays.sort(points, new Compara
2021-03-11 11:52:10
47
原创 区间调度1.找到移除区间的最小数量
求出最多有几个互不相交的区间则做法是按end升序排序，选择一个结束最早的x，然后把区间中与它冲突的全部删除（别的区间的start要大于这个区间的end），接着重复步骤直到堆中没有区间。不用堆只用数组的话可以用一个for循环遍历整个数组，记录此时这个节点的start，如果它大于x的end，就令可选择数量加1，并更新x。找到要移除区间的最小数量，使得剩下的区间不重叠和求最多有几个不相交区间一样，统计方式不同罢了。class Solution { public int eraseOverlapI
2021-03-11 10:45:57
904
原创 子序列7.最长回文子序列
在回文子序列中，dp[i][j]定义的是数组i到j中最长的回文子序列的长度，如果此时知道了dp[i+1][j-1]，则s[i]和s[j]如果相等，则dp[i][j]=dp[i+1][j-1]+2如果不同则他俩可能同时出现，则选一个最大的dp[i][j]=max（dp[i+1][j]，dp[i][j-1]），如果只有一个字符，也就是i和j相同时肯定为1，则中间这一列为1，求一个位置需要先求出它的下，左下，左三个位置，最终要求的为dp[0][nums.length-1]，从最后一行第一个开始遍历吧，从左到右，
2021-03-10 16:05:47
92
原创 子序列3.俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。这实际上是一个最长递增子序列的问题。要把小信封装进大信封，问能套几次，给了信封的长和宽数组，其实这是两个维度的最长递增子序列，因为有两个因素，所以先按照宽来升序，如果宽相同则按照
2021-03-10 14:14:43
77
原创 01背包3.目标和494
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。这个题的选择就两种，做加法或者做减法，所以也不用写循环了，写两个就行了。但用回溯始终是一个递归问题，比较低效，所以最好是利用重叠子问题也就是用动态规划来做，我们把nums划分为两个子集A和B，分别代表分配+的数字和分配-的数字，则可以得出A-B=S A=S+B 2A=S+
2021-03-09 16:09:08
83
原创 子集背包2.目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。对比回溯和动态规划其实任何题都可以看成穷举，回溯是一种暴力穷举算法，求有几种方法，则if（满足条件） resut.add(路径); returnfor(){ 做选择； 递归； 撤
2021-03-09 10:57:21
48
原创 回文子串数量
求一个字符串有多少个回文子串最朴素的方法就是列举出所有的回文子串如果列举出所有的子串再判断它是不是回文串，那需要O（n3）但如果枚举每个中心，扩展的判断以其为中心的子串是不是回文，则需要O（n2）那如何有序的枚举所有的中心，因为中心可能是单数的，也可能是双数的，列举发现n个长度的子串产生的扩展中心单数加双数有2n-1组每一个i可以产生一组下标[l,r],如果l和r一样则说明奇数，如果l和r不一样，则说明他们是两个相挨的下标。所以一个i可以得到的两个下标为i/2和i/2+（imod2）如果这个没
2021-03-03 03:33:32
200
原创 前缀和--和为k的数组 560
求一个数组中连续数字的和为k的子数组个数。一开始想到是滑动窗口，但是滑动窗口并不能解决，因为有负数，所以走过的还可能要用到。又想到动态规划，也不行，因为状态转移式推不出来。难道只能用枚举，固定每一个起点的i，然后for循环每一个终点来检查了吗，答案是否定的，可以对检查这一步进行优化。从而O（n）结束。就是利用前缀和若定义pre（i）是0到i的所有数的和，则一个j到i的子数组的和为k就可以表达为pre（i）-pre（j-1）=k所以需要满足pre（j-1）=pre（i）-k所以考虑以i结尾的
2021-03-01 23:38:33
133
原创 完全背包2.换钱的最少组合数322
求可兑换的组合数量。注意必须等于amount而不是小于等于。与01背包问题不同的是，01背包考虑的是这个物品是否可拿，而这个问题是这个物品是否可拿，拿的话可以无限拿直到装不下。因为每个硬币都能选多个，所以要遍历每个硬币的每个选择，不像上个题只要找到最小的硬币数就可以，所以尽可能是选择比较大的 硬币，这样可以有最小的数量。直接遍历每个amount，然后在每个amount中选一个就行。而这个是要所有的组合，所以每个都要尽可能多的选择。所以首先遍历每一个硬币，然后尽可能多的选择硬币的个数，穷尽每一种选择d
2021-02-27 17:40:32
65
原创 01背包2.1和0
给一个二进制数组，要求返回其最多的子集数目，要求返回的子集中0的个数不大于m，1的个数不大于n。分析一下可以知道这其实也是一个是否选数组中元素的题，每个元素只能选一次，限制条件是0和1个个数，所以可以看成是一个01背包的问题。dp[i][j][k]表示的是在数组0到i中，可以拥有的最大子集数，其中j和k代表此时的0和1的个数。dp[i][j][k]如果此时选i，则等于dp[i-1][j-q][k-w]+1如果不选则是dp[i-1][j][k]有两个需要注意的是ijk都要多设置一行，这样可以避免
2021-02-27 12:12:47
55
原创 01背包1.分割等和子集474
把一个数组分成两部分，是他们的和相同，这就是典型的分成两部分的01背包问题。可以想到两个数相同，也就是这个数是数组和的一半，是一个偶数。与01背包的区别是01背包需要保证值小于规定值，而这个题需要恰好等于规定值的一半。特点是每个数只能用一次，所以只能慢慢去添加容量。用一个二维数组来表示，行数就是物品的数量，表示每次考虑一个物品，列数表示背包容量+1，因为我们需要为0的背包容量dp[i][j]就是是否可以从0到i的区间中取出总量为j的物品，也就是它是一个布尔值。有两种选择就是是否选num【i】这个位置的
2021-02-27 10:51:08
70
原创 数对排序--根据身高重建队列406
整数对（h,k）表示h是身高，k是排在这个人前面大于等于h的人数。有一个数组存储了这些数对，但它的顺序并不是按照这个顺序来排列的经过处理之后要求得到按照他们各自属性相符顺序的数组。对于这种数对还涉及排序的问题，一般要根据第一个元素正向排序，根据第二个元素反向排序。我们对于这个题来说就按照身高先逆序排序，然后按照k来升序排序，因为这样排之后可以发现每个元素前面的元素都是大于等于它的元素，而k按升序说明可以把k更大的数放后面，减少操作次数。排序好之后把各个数插入到它的k所在的位置。class Solu
2021-02-25 17:43:42
191
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人