3 ervy

尚未进行身份认证

暂无相关简介

等级
TA的排名 13w+

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

leetcode 287. 寻找重复数【二分法】

此题的二分法与常规的二分法搜索不一样。平常我们用到二分法通常是对拍好序后的元素进行二分搜索,用来搜索数组中特定的元素。该提中的二分则是对数组中元素与给定值之间的大小关系进行二分,首先取数组中最大和最小值的平均值作为mid值,然后统计整个数组中比mid小的数的数量,若数量>mid,这说明重复的数一定在left和mid这个区间内,否则就在mid+1和right这个区间。class Solution { public int findDuplicate(int[] nums) {

2020-05-26 21:09:24

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

leetcode 5. 最长回文子串【双指针】

字符串类型的题目很多都可以用双指针解决,这题是要在一个字符串中找到最长的回文子字符串,对于回文字符串,我们可以使用中心扩散的方式来寻找。回文串有两种形式,一种是中心字符为奇数,另一种则是中心字符为偶数。因此采用中心扩散时,需要对两种形式的中心都进行处理,即从单个字符开始扩散和从两个字符开始扩散两种方式。扩散就是利用双指针不断地向字符串的两端遍历,直到回文字符串条件不成立,终止遍历。class Solution { public String longestPalindrome(String s

2020-05-21 09:45:03

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

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

leetcode 51. N皇后【回溯】

一个经典的回溯算法问题。回溯的本质是决策树的递归过程,用递归的方式遍历所有可能得结果,在遍历过程可以添加适当的判断来实现剪枝从而提高算法的性能。对应本题,决策树的每一层元素可以对应为皇后在每一层所放置的位置,剪枝的判断条件为皇后的攻击范围(即不可将下一层的皇后放置在上层皇后的攻击范围内),由此套用回溯算法的模板即可得到答案。class Solution { //将数组转换为字符串 public List<String> charToString(char[][] chars){

2020-05-18 20:08:24

leetcode 152. 乘积最大子数组【动态规划】

由题意知,每次使用 nums[i] 计算最大值时,都需要使用到之前的历史计算结果,因此可使用动态规划思想,创建dp数组来保存历史的计算结果。本题中每次计算仅使用了上一次的计算结果,可以使用状态压缩将dp数组压缩至一个变量。由于数组中可能存在负数,除了需要记录每次计算后的最大值,还需要记录最小值,当遇到数组中的负数时,需要将最大、最小值交换。class Solution { public int maxProduct(int[] nums) { int max = Integer.

2020-05-18 11:11:15

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

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

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

leetcode 221. 最大正方形【动态规划】

本题难点在于状态转移方程的确定。我们用 dp[i][j] 来表示以(i,j)为右下角的正方形的最大边长。leetcode官方给出了详细的推导过程,因此可以得到状态转移方程为:f[i][j]=min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1class Solution { public int maximalSquare(char[][] matrix) {...

2020-05-08 10:06:18

leetcode 572. 另一个树的子树【递归】

若一颗树是另一个树的子树,那么它可能与另个一相等、或是另一个树的左子树、或是另一个树的右子树。当上述三个条件满足一个时,即可返回true,因此使用 || 运算符。判断两个数是否相等,可以参考 100. 相同的树,也是通过递归判断每个结点的值预计左子树和右子树的各结点的值。class Solution { public boolean isSubtree(TreeNode s, Tre...

2020-05-07 17:18:07

leetcode 983. 最低票价【动态规划】

一个典型的动态规划题,创建一个dp数组来记录每一天的最低消费,这里创建的dp数组长度为days数组最后一个元素的大小+1,即从第0天到最后一天。计算某一天的最低票价时,需要考虑三种票价的情况,因此需要对三种情况取最小值。class Solution { public int mincostTickets(int[] days, int[] costs) { int[] d...

2020-05-07 14:46:05

leetcode 42. 接雨水【单调栈】

方法一:遍历每一列,然后求该列两边的最高的柱子高度,那么该列能存放的雨水量为两边柱子高度较低的一个柱子和当前列的高度差。可以使用动态规划来优化求某一列的两边最高的柱子高度的过程,使用dp数组来保存,可以避免每次都重新遍历整个数组。class Solution { public int trap(int[] height) { int sum = 0; ...

2020-05-07 12:53:46

leetcode 1095. 山脉数组中查找目标值【二分查找】

题目要求对数组的查询次数不超过100次,因此肯定无法使用暴力的遍历。考虑到数组是属于部分有序的,因此可以使用二分查找找到“山顶”,然后对两边的有序数组分别使用二分查找。class Solution { public int findInMountainArray(int target, MountainArray mountainArr) { int size = mo...

2020-04-29 14:44:24

leetcode 103. 二叉树的锯齿形层次遍历【二叉树】

方法一:使用dfs的递归模板,在递归方法中传入一个代表二叉树层数的参数level,该层数决定了往答案数组中放入节点数值的顺序,偶数层顺序放入,奇数层逆序放入。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * Tre...

2020-04-28 16:12:30

leetcode 面试题56 - I. 数组中数字出现的次数【位运算】

将全部数进行异或操作后,结果与需要我们求的两个数字异或的结果相同。找出结果中二进制数为1的位,然后根据该位结果将数组的数字分为两组,两组数字分别异或,最后得到的两个数字即为要求的数字。class Solution { public int[] singleNumbers(int[] nums) { int sum=0; for(int i=0; i<...

2020-04-28 15:31:51

leetcode 46. 全排列【回溯】

一个非常典型的回溯算法案例。回溯算法本质是对一个决策树的遍历,对于本题,进入下一层决策树的条件是往链表里添加一个数字,每个节点的下一层决策树的节点数为数组中剩余的数字个数,因此对于每个节点,都要遍历数组中剩余的数字个数。class Solution { List<List<Integer>> res = new LinkedList<>(); ...

2020-04-25 19:57:10

leetcode 面试题51. 数组中的逆序对【归并排序】

题目的意思可以简化为:对于数组中的某个元素,统计在他之前比它大的元素的个数。对所有每个元素进行统计并累加后即为答案。因此首先可以想到使用两层循环遍历数组,但该方法超时。然后可以想到采用分治的思想,使用归并排序来实现逆序对的计算。通过归并排序,我们可以先对仅有1个元素组成的子数组中的逆序对进行计算,显然此时为0,然后将各个子数组排好序后,再将2个子数组合并为一个子数组。由于合并时每个子数组时有...

2020-04-24 21:27:49

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)