waigo

题解

/ 注册

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

题解 | #数组中的逆序对#

public class Solution { public static final int MOD = 1000000007; int res; public int InversePairs(int [] array) { //进行归并排序，在merge...

Java 归并排序

2021-09-20

0 414

题解 | #丑数#

import java.util.*; public class Solution { /*public int GetUglyNumber_Solution(int index) { //很明显，丑数除了2,3,5之外其他丑数肯定都是由丑数乘来的，不是丑数的数乘啥都不会变成...

Java 动态规划三指针

2021-09-20

5 526

题解 | #JZ31 整数中1出现的次数#

public int NumberOf1Between1AndN_Solution(int n) { //出现的总数其实就是各个位置上的1的个数的和 //当前位，n(i),cur //高位n(N)....n(i+1)，high //低位...

Java 数学

2021-09-19

0 335

题解 | #二叉搜索树的后序遍历序列#

将后序序列看成树，在数组上玩树的深度遍历，关键点在于找到左子树和右子树的切分点，可以使用二分来加速 public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence...

二分查找二叉树深度优先搜索 DFS

2021-09-17

0 388

题解 | #栈的压入、弹出序列#

这题使用模拟法，也就是我们脑子咋分辨是否能够作为弹出序列的？就是看看照着弹出序列能不能弹完，其实我觉得不管是有没有重复值这种模拟的方法都能正确的，比如下面这种，老实说其实不在意到底哪个4先弹出来。1 4 2 3 5 44 5 3 2 4 1 import java.util.*; public c...

Java 栈

2021-09-17

0 363

题解 | #数字在升序数组中出现的次数#二分法

public int GetNumberOfK(int [] array , int k) { if(array==null||array.length==0) return 0; //有序，想到二分，如何用二分来优化？ //这是数组，如何确定某个数的个数？...

二分法

2021-09-04

0 403

题解 | #矩形覆盖#矩阵快速幂乘法解决

这题通过找规律可以发现是一个类似斐波那契数列的二阶问题，常规解法就是使用递归或者改迭代，但是这个复杂度就是O(N)的。可以有一种矩阵快速幂乘来优化的算法。 public int rectCover(int target) { if(target==0||target==1||...

矩阵快速幂乘算法

2021-09-04

0 381

题解 | #二维数组中的查找#

两个重要点 1.每一行都按照从左到右递增的顺序排序 2.每一列都按照从上到下递增的顺序排序那么起始点a选择右上角* 1.如果a下方位置b小于等于target，由于b>=a,很明显a所在这行就直接淘汰了 2.如果b位置大于target了，说明这一列就淘汰了，再往下走都是大于target的,该...

矩阵

2021-09-02

0 387

题解 | #螺旋矩阵#

矩阵类题目关键点在于将问题进行拆分，这里就可以拆分成一层一层的矩阵，只要规定好每个矩阵如何螺旋收集外围数字就好了。 public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integ...

矩阵

2021-09-02

0 535

题解 | #重建二叉树#

就是利用前序序列找到头，然后在中序序列中找到这个头的位置h，h左边就是左子树，h右边就是右子树，然后递归就可以了 public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { if(pre==null||vin=...

DFS 树

2021-08-30

0 350