知識像個?，里面是我們所知的，外面是未知的。知道的越多，我們會發(fā)現未知的也越多。今日份自勉語句。

鏈表組件

題目：給定鏈表頭結點 head，該鏈表上的每個結點都有一個 唯一的整型值 。同時給定列表 G，該列表是上述鏈表中整型值的一個子集。返回列表 G 中組件的個數，這里對組件的定義為：鏈表中一段最長連續(xù)結點的值（該值必須在列表 G 中）構成的集合。

示例 1：
輸入:
head: 0->1->2->3
G = [0, 1, 3]
輸出: 2
解釋:
鏈表中,0 和 1 是相連接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一個組件，同理 [3] 也是一個組件，故返回 2。
示例 2：
輸入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
輸出: 2
解釋:
鏈表中，0 和 1 是相連接的，3 和 4 是相連接的，所以 [0, 1] 和 [3, 4] 是兩個組件，故返回 2。
提示：
如果 N 是給定鏈表 head 的長度，1 <= N <= 10000。
鏈表中每個結點的值所在范圍為 [0, N - 1]。
1 <= G.length <= 10000
G 是鏈表中所有結點的值的一個子集.

思路：這個題的思路我暫時的想法就是把G用set記錄。然後從頭遍歷鏈表。用一個計數器count來記錄。如果當前節(jié)點G中存在則count+1。不存在并且count不為0則ans+1,且count歸0。。暫時就是這樣，我去代碼實現試試.
好了,ac了,上第一版本代碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i : G) set.add(i);
        int count = 0;
        int ans = 0;
        while(head != null) {
            if(set.contains(head.val)) {
                count++;
            }else {
                if(count != 0) ans++;
                count = 0;
            }
            head = head.next;
        }
        if(count != 0) ans++;
        return ans;
    }
}

這個題怎么說呢,比較簡單,簡單難度撐死了,不知道怎么混到中等難度里的.然後一開始我忘記了結尾count不為0也要算所以wa了一次.我這個代碼性能也還好,O(n)時間復雜度,O(1)空間復雜度.我去看看性能第一的代碼,沒什么大問題的話就過了:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] G) {
        boolean hash[] = new boolean[10000];
        for(int i = 0; i < G.length; i++){
            hash[G[i]] = true;
        } 
        int res = 0; //記錄組件的個數
        while(head != null){
            if(hash[head.val]){
                while(head.next != null && hash[head.val]){
                    head = head.next;
                }
                res++;
            }           
            head = head.next;
        }
        return res;
    }
}

這個用的空間換時間?反正用了hash數組,性能變好了能理解.這個題就這樣吧.

單詞的壓縮編碼

題目:單詞數組 words 的 有效編碼 由任意助記字符串 s 和下標數組 indices 組成，且滿足：

words.length == indices.length

助記字符串 s 以 '#' 字符結尾

對于每個下標 indices[i] ，s 的一個從 indices[i] 開始、到下一個 '#' 字符結束（但不包括 '#'）的 子字符串 恰好與 words[i] 相等

給你一個單詞數組 words ，返回成功對 words 進行編碼的最小助記字符串 s 的長度 。

示例 1：
輸入：words = ["time", "me", "bell"]
輸出：10
解釋：一組有效編碼為 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 開始于 indices[0] = 0 到下一個 '#' 結束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 開始于 indices[1] = 2 到下一個 '#' 結束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 開始于 indices[2] = 5 到下一個 '#' 結束的子字符串，如加粗部分所示 "time#bell#"
示例 2：
輸入：words = ["t"]
輸出：2
解釋：一組有效編碼為 s = "t#" 和 indices = [0] 。
提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 僅由小寫字母組成

