- 博客(110)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 leetcode 84. 柱状图中最大的矩形【单调栈】
暴力法数组提肯定首先想到用暴力法解，求出所有可能得矩形面积并从中取最大值。但其实不难发现我们并不需要真的求出所有矩形面积，只需要求出在某一柱体的高度下，矩形所能达到的最大宽度，这样就能求出该柱体所对应的最大矩形面积，这样求出所有柱体的最大矩形面积即可得到答案。class Solution { public int largestRectangleArea(int[] heights) { int area = 0, n = heights.length; /.
2020-09-10 14:27:03
154
原创 leetcode 面试题 01.06. 字符串压缩【双指针】
使用双指针来确定重复字符的个数class Solution { public String compressString(String S) { int len = S.length(); if(len<1)return ""; StringBuilder sb = new StringBuilder(); int s...
2020-09-10 11:15:06
139
原创 leetcode 面试题 17.13. 恢复空格【动态规划】
方法一（暴力法）遍历sentence字符串中的所有可能的子串，并将每个子串与dictinary数组中的每个单词比较，若相等，则说明这个子串已被识别，dp数组中对应位置的大小可以减掉对应的单词长度，即 dp[i] = dp[i-word.length()] 。class Solution { public int respace(String[] dictionary, String sentence) { int slen = sentence.length(); .
2020-09-10 11:07:27
149
原创 leetcode 139. 单词拆分【动态规划】
一个典型的动态规划题，利用两层循环，遍历所有的子串，当wordDict中含有子串substring（j,i）组成的单词并且上dp数组中对应子串的上一位dp[j] = true时，表明0~i中的所有单词满足拆分要求，因此dp[i] = true。class Solution { public boolean wordBreak(String s, List<String> wordDict) { boolean[] dp = new boolean[s.length()
2020-09-10 11:00:53
122
原创 一文搞定Leetcode数据库
184. 部门工资最高的员工注意IN的用法，可以将多个字段合并成一个整体然后用IN进行筛选；IN后跟的子查询用于对部门进行分类。当我们要查询xxx中最xxx的数据时，通常可以采用GROUP BY关键字来进行分类。SELECT d.name Department, e.name Employee, e.salary FROM Employee e INNER JOIN Department d ON e.DepartmentId=d.Id AND
2020-08-11 22:51:49
155
原创 leetcode 207. 课程表【拓扑排序】
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int[] indegrees = new int[numCourses]; List<List<Integer>> adjacency = new ArrayList<>(); for(int i = 0; i < numCourses
2020-08-04 11:17:02
129
原创 leetcode 785. 判断二分图【BFS】
查看二分图的定义可知，每条边的顶点分别属于两个不同的集合。因此可以采用染色法，对顶点所属的两个顶点染上不同的颜色。使用BFS遍历与每个顶点所连接的其他顶点，如果发现某个顶点两次染色的颜色不一致，则说明该图不是二分图。class Solution { public boolean isBipartite(int[][] graph) { int[] color = new int[graph.length]; for(int i = 0; i<graph.l
2020-07-16 13:54:19
157
原创 leetcode 47. 全排列 II【回溯】
全排列的题首先可以想到用回溯解决。在本题中，需要考虑的有两点：如何判断构建的排列数组是否存在重复，以及如何避免使用重复的元素。避免重复比较简单，可以构建一个与nums等长的数组，用于记录哪个元素被使用过，这样在往下遍历时可以用该数组进行判断并避免重复使用。去重则比较麻烦，可以考虑使用JDK自带的Set类型的集合，自动实现去重，但这样效率较低，可以尝试使用剪枝完成去重。首先将数组进行排序，这样重复的数字就被摆列在相邻的位置，然后每次递归前，首先判断一下当前元素是否等于上一个元素。如果相等，而且上一个元素已
2020-07-15 21:16:06
293
原创 leetcode 77. 组合【回溯】
组合类的题目基本都是套用回溯的模板就可以解决。class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { ArrayList<Integer> list = new ArrayList<>(); helper(1
2020-07-09 17:21:08
103
原创 leetcode 73. 矩阵置零【数组】
本题解法较为常规，难点在于要求的O(1)空间复杂度。先看一下O(m+n)空间复杂度的解法，定义两个长度分别为矩阵长和宽的数组来记录矩阵各行或和各列是否出现了数字0。然后在遍历一次将对应和行和列的全部元素赋值为0。class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean[] row
2020-07-09 16:53:13
116
原创 leetcode 26 & 80. 删除排序数组中的重复项（II）【双指针】
class Solution { public int removeDuplicates(int[] nums) { if(nums.length <=1)return nums.length; int slow = 0; int fast = 1; while(fast < nums.length){ if(nums[slow] != nums[fast]){ num
2020-07-07 21:15:32
94
原创 leetcode 33. 搜索旋转排序数组【二分查找】
从题目可知数组是部分有序的，因此可以使用二分查找来缩短查找时间。由于数组被旋转了一次，因此被分为了前后两部分，其中每一部分内部都是升序的，因此可以用两段式的二分查找的做，即先进行一次判断，nums[mid] 是属于前半部分还是后半部分，然后再根据大小关系进行二分查找。class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length-1;
2020-07-07 14:55:48
129
原创 leetcode 86. 分隔链表【链表】
定义两个节点来分别连接 <x 的节点和 >=x 的节点。遍历一遍原链表，然后将链表拆分成两部分，最后将两部分连接起来即可。要注意dummyhead节点的运用可以简化链表的操作。class Solution { public ListNode partition(ListNode head, int x) { ListNode h = new ListNode(-1); ListNode hh = h; ListNode t = new
2020-07-07 14:31:45
65
原创 leetcode 45. 跳跃游戏 II【贪心算法】
贪心算法的本质是求局部最优解。在本题中，局部最优解就是在每一个位置都尽可能地一次跳到更远的位置。因此，对于当前位置，假设最远可以跳2个位置，我们定义一个max变量记录这两个位置中再跳一次所能得到的最远位置，这样，我们就可以保证每一次跳跃所得到的结果都是最远的。class Solution { public int jump(int[] nums) { int max = 0; int end = 0; int n = nums.length-1;
2020-07-06 20:41:05
204
原创 leetcode 剑指 Offer 03. 数组中重复的数字【原地哈希】
最简单的解法是创建一个HashMap，将以数组中的数字作为key，出现的次数作为value存入该Map中。实现后发现同时较慢，肯定有更优的解法。利用数组代替HashMap，利用数组下标作为Key可以实现更快速的寻找，因此遍历数组时，将数字交换到与之数值相对应的数组下标处，交换前先比较一下，如果两个位置的数值相同，则说明元素重复，直接返回，否则就执行交换操作。class Solution { public int findRepeatNumber(int[] nums) { for
2020-07-06 17:22:35
147
1
原创 leetcode 41. 缺失的第一个正数【原地哈希】
这个题目难点在于要求的时间复杂度O(n)和空间复杂度O(1)，因此只能在原数组上进行操作。将数组中的数字放置在与之数值相对应的数组下标中。如将数字1放置在下标为0的位置中，将数字5放置在下标为4的位置中…题目要求仅寻找正整数，因此从1开始遍历。数组中的数字可能比数组长度要大，此时数组长度中一定存在无法与下标对应的数字，那么这个下标遍为需要返回的结果，而超出数组长度的数值可以不用处理。class Solution { public int firstMissingPositive(int[] n
2020-07-06 16:03:53
144
原创 leetcode 63. 不同路径 II【动态规划】
一个典型的动态规划题，首先可以考虑用二维dp数组来解答。由于题目要求角色只能想下或想右走，因此状态转移方程也比较容易想到。当一个网格存在障碍时，由于无法到达，因此dp数组中对应位置设为0。对于其他位置，可到达路径数=上方位置可到达路径数+左方位置可到达路径数，因此有dp[i][j] = dp[i-1][j] + dp[i][j-1]class Solution { public int uniquePathsWithObstacles(int[][] grid) { int
2020-07-06 13:39:23
93
原创 leetcode 718. 最长重复子数组【动态规划】
寻找公共子数组，类似于公共子串问题，可以定义一个二维的dp数组来记录两个数组之间的匹配情况，当 A[i] == B[j] 时，令 dp[i][j]=dp[i-1][j-1]+1 。根据该状态转移方程可以得到动态规划解法的代码如下：class Solution { public int findLength(int[] A, int[] B) { int n = A.length, m = B.length; int[][] dp = new int[n + 1][m
2020-07-01 14:46:59
69
原创 leetcode 79. 单词搜索【DFS、回溯】
class Solution { int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}; public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean[][] visited = new boolean[m][n]; for(int i=0; i&l
2020-06-30 19:30:31
101
原创 leetcode 1028. 从先序遍历还原二叉树【DFS】
class Solution { public TreeNode recoverFromPreorder(String S) { Stack<TreeNode> st = new Stack<>(); TreeNode head= null; for(int i=0; i<S.length();){ int curLevel = 0; while(i < S.lengt
2020-06-18 14:22:15
145
原创 JavaSE - 集合【1】详解HashMap
JavaSE - 集合 (1) HashMapHashMap作为Java中最常用的集合类之一，也是各种面试必问的考点，因此很有必要深入了解HashMap源码，剖析它的实现原理和具体的实现细节。常量首先看一些HashMap类的源码中定义的常量及其基本含义。//默认初始化容量：该容量指`table`数组的默认大小，默认值为16。static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量：`table`数组的最大长度为 2^30=
2020-06-16 13:53:35
223
原创 leetcode 739. 每日温度【单调栈】
方法一采用暴力法两层循环即可，内层循环用于向后遍历寻找下一个比当前天数（i）温度更高的天数。class Solution { public int[] dailyTemperatures(int[] T) { int len = T.length; int[] res = new int[len]; for(int i=0; i<len-1; i++){ for(int j=i+1; j<len; j++){.
2020-06-11 10:05:22
143
原创 leetcode 面试题46. 把数字翻译成字符串【动态规划】
回溯看到题目首先能想到是将所有可能的情况排列组合一下并找到所有符合题意的组合，因此可以利用回溯法枚举所有可能的组合并将所有可能的组合累加得到总的组合数。class Solution { int count=0; public int translateNum(int num) { String str = String.valueOf(num); return dfs(str, 0); } public int dfs(String s.
2020-06-09 10:49:43
160
原创 leetcode 990. 等式方程的可满足性【并查集】
https://leetcode-cn.com/problems/satisfiability-of-equality-equations/solution/shou-hui-tu-jie-shou-xie-unionfind-bing-cha-ji-bu-/不同的字母之间存在联通的关系，因此可以将字母作为图的节点构造成联通图。利用并查集的特性可以快速的判断两个字母之间是否存在连通通路。路径压缩可以利用树的高度，将高度更高的树的根节点作为两棵树合并后的根节点，也可以更简单地将每个节点都指向根节点，这样查
2020-06-08 22:42:31
124
原创 leetcode 130. 被围绕的区域【BFS】【DFS】
方法一：BFS本题可以逆向思考，若我把与边界的“O”相连的“O”全部找到，其他“O”全部替换为“X”即可。利用图的BFS算法找到所有与边界相连的“O”即可。class Solution { private class Pos{ public int x; public int y; public Pos(int x, int y){ this.x = x; this.y = y; .
2020-06-08 21:20:20
171
原创 leetcode 54. 螺旋矩阵 、面试题29. 顺时针打印矩阵【数组】
定义四个变量分别表示矩阵上、下、左、右的行或列，然后按顺时针顺序遍历这些行或列，遍历过的行或列用四个变量的自增或自减来去除，没遍历完一行或一列后，都需要判断是否遍历完整个矩阵，否则会添加多余元素。class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); int height =
2020-06-05 19:16:33
178
原创 leetcode 57. 插入区间【数组】
本题主要难点是如何将重复的区间合并以及如何将合并好的区间重新插入到数组中。结果数组的构建：定义一个List用于保存区间，当区间小于被插入区间时，直接放入list中，并记录插入元素的下标，改下标最后用于将新构建的区间插入到list中。当原区间与被插入区间有重复时，合并区间，当区间大于被插入区间时，直接放入list中。合并区间：利用Matth工具类求取区间的最大和最小值，当数组中的区间与被插入区间存在重叠时，更新被插入区间的最大和最小值，然后用更新后的区间进行下一步的判断。class Solution {
2020-06-04 09:58:18
174
原创 leetcode 238. 除自身以外数组的乘积【数组】
暴力法最简单的方法时暴力法，两层遍历就可以搞定，但不符合题目的O(n)时间复杂度。记录前后遍历结果利用空间换时间的思想，分别建立两个数组来保存数组从前向后遍历和从后向前遍历时的各个元素的乘积，最后在利用一次遍历求出某个元素前、后乘积的乘积即为所需要的结果。class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] leftswe..
2020-06-04 08:34:06
78
原创 leetcode 974. 和可被 K 整除的子数组【前缀和、同余定理】
首先题目中明确表示所求的子数组和连续、非空的，因此可以使用前缀和来对暴力的遍历进行简化。为了直观地体现前缀和的作用，在不使用同余定理的前提下写出以下仅使用前缀和数组的方法，由于使用两重循环，因此该方法会超时。class Solution { public int subarraysDivByK(int[] A, int K) { int len = A.length; int[] prefix = new int[len]; int sum=0;
2020-05-27 10:43:20
174
原创 leetcode 287. 寻找重复数【二分法】
此题的二分法与常规的二分法搜索不一样。平常我们用到二分法通常是对拍好序后的元素进行二分搜索，用来搜索数组中特定的元素。该提中的二分则是对数组中元素与给定值之间的大小关系进行二分，首先取数组中最大和最小值的平均值作为mid值，然后统计整个数组中比mid小的数的数量，若数量>mid，这说明重复的数一定在left和mid这个区间内，否则就在mid+1和right这个区间。class Solution { public int findDuplicate(int[] nums) {
2020-05-26 21:09:24
151
原创 leetcode 10. 正则表达式匹配【动态规划】
字符串的匹配类问题通常都能用二维数组的动态规划解决。该类问题的难点在于dp数组的初始化以及状态转移方程的确定。dp数组的初始化需要考虑p字符串的特殊情况，因此需要对数字的第一行进行初始化。当第二个字符为 * 时，它能对空字符串进行匹配，因此dp[0][2] = true，后面的元素依次类推。求状态转移方程首先要对两个字符串可能存在的各种情况进行分析：s[i-1] == p[j-1] ，此时两个字符串中对应的字符匹配，因此该位置状态与上一个位置的状态有关，因此有：dp[i][j] = dp[i-1][
2020-05-22 17:12:59
129
原创 leetcode 5. 最长回文子串【双指针】
字符串类型的题目很多都可以用双指针解决，这题是要在一个字符串中找到最长的回文子字符串，对于回文字符串，我们可以使用中心扩散的方式来寻找。回文串有两种形式，一种是中心字符为奇数，另一种则是中心字符为偶数。因此采用中心扩散时，需要对两种形式的中心都进行处理，即从单个字符开始扩散和从两个字符开始扩散两种方式。扩散就是利用双指针不断地向字符串的两端遍历，直到回文字符串条件不成立，终止遍历。class Solution { public String longestPalindrome(String s
2020-05-21 09:45:03
346
原创 leetcode 1371. 每个元音包含偶数次的最长子字符串【动态规划】
此题非常精妙，咋看之下，由于计算最长子字符串需要用到字符串之前的状态，所以首先考虑到使用动态规划。使用动态规划的难点在于如何判断使用dp数组中哪一个位置元素。这涉及到5个字符的奇偶的判断，参考（chaoxi）了大佬的解法后，可以使用bitmask来解决。利用二进制来表示元音字母出现的奇偶class Solution { public int findTheLongestSubstring(String s) { int[] pos = new int[1 << 5];
2020-05-20 22:09:05
167
原创 leetcode 37. 解数独【回溯】
解数独也是一个典型的回溯算法问题。与N皇后可以直接套用class Solution { public void solveSudoku(char[][] board) { //定义三个数组记录行、列和方格中出现过的数字 boolean[][] rowUsed = new boolean[9][10]; boolean[][] colUsed = new boolean[9][10]; boolean[][][] blockUsed
2020-05-19 19:55:09
137
原创 leetcode 51. N皇后【回溯】
一个经典的回溯算法问题。回溯的本质是决策树的递归过程，用递归的方式遍历所有可能得结果，在遍历过程可以添加适当的判断来实现剪枝从而提高算法的性能。对应本题，决策树的每一层元素可以对应为皇后在每一层所放置的位置，剪枝的判断条件为皇后的攻击范围（即不可将下一层的皇后放置在上层皇后的攻击范围内），由此套用回溯算法的模板即可得到答案。class Solution { //将数组转换为字符串 public List<String> charToString(char[][] chars){
2020-05-18 20:08:24
110
原创 leetcode 152. 乘积最大子数组【动态规划】
由题意知，每次使用 nums[i] 计算最大值时，都需要使用到之前的历史计算结果，因此可使用动态规划思想，创建dp数组来保存历史的计算结果。本题中每次计算仅使用了上一次的计算结果，可以使用状态压缩将dp数组压缩至一个变量。由于数组中可能存在负数，除了需要记录每次计算后的最大值，还需要记录最小值，当遇到数组中的负数时，需要将最大、最小值交换。class Solution { public int maxProduct(int[] nums) { int max = Integer.
2020-05-18 11:11:15
141
原创 leetcode 44. 通配符匹配 【动态规划】
类似的两个字符串之间的对比都可以使用二维的动态规划实现。首先定义二维dp数组并且初始化数组，注意字符串s中的 * 号可以匹配任意字符串，因此有：dp[i][j] = dp[i - 1][j] || dp[i][j - 1]当字符串s中的字符为?号或者连个字符串对应位置的字符相等时，有：dp[i][j] = dp[i - 1][j - 1]最后返回dp数组的右下角元素即可。class Solution { public boolean isMatch(String s, String p) {
2020-05-14 10:36:45
119
原创 leetcode 113. 路径总和 II【回溯】
深度优先搜索结合回溯的思路可以解决本题。定义一个List来存放搜索路径上的节点值，当搜索到达某个叶子节点且路径总和满足题目要求时，将该路径对应的List放入记录答案的List中，并回溯；如此递归下去，直到所有路径都被遍历一次。class Solution { List<List<Integer>> res; public List<List<Integer>> pathSum(TreeNode root, int sum) {
2020-05-13 13:47:22
159
原创 leetcode 105. 从前序与中序遍历序列构造二叉树、106. 从中序与后序遍历序列构造二叉树【DFS】
105和106都是根据二叉树的遍历结果来重构二叉树，这两题的解题思路是一致的，因此将两题放在一起记录。105首先根据前序遍历的结果数组得到根节点（每个左、右子树的根节点）对应的大小，然后根据中序遍历结果数组可以求出左、右子树的数组下标，然后递归地从根节点开始构建左、右子树；class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null |
2020-05-11 13:40:50
99
Cglib3.3.0最新版jar包
2020-06-03
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人