數(shù)組

1207 獨一無二的出現(xiàn)次數(shù)

看數(shù)組的大小和長度都沒有很大，所以可以直接用數(shù)組來做哈希表，用一個數(shù)組來記錄出現(xiàn)次數(shù)，再用一個數(shù)組來標(biāo)記出現(xiàn)次數(shù)的值是否出現(xiàn)過。就是O(n)

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        //07
        // 排序 nlogn  用兩個hash O(n)
        int[] hash = new int[2001];
        Arrays.fill(hash,0);
        for(int i=0;i<arr.length;i++){
            hash[arr[i]+1000]++;
        }
        // Arrays.sort(hash);//將出現(xiàn)次數(shù)排序
        // for(int i=1;i<hash.length;i++){
        //     if(hash[i]==hash[i-1]&&hash[i]!=0) return false;
        // }
        // return true;

        boolean[] flag = new boolean[1002]; // 標(biāo)記相同頻率是否重復(fù)出現(xiàn)
        Arrays.fill(flag,false);
        for(int i=0;i<hash.length;i++){
            if(hash[i]>0&&flag[hash[i]]==false){
                flag[hash[i]] = true;
            }else if(hash[i]>0&&flag[hash[i]]==true){
                return false;
            }
        }
        return true;

    }
}

189 旋轉(zhuǎn)數(shù)組

思路就是反轉(zhuǎn)三次，先全部反轉(zhuǎn)，然后前K個反轉(zhuǎn)一次，后面剩下的反轉(zhuǎn)一次。
要注意的是k大于數(shù)組長度的時候要取余

class Solution {
    public void rotate(int[] nums, int k) {
        //反轉(zhuǎn)三次 原地
        //開另外數(shù)組
        if(k>nums.length) k=k%nums.length;  //重要 注意?。。?！
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);

    }
    public void reverse(int[] nums, int begin, int end){
        while(begin<end){
            int tmp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = tmp;
            begin++;
            end--;
        }
    }
}

34 在排序數(shù)組中查找元素的第一個和最后一個位置

要求logn 那就明顯是二分查找算法

class Solution {
    int[] res = new int[2];
    public int[] searchRange(int[] nums, int target) {
        //要求logn 那就二分查找
        int begin = 0;
        int end = nums.length-1;
        res[0] = -1;//如果沒找到就是-1
        res[1] = -1;
        while(begin<=end){//注意要相等
            int mid = (begin+end)/2;
            if(nums[mid]==target){
                int j=mid-1;
                while(j>=0&&nums[j]==target){//找到了之后開始向兩邊擴展搜索
                    j--;
                } 
                res[0] = j+1;
                int k=mid+1;
                while(k<nums.length&&nums[k]==target){
                    k++;
                }  
                res[1] = k-1;
                return res;        
            }else if(nums[mid]<target){
                begin=mid+1;
            }else{
                end = mid-1;
            }
        }
        return res; //如果沒找到 就不會更新 返回初始值-1
    }   
}

922 按奇偶排序數(shù)組 II

一開始就沒想用額外的數(shù)組，不然本地就太簡單，然后我看了實例，因為奇數(shù)和偶數(shù)是連續(xù)的，就只有連續(xù)奇數(shù)+偶數(shù) 和連續(xù)偶數(shù)+奇數(shù)兩種情況，然后才發(fā)現(xiàn)是可以不連續(xù)的，所以才改了很久。只要兩個指針去判斷和交換即可

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        //17 -46 原地 一半一半 沒說是不是連續(xù)的！?。〔灰欢ㄊ沁B續(xù)的奇數(shù)和偶數(shù)??！
        for(int i=0,j=1;i<nums.length&&j<nums.length;){
            if(nums[i]%2==1&&nums[j]%2==0){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i+=2;
                j+=2;
            }
            else if(nums[i]%2==0){
                i+=2;
            }else if(nums[j]%2==1){
                j+=2;
            }
        } 
        return nums;
    }
}

鏈表

143 重排鏈表（美團一面題目）

簡單做法，先用數(shù)組存起來,一個一個去改變指向，注意不是新建節(jié)點，而是直接利用這些節(jié)點，只是改變指向，所以也是符合要求的。 時間復(fù)雜度O（N）和空間復(fù)雜度都是O（n）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //35-49
        //簡單做法，先用數(shù)組存起來,一個一個去改變指向 時間復(fù)雜度O（N）和空間復(fù)雜度都是O（n）
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while(node!=null){
            list.add(node);
            node = node.next;
        }
        node = head;
        int left =1;//從1開始 因為頭不用變
        int right = list.size()-1;
        int count=0;
        while(left<=right){
            if(count%2==0){
                node.next = list.get(right);
                node  = node.next;
                right--;
            }else{
                node.next = list.get(left);
                node = node.next;
                left++;
            }
            count++;
        }
        node.next = null;

    }
}

