1 啊我太菜了

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

120. 三角形最小路径和 两种动态规划

120. 三角形最小路径和难度:中等 2020/7/14每日一题打卡√题目描述解题思路这个是我自己完全没看答案写出来的,用的是自顶向下的递归,然后一看题解?为啥别人写的都那么短,噢原来别人写的都是自底向上的,这样可以省去判断边界条件1、自顶向下的思路很简单啦,就是贪心加动态规划的思想,对于每个位置的元素,选择从上面一层到这一层的两个路径中最小的,这样到底层就能得到所有可能的路径和,取最小的。这样做其实做复杂了,因为从顶部开始选择的时候,其实是不知道选哪个点会得到全部最小值的,还需要最后的结

2020-07-14 17:19:06

174. 地下城游戏 逆向动态规划

174. 地下城游戏难度:困难2020/7/12每日一题打卡√题目描述解题思路这个月好多动态规划的题,这道题也长得就很动态规划,每一步都跟前一步有关。但是这个不能像普通的那样从左上角走到右下角,因为这样的法没法得到最小值,因为后面会出现什么数字,正数还是负数是无法预知的。正确的做法是从右下角元素开始,依次计算到达这个位置需要的健康点数最小值,然后递推到左上角开始元素。以题目例子 -2 -3 3-5 -10 110 30 -5 为例,首先看-5,因为扣除后健康点必须大于0,所以要想顺利救

2020-07-12 15:44:53

309. 最佳买卖股票时机含冷冻期 动态规划

309. 最佳买卖股票时机含冷冻期难度:中等2020/7/10每日一题打卡√题目描述解题思路买卖股票真的是一整个系列这道题可以用两种状态,当前这天持有股票和当前这天未持有股票1、定义状态dp[i][0] 表示第i天不持有股票的收益dp[i][1] 表示第i天持有股票的收益因为冷冻期的设定,所以不持有股票可能是因为今天刚好卖掉了,也有可能是之前卖出之后一直没有买进;持有股票有可能是前一天一直持有,或者之前卖了然后今天买进的2、状态转移不持有收益 dp[i][0] = Math.m

2020-07-10 23:41:46

面试题 17.13. 恢复空格

面试题 17.13. 恢复空格难度:中等题目描述解题思路1、简单动态规划 O(n2) public int respace(String[] dictionary, String sentence) { Set<String> dict = new HashSet<>(Arrays.asList(dictionary)); int n = sentence.length(); int[] dp = new int[n + 1];

2020-07-09 20:08:30

面试题 16.11. 跳水板

面试题 16.11. 跳水板难度:简单题目描述解题思路做这道题,看看题干,突然感觉,这不就是道高中数学题嘛!所有可能的长度,而且就只有两种长度,不就是首先k个最短的,这就是跳水板最短的长度;再长一点,k-1个短的,1个长的;依次类推,最长的情况是k个长的。所以对于k块木板,可能的长度是k+1种要注意的是边界情况,当k=0的时候,不能生成跳水板;当shorter= longer的时候,只有一种可能的长度;public int[] divingBoard(int shorter, int l

2020-07-09 16:19:56

63. 不同路径 II 动态规划

63. 不同路径 II难度:中等 2020/7/6每日一题打卡最近动态规划的题目好多啊题目描述解题思路/* * 63. 不同路径 II * 2020/7/6 动态规划 */ public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].lengt

2020-07-06 11:12:22

32. 最长有效括号 动态规划

32. 最长有效括号难度:困难2020/7/4每日一题打卡√题目描述解题思路1、动态规划困难题果然有困难的道理,这道题一看就知道是动态规划,可是一写就不会dp[i]代表以i结尾的连续有效子串的长度,只有当是s[i]是右括号)的时候,才有意义举几个简单的例子:比如(),第一个是左括号肯定形不成子串,遇到右括号,那就等于2此时的dp数组就是0 2如果是()()()这种连续的,每次匹配一个括号对,dp[i] = dp[i-2]+2dp数组是0 2 0 4 0 6也有可能是((()))这

2020-07-04 15:00:24

面试题 10.01. 合并排序的数组