思路:這個題我覺得首先看單詞之間的關系.比如time和me.這種time的結尾包含me的.但是因為單詞總共2000個..所以這種包含關系我覺得還是挺不好算的.我打算先暴力法試試.首先第一個單詞看有沒有endwith第一個單詞的,沒有的話則先把第一個單詞放這.然後一個字符一個字符的減.看后面有沒有同等的單詞,有的話直接算在這里.思路還算清楚.就是怕超時.我去試試代碼了.又想出一些算是優(yōu)化的措施:比如可以單詞按照長度分組.
暴力法居然ac了,哈哈,我直接貼代碼:

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> set1 = new HashSet<String>();
        Set<String> set2 = new HashSet<String>();
        Set<String> set3 = new HashSet<String>();
        Set<String> set4 = new HashSet<String>();
        Set<String> set5 = new HashSet<String>();
        Set<String> set6 = new HashSet<String>();
        Set<String> set7 = new HashSet<String>();
        for(String s : words) {
            switch (s.length()) {
            case 1: set1.add(s); break;
            case 2: set2.add(s); break;
            case 3: set3.add(s); break;
            case 4: set4.add(s); break;
            case 5: set5.add(s); break;
            case 6: set6.add(s); break;
            default: set7.add(s);
            }
        }
        int ans = 0;
        for(String s: set7) {
            ans += 8;
            set6.remove(s.substring(1, 7));
            set5.remove(s.substring(2, 7));
            set4.remove(s.substring(3, 7));
            set3.remove(s.substring(4, 7));
            set2.remove(s.substring(5, 7));
            set1.remove(s.substring(6, 7));
        }
        for(String s: set6) {
            ans += 7;
            set5.remove(s.substring(1, 6));
            set4.remove(s.substring(2, 6));
            set3.remove(s.substring(3, 6));
            set2.remove(s.substring(4, 6));
            set1.remove(s.substring(5, 6));
        }
        for(String s: set5) {
            ans += 6;
            set4.remove(s.substring(1, 5));
            set3.remove(s.substring(2, 5));
            set2.remove(s.substring(3, 5));
            set1.remove(s.substring(4, 5));
        }
        for(String s: set4) {
            ans += 5;
            set3.remove(s.substring(1, 4));
            set2.remove(s.substring(2, 4));
            set1.remove(s.substring(3, 4));
        }
        for(String s: set3) {
            ans += 4;
            set2.remove(s.substring(1, 3));
            set1.remove(s.substring(2, 3));
        }
        for(String s: set2) {
            ans += 3;
            set1.remove(s.substring(1, 2));
        }
        for(String s: set1) {
            ans += 2;
        }       
        return ans;
    }
}

思路和我上面說的差不多.然後重點是四個字符的單詞可能包含3個的,2個的,1個的.但是不可能包含四個的(set自動去重,一樣的不占用長度).所以說這個代碼寫的比較丑,但是思路還是挺清晰的.而且性能并沒有我想的那么慘不忍睹.其實我現在覺得沒必要分這么多set,應該一個也能搞定.我去試試代碼:

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet<String>(Arrays.asList(words));
        for (String word: words) {
            for (int k = 1; k < word.length(); ++k) {
                good.remove(word.substring(k));
            }
        }

        int ans = 0;
        for (String word: good) {
            ans += word.length() + 1;
        }
        return ans;
    }
}

下面我去看看性能第一的代碼吧:
只能說不出所料,其實在做的時候我就想過字典樹了,還尋思暴力法超時了就換..但是因為沒超時,emmmm...總而言之思路就是每一個單詞從后往前.最后一個字母是字典的開始.每次都從后往前遍歷,如果找到一樣的子分支了則說明當前的不需要額外加長.如果找到包含的子分支并且這個分支不夠長,那么把之前的單詞算在這個單詞的一部分,所以要續(xù)上的是當前大于之前的那個長度.最后如果找不到類似的子分支則這個新掛在樹上,思路還算好理解,下面是大佬的代碼實現:

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        int ans = 0;
        for (String word: words) {
            ans += trie.insert(word);
        }
        return ans;
    }
}

class TrieNode {
    TrieNode[] next;
    boolean end;

    public TrieNode() {
        this.next = new TrieNode[26];
        this.end = false;
    }
}

class Trie {
    TrieNode node;

    public Trie() {
        this.node = new TrieNode();
    }

    public int insert(String word) {
        char[] chs = word.toCharArray();
        int len = chs.length;
        TrieNode cur = this.node;
        int ans = len + 1;
        boolean update = false;
        for (int i = len - 1; i >= 0; i--) {
            int p = chs[i] - 'a';
            if (cur.end) {
                cur.end = false;
                // common suffix
                ans -= len - i;
            }
            if (cur.next[p] == null) {
                cur.next[p] = new TrieNode();
                update = true;
            }
            cur = cur.next[p];
        }
        if (update) {
            cur.end = true;
            return ans;
        } else {
            return 0;
        }
    }
}

這個題解出來不算難,但是怎么優(yōu)雅的解出來還是挺不容易的.下一題.

翻轉卡片游戲

題目:在桌子上有 N 張卡片，每張卡片的正面和背面都寫著一個正數（正面與背面上的數有可能不一樣）。

我們可以先翻轉任意張卡片，然后選擇其中一張卡片。如果選中的那張卡片背面的數字 X 與任意一張卡片的正面的數字都不同，那么這個數字是我們想要的數字。哪個數是這些想要的數字中最小的數（找到這些數中的最小值）呢？如果沒有一個數字符合要求的，輸出 0。其中, fronts[i] 和 backs[i] 分別代表第 i 張卡片的正面和背面的數字。如果我們通過翻轉卡片來交換正面與背面上的數，那么當初在正面的數就變成背面的數，背面的數就變成正面的數。