然后是原地改變指向，不用額外數(shù)組。思路就是反轉(zhuǎn)后半部分鏈表，然后交替指向，需要注意反轉(zhuǎn)之后結(jié)尾要null,然后判斷奇數(shù)偶數(shù)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //53-05
        //原地改變指向 反轉(zhuǎn)后半部分鏈表 然后交替指向
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode fast = node,slow = node;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode pre,cur;
        if(fast!=null){//鏈表長度是偶數(shù)
            pre = null;
        }else pre = slow;//鏈表長度是奇數(shù)
        cur = slow.next;
        //開始反轉(zhuǎn)
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        slow.next = null;//要記得！！
        //兩個頭分別是head和pre
        node = head;
        while(node!=null&&pre!=null){ //交替指向
            ListNode node2 = node.next;
            ListNode pre2 = pre.next;
            node.next = pre;
            pre.next = node2;
            node = node2;
            pre = pre2;
        }
    }
}

160 鏈表相交

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //13
        //長的走完走短的
        ListNode a = headA, b = headB;
        int fa = 0;
        int fb = 0;//標(biāo)記是否連接過一次
        while(a!=null||b!=null){   
            if(a==b) return a;        //要放在前面 因為可能第一個節(jié)點就相交
            if(a.next==null&&fa==0){
                a = headB;
                fa=1;
            }else a = a.next;
            if(b.next==null&&fb==0){
                b = headA;
                fb=1;
            }else b = b.next;          
        }
        return null;
        
    }
}

字符串

205 同構(gòu)字符串

要注意的是多個key映射到相同的value也是不行的，第一次提交忽略了這種情況

class Solution {
    public boolean isIsomorphic(String s, String t) {
        //00-09
        Map<Character,Character> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                if(map.containsValue(t.charAt(i))) return false;//多個key對應(yīng)相同的value也是不行的
                map.put(s.charAt(i),t.charAt(i));
            }
            else{
                if(t.charAt(i)!=map.get(s.charAt(i))) return false;
                
            }
        }
        return true;

    }
}

1002 查找公用字符

感覺這題的難度不像是簡單題，整體思路就是統(tǒng)計出搜索字符串里26個字符的出現(xiàn)的頻率，然后取每個字符頻率最小值，最后轉(zhuǎn)成輸出格式就可以了

知道了思路之后第一時間也沒有想好怎么做，總之就是用第一個字符串初始化之后，和之后的每個字符串出現(xiàn)的次數(shù)取最小

class Solution {
    public List<String> commonChars(String[] words) {
        //11
        int[] hash = new int[26];
        Arrays.fill(hash,0);
        for(int i=0;i<words[0].length();i++){
            hash[words[0].charAt(i)-'a']++; //用第一個字符給hash初始化
        }
        //其他字符的出現(xiàn)次數(shù)
        for(int i=1;i<words.length;i++){
            int[] hashOther = new int[26];
            Arrays.fill(hashOther,0);
            for(int j=0;j<words[i].length();j++){
                hashOther[words[i].charAt(j)-'a']++;
            }

            //更新最小值
            for(int k=0;k<26;k++){
                hash[k] = Math.min(hash[k],hashOther[k]);
            }
        }
        List<String> res = new ArrayList<>();
        for(int i=0;i<26;i++){
            while(hash[i]>0){
                char c = (char)('a'+i);
                res.add(String.valueOf(c)); //char能不能轉(zhuǎn)換為String
                hash[i]--;
            }
        }
        return res;
    }
}

字符串

925 長鍵按入

