waigo

题解

/ 注册

全部文章 / 题解（共42篇）

题解 | #丢棋子问题#动态规划的两种思维来自专栏

/** *O(n*k)的解法，这种解法就是通常想到的正向思维，由于不知道在哪一楼丢下就会碎， *所以需要从i楼开始进行尝试 *如果i楼碎了，那么就得以左边为子过程去查最少需要多少次能得出答案了。 *如果i楼没碎，那么就得以右边为子过程去查最少需要多少次能得出答...

Java 动态规划

2021-10-18

1 624

题解 | # NC83 子数组最大乘积# 来自专栏

其实想要知道一个子数组的最大乘积首先要意识到其实子数组的乘积可以由前缀乘积除以某个更小前缀的乘积来得到，需要注意的是碰到0得重新记录前缀乘积为1，因为答案子数组不可能跨过0的。 public double maxProduct(double[] arr) { if(arr==null...

动态规划

2021-10-10

0 508

题解 | #获取当前薪水第二多的员工的emp_no以及其对应的薪水salary#

#1.先将薪水最高的找出来 #select max(salary) from `salaries`; #2.找出薪水第二高的 #select max(salary) from `salaries` where salary<(select max(salary) from `salaries`...

Mysql

2021-09-27

0 330

题解 | #矩阵中的路径# 来自专栏

进行DFS遍历，每次到一个位置先判断是否能匹配word中的一个，能才踩下去 int[][] dirs = {{0,-1},{0,1},{-1,0},{1,0}};//左，右，上，下 public boolean hasPath (char[][] matrix, String wor...

Java DFS

2021-09-25

1 525

题解 | #二叉搜索树的第k个结点#Morris遍历实现的O(1)空间复杂度来自专栏

TreeNode KthNode(TreeNode pRoot, int k) { //Morris遍历 TreeNode tmp = pRoot; TreeNode res = null; int cnt = 0; w...

Java 中序遍历 Morris遍历

2021-09-25

0 385

题解 | #字符流中第一个不重复的字符# 来自专栏

用一个数组记录一下各个字符出现次数，然后用队列来存一下上一个走了该由谁来接替，所以的字符进一次出一次队列，所以算法时间复杂度为O(N); public void Insert(char ch) { //所有字符都在第一次来的时候进队列，换的时候将不为1次的全部弹出 ...

Java 队列哈希表

2021-09-23

0 481

题解 | #表示数值的字符串#有限状态自动机来自专栏

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @...

Java 状态自动机

2021-09-23

0 422

题解 | #正则表达式匹配#递归+栈

用递归结合没有括号的做法 public int solve(String s) { if (s == null || s.length() == 0) return 0; return calc(s.toCharArray(), 0)[0]; } ...

Java 递归栈

2021-09-23

0 412

题解 | #正则表达式匹配#动态规划解法

这里dp[row][col]的意思是，str的row长度去和pattern的col长度做一个正则匹配是否能成功，所以说此时最后一位字符分别是row-1和col-1位置 public boolean match (String str, String pattern) { if...

Java 动态规划

2021-09-23

1 470

#JZ45 扑克牌顺子#O(N)和O(NlogN)解法

import java.util.*; public class Solution { //方法一：除了0之外的数中不能有重复，在这基础上最大和最小值的差不能大于5 //需要保存一个数是否出现过，空间复杂度O(N),时间复杂度O(N) public boolean IsCon...

Java 数组

2021-09-21

0 417