新的一天，刷題繼續(xù)！今天小目標(biāo)：五道題。shiro權(quán)限框架的一篇筆記寫完。有額外時(shí)間就再寫個(gè)定時(shí)器的筆記。好的，就這樣！

尋找峰值

題目：峰值元素是指其值大于左右相鄰值的元素。給定一個(gè)輸入數(shù)組 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。數(shù)組可能包含多個(gè)峰值，在這種情況下，返回任何一個(gè)峰值所在位置即可。你可以假設(shè) nums[-1] = nums[n] = -∞。

示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2。
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
說明:
你的解法應(yīng)該是 O(logN) 時(shí)間復(fù)雜度的。

思路：這個(gè)題感覺才是正確的打開方式，這個(gè)進(jìn)階要求是主要的，不然這個(gè)題就是送分題，昨天也是有一個(gè)旋轉(zhuǎn)數(shù)組找最小值的，就差了這么一句話。好了，閑話不說，logN的時(shí)間復(fù)雜度，二分法是最容易想到的一個(gè)了，我去實(shí)現(xiàn)下看看。
好了，面向測(cè)試案例編程，我直接貼代碼：

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length == 1) return 0;
        if(nums[0]>nums[1]) return 0;
        if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
        return dfs(nums,0,nums.length-1);
    }
    public int dfs(int[] nums,int start,int end){
        if(start+1<end){
            int mid = (end-start)/2+start;
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])return mid;
            return Math.max(dfs(nums,start,mid),dfs(nums,mid,end));
        }else{
            return 0;
        }
    }
}

先判斷邊值，邊值不行再往里判斷，雖然我現(xiàn)在也不確定這個(gè)二分法是不是有用，是不是logN了。。。反正這個(gè)代碼執(zhí)行是0ms，超過百分百。我去看下別人的代碼吧。
看到了一個(gè)更好的思路，差不多想法，都是二分，但是思路就是優(yōu)秀，我先貼代碼：

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length == 1) return 0;
        if(nums[0]>nums[1]) return 0;
        if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
        return dfs(nums,0,nums.length-1);
    }
    public int dfs(int[] nums,int start,int end){
        if(start+1<end){
            int mid = (end-start)/2+start;
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])return mid;
            //后面一定有峰值。
            if(nums[mid]<nums[mid+1]) return dfs(nums,mid,end);
            //前面有峰值
            if(nums[mid]<nums[mid-1]) return dfs(nums,start,mid);
        }
        return -1;
    }
}

一開始我沒太明白怎么判斷前后一定 有峰值的，后來仔細(xì)想了想才明白。其實(shí)畫個(gè)圖就能理解了。

題解

好了，這道題比較簡(jiǎn)單，所以就這樣了，下一題了。

比較版本號(hào)

題目：比較兩個(gè)版本號(hào) version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。你可以假設(shè)版本字符串非空，并且只包含數(shù)字和 . 字符。

. 字符不代表小數(shù)點(diǎn)，而是用于分隔數(shù)字序列。例如，2.5 不是“兩個(gè)半”，也不是“差一半到三”，而是第二版中的第五個(gè)小版本。你可以假設(shè)版本號(hào)的每一級(jí)的默認(rèn)修訂版號(hào)為 0。例如，版本號(hào) 3.4 的第一級(jí)（大版本）和第二級(jí)（小版本）修訂號(hào)分別為 3 和 4。其第三級(jí)和第四級(jí)修訂號(hào)均為 0。

示例 1:
輸入: version1 = "0.1", version2 = "1.1"
輸出: -1
示例 2:
輸入: version1 = "1.0.1", version2 = "1"
輸出: 1
示例 3:
輸入: version1 = "7.5.2.4", version2 = "7.5.3"
輸出: -1
示例 4：
輸入：version1 = "1.01", version2 = "1.001"
輸出：0
解釋：忽略前導(dǎo)零，“01” 和 “001” 表示相同的數(shù)字 “1”。
示例 5：
輸入：version1 = "1.0", version2 = "1.0.0"
輸出：0
解釋：version1 沒有第三級(jí)修訂號(hào)，這意味著它的第三級(jí)修訂號(hào)默認(rèn)為 “0”。
提示：
版本字符串由以點(diǎn) （.） 分隔的數(shù)字字符串組成。這個(gè)數(shù)字字符串可能有前導(dǎo)零。
版本字符串不以點(diǎn)開始或結(jié)束，并且其中不會(huì)有兩個(gè)連續(xù)的點(diǎn)。

