牛客289281343号

题解

/ 注册

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

最大正方形

解题思路：根据提示，采用动态规划的方法求解。观察规律，除了单个元素的正方形，其余常规的正方形判断如下，1 11 1这是一个正方形，是因为arr[i-1][j-1]，arr[i-1][j]，arr[i][j-1]，arr[i][j]的元素相同增加问题规模，继续观察，1 1 11 1 11 1 1这是一...

2020-10-28

1 829

寻找第K大

解题思路：根据题目的提示，按照快排的思想解题。在快排过程中，每次递归都可以确定某一个元素的位置，若该元素正处于第K大的位置，则直接返回该值；否则，在快排之后返回第K大的元素值。需注意的是，如果按照升序排列，第K大的元素位置在数组a的n-K的位置上。 import java.util.*; publ...

2020-10-26

0 587

二叉树的深度

解题思路：树的深度等于左右子数的最大值加一，若根节点为空，则返回0. /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeN...

2020-10-22

0 544

变态跳台阶

解题思路：有n个台阶时，F(n)=F(n-1)+F(n-2)+F(n-3)+……+F(1)+F(0).又因为F(1)=F(0)=1,经计算可得，F(n)=2^(n-1) import java.lang.Math; public class Solution { public int Jum...

2020-10-22

0 522

找到字符串的最长无重复字符子串

解题思路：通过两个指针分别指向子串的头尾，并将出现过的字符以及最新一次出现的位置存入hash表中。当尾指针所指字符在hash表中，则改变头指针位置；否则，只向后移动尾指针。 import java.util.*; public class Solution { /** * ...

2020-09-24

1 612

合并二叉树

解题思路：将两个节点的值求和并赋给t1，然后递归合并t1、t2的左右节点。 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode ri...

2020-09-23

10 1254

进制转换

解题思路：可以用栈来存储每次的余数；也可直接用StringBuilder,之后用reverse()方法反转字符串。注意：M为0、负数、正数的三种情况，以及十进制以上的转化情况。例：11进制中，10用A表示。 import java.util.*; public class Solution { ...

2020-09-22

0 678

缺失数字

解题思路：由于数组中的数字可能不是有序的，所以首先根据规律求出这n+1个数字之和，然后遍历数组并从和中依次减去出现的数字，最后便得出了未选中的数字。 import java.util.*; public class Solution { /** * 找缺失数字 * @...

2020-09-22

0 589

数组中出现次数超过一半的数字

解题思路：遍历数组，用哈希表存储每个数字出现的次数。当出现次数等于长度的一半时，就可以返回该数字了；否则，返回0。注意：数组为空和数组长度为1的情况；另外，在哈希表中若用整型作为key，需用Integer.valueOf()将其转化下,不然易于索引混淆。 import java.util.*; p...

2020-09-21

0 646

旋转数组的最小数字

解题思路：若数组为空，则返回0；否则，依次比较数组相邻的两个值，由于旋转数组的规律，当不满足array[i]<=array[i+1]时，返回array[i+1]。注意:数组内的值都相同的情况也要考虑在内。 import java.util.ArrayList; public class Sol...

2020-09-21

0 605