思路很簡單，就是寫起來判斷條件有點多
兩個指針同時向后，判斷第一個字符是否相同，不同直接false,然后各自計算連續(xù)相同的字符有多少個，如果輸入的不夠名字的重復(fù)字符個數(shù)返回false,然后就是各自判斷有沒有結(jié)束，誰還沒結(jié)束都是不行

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        //15-30
        int left = 0;
        int right = 0;
        while(right<typed.length()){
            if(left>=name.length()) return false; //name已經(jīng)結(jié)束了 字符更長
            if(name.charAt(left)!=typed.charAt(right)){
                return false;
            }
            int count=1;//name的當(dāng)前字符連續(xù)的有幾個
            while(left+1<name.length()&&name.charAt(left+1)==name.charAt(left)){
                count++;
                left++;
            }  
            left++;      //每次在的都是新字符的第一位    
            //這里就相等了
            int c_right = 1;
            while(right+1<typed.length()&&typed.charAt(right+1)==typed.charAt(right)){
                c_right++;
                right++;
            }
            right++; //每次在的都是新字符的第一位
            if(c_right<count) return false; //字符數(shù)量不夠匹配
        }
        if(left<name.length()) return false;//名字還沒結(jié)束 名字更長
        return true;

    }
}

二叉樹

從根節(jié)點到葉節(jié)點數(shù)字之和

層次遍歷，每次遍歷的時候把子節(jié)點的值加上根節(jié)點的值，把所有葉子節(jié)點的值相加就得到結(jié)果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        //15-25
        //怎么遍歷都行 更新節(jié)點值
        int sum = 0;
        //層次遍歷
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left!=null){
                node.left.val = node.val*10+node.left.val;
                q.offer(node.left);
            }
            if(node.right!=null){
                node.right.val = node.val*10+node.right.val;
                q.offer(node.right);
            }
            if(node.left==null&&node.right==null) sum+=node.val;
        }
        return sum;
    }
}

1382. 將二叉搜索樹變平衡

第一次看到還是無從下手，明明昨天才剛復(fù)習(xí)了將有序數(shù)組轉(zhuǎn)換成平衡二叉搜索樹?。∷悸肪褪欠謨刹?，先將搜索樹轉(zhuǎn)換為有序數(shù)組，再將有序數(shù)組轉(zhuǎn)換為平衡二叉搜索樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        //06 將樹轉(zhuǎn)換成有序數(shù)組，再將有序數(shù)組構(gòu)建平衡二叉樹 -23
        ArrayList<Integer> list = new ArrayList<>();
        inorder(list,root);

        //將有序數(shù)組轉(zhuǎn)換成平衡二叉搜索樹
        return makeTree(list,0,list.size()); //左開右閉

    }
    public void inorder(ArrayList<Integer> list, TreeNode root){
        if(root==null) return;
        inorder(list, root.left);
        list.add(root.val);
        inorder(list, root.right);
    }

    public TreeNode makeTree(ArrayList<Integer> list,int begin, int end){
        if(begin>=end) return null;
        if(end-begin==1) return new TreeNode(list.get(begin)); //記得這個！??！
        int mid = begin + (end-begin)/2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = makeTree(list,begin,mid);
        root.right = makeTree(list,mid+1,end);
        return root;
    }
}

100 相同的樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //27 隨意一種遍歷都行

        if(p==null&&q==null) return true;
        else if(p==null||q==null) return false;
        else if(p.val!=q.val) return false;
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
        
    }
}

貪心

649 data2參議院

思路很簡單，就是實現(xiàn)的時候一開始覺得有點難，可能復(fù)雜度有點高。思路就是每次消滅后面的對手，遍歷字符串，可以記錄之前出現(xiàn)過的未行使權(quán)力的對手的數(shù)量，遍歷到的時候如果前面還有未行使權(quán)力的對手，當(dāng)前的就被消滅了，記錄兩個字符剩下的個數(shù)，直到有一方先消失

class Solution {
    public String predictPartyVictory(String senate) {
        //16-41
        //每次消除在自己后面的對手
        char[] chars = senate.toCharArray();
        int r = 0;
        int d = 0;//表示剩下的分別的個數(shù)
        for(int i=0;i<chars.length;i++){
            if(chars[i]=='R') r++;
            if(chars[i]=='D') d++;
        }
        int rr = 0, dd=0;//表示前面出現(xiàn)過的，還沒行使消除權(quán)力的數(shù)量 不能放在while循環(huán)內(nèi) 因為不是每輪都清空 上一輪的后面字符指定消滅下一輪前面的
        while(r>0&&d>0){
            for(int i=0;i<chars.length;i++){
                if(chars[i]=='R'){
                    if(dd>0){//前面還有d未行使權(quán)力
                        dd--;
                        chars[i]=0;
                        r--;
                    }else{
                        rr++;
                    }
                }
                if(chars[i]=='D'){
                    if(rr>0){
                        rr--;
                        chars[i]=0;
                        d--;
                    }else{
                        dd++;
                    }
                }

            }
        }
        return r>0?"Radiant":"Dire";
    }
}