思路：我差點(diǎn)笑出了聲，我真的發(fā)現(xiàn)最近這幾道題都簡(jiǎn)單的離譜，，，差點(diǎn)以為我刷回簡(jiǎn)單的了呢。這道題的思路就是從前往后逐個(gè)比較，然后沒有任何額外要求，比如空間，時(shí)間復(fù)雜度，有點(diǎn)奇怪啊。偷懶點(diǎn)的做法通過點(diǎn)分割數(shù)組，然后從第一個(gè)開始逐個(gè)比較。稍微好一點(diǎn)的拆成char數(shù)組，然后比較，至于前導(dǎo)0.應(yīng)該就是多加判斷的事，我去寫代碼了
回來了，標(biāo)準(zhǔn)的面向測(cè)試案例編程，性能超過百分之九十四。我直接貼代碼：

class Solution {
    public int compareVersion(String version1, String version2) {
       char[] c1 = version1.toCharArray();
       char[] c2 = version2.toCharArray();
       int sum1 = 0;
       int sum2 = 0;
       int l1 = 0;
       int l2 = 0;
       while(l1<c1.length && l2<c2.length){
           while(l1<c1.length && c1[l1]!='.'){
               sum1 = sum1*10 + (c1[l1]-'0');
               l1++;
           } 
           while(l2<c2.length && c2[l2]!='.'){
               sum2 = sum2*10 + (c2[l2]-'0');
               l2++;
           }
           if(sum2!=sum1) return sum1>sum2?1:-1;
           sum1 = 0;
           sum2 = 0;
           if(l1<c1.length) l1++;
           if(l2<c2.length) l2++;
       }
       if(l1 == c1.length && l2 == c2.length){
            return 0;
       }else if(l1 < c1.length){
            for(int i = l1;i<c1.length;i++){
                if(c1[i] != '0' && c1[i] != '.') return 1;
            }
            return 0;
       }else{
           for(int i = l2;i<c2.length;i++){
               if(c2[i] != '0' && c2[i] != '.') return -1;
           }
           return 0;
       }
    }
}

這個(gè)題好麻煩啊，我后悔了，應(yīng)該直接用字符串分割的方式，我去用那種方式寫一遍。

class Solution {
    public int compareVersion(String version1, String version2) {
       String[] c1 = version1.split("\\.");
       String[] c2 = version2.split("\\.");
       for(int i = 0;i<c1.length;i++){
            if(i<c2.length){
                if(Integer.valueOf(c1[i])==Integer.valueOf(c2[i])) continue;
                if(Integer.valueOf(c1[i])>Integer.valueOf(c2[i])){
                    return 1;
                }else{
                    return -1;
                }
            }else{
                if(Integer.valueOf(c1[i])>0) return 1;
            }
       }
       if(c2.length>c1.length){
            for(int i = c1.length;i<c2.length;i++){
                if(Integer.valueOf(c2[i])>0) return -1;
            }
       }
       return 0;
    }
}

第二種寫法， 代碼簡(jiǎn)潔，性能是一樣的。這道題因?yàn)樾阅鼙容^好了我就不看題解了，直接下一題了。

分?jǐn)?shù)到小數(shù)

題目：給定兩個(gè)整數(shù)，分別表示分?jǐn)?shù)的分子 numerator 和分母 denominator，以字符串形式返回小數(shù)。如果小數(shù)部分為循環(huán)小數(shù)，則將循環(huán)的部分括在括號(hào)內(nèi)。

示例 1:
輸入: numerator = 1, denominator = 2
輸出: "0.5"
示例 2:
輸入: numerator = 2, denominator = 1
輸出: "2"
示例 3:
輸入: numerator = 2, denominator = 3
輸出: "0.(6)"

