下一個(gè)更大的元素

題目：給定兩個(gè)沒有重復(fù)元素的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值。nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對(duì)應(yīng)位置的右邊的第一個(gè)比 x 大的元素。如果不存在，對(duì)應(yīng)位置輸出-1。

示例 1:
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對(duì)于num1中的數(shù)字4，你無法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字，因此輸出 -1。
對(duì)于num1中的數(shù)字1，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3。
對(duì)于num1中的數(shù)字2，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字，因此輸出 -1。
示例 2:
輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
對(duì)于num1中的數(shù)字2，第二個(gè)數(shù)組中的下一個(gè)較大數(shù)字是3。
對(duì)于num1中的數(shù)字4，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字，因此輸出 -1。

注意:

nums1和nums2中所有元素是唯一的。
nums1和nums2 的數(shù)組大小都不超過1000。

思路：這道題感覺就和很復(fù)雜，需要存儲(chǔ)的點(diǎn)太多了。比如數(shù)組數(shù)組元素1的位置。并且兩個(gè)都是無序的所以如果暴力判斷還得一遍一遍循環(huán)，絕對(duì)不應(yīng)該這么寫，目前的想法就是保存每一個(gè)元素和他下一個(gè)大元素，存在一個(gè)map里，沒有存value存-1.等把num2遍歷存到map后在直接獲取num1中的每一個(gè)元素對(duì)應(yīng)的value。

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        //這里用到了棧先進(jìn)后出的原則
        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;
    }
}

第一個(gè)版本的代碼。這里有一個(gè)很繞的邏輯：就是棧中，后入元素一定小于前面的元素。不然也不會(huì)累加存儲(chǔ)。這塊的我參考題解的邏輯。我自己一開始用的數(shù)組，結(jié)果發(fā)現(xiàn)來回來去for循環(huán)要寫瘋了?？戳祟}解才發(fā)現(xiàn)思路沒問題，數(shù)據(jù)結(jié)構(gòu)用錯(cuò)了而已。

棧中元素

剩下也看了執(zhí)行時(shí)間1ms，2ms的代碼。講真大循環(huán)小循環(huán)，隨隨便便四五個(gè)for循環(huán)，這個(gè)題真的有點(diǎn)復(fù)雜啊。貪多嚼不爛，我就暫時(shí)會(huì)這一種方法就行了。下一題吧。

鍵盤行

給定一個(gè)單詞列表，只返回可以使用在鍵盤同一行的字母打印出來的單詞。鍵盤如下圖所示。

題目截圖

思路：額，如圖吧，這道題應(yīng)該不難做，但是絕對(duì)很麻煩。畢竟看著就是那種判斷來判斷去的。初步一看判斷數(shù)組中每個(gè)字符串的每個(gè)字符就已經(jīng)是雙層循環(huán)了。。還有細(xì)節(jié)處理，嘖嘖。一點(diǎn)點(diǎn)來吧只能。我去寫代碼
emmmm~第一版本做完了，一次通過了，除了墨跡點(diǎn)沒別的。性能也超過百分百：

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;
    }
}

咳咳，這里其實(shí)可以用統(tǒng)一小寫的，但是我直接在給定字符串就大小寫都算上了，其實(shí)我想的是先做出來如果性能不行再優(yōu)化，但是直接0ms就不優(yōu)化了。
思路就是判斷一個(gè)字符串的第一個(gè)單詞屬于哪一行的，接下來照著這行判斷，出現(xiàn)這行不存在的直接break。都判斷完了沒有不是的加到結(jié)果集中。
因?yàn)橐婚_始不知道結(jié)果集多長(zhǎng)所以創(chuàng)建的數(shù)組和給定數(shù)組長(zhǎng)度一樣，再遍歷一遍使得結(jié)果集大小正好。

二叉搜索樹中的眾數(shù)

題目：給定一個(gè)有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）。

假定 BST 有如下定義：

結(jié)點(diǎn)左子樹中所含結(jié)點(diǎn)的值小于等于當(dāng)前結(jié)點(diǎn)的值
結(jié)點(diǎn)右子樹中所含結(jié)點(diǎn)的值大于等于當(dāng)前結(jié)點(diǎn)的值
左子樹和右子樹都是二叉搜索樹

題目

