刷leetCode算法题+解析（二十八）
下一个更大的元素
题目：给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2，第二个数组中的下一个较大数字是3。
对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
注意:
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
思路：这道题感觉就和很复杂，需要存储的点太多了。比如数组数组元素1的位置。并且两个都是无序的所以如果暴力判断还得一遍一遍循环，绝对不应该这么写，目前的想法就是保存每一个元素和他下一个大元素，存在一个map里，没有存value存-1.等把num2遍历存到map后在直接获取num1中的每一个元素对应的value。
public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
//这里用到了栈先进后出的原则
Stack < Integer > stack = new Stack < > ();
HashMap < Integer, Integer > map = new HashMap < > ();
int[] res = new int[findNums.length];
for (int i = 0; i < nums.length; i++) {
while (!stack.empty() && nums[i] > stack.peek())
map.put(stack.pop(), nums[i]);
stack.push(nums[i]);
}
while (!stack.empty())
map.put(stack.pop(), -1);
for (int i = 0; i < findNums.length; i++) {
res[i] = map.get(findNums[i]);
}
return res;
}
}
第一个版本的代码。这里有一个很绕的逻辑：就是栈中，后入元素一定小于前面的元素。不然也不会累加存储。这块的我参考题解的逻辑。我自己一开始用的数组，结果发现来回来去for循环要写疯了。看了题解才发现思路没问题，数据结构用错了而已。
栈中元素
剩下也看了执行时间1ms，2ms的代码。讲真大循环小循环，随随便便四五个for循环，这个题真的有点复杂啊。贪多嚼不烂，我就暂时会这一种方法就行了。下一题吧。
键盘行
给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
题目截图
思路：额，如图吧，这道题应该不难做，但是绝对很麻烦。毕竟看着就是那种判断来判断去的。初步一看判断数组中每个字符串的每个字符就已经是双层循环了。。还有细节处理，啧啧。一点点来吧只能。我去写代码
emmmm~第一版本做完了，一次通过了，除了墨迹点没别的。性能也超过百分百：
class Solution {
public String[] findWords(String[] words) {
String[] res = new String[words.length];
String fir = "qwertyuiopQWERTYUIOP";
String sec = "asdfghjklASDFGHJKL";
String tir = "zxcvbnmZXCVBNM";
int k = 0;
for(int i = 0;i<words.length;i++){
String temp = "";
for(int j = 0;j<words[i].length();j++){
if(fir.indexOf(words[i].charAt(0))!=-1){
temp = fir;
}else if(sec.indexOf(words[i].charAt(0))!=-1){
temp = sec;
}else{
temp = tir;
}
if(temp.indexOf(words[i].charAt(j))==-1){
break;
}
if(temp.indexOf(words[i].charAt(j))!=-1&&j==words[i].length()-1){
res[k]=words[i];
k++;
}
}
}
String[] result = new String[k];
for(int p = 0;p<k;p++){
result[p] = res[p];
}
return result;
}
}
咳咳，这里其实可以用统一小写的，但是我直接在给定字符串就大小写都算上了，其实我想的是先做出来如果性能不行再优化，但是直接0ms就不优化了。
思路就是判断一个字符串的第一个单词属于哪一行的，接下来照着这行判断，出现这行不存在的直接break。都判断完了没有不是的加到结果集中。
因为一开始不知道结果集多长所以创建的数组和给定数组长度一样，再遍历一遍使得结果集大小正好。
二叉搜索树中的众数
题目：给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
题目
思路：额，树的问题，递归迭代循环。我觉得这个进阶怕不是一个隐含的提醒，告诉我们要用递归吧？哈哈，反正我现在的思路就是遍历树，存list或者数组。然后排序，然后判断出现次数最多的元素。然后输出。对，就是这个逻辑。我去尝试写代码。
好的吧，要开始写了发现我这个思路的大bug，对，用了额外的空间了。。。但是我还是不要脸的用了这个办法，别说不用额外空间了，我不仅用了，还大用特用，list，map都没缺的。没办法，不然真的没思路。先把代码贴出来（虽然性能不咋地，但是跟题解的代码比短了一半得）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] findMode(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
getAllNode(root,list);
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int max = 0;
int n = 1;
for(Integer i :list){
if(map.containsKey(i)){
map.put(i,map.get(i)+1);
if(max<map.get(i)){
//当有次数更多的，max被替换掉。同时数量也归1
max = map.get(i);
n = 1;
}else if(max==map.get(i)){
//当数量最多的有多个n计数。
n++;
}
}else{
map.put(i,1);
}
}
//说明没有两次出现的元素，则原树中所有元素都是众数
if(max==0) return list.stream().mapToInt(Integer::valueOf).toArray();
int [] res = new int[n];
int index = 0;
for(Integer key: map.keySet()){
if(map.get(key)==max){
res[index] = key;
index++;
}
}
return res;
}
public void getAllNode(TreeNode root,List<Integer> list){
if(root==null) return;
list.add(root.val);
getAllNode(root.left,list);
getAllNode(root.right,list);
}
}
很遗憾，这道题一共就31题解，65评论，那种三五行解决问题的大神至今没出现。而且提交记录我之前的代码没有不用额外空间的。所以这道题的优化先待定吧。下一题。
七进制数
题目：给定一个整数，将其转化为7进制，并以字符串形式输出。
示例 1:
输入: 100
输出: "202"
示例 2:
输入: -7
输出: "-10"
注意: 输入范围是 [-1e7, 1e7] 。
思路：怎么说呢，从二进制到16进制，之前的excel格还用到了26进制，今天又有一个七进制，完全不意外。本来看到负号我还挺虚，寻思还得补码啥的咋的？再一看不就是正数前面加一个负号么，我直接去撸代码了。
emmm。。。还好这道题没什么坑，一次通过的送分题，算是和上个题的难度综合？直接贴代码：
class Solution {
public String convertToBase7(int num) {
String res = "";
if(num==0) return res+0;
if(num<0){
num = -num;
while(num>0){
res = num%7 + res;
num = num/7;
}
return "-"+res;
}
while(num>0){
res = num%7 + res;
num = num/7;
}
return res;
}
}
因为性能直接超过百分百了，所以我也不看题解了，直接下一题。
相对名次
题目：给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。
(注：分数越高的选手，排名越靠前。)
示例 1:
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。
提示:
N 是一个正整数并且不会超过 10000。
所有运动员的成绩都不相同。
思路：额，这道题有点意思，乍一看很简单啊。仔细一看居然一时间想不出来好办法。但是我相信没有万能哈希解决不了的问题。二话不说先上排序存个map在往下。
我哈希大法好，果然解决了问题。至于性能什么的是实现以后该考虑的，贴上第一版本的代码：
class Solution {
public String[] findRelativeRanks(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int [] ar = new int[nums.length];
for(int l=0;l<nums.length;l++){
ar[l] = nums[l];
}
Arrays.sort(ar);
int j = 1;
for(int i = ar.length-1;i>=0;i--){
map.put(ar[i],j);
j++;
}
String [] res = new String[nums.length];
for(int k = 0;k<nums.length;k++){
if(map.get(nums[k])<=3){
if(map.get(nums[k])==3) res[k] = "Bronze Medal";
if(map.get(nums[k])==2) res[k] = "Silver Medal";
if(map.get(nums[k])==1) res[k] = "Gold Medal";
}else{
res[k] = map.get(nums[k])+"";
}
}
return res;
}
}
我也不知道我现在是中了什么毒，写出来的代码又臭又长，哎，开始想着怎么优化吧。其实我觉得这道题的优化点应该是在于map。我这里map的key 是数值没问题，但是value完全就是一个没用的表示（这里value是排名，但是其实也可以用数组下标表示，所以不是必要的）。我觉得这里如果把map换成数组性能会好多了。
但是问题来了，这个数组，长度是多少？想用下标表示原数组的数值，万一是1,10000，那么就要建立一个10001的数组。。。不过应该也是一个优化点，我去试试再说。
class Solution {
public String[] findRelativeRanks(int[] nums) {
int max = 0;
for(int n:nums){
max = Math.max(max,n);
}
int [] arr = new int[max+1];
int j = 1;
for(int i = nums.length-1;i>=0;i--){
arr[nums[i]] = i+1;
}
String [] res = new String[nums.length];
for (int i = max, rank = 1; i >= 0; i--) {
if (arr[i] > 0) {
//因为是从后往前遍历，所以第一个元素就是最大的。金牌
switch (rank) {
case 1:
//这里arr[i]的值是nums[index]的值，相当于直接放到了排名的下标位置
res[arr[i] - 1] = "Gold Medal";
break;
case 2:
res[arr[i] - 1] = "Silver Medal";
break;
case 3:
res[arr[i] - 1] = "Bronze Medal";
break;
default:
res[arr[i] - 1] = Integer.toString(rank);
break;
}
rank++;
}
}
return res;
}
}
把map换成数组果然性能上来的，但是逻辑也更不直观了，尽量理解吧。
完美数
题目：对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False
示例：
输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14
提示：
输入的数字 n 不会超过 100,000,000. (1e8)
思路：我理解的这道题分为两部分：1，这个数的因数。 2，和是不是相等。首先这个因数这个好说，暴力法也能判断，但是那样太low了，关键是怎么做的优雅？首先因子肯定成对出现的。所以只要遍历到开根号的数字就可以了。再大的属于成对的另一个数字。不需要遍历。直接上代码。
class Solution {
public boolean checkPerfectNumber(int num) {
if(num==1) return false;
int res = num-1;
for(int i =2;i<=Math.sqrt(num);i++){
if(num%i==0){
res -= i;
res -= num/i;
}
}
return res==0?true:false;
}
}
！！！我看了排名第一的代码，6的飞起，真的，蒂花之秀！
性能第一的代码
斐波那契数列
题目：斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
思路：讲真，这个是早有耳闻的一个数学知识。依稀记得刚刚接触的时候是在爬楼梯的那道题。也第一次知道了所谓的动态规划。甚至当时钻研了很久才勉强理解。不过现在动态规划的题做了好几道了，也多多少少比一开始有那么一点意识了。再回来看这道题，就是送分的了。直接上代码,主思路妥妥的递归。
class Solution {
public int fib(int N) {
return N<=1?N:fib(N-1)+fib(N-2);
}
}
额，三分钟写出来的递归，虽然性能不行但是进步妥妥的，我有一个不太成熟的猜想，我觉得性能好的可能用了常量switch-case。。毕竟大力扣什么人才都有。。哈哈
好的吧，是我小人了，其实只不过是把递归用循环实现了而已。直接上代码：
class Solution {
public int fib(int N) {
if (N == 0) {
return 0;
}
if (N == 1) {
return 1;
}
int before = 0, current = 1;
for (int i = 2; i <= N; i++) {
int temp = before + current;
before = current;
current = temp;
}
return current;
}
}
感慨一下，真的很谢谢这道题，让我实实在在的看到了自己的进步。这篇文章是第二十八篇。刷leetcode差不多一个月了。从基础不扎实，数据结构不清晰，递归用的少等等等等，到现在虽然没多厉害但是确实很多以前不熟悉，不会的东西都手到擒来。其实学习坚持最难。为什么?因为这个不是一个可以一直肉眼可见进度的东西。
就好像比如一个学生，刻苦努力一个月，但是这次月考的题恰好不是复习到的，会出现的状况就是努力学习一个月越学成绩越下降了。吃苦不可怕，看不到进步，可能是在做无用功等迷茫不确定，才会把一个人击垮！
又是一个周五，时光荏苒，力扣的1298道题，总有一天会做完了！加油！
今天的笔记就记到这里，毕竟周末。给自己放个假，吃个夜宵啥的，也祝大家周末愉快，工作顺顺利利！