1221 分割平衡字符串

很簡單，只要標(biāo)記未被分割的兩個字符的數(shù)量，相等時就分割，然后變量清零

class Solution {
    public int balancedStringSplit(String s) {
        //46-49
        int r = 0,l=0;
        int count = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='R'){
                r++;               
            }
            else if(s.charAt(i)=='L'){
                l++;
            }
            if(r==l){//分割 清零
                count++;
                r=0;
                l=0;
            }
        }
        return count;

    }
}

動態(tài)規(guī)劃

5 最長回文子串

class Solution {
    int be = 0;
    int len = 0;
    public String longestPalindrome(String s) {
        //26-37 中心向兩邊擴展
        for(int i=0;i<s.length();i++){
            huiwen(s,i,i);
            huiwen(s,i,i+1);
        }
        return s.substring(be,be+len);
    }
    public void huiwen(String s, int begin, int end){
        while(begin>=0&&end<s.length()&&begin<=end&&s.charAt(begin)==s.charAt(end)){
            begin--;
            end++;
        }
        if(end-begin-1>len){
            len = end-begin-1;
            be = begin+1;
        }
    }
}

132 分割回文串2

這題求的是最小分割次數(shù)，只要次數(shù)就可以用動態(tài)規(guī)劃，用回溯會超時。之前最小分割次數(shù)要求返回的是分割方案，就需要用回溯，也放在了下面，進(jìn)行對比