思路：這個(gè)題，難點(diǎn)暫時(shí)不知道，可能是循環(huán)小數(shù)括號(hào)？我先寫代碼試試吧，沒有太好的思路，就是硬算被？
我直接貼代碼吧，寫的有點(diǎn)鬧心：

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if(numerator==0) return "0";
        if(denominator==1) return numerator+"";      
        //轉(zhuǎn)成long是因?yàn)橐绯鰡栴}，-最大值除-1.結(jié)果溢出,倍數(shù)
        long b = (long)numerator/(long)denominator;
        StringBuffer sb = new StringBuffer();
        if(numerator>0 && denominator<0) sb.append("-");
        sb.append(b+"");
        long x = numerator%denominator;//余數(shù)
        if(x!=0){//不是整除
            sb.append(".");
            StringBuffer sb2 = new StringBuffer();
            Map<Long,Integer> map = new HashMap<Long,Integer>();
            while(x != 0){
                x *= 10;
                if(map.containsKey(x)){
                    sb2.append(")");
                    sb2.insert(map.get(x),"(");
                    break;
                }else{
                    map.put(x,sb2.length());
                    sb2.append(Math.abs(x/denominator));
                }
                x = x%denominator;                               
            } 
            sb.append(sb2);
        }
        return sb.toString();

    }
}

居然寫煩躁了，這個(gè)題不難，但是很墨跡，而且很弱智。測(cè)試案例更是奇葩，居然還特么溢出了，簡(jiǎn)直日狗了。這個(gè)題重點(diǎn)就是找出循環(huán)，然后一開始我甚至想用鏈表的，但是沒寫明白。改用map了，因?yàn)槌龜?shù)已經(jīng)確定，所以當(dāng)被除數(shù)x重復(fù)說明進(jìn)入循環(huán)了，然后第一的出現(xiàn)的位置填左括號(hào)，當(dāng)前位置添加有括號(hào)，跳出循環(huán)。
反正就這樣吧，我這個(gè)代碼性能賊差，我去看看排行第一的代碼，差不多就行了。

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        return "0";
    }
    StringBuilder fraction = new StringBuilder();
    // If either one is negative (not both)
    if (numerator < 0 ^ denominator < 0) {
        fraction.append("-");
    }
    // Convert to Long or else abs(-2147483648) overflows
    long dividend = Math.abs(Long.valueOf(numerator));
    long divisor = Math.abs(Long.valueOf(denominator));
    fraction.append(String.valueOf(dividend / divisor));
    long remainder = dividend % divisor;
    if (remainder == 0) {
        return fraction.toString();
    }
    fraction.append(".");
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            fraction.insert(map.get(remainder), "(");
            fraction.append(")");
            break;
        }
        map.put(remainder, fraction.length());
        remainder *= 10;
        fraction.append(String.valueOf(remainder / divisor));
        remainder %= divisor;
    }
    return fraction.toString();
}
}

這是性能排行第一的代碼，思路差不多，細(xì)節(jié)處理有區(qū)別，然后過了，我繼續(xù)往下做了。

二叉搜索樹迭代器

題目：實(shí)現(xiàn)一個(gè)二叉搜索樹迭代器。你將使用二叉搜索樹的根節(jié)點(diǎn)初始化迭代器。調(diào)用 next() 將返回二叉搜索樹中的下一個(gè)最小的數(shù)。

示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
提示：
next() 和 hasNext() 操作的時(shí)間復(fù)雜度是 O(1)，并使用 O(h) 內(nèi)存，其中 h 是樹的高度。
你可以假設(shè) next() 調(diào)用總是有效的，也就是說，當(dāng)調(diào)用 next() 時(shí)，BST 中至少存在一個(gè)下一個(gè)最小的數(shù)。

題目截圖