思路：額，樹的問題，遞歸迭代循環(huán)。我覺得這個(gè)進(jìn)階怕不是一個(gè)隱含的提醒，告訴我們要用遞歸吧？哈哈，反正我現(xiàn)在的思路就是遍歷樹，存list或者數(shù)組。然后排序，然后判斷出現(xiàn)次數(shù)最多的元素。然后輸出。對(duì)，就是這個(gè)邏輯。我去嘗試寫代碼。
好的吧，要開始寫了發(fā)現(xiàn)我這個(gè)思路的大bug，對(duì)，用了額外的空間了。。。但是我還是不要臉的用了這個(gè)辦法，別說不用額外空間了，我不僅用了，還大用特用，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)){
                    //當(dāng)有次數(shù)更多的，max被替換掉。同時(shí)數(shù)量也歸1
                    max = map.get(i);
                    n = 1;
                }else if(max==map.get(i)){
                    //當(dāng)數(shù)量最多的有多個(gè)n計(jì)數(shù)。
                    n++;
                }              
            }else{
                map.put(i,1);
            }
        }
        //說明沒有兩次出現(xiàn)的元素，則原樹中所有元素都是眾數(shù)
        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評(píng)論，那種三五行解決問題的大神至今沒出現(xiàn)。而且提交記錄我之前的代碼沒有不用額外空間的。所以這道題的優(yōu)化先待定吧。下一題。

七進(jìn)制數(shù)

題目：給定一個(gè)整數(shù)，將其轉(zhuǎn)化為7進(jìn)制，并以字符串形式輸出。

示例 1:
輸入: 100

輸出: "202"
示例 2:
輸入: -7
輸出: "-10"
注意: 輸入范圍是 [-1e7, 1e7] 。

思路：怎么說呢，從二進(jìn)制到16進(jìn)制，之前的excel格還用到了26進(jìn)制，今天又有一個(gè)七進(jìn)制，完全不意外。本來看到負(fù)號(hào)我還挺虛，尋思還得補(bǔ)碼啥的咋的？再一看不就是正數(shù)前面加一個(gè)負(fù)號(hào)么，我直接去擼代碼了。
emmm。。。還好這道題沒什么坑，一次通過的送分題，算是和上個(gè)題的難度綜合？直接貼代碼：

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;
    }
}

因?yàn)樾阅苤苯映^百分百了，所以我也不看題解了，直接下一題。

相對(duì)名次

題目：給出 N 名運(yùn)動(dòng)員的成績(jī)，找出他們的相對(duì)名次并授予前三名對(duì)應(yīng)的獎(jiǎng)牌。前三名運(yùn)動(dòng)員將會(huì)被分別授予 “金牌”，“銀牌” 和“ 銅牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。

(注：分?jǐn)?shù)越高的選手，排名越靠前。)
示例 1:
輸入: [5, 4, 3, 2, 1]
輸出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解釋: 前三名運(yùn)動(dòng)員的成績(jī)?yōu)榍叭叩模虼藢?huì)分別被授予 “金牌”，“銀牌”和“銅牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的兩名運(yùn)動(dòng)員，我們只需要通過他們的成績(jī)計(jì)算將其相對(duì)名次即可。

提示:

N 是一個(gè)正整數(shù)并且不會(huì)超過 10000。
所有運(yùn)動(dòng)員的成績(jī)都不相同。

思路：額，這道題有點(diǎn)意思，乍一看很簡(jiǎn)單啊。仔細(xì)一看居然一時(shí)間想不出來好辦法。但是我相信沒有萬能哈希解決不了的問題。二話不說先上排序存?zhèn)€map在往下。
我哈希大法好，果然解決了問題。至于性能什么的是實(shí)現(xiàn)以后該考慮的，貼上第一版本的代碼：

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;
    }
}

