第二章：二分法

目录：

 

 

 

 

414：

public int divide(int dividend, int divisor) {        if (divisor == 0) {            return dividend >= 0? Integer.MAX_VALUE : Integer.MIN_VALUE;        }                if (dividend == 0) {            return 0;        }                if (dividend == Integer.MIN_VALUE && divisor == -1) {            return Integer.MAX_VALUE;        }                boolean isNegative = (dividend < 0 && divisor > 0) ||                              (dividend > 0 && divisor < 0);                                     long a = Math.abs((long)dividend);        long b = Math.abs((long)divisor);        int result = 0;        while(a >= b){            int shift = 0;            while(a >= (b << shift)){                shift++;            }            a -= b << (shift - 1);            result += 1 << (shift - 1);        }        return isNegative? -result: result;    }

 

617：

public double maxAverage(int[] nums, int k) {        double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;        for (int i = 0; i < nums.length; ++i) {            if (nums[i] < l)                l = nums[i];            if (nums[i] > r)                r = nums[i];        }                       while (r - l >= 1e-6) {            double mid = (l + r) / 2.0;            if (check_valid(nums, mid, k)) {                l = mid;            }            else {                r = mid;            }        }        return l;    }        private boolean check_valid(int nums[], double mid, int k) {        int n = nums.length;        double min_pre = 0;        double[] sum = new double[n + 1];        sum[0] = 0;         for (int i = 1; i <= n; ++i) {            sum[i] = sum[i - 1] + nums[i - 1] - mid;            if (i >= k && sum[i] - min_pre >= 0) {                return true;            }            if (i >= k)                min_pre = Math.min(min_pre, sum[i - k + 1]);        }        return false;    }

 

586：

二分法：