面试题 10.01. 合并排序的数组难度:简单题目描述解题思路归并数组,从后往前,很简单public void merge(int[] A, int m, int[] B, int n) { --m; --n; for (int i = m+n+1; i >= 0; i--) { int a = m>=0?A[m]:Integer.MIN_VALUE; int b = n>=0?B[n]:Intege

2020-07-03 11:27:32

剑指 Offer 04. 二维数组中的查找

剑指 Offer 04. 二维数组中的查找难度:简单题目描述解题思路好像前几天做过的,这个数组,找第k个最小元素。所以第一眼感觉用二分法做,但是这道题二分法好像不是很适用。最优解是从右上角或者左下角开始搜索,以右上角为例,如果目标比15小,那么就可以减小搜索范围到15那一列左边,如果小,就可以缩小范围到15那一行下面。整个过程类似于二叉搜索树,左小右大/* * 剑指 Offer 04. 二维数组中的查找 * 2020/7/3 */ public boolean fin

2020-07-03 10:46:47

448. 找到所有数组中消失的数字

448. 找到所有数组中消失的数字难度:简单题目描述解题思路跟442. 数组中重复的数据 简直是一模一样的嘛。442最后要求返回重复的数字,这道题要求返回没出现过的数字,按照方法最后重复的数字占的下标就是本来应该出现的数字。1、原地哈希交换元素/* * 448. 找到所有数组中消失的数字 * 2020/7/2 */ public List<Integer> findDisappearedNumbers(int[] nums) {

2020-07-02 15:31:21

442. 数组中重复的数据 原地哈希

442. 数组中重复的数据难度:中等题目描述解题思路不使用额外空间,而且时间复杂度O(n),那就原地哈希了思路很清楚,就是把每个数字放到对应的下标处,如果最后不对应,就是重复出现的数字/* * 442. 数组中重复的数据 * 2020/7/2 */ public static List<Integer> findDuplicates(int[] nums) { List<Integer> re = ne

2020-07-02 13:34:16

剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字难度:简单题目描述解题思路1、简单哈希因为数组范围确定,所以可以用一个很简单的数组来代替哈希表public int findRepeatNumber(int[] nums) { int n = nums.length; int[] count = new int[n]; for (int i = 0; i < nums.length; i++) { if(count[nums[i]] != 0) {

2020-07-02 12:09:47

378. 有序矩阵中第K小的元素 k路归并+二分法

378. 有序矩阵中第K小的元素难度:中等2020/7/2每日一题打卡√题目描述解题思路1、直接用优先队列简单直接无脑/* * 378. 有序矩阵中第K小的元素 * 2020/7/2 类似于合并k个有序列表 */ public int kthSmallest(int[][] matrix, int k) { if(k == 1) return matrix[0][0]; int n = ma

2020-07-02 11:29:21

1143. 最长公共子序列 动态规划

1143. 最长公共子序列难度:中等今天做了一个最长公共子数组,评论里面很多人提到这道题,就顺便一起做了。子数组是连续的,如果某个位置没匹配上就直接等于0,以这个位置为起点重新匹配。这个子序列可以不连续,如果匹配上那就直接等于dp[i][j]+1如果没匹配上,就取前面过程中的最大值题目描述解题思路还是动态规划,dp[i][j]代表以A[i-1]与B[j-1]结尾的子序列的长度。如果某个位置匹配上了,那么加一。如果没匹配上,一个位置没匹配上并不影响总的值,在dp[i][j+1], dp[i+

2020-07-01 11:48:02

718. 最长重复子数组 动态规划

718. 最长重复子数组难度:中等题目描述解题思路1、动态规划长得就像动态规划的题,但是还是不是自己想出来的设置状态dp[i][j]代表以A[i-1]与B[j-1]结尾的公共字串的长度初始的时候是0,循环遍历填表,记录全局最大值比如A: [1,2,3,2,1]B: [3,2,1,4,7]0 0 1 0 00 1 0 0 01 0 0 0 00 2 0 0 00 0 3 0 0/* * 718. 最长重复子数组 * 2020/7/1 动态规划 * dp

2020-07-01 11:07:03

剑指 Offer 57. 和为s的两个数字

剑指 Offer 57. 和为s的两个数字难度:简单题目描述解题思路因为有前提条件是数组递增有序,所以可以采用双指针的方式,时间复杂度O(n),空间复杂度O(1)/* * 剑指 Offer 57. 和为s的两个数字 * 2020/6/30 */ public int[] twoSum(int[] nums, int target) { int i = 0,j = nums.length-1; while(i < j) { int sum = num

2020-06-30 12:44:10

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表难度:简单题目描述解题思路1、用栈辅助/* * 剑指 Offer 06. 从尾到头打印链表 * 2020/6/30 */ public int[] reversePrint(ListNode head) { Stack<Integer> stack = new Stack<>(); ListNode p = head; while(p !

2020-06-30 12:29:32

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列难度:简单招银网络科技的电话面试,好多人都被问到了这道题,正有想做一做的想法,力扣就出了每日一题!是快乐的感觉题目描述解题思路栈的特点是后进先出,队列的特点是先进先出,用两个栈,一个栈用来保存入栈元素,另一个栈用来颠倒出栈顺序~/* * 剑指 Offer 09. 用两个栈实现队列 * 2020/6/30每日一题打卡 */ class CQueue { Stack<Integer> stack_in;

2020-06-30 12:10:52

414. 第三大的数

414. 第三大的数难度:简单题目描述本来这道题不难,但是测试用例好坑,面向测试用例编程了好久解题思路类似于大根堆的思想,维护一个长度为3的数组,数组里元素按照从大到小的顺序排序。初始是int型最小值,每添加一个元素,维护数组里的元素大小顺序。要注意的细节(巨坑)有:重复的元素不能计算,如果不足三个值要返回最大值。这里的三个值不是数组的长度,是不重复出现的数字,比如111112,就只能算1和2,应该返回2.还有测试用例[-2147483648,-2147483648,-2147483648

2020-06-29 15:26:24

703. 数据流中的第K大元素 优先队列实现

703. 数据流中的第K大元素难度:简单题目描述解题思路这个跟TOP K问题差不多嘛,因为强调了是数据流中的元素,所以实时维护一个大小为k的小根堆比较合适。还是用优先队列来实现小根堆,要考虑num数组是空的情况,为了避免后面堆为空,加入一个最小元素import java.util.PriorityQueue;public class KthLargest { PriorityQueue<Integer> minHead; int k; public KthLargest(i

2020-06-29 11:35:05

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。