class Solution {
    public int minCut(String s) {
        //20-34

        //先構(gòu)建數(shù)組 表示i-j的字符串是不是回文串
        boolean[][] isHuiwen = new boolean[s.length()][s.length()];
        //初始化為false
        for(boolean[] tmp:isHuiwen){
            Arrays.fill(tmp,false);
        }
        //遞推公式是dp[i][j]=dp[i+1][j-1]    
        //遍歷要從下到上，從左到右遍歷 
        for(int i=s.length();i>=0;i--){
            for(int j=i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1) isHuiwen[i][j] = true;
                    else    isHuiwen[i][j] = isHuiwen[i+1][j-1];
                }
            }
        }
 
        //dp[i]表示0-i之間的字符串最少分割次數(shù)
        int[] dp = new int[s.length()];
        //初始化 s的最大分割次數(shù)是s.length-1
        for(int i=0;i<s.length();i++){
            dp[i] = i;
        }
        for(int i=1;i<s.length();i++){
            if(isHuiwen[0][i]){ //到i為止已經(jīng)是回文 不用分割
                dp[i] = 0;
                continue;
            }
            for(int j=0;j<i;j++){ //如果j~i是回文，在0-i之間再分割一個j,次數(shù)是dp[j]+1
                if(isHuiwen[j+1][i]){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[s.length()-1];

    }
}

131 分割回文串

class Solution {
    ArrayList<String> tmp = new ArrayList<String>();
    ArrayList<List<String>> res = new ArrayList<List<String>>();
    public List<List<String>> partition(String s) {
        //38-49
        dfs(s,0);
        return res;

    }
    public void dfs(String s, int index){
        if(index==s.length()){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=index;i<s.length();i++){
            if(ishuiwen(s,index,i)){
                tmp.add(s.substring(index,i+1));//左閉右開
                dfs(s,i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
    public boolean ishuiwen(String s, int begin, int end){//左閉右閉
        for(int i=begin,j=end;i<=j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

673 最長遞增子序列的個數(shù)

注意是序列個數(shù)！而不是序列長度，求長度很簡單，求序列個數(shù)的話看了很久的題解才寫出來。問題出在定義上，count[i]定義是以nums[i]為結(jié)尾的最長序列個數(shù)，而且不能只判斷求出的序列長度，還是要根據(jù)nums的大小來更新

class Solution {
    public int findNumberOfLIS(int[] nums) {
        //52-36!!!
        //往前找比自己小的最大的dp 子序列中數(shù)字的個數(shù)
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        //最長遞增子序列的個數(shù) 以nums[i]為結(jié)尾
        int[] count = new int[nums.length];
        int res = 0;
        int max = 1;
        Arrays.fill(count,1);

        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    if(dp[j]+1>dp[i]){ //第一次更新，count數(shù)量和前面一樣，因為是同一個序列
                        dp[i] = dp[j]+1;
                        count[i] = count[j];
                    }
                    else if(dp[j]+1==dp[i]){//已經(jīng)更新過的，這次相等就可以直接相加
                        count[i]+=count[j];
                    }                  
                }              
            }
            max = Math.max(max,dp[i]);
        }     
        //注意定義 是nums[i]為結(jié)尾的子序列的個數(shù)，所以要把dp為最長的對應(yīng)的count相加
        for(int i=0;i<nums.length;i++){
           if(dp[i]==max){
               res+=count[i];
           }
        }
        return res;
    }
}

圖論

841 鑰匙和房間

一開始自己寫用list去模擬，要重復(fù)插入和刪除數(shù)據(jù)，超內(nèi)存，還是看了題解，回溯寫多了忘了最初的深搜，需要認(rèn)真看一下這題

class Solution {
    int num = 0;//到過的房間數(shù)量
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //46--10!!!!
        //深度優(yōu)先搜索的方式遍歷整張圖，統(tǒng)計可以到達(dá)的節(jié)點個數(shù)，
        //并利用數(shù)組 vis標(biāo)記當(dāng)前節(jié)點是否訪問過，以防止重復(fù)訪問
        
        int len = rooms.size();
        boolean[] vis = new boolean[len];
        Arrays.fill(vis,false);
        dfs(rooms,0,vis);//0表示索引，也就是第幾個房間
        return num==len;      
    }
    public void dfs(List<List<Integer>> rooms, int index, boolean[] vis){
        vis[index] = true;
        num++;
        for(int x:rooms.get(index)){
            if(!vis[x]){
                dfs(rooms,x,vis);
            }
        }
    }
}

127 單詞接龍

第一反應(yīng)無從下手，主要還是覺得暴力會復(fù)雜度太高，但最后的解法還是暴力匹配+廣搜，用了技巧是把list轉(zhuǎn)換為hashset,因為有大量的判斷contains的操作，轉(zhuǎn)換后就沒超時，用原來的list會超時
用廣搜搜到的第一個符合條件的一定就是路徑最短的

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //14-27
        HashSet<String> wordSet = new HashSet<>(wordList);//轉(zhuǎn)換為hashset才能通過 否則超時 在查找時contains用的多就用hashset
        Map<String, Integer> map = new HashMap<>();
        map.put(beginWord,1);//數(shù)字表示路徑中的第幾個
        if(wordSet.size()==0||!wordSet.contains(endWord)){
            return 0;
        }
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        while(!q.isEmpty()){
            String word = q.poll();
            int path = map.get(word);
            //遍歷
            for(int i=0;i<word.length();i++){
                char[] chars = word.toCharArray();
                for(char j = 'a';j<='z';j++){
                    chars[i] = j;//替換每個字符
                    String s = String.valueOf(chars);//得到新詞
                    if(s.equals(endWord)){
                        return path+1;
                    }else if(wordSet.contains(s)&&!map.containsKey(s)){
                        map.put(s,path+1);
                        q.offer(s);
                    }
                }
            }
        }
        return 0;
    }
}

并查集

684 冗余連接

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        //32-45
        int n = edges.length;
        int[] father = new int[n+1];
        for(int i=1;i<=n;i++){
            father[i] = i;
        }
        for(int i=0;i<n;i++){
            if(same(father,edges[i][0],edges[i][1])){
                return new int[]{edges[i][0],edges[i][1]};
            }else{
                add(father,edges[i][0],edges[i][1]);
            }
        }
        return null;

    }
    public boolean same(int[] father, int u, int v){
        return find(father, u)==find(father, v);
    }
    public int find(int[] father, int u){
        if(father[u]!=u){
            father[u] = find(father, father[u]);
        }
        return father[u];
    }
    public void add(int[] father, int u, int v){
        u = find(father,u);//注意是父節(jié)點
        v = find(father,v);
        if(u!=v){
           // father[u] = v; 兩種都可以
           father[v] = u;
        }
    }
}

685 冗余連接2

和上題的區(qū)別在于這是有向圖，用上面的代碼只能過30%左右，因為加了方向，就不一定是之前的刪除方式。
主要有三種情況

這是存在入度為2的節(jié)點，這種情況下，一定是刪除入度為2的邊的其中一條，要優(yōu)先刪除最后面出現(xiàn)的，