思路：首先，我看了下這個(gè)迭代是中序迭代（因?yàn)槭嵌嫠阉鳂?，從小到大肯定是中序）。然后主要難度應(yīng)該是時(shí)間復(fù)雜度O（1），也就是常量級(jí)別的，還有O(h)內(nèi)存。首先這個(gè)O(h)內(nèi)存就決定了不能直接遍歷整個(gè)樹來實(shí)現(xiàn)這兩個(gè)方法。其次，因?yàn)橹荒鼙闅v一部分，我覺得應(yīng)該是先遍歷左節(jié)點(diǎn)，因?yàn)槭紫鹊谝粋€(gè)next肯定是要獲取最左邊的節(jié)點(diǎn)，保證時(shí)間復(fù)雜度是常量的情況下一定是先找到這個(gè)節(jié)點(diǎn)的，有了個(gè)模糊的想法，我去實(shí)現(xiàn)下。
這個(gè)題挺有意思，我也錯(cuò)了幾次，但是大概思路是對(duì)的，先入后出用棧保存效果好，其實(shí)別的數(shù)據(jù)結(jié)構(gòu)也是可以實(shí)現(xiàn)的。我直接貼代碼了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack ;
    public BSTIterator(TreeNode root) {
        //從頭遍歷，應(yīng)該是最左邊的最后遍歷到。適合先入后出
        stack = new Stack<TreeNode>();
        while(root!= null){
            stack.push(root);
            root = root.left;
        }
        //初始化保證棧中最上面的元素的最小值
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode n = stack.pop();
        int res = n.val;
        //這個(gè)n的左節(jié)點(diǎn)要么沒有，要么已經(jīng)用過了， 只要判斷右節(jié)點(diǎn)就行
        if(n.right!=null){
            n = n.right;
            while(n != null){
                stack.push(n);
                n = n.left;        
            }
        }
        return res;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
         return !stack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

之前在next中有點(diǎn)錯(cuò)誤，一開始我是想著用if，如果有左節(jié)點(diǎn)添加進(jìn)去，后來提交報(bào)錯(cuò)我檢查了好幾遍因?yàn)闃溆植缓谜{(diào)試，怎么也找不到問題。最后去看了題解，才發(fā)現(xiàn)這個(gè)問題。因?yàn)闃涓哂邢?，一層存一個(gè)節(jié)點(diǎn)空間復(fù)雜度滿足O（h）。
我這個(gè)性能只超過百分之七十多，我去看看性能排行第一的代碼。
額，他用的全遍歷，O（n）空間復(fù)雜度，，沒啥好看的了。
這個(gè)題就這樣吧。最后一道題。
接下來幾道題是sql題，本來我打算自己寫寫就好了，但是看到一個(gè)不錯(cuò)的題目，所以分享下。

分?jǐn)?shù)排名

題目截圖

這個(gè)題其實(shí)做法很多，反正我是不會(huì)。因?yàn)槲沂莝ql渣，工作中只學(xué)會(huì)了crud。稍微難點(diǎn)的就是靠著百度一點(diǎn)點(diǎn)嘗試了，哈哈，不過基本的連表查詢還是知道一些的。然后這個(gè)題我是直接看的題解，有的寫得復(fù)雜有的寫得簡(jiǎn)單，我把我看了覺得很容易懂的分享下：

SELECT a.score as Score,count(DISTINCT b.score) as Rank
from scores a join scores b where b.score>=a.score
group by a.id
order by a.score Desc

這個(gè)幾乎是最簡(jiǎn)潔的做法了，關(guān)聯(lián)條件大于等于，然后distinct b.score使得從1開始排名。group by a.id使得每一個(gè)同學(xué)都有排名，最后的升序排列不用說了。我不是說這個(gè)sql性能會(huì)多好，但是真的很容易理解，順便貼上我看了就眼花的sql：

-- select Scores.Score ,
-- if(@agerank=Scores.Score ,@curRank, @curRank := @curRank + 1) as Rank,
-- @agerank := Scores.Score 
-- from Scores , (select @curRank :=0,@agerank = NULL) r
-- order by Score desc;

SELECT Score, Rank FROM
(SELECT Score,
@curRank := IF(@prevRank = Score, @curRank+0,@curRank:=@curRank+1) AS Rank,
@prevRank := Score
FROM Scores, (
SELECT @curRank :=0, @prevRank := NULL
) r
ORDER BY Score DESC) s

說真的，我都開始懷疑我平時(shí)用的是不是假的mysql數(shù)據(jù)庫(kù)?。?！看不太懂我都，這個(gè)@是什么？
哎，反正我第一次貼的那個(gè)方法我是記住了，也算是學(xué)到了，這個(gè)就這樣了。

最大數(shù)

題目：給定一組非負(fù)整數(shù)，重新排列它們的順序使之組成一個(gè)最大的整數(shù)。

示例 1:
輸入: [10,2]
輸出: 210
示例 2:
輸入: [3,30,34,5,9]
輸出: 9534330
說明: 輸出結(jié)果可能非常大，所以你需要返回一個(gè)字符串而不是整數(shù)。

思路：這個(gè)題比較簡(jiǎn)單啊，我目前的想法是從寫排序規(guī)則，然后排序，排序規(guī)則是從第一個(gè)數(shù)開始比較，大的就大，如果第一個(gè)數(shù)一樣比較第二個(gè)。如果是數(shù)位少的默認(rèn)按照當(dāng)前首位計(jì)算。說起來有點(diǎn)清楚，我去寫一下吧。
很好，學(xué)到一點(diǎn)，基本類型不能重寫compare。。。拉倒吧，我自己排序吧。
這個(gè)題做出來了，我之前思路錯(cuò)了，沒必要一個(gè)數(shù)一個(gè)數(shù)比較。直接轉(zhuǎn)成字符串相加，a+b 和b+a比較就行了。我先貼代碼：