示例：
輸入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
輸出：2
解釋：假設我們翻轉第二張卡片，那么在正面的數變成了 [1,3,4,4,7] ， 背面的數變成了 [1,2,4,1,3]。
接著我們選擇第二張卡片，因為現在該卡片的背面的數是 2，2 與任意卡片上正面的數都不同，所以 2 就是我們想要的數字。
提示：
1 <= fronts.length == backs.length <= 1000
1 <= fronts[i] <= 2000
1 <= backs[i] <= 2000

思路:講真,這個 題目我自己讀了好幾遍都沒看懂,還是問了群里的人才算是理解題意了.本來我很奇怪為什么是2而不是1.后來發(fā)現是因為這個背面的值,要和正面所有的值都不同(包括自己這張的正面).所以1pass了.理解完題意以后說這個題的解題思路:首先正負面一樣的元素直接pass.其次因為數字最大2千.我暫時的想法是2000個元素數組.然後正負面一樣的直接false.剩下的從前往后一個個數判斷.我去試試代碼.
第一版本代碼:

class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        int[] d = new int[2001];//2是false?？隙ú恍辛?。1是有可能，可以試試。 0是不存在這個元素
        for(int i = 0;i<fronts.length;i++) {
            if(fronts[i] == backs[i]) {
                d[fronts[i]] = 2;
            }else {
                if(d[fronts[i]] != 2) d[fronts[i]] = 1;
                if(d[backs[i]] != 2) d[backs[i]] = 1;
            }           
        }
        int min = 2001;
        for(int i = 0;i<2001;i++) {
            if(d[i] == 0 || d[i] == 2) continue;
            return i;
        }
        return 0;       
    }
}

說真的,我覺得這個題難度在于閱讀理解吧?反正做出來挺容易的,比我想的還簡單.然後性能也不錯,我再去看看性能第一的代碼:

class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        
        int[] arr = new int[2000];
        int i =0;
        while(i < fronts.length){
            if(fronts[i] == backs[i]){
                arr[fronts[i]] = 1;
            }
            i++;
        }
        int j=0;
        int min = Integer.MAX_VALUE;
        while(j < fronts.length){
            int test = fronts[j];
            if(arr[test] ==0 && test < min){
                min = test;
            }
            int test2 = backs[j];
            if(arr[test2] ==0 && test2 < min){
                min = test2;
            }
            j++;
        }

        if(min < Integer.MAX_VALUE){
            return min;
        }else{
            return 0;
        }
    }
}

感覺這個代碼的好處是不用多加很多無用的判斷.比如我這邊數組是2000個.但是如果最大數是4.可是5-2000我還要判斷一遍的.然後這個解法就不用這個判斷了.除了這個也沒啥了.下一題吧.

帶因子的二叉樹

題目:給出一個含有不重復整數元素的數組，每個整數均大于 1。我們用這些整數來構建二叉樹，每個整數可以使用任意次數。其中：每個非葉結點的值應等于它的兩個子結點的值的乘積。滿足條件的二叉樹一共有多少個？返回的結果應模除 10 ** 9 + 7。

示例 1:
輸入: A = [2, 4]
輸出: 3
解釋: 我們可以得到這些二叉樹: [2], [4], [4, 2, 2]
示例 2:
輸入: A = [2, 4, 5, 10]
輸出: 7
解釋: 我們可以得到這些二叉樹: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示:
1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

思路:這個題首先因為每個整數都大于1.因為不存在等于1的情況,所以我們可以從最高層開始找.雖然這個沒有標簽,但是我覺得應該可以用dp解決.每一個數字本身都可以單獨作為一個樹.所以開始就是1.然後比如4可以被2乘2來組成,所以4在1的基礎上+1.也就是4的組成個數是2.所以2.4這個數組的答案是3.重點是如果三層樹:20->4->2這種.4本身就兩種可能,一種是單獨的4一種是422.5的系數是1.20的結果就是20本身的1+(1乘2)乘2 = 5.之所以(1乘2)乘2是因為左右分支兩種可能.如果是2,2或者4,4這種就不用再乘2了.大概思路是這樣,我去代碼試試.
第一版本代碼:

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        Map<Integer, Long> map = new HashMap<Integer, Long>();
        for(int i:arr) map.put(i, 1l);//都可以單獨成樹，所以是1
        for(int i = 1;i<arr.length;i++) {
            int temp = arr[i];
            Set<Integer> set = new HashSet<>();
            for(int j = i-1;j>=0;j--) {                
                int cur = arr[j];
                if(set.contains(cur)) continue;
                if(temp%cur == 0 && map.containsKey(temp/cur)) {                   
                    if(temp/cur == cur) {
                        map.put(temp, map.get(temp)+map.get(cur)*map.get(cur)); 
                    }else {
                        set.add(temp/cur);
                        map.put(temp,map.get(temp)+map.get(cur)*map.get(temp/cur)*2);
                    }
                }
            }
        }
        long ans = 0;
        for(long i:map.values()) ans += i;
        return (int)(ans%1000000007);
    }
}