如果不存在入度為2的點一定存在有向環(huán)，刪除導(dǎo)致出現(xiàn)有向環(huán)的邊，就和上題一樣

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        //52 和無向的區(qū)別？ --26
         
        int n = edges.length;
        int[] father = new int[n+1];
        for(int i=1;i<=n;i++){
            father[i] = i;
        }

        //計算入度為2的節(jié)點
        int[] in = new int[n+1];
        Arrays.fill(in,0);
        for(int i=0;i<n;i++){
            in[edges[i][1]]++;
        }
        //找入度為2節(jié)點對應(yīng)的邊
        //要從后遍歷 因為要返回的是最后出現(xiàn)的
        ArrayList<Integer> ed = new ArrayList<>();
        for(int i=n-1;i>=0;i--){
            if(in[edges[i][1]]==2){
                ed.add(i);
            }
        }
        //有入度為2的節(jié)點
        if(!ed.isEmpty()){
            if(isTreeAfterRemoveEdge(father, edges,ed.get(0))){//ed先存的是后出現(xiàn)的，這里要先刪除索引為0的，反之就反過來
                return edges[ed.get(0)];
            }else return edges[ed.get(1)];
        }
        //沒有入度為2的節(jié)點
        return getRemoveEdge(father, edges);

    }
    public void init(int[] father, int n){
        for(int i=1;i<=n;i++){
            father[i] = i;
        }
    }
    public boolean same(int[] father, int u, int v){
        return find(father, u)==find(father, v);
    }
    public int find(int[] father, int u){
        if(father[u]!=u){
            father[u] = find(father, father[u]);
        }
        return father[u];
    }
    public void add(int[] father, int u, int v){
        u = find(father,u);//注意是父節(jié)點
        v = find(father,v);
        if(u!=v){
            father[u] = v; //兩種都可以
           //father[v] = u;
        }
    }

    public boolean isTreeAfterRemoveEdge(int[] father, int[][] edges, int index){
        int n = edges.length;
        init(father, n);
        
        for(int i=0;i<n;i++){
            if(i==index) continue;
            
            if(same(father,edges[i][0],edges[i][1])){
                return false;
            }else{
                add(father,edges[i][0],edges[i][1]);
            }
        }
        return true;
    }
    public int[] getRemoveEdge(int[] father, int[][] edges){
        int n = edges.length;
        init(father, n);
        for(int i=0;i<n;i++){
            if(same(father,edges[i][0],edges[i][1])){
                return edges[i];
            }else{
                add(father,edges[i][0],edges[i][1]);
            }
        }
        return null;
    }
}
        

模擬

31 下一個排列

可以先把全排列寫出來，然后找規(guī)律，我第一次沒有全寫出來，就是憑感覺只交換了一個，過了50%

class Solution {
    public void nextPermutation(int[] nums) {
        //40
        //從尾向前找最 nums[i]<nums[j]的 然后交換 沒找到就全部反轉(zhuǎn)
        for(int i=nums.length-1;i>=0;i--){
            for(int j=nums.length-1;j>i;j--){
                if(nums[j]>nums[i]){
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    Arrays.sort(nums,i+1,nums.length);
                    return;
                }
            }            
        }
        //沒找到就全部反轉(zhuǎn)
        Arrays.sort(nums);

    }
}

463 島嶼的周長

總周長減去相鄰的邊數(shù)

class Solution {
    public int islandPerimeter(int[][] grid) {
        //04-11
        int count = 0;//陸地個數(shù)
        int edge = 0;//相鄰的邊
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    count++;
                    if(i>0&&grid[i-1][j]==1) edge++;
                    if(i+1<grid.length&&grid[i+1][j]==1) edge++;
                    if(j>0&&grid[i][j-1]==1) edge++;
                    if(j+1<grid[0].length&&grid[i][j+1]==1) edge++;
                } 
            }
        }
        return count*4-edge;
    }
}

1356

文章來源地址http://www.zghlxwxcb.cn/news/detail-437812.html

class Solution {
    public int[] sortByBits(int[] arr) {
        //13-23
        int[][] a = new int[arr.length][2];//第一維是arr 第二維是1的個數(shù)
        for(int i=0;i<arr.length;i++){
            a[i][0] = arr[i];
            int t = arr[i]; 
            int count = 0;//1的個數(shù)
            while(t!=0){
                if((t&1)==1){ //或者t%2==1
                    count++;               
                }
               // t /=2;
               t>>=1;
            }
            a[i][1] = count;
        }
        Arrays.sort(a,(o1,o2)->o1[1]-o2[1]!=0?o1[1]-o2[1]:o1[0]-o2[0]);
        int[] res = new int[arr.length];
        for(int i=0;i<arr.length;i++){
            res[i] = a[i][0];
        }
        return res;


    }
}

到了這里，關(guān)于代碼隨想錄之額外題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！