public double sqrt(double x) {        double left = 0.0;        double right = x;        double eps = 1e-12;        if(right < 1.0) {            right = 1.0;        }        while(right - left > eps) {            // 二分浮点数 和二分整数不同            // 一般都有一个精度的要求 譬如这题就是要求小数点后八位            // 也就是只要我们二分的结果达到了这个精度的要求就可以            // 所以 需要让 right 和 left 小于一个我们事先设定好的精度值 eps            // 一般eps的设定1e-8,因为这题的要求是到1e-8,所以我把精度调到了1e-12            // 最后 选择 left 或 right 作为一个结果即可             double mid = (right + left) / 2;            if(mid * mid < x) {                left = mid;            }            else {                right = mid;            }        }        return left;    }

牛顿法：

public double sqrt(double x) {        // Write your code here        double res = 1.0;        double eps = 1e-12;        while(Math.abs(res * res - x) > eps) {            res = (res + x / res) / 2;        }        return res;    }

 

160：

一个循环：

public int findMin(int[] nums) {        //  这道题目在面试中不会让写完整的程序        //  只需要知道最坏情况下 [1,1,1....,1] 里有一个0        //  这种情况使得时间复杂度必须是 O(n)        //  因此写一个for循环就好了。        //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。        //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。        int min = nums[0];        for (int i = 1; i < nums.length; i++) {            if (nums[i] < min)                min = nums[i];        }        return min;    }

二分：

public int findMin(int[] nums) {        if (nums == null || nums.length == 0) {            return -1;        }                int start = 0, end = nums.length - 1;        while (start + 1 < end) {            int mid = start + (end - start) / 2;            if (nums[mid] == nums[end]) {                // if mid equals to end, that means it's fine to remove end                // the smallest element won't be removed                end--;            } else if (nums[mid] < nums[end]) {                end = mid;                // of course you can merge == & <            } else {                start = mid;                // or start = mid + 1            }        }                if (nums[start] <= nums[end]) {            return nums[start];        }        return nums[end];    }

 

63：

// 这个问题在面试中不会让实现完整程序    // 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。    // 在这种情况下是无法使用二分法的，复杂度是O(n)    // 因此写个for循环最坏也是O(n)，那就写个for循环就好了    //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。    //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。    public boolean search(int[] A, int target) {        for (int i = 0; i < A.length; i ++) {            if (A[i] == target) {                return true;            }        }        return false;    }

 

 

第三章：二叉树和分治法

目录：

 

 

 

88：

// 在root为根的二叉树中找A,B的LCA:    // 如果找到了就返回这个LCA    // 如果只碰到A，就返回A    // 如果只碰到B，就返回B    // 如果都没有，就返回null    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {        if (root == null || root == node1 || root == node2) {            return root;        }                // Divide        TreeNode left = lowestCommonAncestor(root.left, node1, node2);        TreeNode right = lowestCommonAncestor(root.right, node1, node2);                // Conquer        if (left != null && right != null) {            return root;        }         if (left != null) {            return left;        }        if (right != null) {            return right;        }        return null;    }

 

474：

public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,                                                 ParentTreeNode A,                                                 ParentTreeNode B) {        ArrayList
      
        pathA = getPath2Root(A);        ArrayList
       
         pathB = getPath2Root(B);                int indexA = pathA.size() - 1;        int indexB = pathB.size() - 1;                ParentTreeNode lowestAncestor = null;        while (indexA >= 0 && indexB >= 0) {            if (pathA.get(indexA) != pathB.get(indexB)) {                break;            }            lowestAncestor = pathA.get(indexA);            indexA--;            indexB--;        }                return lowestAncestor;    }        private ArrayList
        
          getPath2Root(ParentTreeNode node) {        ArrayList
         
           path = new ArrayList<>();        while (node != null) {            path.add(node);            node = node.parent;        }        return path;    }
         
        
       
      

 

578：

class ResultType {    public boolean a_exist, b_exist;    public TreeNode node;    ResultType(boolean a, boolean b, TreeNode n) {        a_exist = a;        b_exist = b;        node = n;    }}public class Solution {    /**     * @param root The root of the binary tree.     * @param A and B two nodes     * @return: Return the LCA of the two nodes.     */    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {        // write your code here        ResultType rt = helper(root, A, B);        if (rt.a_exist && rt.b_exist)            return rt.node;        else            return null;    }    public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {        if (root == null)            return new ResultType(false, false, null);                    ResultType left_rt = helper(root.left, A, B);        ResultType right_rt = helper(root.right, A, B);                boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;        boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;                if (root == A || root == B)            return new ResultType(a_exist, b_exist, root);        if (left_rt.node != null && right_rt.node != null)            return new ResultType(a_exist, b_exist, root);        if (left_rt.node != null)            return new ResultType(a_exist, b_exist, left_rt.node);        if (right_rt.node != null)            return new ResultType(a_exist, b_exist, right_rt.node);        return new ResultType(a_exist, b_exist, null);    }}

 

95：

private int lastVal = Integer.MIN_VALUE;    private boolean firstNode = true;    public boolean isValidBST(TreeNode root) {        if (root == null) {            return true;        }        if (!isValidBST(root.left)) {            return false;        }        if (!firstNode && lastVal >= root.val) {            return false;        }        firstNode = false;        lastVal = root.val;        if (!isValidBST(root.right)) {            return false;        }        return true;    }

 

155：

public int minDepth(TreeNode root) {        if (root == null) {            return 0;        }        return getMin(root);    }    public int getMin(TreeNode root){        if (root == null) {            return Integer.MAX_VALUE;        }        if (root.left == null && root.right == null) {            return 1;        }        return Math.min(getMin(root.left), getMin(root.right)) + 1;    }

 

246：

public List
      
       
        > binaryTreePathSum2(TreeNode root, int target) {        // Write your code here        List
        
         
          > results = new ArrayList
          
           
            >(); ArrayList
            
              buffer = new ArrayList
             
              (); if (root == null) return results; findSum(root, target, buffer, 0, results); return results; } public void findSum(TreeNode head, int sum, ArrayList
              
                buffer, int level, List
               
                
                 > results) { if (head == null) return; int tmp = sum; buffer.add(head.val); for (int i = level;i >= 0; i--) { tmp -= buffer.get(i); if (tmp == 0) { List
                 
                   temp = new ArrayList
                  
                   (); for (int j = i; j <= level; ++j) temp.add(buffer.get(j)); results.add(temp); } } findSum(head.left, sum, buffer, level + 1, results); findSum(head.right, sum, buffer, level + 1, results); buffer.remove(buffer.size() - 1); }
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

public List
      
       
        > binaryTreePathSum3(ParentTreeNode root, int target) {        // Write your code here        List
        
         
          > results = new ArrayList
          
           
            >(); dfs(root, target, results); return results; } public void dfs(ParentTreeNode root, int target, List
            
             
              > results) { if (root == null) return; List
              
                path = new ArrayList
               
                (); findSum(root, null, target, path, results); dfs(root.left, target, results); dfs(root.right, target, results); } public void findSum(ParentTreeNode root, ParentTreeNode father, int target, List
                
                  path, List
                 
                  
                   > results) { path.add(root.val); target -= root.val; if (target == 0) { ArrayList
                   
                     tmp = new ArrayList
                    
                     (); Collections.addAll(tmp, new Integer[path.size()]); Collections.copy(tmp, path); results.add(tmp); } if (root.parent != null && root.parent != father) findSum(root.parent, root, target, path, results); if (root.left != null && root.left != father) findSum(root.left, root, target, path, results); if (root.right != null && root.right != father) findSum(root.right, root, target, path, results); path.remove(path.size() - 1); }
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

475：

public int maxPathSum2(TreeNode root) {        if (root == null) {            return Integer.MIN_VALUE;        }                int left = maxPathSum2(root.left);        int right = maxPathSum2(root.right);        return root.val + Math.max(0, Math.max(left, right));    }

 

614：

class ResultType {    public int max_length, max_down, max_up;    ResultType(int len, int down, int up) {        max_length = len;        max_down = down;        max_up = up;        }}public class Solution {    /**     * @param root the root of binary tree     * @return the length of the longest consecutive sequence path     */    public int longestConsecutive2(TreeNode root) {        // Write your code here        return helper(root).max_length;    }        ResultType helper(TreeNode root) {        if (root == null) {            return new ResultType(0, 0, 0);        }        ResultType left = helper(root.left);        ResultType right = helper(root.right);        int down = 0, up = 0;        if (root.left != null && root.left.val + 1 == root.val)            down = Math.max(down, left.max_down + 1);        if (root.left != null && root.left.val - 1 == root.val)            up = Math.max(up, left.max_up + 1);        if (root.right != null && root.right.val + 1 == root.val)            down = Math.max(down, right.max_down + 1);        if (root.right != null && root.right.val - 1 == root.val)            up = Math.max(up, right.max_up + 1);        int len = down + 1 + up;        len = Math.max(len, Math.max(left.max_length, right.max_length));        return new ResultType(len, down, up);    }}

 

619：

class ResultType {    public int max_len, max_down, max_up;    ResultType(int len, int down, int up) {        max_len = len;        max_down = down;        max_up = up;        }}public class Solution {    /**     * @param root the root of k-ary tree     * @return the length of the longest consecutive sequence path     */    public int longestConsecutive3(MultiTreeNode root) {        // Write your code here        return helper(root).max_len;    }        ResultType helper(MultiTreeNode root) {        if (root == null) {            return new ResultType(0, 0, 0);        }        int down = 0, up = 0, max_len = 1;        for (MultiTreeNode node : root.children) {            ResultType type = helper(node);            if (node.val + 1 == root.val)                down = Math.max(down, type.max_down + 1);            if (node.val - 1 == root.val)                up = Math.max(up, type.max_up + 1);            max_len = Math.max(max_len, type.max_len);        }        max_len = Math.max(down + 1 + up, max_len);        return new ResultType(max_len, down, up);    }}

 

448：

public class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {        TreeNode successor = null;        while (root != null && root != p) {            if (root.val > p.val) {                successor = root;                root = root.left;            } else {                root = root.right;            }        }                if (root == null) {            return null;        }                if (root.right == null) {            return successor;        }                root = root.right;        while (root.left != null) {            root = root.left;        }                return root;    }}

更短：

public class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {        // write your code here        if (root == null || p == null) {            return null;        }        if (root.val <= p.val) {            return inorderSuccessor(root.right, p);        } else {            TreeNode left = inorderSuccessor(root.left, p);            return (left != null) ? left : root;        }    }}

 

378：

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } * Definition for Doubly-ListNode. * public class DoublyListNode { *     int val; *     DoublyListNode next, prev; *     DoublyListNode(int val) { *         this.val = val; *         this.next = this.prev = null; *     } * } */  class ResultType {    DoublyListNode first, last;        public ResultType(DoublyListNode first, DoublyListNode last) {        this.first = first;        this.last = last;    }}public class Solution {    /**     * @param root: The root of tree     * @return: the head of doubly list node     */    public DoublyListNode bstToDoublyList(TreeNode root) {          if (root == null) {            return null;        }                ResultType result = helper(root);        return result.first;    }        public ResultType helper(TreeNode root) {          if (root == null) {            return null;        }                ResultType left = helper(root.left);        ResultType right = helper(root.right);        DoublyListNode node = new DoublyListNode(root.val);                ResultType result = new ResultType(null, null);                if (left == null) {            result.first = node;        } else {            result.first = left.first;            left.last.next = node;            node.prev = left.last;        }                if (right == null) {            result.last = node;        } else {            result.last = right.last;            right.first.prev = node;            node.next = right.first;        }                return result;    }}

 

 

 

 

第四章：宽度优先搜索

目录：

 

 

 

 624：

public int minLength(String s, Set
      
        dict) {        // Write your code here        Queue
       
         que = new LinkedList
        
         ();        Set
         
           hash = new HashSet
          
           ();            int min = s.length();        que.offer(s);        hash.add(s);        while (!que.isEmpty()) {            s = que.poll();            for (String sub : dict) {                int found = s.indexOf(sub);                while (found != -1) {                    String new_s = s.substring(0, found) +                        s.substring(found + sub.length(), s.length());                    if (!hash.contains(new_s)) {                        if (new_s.length() < min)                            min = new_s.length();                        que.offer(new_s);                        hash.add(new_s);                    }                    found = s.indexOf(sub, found + 1);                }            }        }        return min;    }
          
         
        
       
      

 

605：

 

public boolean sequenceReconstruction(int[] org, int[][] seqs) {        // Write your code here        Map
      
       > map = new HashMap
       
        >();        Map
        
          indegree = new HashMap
         
          ();                for (int num : org) {            map.put(num, new HashSet
          
           ());            indegree.put(num, 0);        }        int n = org.length;        int count = 0;        for (int[] seq : seqs) {            count += seq.length;            if (seq.length >= 1 && (seq[0] <= 0 || seq[0] > n))                return false;            for (int i = 1; i < seq.length; i++) {                if (seq[i] <= 0 || seq[i] > n)                    return false;                if (map.get(seq[i - 1]).add(seq[i]))                    indegree.put(seq[i], indegree.get(seq[i]) + 1);            }        }        // case: [1], []        if (count < n)            return false;                Queue
           
             q = new ArrayDeque
            
             (); for (int key : indegree.keySet()) if (indegree.get(key) == 0) q.add(key); int cnt = 0; while (q.size() == 1) { int ele = q.poll(); for (int next : map.get(ele)) { indegree.put(next, indegree.get(next) - 1); if (indegree.get(next) == 0) q.add(next); } if (ele != org[cnt]) { return false; } cnt++; } return cnt == org.length; }
            
           
          
         
        
       
      

 

531：

public int sixDegrees(List
      
        graph,                          UndirectedGraphNode s,                          UndirectedGraphNode t) {        // Write your code here        if (s == t)            return 0;        Map
       
         visited = new HashMap
        
         ();        Queue
         
           queue = new LinkedList
          
           ();                queue.offer(s);        visited.put(s, 0);        while (!queue.isEmpty()) {            UndirectedGraphNode node = queue.poll();            int step = visited.get(node);            for (int i = 0; i < node.neighbors.size(); i++) {                if (visited.containsKey(node.neighbors.get(i))) {                    continue;                }                visited.put(node.neighbors.get(i), step + 1);                queue.offer(node.neighbors.get(i));                if (node.neighbors.get(i) == t) {                    return step + 1;                }            }        }                return -1;    }
          
         
        
       
      

 

120：

public class Solution {    public int ladderLength(String start, String end, Set
      
        dict) {        if (dict == null) {            return 0;        }        if (start.equals(end)) {            return 1;        }                dict.add(start);        dict.add(end);        HashSet
       
         hash = new HashSet
        
         ();        Queue
         
           queue = new LinkedList
          
           ();        queue.offer(start);        hash.add(start);                int length = 1;        while(!queue.isEmpty()) {            length++;            int size = queue.size();            for (int i = 0; i < size; i++) {                String word = queue.poll();                for (String nextWord: getNextWords(word, dict)) {                    if (hash.contains(nextWord)) {                        continue;                    }                    if (nextWord.equals(end)) {                        return length;                    }                                        hash.add(nextWord);                    queue.offer(nextWord);                }            }        }        return 0;    }    // replace character of a string at given index to a given character    // return a new string    private String replace(String s, int index, char c) {        char[] chars = s.toCharArray();        chars[index] = c;        return new String(chars);    }        // get connections with given word.    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}    // it will return ['hit', 'hog']    private ArrayList
           
             getNextWords(String word, Set
            
              dict) { ArrayList
             
               nextWords = new ArrayList
              
               (); for (char c = 'a'; c <= 'z'; c++) { for (int i = 0; i < word.length(); i++) { if (c == word.charAt(i)) { continue; } String nextWord = replace(word, i, c); if (dict.contains(nextWord)) { nextWords.add(nextWord); } } } return nextWords; }}
              
             
            
           
          
         
        
       
      

 

615：

public boolean canFinish(int numCourses, int[][] prerequisites) {        // Write your code here        List[] edges = new ArrayList[numCourses];        int[] degree = new int[numCourses];                for (int i = 0;i < numCourses; i++)            edges[i] = new ArrayList
      
       ();                    for (int i = 0; i < prerequisites.length; i++) {            degree[prerequisites[i][0]] ++ ;            edges[prerequisites[i][1]].add(prerequisites[i][0]);        }        Queue queue = new LinkedList();        for(int i = 0; i < degree.length; i++){            if (degree[i] == 0) {                queue.add(i);            }        }                int count = 0;        while(!queue.isEmpty()){            int course = (int)queue.poll();            count ++;            int n = edges[course].size();            for(int i = 0; i < n; i++){                int pointer = (int)edges[course].get(i);                degree[pointer]--;                if (degree[pointer] == 0) {                    queue.add(pointer);                }            }        }                return count == numCourses;    }
      

 

431：

/** * Definition for Undirected graph. * class UndirectedGraphNode { *     int label; *     ArrayList
      
        neighbors; *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList
       
        (); } * }; */public class Solution {    /**     * @param nodes a array of Undirected graph node     * @return a connected set of a Undirected graph     */    public List
        
         
          > connectedSet(List
          
            nodes) {        // Write your code here                int m = nodes.size();        Map
           
             visited = new HashMap<>(); for (UndirectedGraphNode node : nodes){ visited.put(node, false); } List
            
             
              > result = new ArrayList<>(); for (UndirectedGraphNode node : nodes){ if (visited.get(node) == false){ bfs(node, visited, result); } } return result; } public void bfs(UndirectedGraphNode node, Map
              
                visited, List
               
                
                 > result){ List
                 
                  row = new ArrayList<>(); Queue
                  
                    queue = new LinkedList<>(); visited.put(node, true); queue.offer(node); while (!queue.isEmpty()){ UndirectedGraphNode u = queue.poll(); row.add(u.label); for (UndirectedGraphNode v : u.neighbors){ if (visited.get(v) == false){ visited.put(v, true); queue.offer(v); } } } Collections.sort(row); result.add(row); }}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

70：

public List
      
       
        > levelOrderBottom(TreeNode root) {        List
        
         
          > result = new ArrayList<>();        if (root == null) {            return result;        }        Queue
          
            queue = new LinkedList
           
            (); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List
            
              level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode head = queue.poll(); level.add(head.val); if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } } result.add(level); } Collections.reverse(result); return result; }
            
           
          
         
        
       
      

 

71：

public List
      
       
        > zigzagLevelOrder(TreeNode root) {        List
        
         
          > result = new ArrayList
          
           
            >(); if (root == null) { return result; } Stack
            
              currLevel = new Stack
             
              (); Stack
              
                nextLevel = new Stack
               
                (); Stack
                
                  tmp; currLevel.push(root); boolean normalOrder = true; while (!currLevel.isEmpty()) { ArrayList
                 
                   currLevelResult = new ArrayList
                  
                   (); while (!currLevel.isEmpty()) { TreeNode node = currLevel.pop(); currLevelResult.add(node.val); if (normalOrder) { if (node.left != null) { nextLevel.push(node.left); } if (node.right != null) { nextLevel.push(node.right); } } else { if (node.right != null) { nextLevel.push(node.right); } if (node.left != null) { nextLevel.push(node.left); } } } result.add(currLevelResult); tmp = currLevel; currLevel = nextLevel; nextLevel = tmp; normalOrder = !normalOrder; } return result; }
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

434：

/** * Definition for a point. * class Point { *     int x; *     int y; *     Point() { x = 0; y = 0; } *     Point(int a, int b) { x = a; y = b; } * } */public class Solution {    /**     * @param n an integer     * @param m an integer     * @param operators an array of point     * @return an integer array     */    int converttoId(int x, int y, int m){        return x*m + y;    }    class UnionFind{        HashMap
      
        father = new HashMap
       
        ();        UnionFind(int n, int m){            for(int i = 0 ; i < n; i++) {                for(int j = 0 ; j < m; j++) {                    int id = converttoId(i,j,m);                    father.put(id, id);                 }            }        }        int compressed_find(int x){            int parent =  father.get(x);            while(parent!=father.get(parent)) {                parent = father.get(parent);            }            int temp = -1;            int fa = x;            while(fa!=father.get(fa)) {                temp = father.get(fa);                father.put(fa, parent) ;                fa = temp;            }            return parent;                        }                void union(int x, int y){            int fa_x = compressed_find(x);            int fa_y = compressed_find(y);            if(fa_x != fa_y)                father.put(fa_x, fa_y);        }    }        public List
        
          numIslands2(int n, int m, Point[] operators) {        // Write your code here        List
         
           ans = new ArrayList
          
           ();        if(operators == null) {            return ans;        }                int []dx = {0,-1, 0, 1};        int []dy = {1, 0, -1, 0};        int [][]island = new int[n][m];                       UnionFind uf = new UnionFind(n, m);        int count = 0;                for(int i = 0; i < operators.length; i++) {            int x = operators[i].x;            int y = operators[i].y;            if(island[x][y] != 1) {                count ++;                island[x][y]  = 1;                int id = converttoId(x,y , m);                for(int j = 0 ; j < 4; j++) {                    int nx = x + dx[j];                    int ny = y + dy[j];                    if(0 <= nx && nx < n && 0 <= ny && ny < m && island[nx][ny] == 1)                     {                        int nid = converttoId(nx, ny, m);                                                int fa = uf.compressed_find(id);                        int nfa = uf.compressed_find(nid);                        if(fa != nfa) {                            count--;                            uf.union(id, nid);                        }                    }                }            }            ans.add(count);        }        return ans;    }}
          
         
        
       
      

 

574：

public int shortestDistance(int[][] grid) {        // Write your code here        int n = grid.length;        if (n == 0)            return -1;        int m = grid[0].length;        if (m == 0)            return -1;        List
      
        sumx = new ArrayList
       
        ();        List
        
          sumy = new ArrayList
         
          ();        List
          
            x = new ArrayList
           
            (); List
            
              y = new ArrayList
             
              (); int result = Integer.MAX_VALUE; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (grid[i][j] == 1) { x.add(i); y.add(j); } Collections.sort(x); Collections.sort(y); int total = x.size(); sumx.add(0); sumy.add(0); for (int i = 1; i <= total; ++i) { sumx.add(sumx.get(i-1) + x.get(i-1)); sumy.add(sumy.get(i-1) + y.get(i-1)); } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (grid[i][j] == 0) { int cost_x = get_cost(x, sumx, i, total); int cost_y = get_cost(y, sumy, j, total); if (cost_x + cost_y < result) result = cost_x + cost_y; } return result; } public int get_cost(List
              
                x, List
               
                 sum, int pos, int n) { if (n == 0) return 0; if (x.get(0) > pos) return sum.get(n) - pos * n; int l = 0, r = n - 1; while (l + 1 < r) { int mid = l + (r - l) / 2; if (x.get(mid) <= pos) l = mid; else r = mid - 1; } int index = 0; if (x.get(r) <= pos) index = r; else index = l; return sum.get(n) - sum.get(index + 1) - pos * (n - index - 1) + (index + 1) * pos - sum.get(index + 1); }
               
              
             
            
           
          
         
        
       
      

public int shortestDistance(int[][] grid) {        // Write your code here        int row = grid.length, column = grid[0].length;        if(row == 0 || column == 0 || !haveZero(grid,row,column)) {            return -1;        }        int[] rowSum = new int[row];        int[] columnSum = new int[column];         for(int i = 0; i < row; i++)            for(int j = 0; j < column; j++)                if(grid[i][j] == 1) {                    rowSum[i]++;                    columnSum[j]++;                }        int[] ansRow = new int[row];        int[] ansColumn = new int[column];        getSumDistance(rowSum,row,ansRow);        getSumDistance(columnSum,column,ansColumn);        int ans = Integer.MAX_VALUE;        for(int i = 0; i < row; i++)            for(int j = 0; j < column; j++)                if(grid[i][j] == 0 && ans > ansRow[i] + ansColumn[j]) {                    ans = ansRow[i] + ansColumn[j];                }        return ans;    }    void getSumDistance(int[] a,int n,int[] ans) {        int[] prefixSum1 = new int[n];        int[] prefixSum2 = new int[n];        /*        第一阶段，处理前缀。        prefixSum1记录数组 a 的前缀和，即:prefixSum1[i]=a[0]+a[1]+..+a[i].        prefixSum2记录数组 prefixSum1 前缀和，prefixSum2即为前 i 个点到第 i 个点的代价和。        */        prefixSum1[0] = a[0];        for(int i = 1; i < n; i++) {            prefixSum1[i] = prefixSum1[i - 1] + a[i];        }        prefixSum2[0] = 0;        for(int i = 1; i < n; i++) {            prefixSum2[i] = prefixSum2[i - 1] + prefixSum1[i - 1];         }         for(int i = 0; i < n; i++) {             ans[i] = prefixSum2[i];         }        /*        第二阶段，处理后缀。        prefixSum1记录数组 a 的后缀和，即:prefixSum1[i]=a[n-1]+a[n-2]+..+a[i].        prefixSum2记录数组 prefixSum1 的后缀和，prefixSum2即为 i 之后的点到第 i 个点的代价和。        */        prefixSum1[n - 1] = a[n - 1];        for(int i = n - 2; i >= 0; i--) {            prefixSum1[i] = prefixSum1[i + 1] + a[i];        }        prefixSum2[n - 1] =0;        for(int i = n - 2; i >= 0; i--) {            prefixSum2[i] = prefixSum2[i + 1] + prefixSum1[i + 1];         }         for(int i = 0; i < n; i++) {             ans[i] += prefixSum2[i];         }         /*         ans[i] 即为a数组中所有点到第 i 点的代价和         */    }    boolean haveZero(int[][] grid, int row, int column) {        for(int i = 0; i < row; i++) {            for(int j = 0; j < column; j++){                if(grid[i][j] == 0) {                    return true;                }            }        }        return false;    }

 

 

 

 

第五章：深度优先算法

目录：

 

 

 

121：

public List
      
       
        > findLadders(String start, String end,            Set
        
          dict) {        List
         
          
           > ladders = new ArrayList
           
            
             >(); Map
             
              > map = new HashMap
              
               >(); Map
               
                 distance = new HashMap
                
                 (); dict.add(start); dict.add(end); bfs(map, distance, start, end, dict); List
                 
                   path = new ArrayList
                  
                   (); dfs(ladders, path, end, start, distance, map); return ladders; } void dfs(List
                   
                    
                     > ladders, List
                     
                       path, String crt, String start, Map
                      
                        distance, Map
                       
                        > map) { path.add(crt); if (crt.equals(start)) { Collections.reverse(path); ladders.add(new ArrayList
                        
                         (path)); Collections.reverse(path); } else { for (String next : map.get(crt)) { if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { dfs(ladders, path, next, start, distance, map); } } } path.remove(path.size() - 1); } void bfs(Map
                         
                          > map, Map
                          
                            distance, String start, String end, Set
                           
                             dict) { Queue
                            
                              q = new LinkedList
                             
                              (); q.offer(start); distance.put(start, 0); for (String s : dict) { map.put(s, new ArrayList
                              
                               ()); } while (!q.isEmpty()) { String crt = q.poll(); List
                               
                                 nextList = expand(crt, dict); for (String next : nextList) { map.get(next).add(crt); if (!distance.containsKey(next)) { distance.put(next, distance.get(crt) + 1); q.offer(next); } } } } List
                                
                                  expand(String crt, Set
                                 
                                   dict) { List
                                  
                                    expansion = new ArrayList
                                   
                                    (); for (int i = 0; i < crt.length(); i++) { for (char ch = 'a'; ch <= 'z'; ch++) { if (ch != crt.charAt(i)) { String expanded = crt.substring(0, i) + ch + crt.substring(i + 1); if (dict.contains(expanded)) { expansion.add(expanded); } } } } return expansion; }
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

51：

public void swapItem(ArrayList
      
        nums, int i, int j) {        Integer tmp = nums.get(i);        nums.set(i, nums.get(j));        nums.set(j, tmp);    }    public void swapList(ArrayList
       
         nums, int i, int j) {        while ( i < j) {            swapItem(nums, i, j);            i ++; j --;        }    }    public ArrayList
        
          previousPermuation(ArrayList
         
           nums) {        int len = nums.size();        if ( len <= 1)            return nums;        int i = len - 1;        while ( i > 0 && nums.get(i) >= nums.get(i-1) )            i --;        swapList(nums, i, len - 1);             if ( i != 0) {            int j = i;            while ( nums.get(j) >= nums.get(i-1) ) j++;            swapItem(nums, j, i-1);        }                return nums;    }
         
        
       
      

 

52：

public void swapItem(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }    public void swapList(int[] nums, int i, int j) {        while (i < j) {            swapItem(nums, i, j);            i ++; j --;        }    }    public int[] nextPermutation(int[] nums) {        int len = nums.length;        if ( len <= 1)            return nums;        int i = len - 1;        while (i > 0 && nums[i] <= nums[i - 1])            i --;        swapList(nums, i, len - 1);        if (i != 0) {            int j = i;            while (nums[j] <= nums[i - 1]) j++;            swapItem(nums, j, i-1);        }        return nums;    }

public void reverse(int[] num, int start, int end) {        for (int i = start, j = end; i < j; i++, j--) {            int temp = num[i];            num[i] = num[j];            num[j] = temp;        }    }        public int[] nextPermutation(int[] num) {        // find the last increase index        int index = -1;        for (int i = num.length - 2; i >= 0; i--) {            if (num[i] < num[i + 1]) {                index = i;                break;            }        }        if (index == -1) {            reverse(num, 0, num.length - 1);            return num;        }                // find the first bigger one        int biggerIndex = index + 1;        for (int i = num.length - 1; i > index; i--) {            if (num[i] > num[index]) {                biggerIndex = i;                break;            }        }                // swap them to make the permutation bigger        int temp = num[index];        num[index] = num[biggerIndex];        num[biggerIndex] = temp;                // reverse the last part        reverse(num, index + 1, num.length - 1);        return num;    }

 

190：

public void reverse(int[] num, int start, int end) {        for (int i = start, j = end; i < j; i++, j--) {            int temp = num[i];            num[i] = num[j];            num[j] = temp;        }    }        public void nextPermutation(int[] num) {        // find the last increase index        int index = -1;        for (int i = num.length - 2; i >= 0; i--) {            if (num[i] < num[i + 1]) {                index = i;                break;            }        }        if (index == -1) {            reverse(num, 0, num.length - 1);            return;        }                // find the first bigger one        int biggerIndex = index + 1;        for (int i = num.length - 1; i > index; i--) {            if (num[i] > num[index]) {                biggerIndex = i;                break;            }        }        // swap them to make the permutation bigger        int temp = num[index];        num[index] = num[biggerIndex];        num[biggerIndex] = temp;                // reverse the last part        reverse(num, index + 1, num.length - 1);    }

 

211：

public boolean stringPermutation(String A, String B) {        // Write your code here        int[] cnt = new int[1000];        for (int i = 0; i < A.length(); ++i)            cnt[(int)A.charAt(i)] += 1;        for (int i = 0; i < B.length(); ++i)            cnt[(int)B.charAt(i)] -= 1;        for (int i = 0; i < 1000; ++i)            if (cnt[i] != 0)                return false;        return true;    }

 

197：

public class Solution {    /**     * @param A an integer array     * @return a long integer     */    long fac(int numerator) {        long now = 1;        for (int i = 1; i <= numerator; i++) {            now *= (long) i;        }        return now;    }    long generateNum(HashMap
      
        hash) {        long denominator = 1;        int sum = 0;        for (int val : hash.values()) {            if(val == 0 )                    continue;            denominator *= fac(val);            sum += val;        }        if(sum==0) {            return sum;        }        return fac(sum) / denominator;    }    public long permutationIndex(int[] A) {        HashMap
       
         hash = new HashMap
        
         ();        for (int i = 0; i < A.length; i++) {            if (hash.containsKey(A[i]))                hash.put(A[i], hash.get(A[i]) + 1);            else {                hash.put(A[i], 1);            }        }        long ans = 0;        for (int i = 0; i < A.length; i++) {            for (int j = i + 1; j < A.length; j++) {                if (A[j] < A[i]) {                    hash.put(A[j], hash.get(A[j]) - 1);                    ans += generateNum(hash);                    hash.put(A[j], hash.get(A[j]) + 1);                }            }            hash.put(A[i], hash.get(A[i])-1);        }        return ans+1;    }}
        
       
      

 

10：

public List
      
        stringPermutation2(String str) {        // Write your code here        List
       
         result = new ArrayList
        
         ();        char[] s = str.toCharArray();        Arrays.sort(s);        result.add(String.valueOf(s));        while ((s = nextPermutation(s)) != null) {            result.add(String.valueOf(s));        }        return result;    }    public char[] nextPermutation(char[] nums) {        int index = -1;        for(int i = nums.length -1; i > 0; i--){            if(nums[i] > nums[i-1]){                index = i-1;                break;            }        }        if(index == -1){            return null;        }        for(int i = nums.length -1; i > index; i--){            if(nums[i] > nums[index]){                char temp = nums[i];                nums[i] = nums[index];                nums[index] = temp;                break;            }        }        reverse(nums,index+1,nums.length-1);        return nums;            }    public void reverse(char[] num, int start, int end) {        for (int i = start, j = end; i < j; i++, j--) {            char temp = num[i];            num[i] = num[j];            num[j] = temp;        }    }
        
       
      

 

198：

long fac(int numerator) {        long now = 1;        for (int i = 1; i <= numerator; i++) {            now *= (long) i;        }        return now;    }       long generateNum(HashMap
      
        hash) {        long denominator = 1;        int sum = 0;        for (int val : hash.values()) {            if(val == 0 )                    continue;                   denominator *= fac(val);            sum += val;         }               if(sum==0) {            return sum;         }               return fac(sum) / denominator;    }       public long permutationIndexII(int[] A) {        HashMap
       
         hash = new HashMap
        
         ();        for (int i = 0; i < A.length; i++) {            if (hash.containsKey(A[i]))                hash.put(A[i], hash.get(A[i]) + 1);            else {                      hash.put(A[i], 1);            }                   }               long ans = 0;        for (int i = 0; i < A.length; i++) {            HashMap
         
           flag = new HashMap
          
           ();             for (int j = i + 1; j < A.length; j++) {                if (A[j] < A[i] && !flag.containsKey(A[j])) {                    flag.put(A[j], 1);                    hash.put(A[j], hash.get(A[j])-1);                    ans += generateNum(hash);                    hash.put(A[j], hash.get(A[j])+1);                }            }            hash.put(A[i], hash.get(A[i])-1);        }        return ans + 1;    }
          
         
        
       
      

public long permutationIndexII(int[] A) {        if (A == null || A.length == 0)            return 0L;        Map
      
        counter = new HashMap
       
        ();        long index = 1, fact = 1, multiFact = 1;        for (int i = A.length - 1; i >= 0; i--) {            if (counter.containsKey(A[i])) {                counter.put(A[i], counter.get(A[i]) + 1);                multiFact *= counter.get(A[i]);            } else {                counter.put(A[i], 1);            }            int rank = 0;            for (int j = i + 1; j < A.length; j++) {                if (A[i] > A[j]) rank++;            }            index += rank * fact / multiFact;            fact *= (A.length - i);        }        return index;    }
       
      

 

107：

private int getMaxLength(Set
      
        dict) {        int maxLength = 0;        for (String word : dict) {            maxLength = Math.max(maxLength, word.length());        }        return maxLength;    }    public boolean wordBreak(String s, Set
       
         dict) {        if (s == null || s.length() == 0) {            return true;        }        int maxLength = getMaxLength(dict);        boolean[] canSegment = new boolean[s.length() + 1];        canSegment[0] = true;        for (int i = 1; i <= s.length(); i++) {            canSegment[i] = false;            for (int lastWordLength = 1;                     lastWordLength <= maxLength && lastWordLength <= i;                     lastWordLength++) {                if (!canSegment[i - lastWordLength]) {                    continue;                }                String word = s.substring(i - lastWordLength, i);                if (dict.contains(word)) {                    canSegment[i] = true;                    break;                }            }        }        return canSegment[s.length()];    }
       
      

 

108：

private boolean[][] CalcPalin(String s, int n) {        boolean[][] isPalin = new boolean[n][n];        int i, j, p;        for (i = 0; i < n; ++i) {            for (j = 0; j < n; ++j) {                isPalin[i][j] = false;            }        }                for (p = 0; p < n; ++p) {            i = j = p;            while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {                isPalin[i][j] = true;                --i;                ++j;            }        }                for (p = 0; p < n-1; ++p) {            i = p;            j = p + 1;            while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {                isPalin[i][j] = true;                --i;                ++j;            }        }        return isPalin;    }    public int minCut(String s) {        int n = s.length();        if (n == 0) {            return 0;        }                int[] f = new int[n+1];        int i, j, p;        boolean[][] isPalin = CalcPalin(s, n);                        f[0] = 0;        for (i=1; i<=n; ++i) {            f[i] = Integer.MAX_VALUE;            for (j = 0; j < i; ++j) {                if (isPalin[j][i-1] && f[j] != Integer.MAX_VALUE && f[j] + 1 < f[i]) {                    f[i] = f[j] + 1;                }            }        }                return f[n] - 1;    }

 

 

 

第六章：链表与数组

目录：

 

 

 

 

103：

public ListNode detectCycle(ListNode head) {        if (head == null || head.next==null) {            return null;        }        ListNode fast, slow;        fast = head.next;        slow = head;        while (fast != slow) {            if(fast==null || fast.next==null)                return null;            fast = fast.next.next;            slow = slow.next;        }                 while (head != slow.next) {            head = head.next;            slow = slow.next;        }        return head;    }

 

620：

 

public int maxSubarray4(int[] nums, int k) {        // Write your code here        int n = nums.length;        if (n < k)            return 0;        int result = 0;        for (int i = 0; i < k; ++i)            result += nums[i];        int[] sum = new int[n + 1];        sum[0] = 0;                int min_prefix = 0;        for (int i = 1; i <= n; ++i) {            sum[i] = sum[i - 1] + nums[i - 1];            if (i >= k && sum[i] - min_prefix > result) {                result = Math.max(result, sum[i] - min_prefix);            }            if (i >= k) {                min_prefix = Math.min(min_prefix, sum[i - k + 1]);            }        }        return result;    }

 

 191：

public class Solution {    /**     * @param nums: an array of integers     * @return: an integer     */    public int maxProduct(int[] nums) {        int[] max = new int[nums.length];        int[] min = new int[nums.length];                min[0] = max[0] = nums[0];        int result = nums[0];        for (int i = 1; i < nums.length; i++) {            min[i] = max[i] = nums[i];            if (nums[i] > 0) {                max[i] = Math.max(max[i], max[i - 1] * nums[i]);                min[i] = Math.min(min[i], min[i - 1] * nums[i]);            } else if (nums[i] < 0) {                max[i] = Math.max(max[i], min[i - 1] * nums[i]);                min[i] = Math.min(min[i], max[i - 1] * nums[i]);            }                        result = Math.max(result, max[i]);        }                return result;    }}

//LintCode version2: O(1) Space Complexitypublic class Solution {    /**     * @param nums: an array of integers     * @return: an integer     */    public int maxProduct(int[] nums) {        // write your code here        if (nums == null || nums.length == 0) {            return 0;        }        int minPre = nums[0], maxPre = nums[0];        int max = nums[0], min = nums[0];        int res = nums[0];        for (int i = 1; i < nums.length; i ++) {            max = Math.max(nums[i], Math.max(maxPre * nums[i], minPre * nums[i]));            min = Math.min(nums[i], Math.min(maxPre * nums[i], minPre * nums[i]));            res = Math.max(res, max);            maxPre = max;            minPre = min;        }        return res;    }}

 

45：

public int maxDiffSubArrays(int[] nums) {        // write your code here        int size = nums.length;        int[] left_max = new int[size];        int[] left_min = new int[size];        int[] right_max = new int[size];        int[] right_min = new int[size];        int[] copy = new int[size];        /*Get negative copy*/        for(int i = 0; i < size; i++){            copy[i] = -1 * nums[i];        }        int max = Integer.MIN_VALUE;        int sum = 0;        int minSum = 0;        /*Forward: get max subarray*/        for(int i = 0; i < size; i++){            sum += nums[i];            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            left_max[i] = max;        }        /*Backward: get max subarray*/        max = Integer.MIN_VALUE;        sum = 0;        minSum = 0;        for(int i = size - 1; i >= 0; i--){            sum += nums[i];            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            right_max[i] = max;        }        /*Forward: get min subarray*/        max = Integer.MIN_VALUE;        sum = 0;        minSum = 0;        for(int i = 0; i < size; i++){            sum += copy[i];            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            left_min[i] = -1 * max;        }        /*Backward: get min subarray*/        max = Integer.MIN_VALUE;        sum = 0;        minSum = 0;        for(int i = size - 1; i >= 0; i--){            sum += copy[i];            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            right_min[i] = -1 * max;        }        int diff = 0;        for(int i = 0; i < size - 1; i++){            diff = Math.max(diff, Math.abs(left_max[i] - right_min[i + 1]));            diff = Math.max(diff, Math.abs(left_min[i] - right_max[i + 1]));        }        return diff;    }

 

42：

public int maxTwoSubArrays(ArrayList
      
        nums) {        // write your code        int size = nums.size();        int[] left = new int[size];        int[] right = new int[size];        int sum = 0;        int minSum = 0;        int max = Integer.MIN_VALUE;        for(int i = 0; i < size; i++){            sum += nums.get(i);            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            left[i] = max;        }        sum = 0;        minSum = 0;        max = Integer.MIN_VALUE;        for(int i = size - 1; i >= 0; i--){            sum += nums.get(i);            max = Math.max(max, sum - minSum);            minSum = Math.min(sum, minSum);            right[i] = max;        }        max = Integer.MIN_VALUE;        for(int i = 0; i < size - 1; i++){            max = Math.max(max, left[i] + right[i + 1]);        }        return max;    }
      

 

43：

// 方法一 划分类DPpublic class Solution {    /**     * @param nums: A list of integers     * @param k: An integer denote to find k non-overlapping subarrays     * @return: An integer denote the sum of max k non-overlapping subarrays     */    public int maxSubArray(int[] nums, int k) {        if (nums.length < k) {            return 0;        }        int len = nums.length;                       int[][] globalMax = new int[k + 1][len + 1];        int[][] localMax = new int[k + 1][len + 1];                for (int i = 1; i <= k; i++) {            localMax[i][i-1] = Integer.MIN_VALUE;            //小于 i 的数组不能够partition            for (int j = i; j <= len; j++) {                localMax[i][j] = Math.max(localMax[i][j-1], globalMax[i - 1][j-1]) + nums[j-1];                if (j == i)                    globalMax[i][j] = localMax[i][j];                else                    globalMax[i][j] = Math.max(globalMax[i][j-1], localMax[i][j]);            }        }        return globalMax[k][len];    }    }

//方法二public class Solution {    /**     * @param nums: A list of integers     * @param k: An integer denote to find k non-overlapping subarrays     * @return: An integer denote the sum of max k non-overlapping subarrays     */     public static int maxSubArray(ArrayList
      
        nums, int k) {        // write your code        int len = nums.size();        int[][] f = new int[k+1][len];        for (int i = 1; i < k+1; i++) {            int sum = 0;            for (int j = 0; j < i; j++) {                sum += nums.get(j);            }            f[i][i-1] = sum;        }        for (int i = 1; i < len; i++) {            f[1][i] = Math.max(f[1][i-1]+nums.get(i), nums.get(i));        }                for (int i = 2; i < k+1; i++) {            for (int n = i;  n< len; n++) {                int curMax = f[i][n-1] + nums.get(n);                for (int j = i-2; j < n; j++) {                    if ((f[i-1][j] + nums.get(n)) > curMax) {                        curMax = f[i-1][j] + nums.get(n);                    }                }                f[i][n] = curMax;            }        }                int res = Integer.MIN_VALUE;        for (int i = k-1; i < len; i++){            if (f[k][i] > res) {                res = f[k][i];            }        }        return res;    }}
      

 

621：

public int maxSubarray5(int[] nums, int k1, int k2) {        // Write your code here        int n = nums.length;        if (n < k1)            return 0;        int result = Integer.MIN_VALUE;        int[] sum = new int[n + 1];        sum[0] = 0;        LinkedList
      
        queue = new LinkedList
       
        ();        for (int i = 1; i <= n; ++i) {            sum[i] = sum[i - 1] + nums[i - 1];            if (!queue.isEmpty() && queue.getFirst() < i - k2) {                queue.removeFirst();            }            if (i >= k1) {                while (!queue.isEmpty() && sum[queue.getLast()] > sum[i - k1]) {                    queue.removeLast();                }                queue.add(i - k1);            }            // [i - k2, i - k1]            if (!queue.isEmpty() && sum[i] - sum[queue.getFirst()] > result) {                result = Math.max(result, sum[i] - sum[queue.getFirst()]);            }        }        return result;    }
       
      

 

 

 

第七章：两根指针

目录：

 

 

 

58：

public List
      
       
        > fourSum(int[] num, int target) {        List
        
         
          > rst = new ArrayList
          
           
            >(); Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { if (i != 0 && num[i] == num[i - 1]) { continue; } for (int j = i + 1; j < num.length - 2; j++) { if (j != i + 1 && num[j] == num[j - 1]) continue; int left = j + 1; int right = num.length - 1; while (left < right) { int sum = num[i] + num[j] + num[left] + num[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { ArrayList
            
              tmp = new ArrayList
             
              (); tmp.add(num[i]); tmp.add(num[j]); tmp.add(num[left]); tmp.add(num[right]); rst.add(tmp); left++; right--; while (left < right && num[left] == num[left - 1]) { left++; } while (left < right && num[right] == num[right + 1]) { right--; } } } } } return rst; }
             
            
           
          
         
        
       
      

 

59：

public int threeSumClosest(int[] numbers, int target) {        if (numbers == null || numbers.length < 3) {            return -1;        }                Arrays.sort(numbers);        int bestSum = numbers[0] + numbers[1] + numbers[2];        for (int i = 0; i < numbers.length; i++) {            int start = i + 1, end = numbers.length - 1;            while (start < end) {                int sum = numbers[i] + numbers[start] + numbers[end];                if (Math.abs(target - sum) < Math.abs(target - bestSum)) {                    bestSum = sum;                }                if (sum < target) {                    start++;                } else {                    end--;                }            }        }                return bestSum;    }

 

382：

public int triangleCount(int S[]) {        // write your code here        int left = 0, right = S.length - 1;        int ans = 0;        Arrays.sort(S);        for(int i = 0; i < S.length; i++) {            left = 0;            right = i - 1;            while(left < right) {                if(S[left] + S[right] > S[i]) {                    ans = ans + (right - left);                    right --;                } else {                    left ++;                }            }        }        return ans;    }

 

461：

public int kthSmallest(int k, int[] nums) {        // write your code here        return quickSelect(nums, 0, nums.length - 1, k - 1);    }    public int quickSelect(int[] A, int start, int end , int k) {        if (start == end)            return A[start];                int left = start, right = end;        int pivot = A[(start + end) / 2];        while (left <= right) {            while (left <= right && A[left] < pivot) {                left++;            }            while (left <= right && A[right] > pivot) {                right--;            }            if (left <= right) {                int temp = A[left];                A[left] = A[right];                A[right] = temp;                                left++;                right--;            }        }        if (right >= k && start <= right)            return quickSelect(A, start, right, k);        else if (left <= k && left <= end)            return quickSelect(A, left, end, k);        else            return A[k];    }

 

443：

public int twoSum2(int[] nums, int target) {        if (nums == null || nums.length < 2) {            return 0;        }                Arrays.sort(nums);                int left = 0, right = nums.length - 1;        int count = 0;        while (left < right) {            if (nums[left] + nums[right] <= target) {                left++;            } else {                count += right - left;                right--;            }        }                return count;    }

 

610：

class Pair {    public int idx, num;    public Pair(int i, int n) {        this.idx = i;        this.num = n;    }}public class Solution {    /*     * @param nums an array of Integer     * @param target an integer     * @return [index1 + 1, index2 + 1] (index1 < index2)     */    public int[] twoSum7(int[] nums, int target) {        // write your code here        int[] indexs = new int[2];        if (nums == null || nums.length < 2)            return indexs;        if (target < 0)            target = -target;        int n = nums.length;        Pair[] pairs = new Pair[n];        for (int i = 0; i < n; ++i)            pairs[i] = new Pair(i, nums[i]);        Arrays.sort(pairs, new Comparator
      
       (){            public int compare(Pair p1, Pair p2){                return p1.num - p2.num;            }         });        int j = 0;        for (int i = 0; i < n; ++i) {            if (i == j)                j ++;            while (j < n && pairs[j].num - pairs[i].num < target)                j ++;            if (j < n && pairs[j].num - pairs[i].num == target) {                indexs[0] = pairs[i].idx + 1;                indexs[1] = pairs[j].idx + 1;                if (indexs[0] > indexs[1]) {                    int temp = indexs[0];                    indexs[0] = indexs[1];                    indexs[1] = temp;                }                return indexs;            }        }        return indexs;    }}
      

 

625：

public void partition2(int[] nums, int low, int high) {        // Write your code here        if (nums == null || nums.length <= 1) {            return;        }                int pl = 0, pr = nums.length - 1;        int i = 0;        while (i <= pr) {            if (nums[i] < low) {                swap(nums, pl, i);                pl++;                i++;            } else if (nums[i] > high) {                swap(nums, pr, i);                pr--;            } else {                i ++;            }        }    }        private void swap(int[] nums, int i, int j) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }

 

 

第八章：哈希表与堆

目录：

 

 

 

124：

public int longestConsecutive(int[] nums) {        HashSet
      
        set = new HashSet<>();        for (int i = 0; i < nums.length; i++) {            set.add(nums[i]);        }                int longest = 0;        for (int i = 0; i < nums.length; i++) {            int down = nums[i] - 1;            while (set.contains(down)) {                set.remove(down);                down--;            }                        int up = nums[i] + 1;            while (set.contains(up)) {                set.remove(up);                up++;            }                        longest = Math.max(longest, up - down - 1);        }                return longest;    }
      

 

130：

// Version Linpzpublic class Solution {    /**     * @param A: Given an integer array     * @return: void     */    private void siftdown(int[] A, int k) {        while (k * 2 + 1 < A.length) {            int son = k * 2 + 1;            if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])                son = k * 2 + 2;            if (A[son] >= A[k])                break;                        int temp = A[son];            A[son] = A[k];            A[k] = temp;            k = son;        }    }        public void heapify(int[] A) {        for (int i = (A.length - 1) / 2; i >= 0; i--) {            siftdown(A, i);        }    }}

// Version 1: this cost O(n)public class Solution {    /**     * @param A: Given an integer array     * @return: void     */    private void siftdown(int[] A, int k) {        while (k < A.length) {            int smallest = k;            if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {                smallest = k * 2 + 1;            }            if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {                smallest = k * 2 + 2;            }            if (smallest == k) {                break;            }            int temp = A[smallest];            A[smallest] = A[k];            A[k] = temp;                        k = smallest;        }    }        public void heapify(int[] A) {        for (int i = A.length / 2; i >= 0; i--) {            siftdown(A, i);        } // for    }}

// Version 2: This cost O(nlogn)public class Solution {    /**     * @param A: Given an integer array     * @return: void     */    private void siftup(int[] A, int k) {        while (k != 0) {            int father = (k - 1) / 2;            if (A[k] > A[father]) {                break;            }            int temp = A[k];            A[k] = A[father];            A[father] = temp;                        k = father;        }    }        public void heapify(int[] A) {        for (int i = 0; i < A.length; i++) {            siftup(A, i);        }    }}

 

471：

class Pair {    String key;    int value;        Pair(String key, int value) {        this.key = key;        this.value = value;    }}public class Solution {    /**     * @param words an array of string     * @param k an integer     * @return an array of string     */         private Comparator
      
        pairComparator = new Comparator
       
        () {        public int compare(Pair left, Pair right) {            if (left.value != right.value) {                return left.value - right.value;            }            return right.key.compareTo(left.key);        }    };        public String[] topKFrequentWords(String[] words, int k) {        if (k == 0) {            return new String[0];        }                HashMap
        
          counter = new HashMap<>();        for (String word : words) {            if (counter.containsKey(word)) {                counter.put(word, counter.get(word) + 1);            } else {                counter.put(word, 1);            }        }                PriorityQueue
         
           Q = new PriorityQueue
          
           (k, pairComparator);        for (String word : counter.keySet()) {            Pair peak = Q.peek();            Pair newPair = new Pair(word, counter.get(word));            if (Q.size() < k) {                Q.add(newPair);            } else if (pairComparator.compare(newPair, peak) > 0) {                Q.poll();                Q.add(newPair);            }        }                String[] result = new String[k];        int index = 0;        while (!Q.isEmpty()) {            result[index++] = Q.poll().key;        }                // reverse        for (int i = 0; i < index / 2; i++) {            String temp = result[i];            result[i] = result[index - i - 1];            result[index - i - 1] = temp;        }                return result;     }}
          
         
        
       
      

 

486：

class Element {    public int row, col, val;    Element(int row, int col, int val) {        this.row = row;        this.col = col;        this.val = val;    }}public class Solution {    private Comparator
      
        ElementComparator = new Comparator
       
        () {        public int compare(Element left, Element right) {            return left.val - right.val;        }    };        /**     * @param arrays k sorted integer arrays     * @return a sorted array     */    public int[] mergekSortedArrays(int[][] arrays) {        if (arrays == null) {            return new int[0];        }                int total_size = 0;        Queue
        
          Q = new PriorityQueue
         
          (            arrays.length, ElementComparator);                    for (int i = 0; i < arrays.length; i++) {            if (arrays[i].length > 0) {                Element elem = new Element(i, 0, arrays[i][0]);                Q.add(elem);                total_size += arrays[i].length;            }        }                int[] result = new int[total_size];        int index = 0;        while (!Q.isEmpty()) {            Element elem = Q.poll();            result[index++] = elem.val;            if (elem.col + 1 < arrays[elem.row].length) {                elem.col += 1;                elem.val = arrays[elem.row][elem.col];                Q.add(elem);            }        }                return result;    }}
         
        
       
      

 

545：

public class Solution {    /*    * @param k: An integer    */    private int maxSize;    private Queue
      
        minheap;    public Solution(int k) {        minheap = new PriorityQueue<>();        maxSize = k;    }    public void add(int num) {        if (minheap.size() < maxSize) {            minheap.offer(num);            return;        }                if (num > minheap.peek()) {            minheap.poll();            minheap.offer(num);        }    }    public List
       
         topk() {        Iterator it = minheap.iterator();        List
        
          result = new ArrayList
         
          ();        while (it.hasNext()) {            result.add((Integer) it.next());        }        Collections.sort(result, Collections.reverseOrder());        return result;    }}
         
        
       
      

 

601：

public class Vector2D implements Iterator
      
        {    private Iterator
       
        
         > i;    private Iterator
         
           j;    public Vector2D(List
          
           
            > vec2d) { // Initialize your data structure here i = vec2d.iterator(); j = null; } @Override public Integer next() { // Write your code here hasNext(); return j.next(); } @Override public boolean hasNext() { // Write your code here while ((j == null || !j.hasNext()) && i.hasNext()) j = i.next().iterator(); return j != null && j.hasNext(); } @Override public void remove() {}}/** * Your Vector2D object will be instantiated and called as such: * Vector2D i = new Vector2D(vec2d); * while (i.hasNext()) v[f()] = i.next(); */
           
          
         
        
       
      

 

 551：

// 递归/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * *     // @return true if this NestedInteger holds a single integer, *     // rather than a nested list. *     public boolean isInteger(); * *     // @return the single integer that this NestedInteger holds, *     // if it holds a single integer *     // Return null if this NestedInteger holds a nested list *     public Integer getInteger(); * *     // @return the nested list that this NestedInteger holds, *     // if it holds a nested list *     // Return null if this NestedInteger holds a single integer *     public List
      
        getList(); * } */public class Solution {        public int depthSum(List
       
         nestedList) {        return helper(nestedList, 1);    }     public int helper(List
        
          nestedList, int depth){        if (nestedList == null || nestedList.size() == 0)            return 0;        int sum = 0;        for(NestedInteger ele : nestedList) {            if (ele.isInteger()) {                sum += ele.getInteger() * depth;            } else {                sum += helper(ele.getList(), depth + 1);            }        }         return sum;    }}
        
       
      

// 非递归/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * *     // @return true if this NestedInteger holds a single integer, *     // rather than a nested list. *     public boolean isInteger(); * *     // @return the single integer that this NestedInteger holds, *     // if it holds a single integer *     // Return null if this NestedInteger holds a nested list *     public Integer getInteger(); * *     // @return the nested list that this NestedInteger holds, *     // if it holds a nested list *     // Return null if this NestedInteger holds a single integer *     public List
      
        getList(); * } */public class Solution {    public int depthSum(List
       
         nestedList) {        // Write your code here        if (nestedList == null || nestedList.size() == 0) {            return 0;        }        int sum = 0;        Queue
        
          queue = new LinkedList
         
          ();        for (NestedInteger nestedInt : nestedList) {            queue.offer(nestedInt);        }        int depth = 0;        while (!queue.isEmpty()) {            int size = queue.size();            depth++;            for (int i = 0; i < size; i++) {                NestedInteger nestedInt = queue.poll();                if (nestedInt.isInteger()) {                    sum += nestedInt.getInteger() * depth;                } else {                    for (NestedInteger innerInt : nestedInt.getList()) {                        queue.offer(innerInt);                    }                }            }        }        return sum;    }}
         
        
       
      

 

494：

public class Stack {    private Queue
      
        queue1;    private Queue
       
         queue2;        public Stack() {        queue1 = new LinkedList
        
         ();        queue2 = new LinkedList
         
          ();    }        private void moveItems() {        while (queue1.size() != 1) {            queue2.offer(queue1.poll());        }    }        private void swapQueues() {        Queue
          
            temp = queue1;        queue1 = queue2;        queue2 = temp;    }        /**     * push a new item into the stack     */    public void push(int value) {        queue1.offer(value);    }        /**     * return the top of the stack     */    public int top() {        moveItems();        int item = queue1.poll();        swapQueues();        queue1.offer(item);        return item;    }        /**     * pop the top of the stack and return it     */    public void pop() {        moveItems();        queue1.poll();        swapQueues();    }        /**     * check the stack is empty or not.     */    public boolean isEmpty() {        return queue1.isEmpty();    }}
          
         
        
       
      

 

575：

// version 1: Stackpublic class Solution {    /**     * @param s  an expression includes numbers, letters and brackets     * @return a string     */    public String expressionExpand(String s) {        Stack

 

540：

public class ZigzagIterator {        public Iterator
      
        it1;    public Iterator
       
         it2;    public int turns;    /**     * @param v1 v2 two 1d vectors     */    public ZigzagIterator(List
        
          v1, List
         
           v2) {        // initialize your data structure here.        this.it1 = v1.iterator();        this.it2 = v2.iterator();        turns = 0;    }    public int next() {        // Write your code here        turns++;        if((turns % 2 == 1 && it1.hasNext()) || (!it2.hasNext())) {            return it1.next();        } else if((turns % 2 == 0 && it2.hasNext()) || (!it1.hasNext())) {            return it2.next();        }        return -1;      }    public boolean hasNext() {        // Write your code here        return it1.hasNext() || it2.hasNext();            }}/** * Your ZigzagIterator object will be instantiated and called as such: * ZigzagIterator solution = new ZigzagIterator(v1, v2); * while (solution.hasNext()) result.add(solution.next()); * Output result */
         
        
       
      

 

541：

public class ZigzagIterator2 {        public List
      
       
        > its;    public int turns;    /**     * @param vecs a list of 1d vectors     */    public ZigzagIterator2(List
        
         
          > vecs) {        // initialize your data structure here.        this.its = new ArrayList
          
           
            >(); for (List
            
              vec : vecs) { if (vec.size() > 0) its.add(vec.iterator()); } turns = 0; } public int next() { // Write your code here int elem = its.get(turns).next(); if (its.get(turns).hasNext()) turns = (turns + 1) % its.size(); else { its.remove(turns); if (its.size() > 0) turns %= its.size(); } return elem; } public boolean hasNext() { // Write your code here return its.size() > 0; }}/** * Your ZigzagIterator2 object will be instantiated and called as such: * ZigzagIterator2 solution = new ZigzagIterator2(vecs); * while (solution.hasNext()) result.add(solution.next()); * Output result */
            
           
          
         
        
       
      

 

528：

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * *     // @return true if this NestedInteger holds a single integer, *     // rather than a nested list. *     public boolean isInteger(); * *     // @return the single integer that this NestedInteger holds, *     // if it holds a single integer *     // Return null if this NestedInteger holds a nested list *     public Integer getInteger(); * *     // @return the nested list that this NestedInteger holds, *     // if it holds a nested list *     // Return null if this NestedInteger holds a single integer *     public List
      
        getList(); * } */import java.util.Iterator;public class NestedIterator implements Iterator
       
         {    private Stack
        
          stack;        private void pushListToStack(List
         
           nestedList) {        Stack
          
            temp = new Stack<>();        for (NestedInteger nested : nestedList) {            temp.push(nested);        }                while (!temp.isEmpty()) {            stack.push(temp.pop());        }    }        public NestedIterator(List
           
             nestedList) { stack = new Stack<>(); pushListToStack(nestedList); } // @return {int} the next element in the iteration @Override public Integer next() { if (!hasNext()) { return null; } return stack.pop().getInteger(); } // @return {boolean} true if the iteration has more element or false @Override public boolean hasNext() { while (!stack.isEmpty() && !stack.peek().isInteger()) { pushListToStack(stack.pop().getList()); } return !stack.isEmpty(); } @Override public void remove() {}}
           
          
         
        
       
      

 

24：

public class LFUCache {    private final Map
      
        cache;    private final LinkedHashSet[] frequencyList;    private int lowestFrequency;    private int maxFrequency;    private final int maxCacheSize;    // @param capacity, an integer    public LFUCache(int capacity) {        // Write your code here        this.cache = new HashMap
       
        (capacity);        this.frequencyList = new LinkedHashSet[capacity * 2];        this.lowestFrequency = 0;        this.maxFrequency = capacity * 2 - 1;        this.maxCacheSize = capacity;        initFrequencyList();    }    // @param key, an integer    // @param value, an integer    // @return nothing    public void set(int key, int value) {        // Write your code here        CacheNode currentNode = cache.get(key);        if (currentNode == null) {            if (cache.size() == maxCacheSize) {                doEviction();            }            LinkedHashSet
        
          nodes = frequencyList[0];            currentNode = new CacheNode(key, value, 0);            nodes.add(currentNode);            cache.put(key, currentNode);            lowestFrequency = 0;        } else {            currentNode.v = value;        }        addFrequency(currentNode);    }    public int get(int key) {        // Write your code here        CacheNode currentNode = cache.get(key);        if (currentNode != null) {            addFrequency(currentNode);            return currentNode.v;        } else {            return -1;        }    }    public void addFrequency(CacheNode currentNode) {        int currentFrequency = currentNode.frequency;        if (currentFrequency < maxFrequency) {            int nextFrequency = currentFrequency + 1;            LinkedHashSet
         
           currentNodes = frequencyList[currentFrequency];            LinkedHashSet
          
            newNodes = frequencyList[nextFrequency];            moveToNextFrequency(currentNode, nextFrequency, currentNodes, newNodes);            cache.put(currentNode.k, currentNode);            if (lowestFrequency == currentFrequency && currentNodes.isEmpty()) {                lowestFrequency = nextFrequency;            }        } else {            // Hybrid with LRU: put most recently accessed ahead of others:            LinkedHashSet
           
             nodes = frequencyList[currentFrequency]; nodes.remove(currentNode); nodes.add(currentNode); } } public int remove(int key) { CacheNode currentNode = cache.remove(key); if (currentNode != null) { LinkedHashSet
            
              nodes = frequencyList[currentNode.frequency]; nodes.remove(currentNode); if (lowestFrequency == currentNode.frequency) { findNextLowestFrequency(); } return currentNode.v; } else { return -1; } } public int frequencyOf(int key) { CacheNode node = cache.get(key); if (node != null) { return node.frequency + 1; } else { return 0; } } public void clear() { for (int i = 0; i <= maxFrequency; i++) { frequencyList[i].clear(); } cache.clear(); lowestFrequency = 0; } public int size() { return cache.size(); } public boolean isEmpty() { return this.cache.isEmpty(); } public boolean containsKey(int key) { return this.cache.containsKey(key); } private void initFrequencyList() { for (int i = 0; i <= maxFrequency; i++) { frequencyList[i] = new LinkedHashSet
             
              (); } } private void doEviction() { int currentlyDeleted = 0; double target = 1; // just one while (currentlyDeleted < target) { LinkedHashSet
              
                nodes = frequencyList[lowestFrequency]; if (nodes.isEmpty()) { break; } else { Iterator
               
                 it = nodes.iterator(); while (it.hasNext() && currentlyDeleted++ < target) { CacheNode node = it.next(); it.remove(); cache.remove(node.k); } if (!it.hasNext()) { findNextLowestFrequency(); } } } } private void moveToNextFrequency(CacheNode currentNode, int nextFrequency, LinkedHashSet
                
                  currentNodes, LinkedHashSet
                 
                   newNodes) { currentNodes.remove(currentNode); newNodes.add(currentNode); currentNode.frequency = nextFrequency; } private void findNextLowestFrequency() { while (lowestFrequency <= maxFrequency && frequencyList[lowestFrequency].isEmpty()) { lowestFrequency++; } if (lowestFrequency > maxFrequency) { lowestFrequency = 0; } } private class CacheNode { public final int k; public int v; public int frequency; public CacheNode(int k, int v, int frequency) { this.k = k; this.v = v; this.frequency = frequency; } }}