class Solution {
    public String largestNumber(int[] nums) {
        for(int i = 0;i<nums.length-1;i++){
            for(int j = i;j<nums.length;j++){
                if(!compare(nums[i],nums[j])){
                    int t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
            }
        }
        StringBuffer sb = new StringBuffer();
    for(int i : nums){
        sb.append(String.valueOf(i));
    }
    if(sb.charAt(0)=='0') return "0";
    return sb.toString();
    }
    //比較兩個(gè)數(shù)大小，第一個(gè)大true，第二個(gè)大false
    public boolean compare(int a, int b){
        String sa = String.valueOf(a);
        String sb = String.valueOf(b);
        String suma = sa+sb;
        String sumb = sb+sa;
        for(int i = 0;i<suma.length();i++){
            if(suma.charAt(i)>sumb.charAt(i)) return true;
            if(suma.charAt(i)<sumb.charAt(i)) return false;
        }
        return true;
    }
}

至于這個(gè)代碼的性能，我覺得是浪費(fèi)在冒泡排序上了啊，我去優(yōu)化一下。
改成快排變成7ms了。

class Solution {
    public String largestNumber(int[] nums) {
        qSort(nums,0,nums.length-1);
        StringBuffer sb = new StringBuffer();
    for(int i : nums){
        sb.append(String.valueOf(i));
    }
    if(sb.charAt(0)=='0') return "0";
    return sb.toString();
    }
    public void qSort(int[] nums,int start,int end){//快排
        if(start>=end) return;
        int l = start;
        int r = end; 
        int mid = nums[(start+end)/2];
        while(l<=r){
            while(l<end && compare(nums[l],mid)) l++;
            while(r>start && compare(mid,nums[r])) r--;
            if(l<=r){
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
                l++;
                r--;
            }
        }
        if(start<r) qSort(nums,start,r);
        if(end>l) qSort(nums,l,end);
    }
    //比較兩個(gè)數(shù)大小，第一個(gè)大true，第二個(gè)大false
    public boolean compare(int a, int b){
        String sa = String.valueOf(a);
        String sb = String.valueOf(b);
        String suma = sa+sb;
        String sumb = sb+sa;
        for(int i = 0;i<suma.length();i++){
            if(suma.charAt(i)>sumb.charAt(i)) return true;
            if(suma.charAt(i)<sumb.charAt(i)) return false;
        }
        return false;
    }
    
}

剛剛看了下性能好的代碼，是直接把數(shù)字?jǐn)?shù)組轉(zhuǎn)化成String數(shù)組。其實(shí)這個(gè)確實(shí)是好辦法，不然像我這樣要來回來去轉(zhuǎn)換，一個(gè)單詞轉(zhuǎn)換好多次。。
附上大佬的代碼：

class Solution {
  public String largestNumber(int[] nums) {
        String[] numstr = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            numstr[i] = String.valueOf(nums[i]);
        }
        quickSort(numstr,0,nums.length-1);
        // System.out.println(Arrays.toString(numstr));
        StringBuffer sb = new StringBuffer();
        if(numstr[0].charAt(0)=='0'){
            return "0";
        }
        for(String num:numstr){
            sb.append(num);
        }
        return sb.toString();
    }
    int compare(String a,String b){
        int l1 = a.length();
        int l2 = b.length();
        int l = l1+l2;
        int i=0;
        for(;i<l;i++){
            char ac = a.charAt(i%l1);
            char bc = b.charAt(i%l2);
            if(ac==bc){
                continue;
            }
            return ac-bc;
        }
        return 0;
        // System.out.println("a:"+a+",b:"+b+",cp:"+cp);
        // return cp;
    }
    void quickSort(String[] nums,int start,int end){
        if(start>=end){
            return;
        }
        int index = getIndex(nums,start,end);
        quickSort(nums,start,index-1);
        quickSort(nums,index+1,end);
    }
    int getIndex(String[]nums,int low,int high){
        String tmp = nums[low];
        while(low<high){
            while(low<high&&compare(nums[high],tmp)<=0){
                high--;
            }
            nums[low] = nums[high];
            while(low<high&&compare(nums[low],tmp)>=0){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = tmp;
        return low;
    }
}

今天的筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注，也祝大家工作順順利利！生活健健康康！~