我只能說勉強過了.低空掠過.因為這個數據太大,我只想到了map.各種map,set查找.感覺性能是耗費在這里.但是優(yōu)化一時半會兒想不出好辦法...我直接去看看性能第一的代碼:

class Solution {
    public final static int MOD = 1000000007;
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        Map<Integer,Integer> map = new HashMap<>() ;
        for(int i = 0;i < arr.length;i++){
            map.put(arr[i],i) ;
        }
        long[] dp = new long[arr.length] ;
        long ans = 0 ;
        for(int i = 0;i < arr.length;i++){
            double sq = Math.sqrt(arr[i]) ;
            dp[i] = 1 ;
            for(int j = 0;j < i;j++){
                if(arr[j] > sq){
                    break;
                }
                if(arr[i]%arr[j] == 0){
                    Integer other = map.get(arr[i]/arr[j]) ;
                    if(other != null){
                        dp[i] = (dp[i]+dp[j]*dp[other]%MOD)%MOD ;
                        if(other != j){
                            dp[i] = (dp[i]+dp[j]*dp[other]%MOD)%MOD ;
                        }
                    }
                }
            }
            ans += dp[i] ;
        }
        return (int) (ans%MOD);
    }
}

這個平方根,著實優(yōu)秀!!都踏馬是我知道的知識,看了人家的代碼恍然大悟,自己就是沒想起來..腦殼痛,反正這個題思路差不多就是這樣.然後細節(jié)的處理優(yōu)化在于平方根往上不用看了.因為如果有在這邊較小的數字上也處理完了.這個題就這樣了,下一題.

適齡的朋友

題目:人們會互相發(fā)送好友請求，現在給定一個包含有他們年齡的數組，ages[i] 表示第 i 個人的年齡。當滿足以下任一條件時，A 不能給 B（A、B不為同一人）發(fā)送好友請求：

age[B] <= 0.5 * age[A] + 7

age[B] > age[A]

age[B] > 100 && age[A] < 100

否則，A 可以給 B 發(fā)送好友請求。注意如果 A 向 B 發(fā)出了請求，不等于 B 也一定會向 A 發(fā)出請求。而且，人們不會給自己發(fā)送好友請求。 求總共會發(fā)出多少份好友請求?

示例 1：
輸入：[16,16]
輸出：2
解釋：二人可以互發(fā)好友申請。
示例 2：
輸入：[16,17,18]
輸出：2
解釋：好友請求可產生于 17 -> 16, 18 -> 17.
示例 3：
輸入：[20,30,100,110,120]
輸出：3
解釋：好友請求可產生于 110 -> 100, 120 -> 110, 120 -> 100.
提示：
1 <= ages.length <= 20000
1 <= ages[i] <= 120

首先說題目:我感覺這個題有點問題啊:感覺條件2和條件三重復了.當然這個不重要.繼續(xù)說題目.我的想法是每個人只要看小于等于當前區(qū)間的.然後我打算年齡最大120.作為一個數組.然後下標代表年齡,值代表人數.直接計算.沒啥好說的,我去寫代碼試試.
第一版本代碼:

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] d = new int[121];
        for(int i :ages) d[i]++;
        int ans = 0;
        for(int i = 0;i<d.length;i++) {
            if(d[i] == 0) continue;
            if(d[i] > 1 && i>14) ans += d[i]*(d[i]-1);
            double temp = 0.5*i+7;
            for(int j = i-1;j>=0;j--) {
                if(d[j] == 0) continue;
                if(j<=temp) break;//太小了不合適
                ans += d[i] * d[j]; 
            }
        }
        return ans;
    }
}

這個代碼一開始i>14我沒寫,所以卡了一下,剩下的沒啥特別難的.就是判斷就行了,和預計的也差不讀.這個題就這樣了,因為性能已經不錯了所以不看性能第一的代碼啦.
本篇筆記就記到這里,如果稍微幫到你了記得點個喜歡點個關注,也祝大家工作順順利利!