我也不知道我現(xiàn)在是中了什么毒，寫出來的代碼又臭又長(zhǎng)，哎，開始想著怎么優(yōu)化吧。其實(shí)我覺得這道題的優(yōu)化點(diǎn)應(yīng)該是在于map。我這里map的key 是數(shù)值沒問題，但是value完全就是一個(gè)沒用的表示（這里value是排名，但是其實(shí)也可以用數(shù)組下標(biāo)表示，所以不是必要的）。我覺得這里如果把map換成數(shù)組性能會(huì)好多了。
但是問題來了，這個(gè)數(shù)組，長(zhǎng)度是多少？想用下標(biāo)表示原數(shù)組的數(shù)值，萬一是1,10000，那么就要建立一個(gè)10001的數(shù)組。。。不過應(yīng)該也是一個(gè)優(yōu)化點(diǎn)，我去試試再說。

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) {
                //因?yàn)槭菑暮笸氨闅v，所以第一個(gè)元素就是最大的。金牌
                switch (rank) {
                    case 1:
                    //這里arr[i]的值是nums[index]的值，相當(dāng)于直接放到了排名的下標(biāo)位置
                        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換成數(shù)組果然性能上來的，但是邏輯也更不直觀了，盡量理解吧。

完美數(shù)

題目：對(duì)于一個(gè) 正整數(shù)，如果它和除了它自身以外的所有正因子之和相等，我們稱它為“完美數(shù)”。給定一個(gè) 整數(shù) n， 如果他是完美數(shù)，返回 True，否則返回 False

示例：
輸入: 28
輸出: True
解釋: 28 = 1 + 2 + 4 + 7 + 14
提示：
輸入的數(shù)字 n 不會(huì)超過 100,000,000. (1e8)

思路：我理解的這道題分為兩部分：1，這個(gè)數(shù)的因數(shù)。 2，和是不是相等。首先這個(gè)因數(shù)這個(gè)好說，暴力法也能判斷，但是那樣太low了，關(guān)鍵是怎么做的優(yōu)雅？首先因子肯定成對(duì)出現(xiàn)的。所以只要遍歷到開根號(hào)的數(shù)字就可以了。再大的屬于成對(duì)的另一個(gè)數(shù)字。不需要遍歷。直接上代碼。

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的飛起，真的，蒂花之秀！

性能第一的代碼

斐波那契數(shù)列

題目：斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為斐波那契數(shù)列。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N，計(jì)算 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

思路：講真，這個(gè)是早有耳聞的一個(gè)數(shù)學(xué)知識(shí)。依稀記得剛剛接觸的時(shí)候是在爬樓梯的那道題。也第一次知道了所謂的動(dòng)態(tài)規(guī)劃。甚至當(dāng)時(shí)鉆研了很久才勉強(qiáng)理解。不過現(xiàn)在動(dòng)態(tài)規(guī)劃的題做了好幾道了，也多多少少比一開始有那么一點(diǎn)意識(shí)了。再回來看這道題，就是送分的了。直接上代碼,主思路妥妥的遞歸。

class Solution {
    public int fib(int N) {
        return N<=1?N:fib(N-1)+fib(N-2);
    }
}

額，三分鐘寫出來的遞歸，雖然性能不行但是進(jìn)步妥妥的，我有一個(gè)不太成熟的猜想，我覺得性能好的可能用了常量switch-case。。畢竟大力扣什么人才都有。。哈哈
好的吧，是我小人了，其實(shí)只不過是把遞歸用循環(huán)實(shí)現(xiàn)了而已。直接上代碼：

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;
    }
}

感慨一下，真的很謝謝這道題，讓我實(shí)實(shí)在在的看到了自己的進(jìn)步。這篇文章是第二十八篇。刷leetcode差不多一個(gè)月了。從基礎(chǔ)不扎實(shí)，數(shù)據(jù)結(jié)構(gòu)不清晰，遞歸用的少等等等等，到現(xiàn)在雖然沒多厲害但是確實(shí)很多以前不熟悉，不會(huì)的東西都手到擒來。其實(shí)學(xué)習(xí)堅(jiān)持最難。為什么?因?yàn)檫@個(gè)不是一個(gè)可以一直肉眼可見進(jìn)度的東西。
就好像比如一個(gè)學(xué)生，刻苦努力一個(gè)月，但是這次月考的題恰好不是復(fù)習(xí)到的，會(huì)出現(xiàn)的狀況就是努力學(xué)習(xí)一個(gè)月越學(xué)成績(jī)?cè)较陆盗?。吃苦不可怕，看不到進(jìn)步，可能是在做無用功等迷茫不確定，才會(huì)把一個(gè)人擊垮！
又是一個(gè)周五，時(shí)光荏苒，力扣的1298道題，總有一天會(huì)做完了！加油！
今天的筆記就記到這里，畢竟周末。給自己放個(gè)假，吃個(gè)夜宵啥的，也祝大家周末愉快，工作順順利利！