- 博客(62)
- 资源 (9)
- 收藏
- 关注
RSS订阅原创 动态规划
图内向右或下走路64.最小路径和给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例:输入:[[1,3,1],[1,5,1],[4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。dp矩阵每一个点更新为当前位置的最小路径和，dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];类似的题目还有求路径数量
2020-08-17 21:48:57
133
原创 DFS--在图里面找一片区域
在图里面，要求多少个分割的区域，最大的区域面积等，都可以使用dfs，这比bfs更快。注意标记已访问过的位置！695.岛屿的最大面积求最大的连续“1”的面积注意面积加一的时机，访问过的位置变为0class Solution { int dfs(int[][]grid, int x, int y){ int area = 0; int []dx = new int[]{0,0,1,-1}; int []dy = new int[]{1,-1,0,
2020-08-02 23:10:25
159
原创 BFS--图内点到点的最短距离
最近做了几道点到点的最短距离，发现都是优先用BFS，用DFS的话会导致时间特别长。1091.二进制矩阵中的最短路径大意是图内1表示阻塞，0表示可以走，求左上到右下的最短步数一开始我想的是用DFS，因为需要用一个数组来存放已经走过的格子，否则会时间爆炸，但是这样就发现了一个问题，就是在错误的路径可能先访问了正确路径的格子，导致结果不对。转而来用BFS，思路是从第一步开始，把下一步可以到达的点都加入队列，记录队列长度，依次弹出这些，当第二步的点全部出队后，步数加一，当到达终点时结束，若到达终点前队列为空
2020-08-02 12:25:57
553
原创 贪心思想？重写比较函数排序
有一类题，有人说是属于贪心，有人说是属于排序，题目看似复杂，但是通过对二维数组进行排序，就可以直接KO，反正不纠结于分类，话不多说，开始看题。435.无重叠区间给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。排序逻辑：安排下尽可能多的区间，就是要使区间右端点尽可能小...
2020-07-26 10:44:51
117
原创 eclipse debug source not found
今天在eclipse想debug的时候，一直跳转到source not found的界面，网上看了一堆博客，什么添加src.zip，什么把项目添加到路径，一直没用，结果是一篇文章的评论区的大佬解决了问题， 果然大佬都在评论区！...
2020-07-25 22:16:32
158
原创 荷兰国旗问题
75.颜色分类给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。示例:输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]使用一遍排序法来做，本质是快排三个指针，分别指向第一个非0元素，当前下标，第一个非2元素class Solution { void swap(int[]num, int a, int b){
2020-06-01 11:56:33
88
原创 最详细的关于比较器的重新实现方法
之前对比较器一直模模糊糊，终于搞清楚了。1. 再定义一个类，让其实现比较器接口Comparator，重写接口中的比较器接口Compare(T o1, T o2)方法比较器类跟原来的类为两个类，原来的类调用比较器方法。class Person{ private int age;}class PersonComparactor implements Comparactor<Person>{ @override public int compare(Person o1, Person
2020-05-31 23:07:58
413
原创 出现次数前k多的元素Ⅱ--大顶堆
451.根据字符出现频率排序给定一个字符串，请将字符串里的字符按照出现的频率降序排列。示例 1:输入:“tree”输出:“eert”解释:'e’出现两次，'r’和’t’都只出现一次。因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。大顶堆解法维持一个从大到小的优先队列，然后输出前k项。class Solution { class letter{ int fre; char value; letter(
2020-05-31 22:54:08
283
原创 出现次数前k多的元素Ⅰ--桶排序
347.前 K 个高频元素给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]示例 2:输入: nums = [1], k = 1输出: [1]你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。普通做法，先统计各个数的
2020-05-26 17:30:06
261
原创 快慢指针之判断链表有无环
141.环形链表给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。示例 1：输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。用快慢指针，若链表有环，则慢指针和快指针终将相遇，若快指针下一个为空，说明无环。/** * Definition for singly-linked list. * cl
2020-05-18 22:23:10
215
原创 回文串
680.验证回文字符串 Ⅱ给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: “aba”输出: True示例 2:输入: “abca”输出: True解释: 你可以删除c字符。用头尾指针的移动来判断回文串，如果不相等，由于可以删去一个字符，可以选择删去头指针的字符或尾指针的字符，只能删一次，所以回文串只有两种情况：删除头的字符后是回文字符串或删除尾的字符是回文串class Solution { int flag=0; public boolea
2020-05-18 22:19:33
124
原创 字符串匹配
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。示例 1:输入:s = “abpcplea”, d = [“ale”,“apple”,“monkey”,“plea”]输出:“apple”先将字典按字典序排好，然后按顺序找到第一个最长匹配的子串。（也可以不排序，找到匹配子串后判断字典序先后）找字符串s的匹配子串，用双指针，相同的字母往下移动，如果子串能移
2020-05-18 22:00:21
173
原创 分割链表
对于一个链表，把小于值x的放在前面，大于值x的放在后面，顺序随意记录这道题主要是因为用到了一个无具体值的假头指针。ListNode hhead=new ListNode(-1);返回链表时返回hhead.nextpre指针指向小于x的最后一个节点，last指针向后遍历，出现新的小于x的节点，把节点插入到pre后面，pre=pre.next。由于当第一个节点大于x时，这个时候后面出现的小于x的节...
2020-05-06 15:26:04
117
原创 求集合的子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: nums = [1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]可以用位运算来求子集。用一串长度为数组大小的二进制串，对应的位表示有无取到那个位置的数。由于求全部子集，所以对这串二进制表示的每一个...
2020-05-06 14:09:43
337
原创 二分查找
mid=left+(right-left)/2全部的区间为[0,array.length-1]闭区间进行中值查找的条件为left<=right(左右端点可以重合)缩小区间为[left,mid-1] [mid+1,right]注意不存在的条件，比如下标为mid时并不等于目标值，或者左右端点越界leetcode 34. 在排序数组中查找元素的第一个和最后一个位置给定一个按照升序排列的...
2020-05-03 21:40:15
104
原创 有序数组求两数和为某个值
167.两数之和 II - 输入有序数组给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。输入: numbers = [2, 7, 11...
2020-05-02 16:44:28
702
原创 求字符串中含有的最长回文串（不用连续）
将字符串反转，回文串的字母反转前后相同。求反转前后两个字符串的最长公共序列（不用连续）即可求得最长回文串。import java.util.*;public class Main{ static int MaxLen[][]; static int maxLen(String s1, String s2){ int length1 = s1.length(); ...
2020-04-26 19:50:08
134
原创 疯狂吐槽！！CSDN的文章编辑器真难用！！
最近开始写博客，被这个文章编辑器搞到没脾气。在别的地方比如leetcode ,牛客上面写的代码，复制过来格式就是乱掉的。。。非得我先粘到记事本上再拷贝过来。复制题目过来可能因为有网站的水印触发复制的条件，整个内容全没了，行，我忍，但是，为什么我复制我这个编辑器里面的内容，就想把上面一段移到下面去，都会全部内容没了，有毒。明明十几分钟能写完的博客，硬生生调格式调了好久，好几次害我被迫熬夜，这是在谋...
2020-04-24 18:42:39
430
1
原创 通用算法之归并求逆序对
将数组分成小数组，对相邻的两个小数组统计逆序对的个数，统计完顺便排好序，避免重复计算。import java.util.*;public class Main { static int count=0;//全局变量，统计逆序对个数 static void splitarray(int[]arr,int start,int end) { if(start>=end) re...
2020-04-24 18:00:56
105
原创 腾讯笔试题逛街-最大栈
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。1<=n&...
2020-04-24 16:06:02
487
原创 腾讯笔试-贪心算法
小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。 这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。输入包括n+1行。第一行包括两个正整数n和L(1<=n<=105,1<=L<=109)接下来的n行,每行两个正...
2020-04-23 22:20:47
255
原创 并查集-leetcode朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。这道题...
2020-04-22 17:59:02
811
原创 回溯算法--解数独
编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。空白格用 ‘.’ 表示。第一次接触回溯算法，道理不难，就是代码比较长int[][]col=new int[9][10];//记录每一列存在的数 int [][]row=n...
2020-04-22 15:57:58
282
原创 字符串的布尔值判断
美团点评2020校招后台开发方向笔试题给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。表达式求值是注意and 的优先级比 or 要高，比如：true or false and ...
2020-04-09 00:09:58
2055
原创 一文读懂不同状态的动态规划
网易2020校招笔试题-跳柱子小易有n根柱子，第n根柱子的高度为。一开始小易站在第一根柱子上。小易能从第i根柱子跳到第j根柱子，当且仅当hj<=hi且1<=j-i<=k。其中k为指定的一个数字。另外小易拥有一次释放超能力的机会。这个超能力能让小易从柱子i跳到任意满足1<=j-i<=k的柱子而无视柱子j高度的限制。现在小易想知道，小易是否能到达第n根柱子。题目理...
2020-04-06 16:44:41
368
原创 图--求某个区域中障碍物的个数
网易校招题目：小易有一个体积巨大的货物，具体来说，是个在二维平面上占地c×d的货物。小易有一个n×m的广场，想把货物放在这个广场上。不幸的是，广场上已经有了一些障碍物，障碍物所在的格子不能放置你的货物。小易现在想知道能否成功地放置货物。在讨论区学习大佬的解法用一个数组来表示从0，0的点到这个点围成的矩形内有多少个障碍物，然后用block[i+c][j+d]-block[i+c][j]-bl...
2020-04-04 21:25:44
454
原创 背包问题
原文章：https://blog.csdn.net/qq_38410730/article/details/81667885问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？punlic class Main{ int[]value=new int[] { 0 , 3 , 4 , 5 , 6 };//用来存储每个物品的价值 ...
2020-04-02 22:36:20
502
原创 207. 课程表 判断排课方式有无环
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？注意，这里的numcourse就是全部出现的课程，我之前还在纠结numcourse比出现课程少的情况1.如果修一...
2020-03-31 21:57:56
152
原创 面试题62.圆圈中最后剩下的数字
0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。这道题一开始用循环链表来模拟，当然地时间超出了。看了一下官方的题解，用的是递归。将问题分解成子问题。n=1的数组规模，最后剩的元素就是...
2020-03-30 12:44:23
374
4
原创 栈（或双向队列）内元素递减
265每日气温请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。这种结果取决于后面出现的元素，可以选择从后面开始遍历，类似的还有股票之类的...
2020-03-29 20:38:38
78
原创 岛屿的个数--dfs&&bfs
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。想当初，面字节跳动就是这道题，只不过把岛屿换成朋友圈罢了。访问过的岛屿改成’0’，避免重复访问dfs做法：递归class Solution { void dfs(char[][]grid,int i,in...
2020-03-29 11:57:31
93
原创 Java实现字典树
字典树的原理类似于自动机，可以用来匹配字符串前缀，后缀也是可以的，就是将字符串倒过来。定义两个类节点类，定义长度为26的数组用来表示这个节点的下一位包含这些字母中的哪一个，一个判断值表示这个节点是否是一个字符串的最后一个节点，因为可以有多个字符串在树的同一路径。节点类用于处理每一个字符class trienode{ private boolean isend;//是否是某个字符串的最后一...
2020-03-28 16:27:55
939
原创 leetcode--找1-N中缺少的数字
136.只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。异或大法好如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位a⊕0=a如果我们对相同的二进制位做 XOR 运算，返回的结果是 0a⊕a=0XOR 满足交换律和结合律a⊕b⊕a=(a⊕a)⊕b=0⊕b=b所以对数组的所有元素进行异或，得到的...
2020-03-24 18:01:13
768
原创 堆排序
前情摘要1.堆本身是一个完全二叉树，左叶子节点下标=跟节点下标2+1，右叶子下标=根下标2+2（如果有的话）2.大顶堆是根节点值大于叶子节点，但是左右叶子节点大小不一定3.堆排序是利用大顶堆的思想，但是全程在数组里面排序，交换节点只是改变下标4.一次大顶堆的调整后，得到一个最大值，将最大值放在数组最后，再对前面n-1个节点递归地进行堆排序。我手贱总是在构造第一个大顶堆的函数的len前面加...
2020-03-20 17:08:48
53
原创 leetcode
面试题40. 最小的k个数难度简单29收藏分享切换为英文关注反馈输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。一开始用选择排序，但是时间耗费较大，看了官方题解，发现可以用快排的思想。因为求最小的k个数，这k个数不用排好序，所以只要找到一个分割点就行了，跟快排类似，在快排分出两边的基础上，判断前边的个数是否...
2020-03-20 14:42:35
59
原创 排序算法
插入排序public void sort(int []arr) { int len=arr.length;int min=0,k=0; for(int i=1;i<len;i++) { int j=i-1;int temp=arr[i]; while(j>=0&&temp<arr[j]) ...
2020-03-16 15:33:11
152
原创 leetcode 岛屿的最大面积
本来最近不打算做图的题，不过既然这个打卡今天轮到这道题，那就来做做吧。这题跟当初我面字节跳动的题目有点类似，当年我就倒在不会写dfs的代码上[/(ㄒoㄒ)/~~]695.岛屿的最大面积给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。找到给定的二维数组中最大的岛屿面...
2020-03-15 11:38:52
213
原创 eclipse Cannot make a static reference to the non-static method
今天写leetcode的时候用eclipse调试，然后出现了Cannot make a static reference to the non-static method这个问题，就是main函数是static的，不能在里面使用非静态方法或成员（this），一个方法是把你原来的方法改成静态的，但是改动比较多...
2020-03-13 17:58:42
408
原创 leetcode-链表，只要我的指针够多，我遍历的次数就够少
328.奇偶链表给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，，而不是节点的值的奇偶性。时间复杂度要是O(N)思路：这种把原来链表搞成一条新链表的，一般就不在原来链表上面改动了，这个跟数组不同，（数组新增一个空数组要N的空间复杂度，而链表直接一个头节点搞定）。直接NEW一个头节点，然后在之后新增新链表节点（类似的题还有有序合并两...
2020-03-12 21:04:25
79
原创 leetcode 从前序中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。你可以假设树中没有重复的元素。md，这道题真是搞到我心态爆炸，一开始虽然思路清晰，但是一把思路转成代码就绕晕了。主要是对这个递归函数该传什么参一直搞不清，对数组的下标怎么传递变化给绕晕。看了题解，首先大方向的思路就是：先序遍历的节点作为根，本质上是按照先序遍历的顺序建树，而中序遍历是用来确定左右子树边界，即什么时候返回。前序遍历的节点值对应的中序遍历...
2020-03-12 17:33:15
74
计算机安全实验2-4
2020-06-16
家谱管理系统.zip
2019-07-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人