llancelot / leetcode Goto Github PK

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// root->left>right, preorder = [3,9,20,15,7]
// left->root->right, inorder = [9,3,15,20,7]
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // HashMap to store indicies(9,0),(3,1),(15,2)...
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i], i);
        
        return build(preorder, inorder, 0, 0, inorder.length-1, map);
    }
    
    private TreeNode build(int[] preorder, int[] inorder,
                           int preBegin, int inBegin, int inEnd, HashMap<Integer, Integer> map){
        // return case
        if (preBegin >= preorder.length || inBegin > inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preBegin]);
        // root_index: get root num index from inorder(map)
        int root_index = map.get(preorder[preBegin]);
        // build the tree
        root.left = build(preorder, inorder, preBegin+1, inBegin, root_index-1, map);
        root.right = build(preorder, inorder, preBegin + root_index-inBegin+1, root_index+1, inEnd, map);
        
        return root;
      }
}

class Solution {
    public String reorganizeString(String S) {
        int[] hash = new int[26]; // hash.length = 26
        for(int i = 0; i < S.length(); i++) {
            hash[S.charAt(i) - 'a']++;
        }
        int max = 0, letter = 0;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > max) {
                max = hash[i];
                letter = i;
            }
        }
        if (max > (S.length() + 1) / 2) {
            return "";
        }
        char[] res = new char[S.length()];
        int idx = 0;

        // 先把最高频字母安排在0,2,4,6....等位置上
        while (hash[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            hash[letter]--; 
        }

        // 对剩下的字母，分别对其安排在1,3,5,7的位置上
        for (int i = 0; i < hash.length; i++) {
            while (hash[i] > 0) {
                if (idx >= res.length) { // idx重置
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                idx += 2;
                hash[i]--;
            }
        }
        return String.valueOf(res);
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] q = new int[n + 1];
        int len = 0;
        for (int i = 0; i < n; i++) {
            int left = 0, right = len;
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (q[mid] >= nums[i]) right = mid - 1;
                else left = mid;
            }
            len = Math.max(len, right + 1);
            q[right + 1] = nums[i];
        }
        return len;
    }

class Solution {
    public int lengthOfLIS(int[] arr) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int idx = 0; idx < i; idx++) {
                if (arr[idx] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[idx] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int lenA = A.length, lenB = B.length;
        if (lenA > lenB) { return findMedianSortedArrays(B,A); }
        if (lenA == 0)
            return ((double)B[(lenB - 1)/2] + (double)B[lenB/2])/2;
        int len = lenA + lenB;
        int A_startK = 0, A_endK = lenA;
        int cutA, cutB;
        while (A_startK <= A_endK) {
            cutA = (A_endK + A_startK) / 2;
            cutB = (len + 1)/2 - cutA;
            double L1 = (cutA == 0) ? Integer.MIN_VALUE : A[cutA-1];
            double L2 = (cutB == 0) ? Integer.MIN_VALUE : B[cutB-1];
            double R1 = (cutA == lenA) ? Integer.MAX_VALUE : A[cutA];
            double R2 = (cutB == lenB) ? Integer.MAX_VALUE : B[cutB];
            if (L1 > R2) {
                A_endK = cutA - 1;
            }
            else if (L2 > R1) {
                A_startK = cutA + 1;
            }
            else {
                if (len % 2 == 0) {
                    return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
                } 
                else {
                    return Math.max(L1, L2);
                }
            }
        }
        return -1;
    }
}

class Solution {    
    public boolean canFinish(int N, int[][] preqs) {        
        ArrayList[] G = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            G[i] = new ArrayList();       
        }
        
        for (int i = 0; i < preqs.length; i++) {
            G[preqs[i][1]].add(preqs[i][0]);    // G[1]=[0, 2, ...]把1的先修课加到集合里
        }
        
        boolean[] visited = new boolean[N];
        
        for (int course_idx = 0; course_idx < N; course_idx++) {
            if (!dfs(G, visited, course_idx)) {
                return false;
            }
        }
    
        return true;
    }
    
    private boolean dfs(ArrayList[] G, boolean[] visited, int course) {
        if (visited[course] == true)
            return false;
        
        visited[course] = true;
        
        for (int i = 0; i < G[course].size(); i++) {
            if (!dfs(G, visited, (int)G[course].get(i)))
                return false;
        }
        
        visited[course] = false;
        return true;
    }
}

class FenwickTree {    
    private int[] sums;    
    
    public FenwickTree(int n) {
      sums = new int[n + 1];
    }
 
    public void update(int i, int delta) {    
      while (i < sums.length) {
          sums[i] += delta;
          i += lowbit(i); //             i += i & -i;
      }
    }
 
    public int query(int i) {       
      int sum = 0;
      while (i > 0) {
          sum += sums[i];
          i -= lowbit(i); //             i += i & -i;
      }
      return sum;
    }    
}

class FenwickTree {    
    int[] sums;
    
    public FenwickTree(int n) {
        // constructor
        sums = new int[n + 1];
    }
    
    public void update(int i, int delta) {
        while (i < sums.length) {
            sums[i] += delta;
            i += i & -i; // 等号右边取lowbit(i)，最低位二进制数
        }
    }
    
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= i & -i;
        }
        return sum;
    }
}

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<>(); // map<num, rank>
        int rank = 0;
        for (int i = 0; i < sorted.length; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1])
                ranks.put(sorted[i], ++rank);
        }
        
        FenwickTree tree = new FenwickTree(ranks.size());
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = nums.length - 1; i >= 0; --i ) { // 从后往前，保证先记录后面数字的rank[i]
            int prefix_sum = tree.query(ranks.get(nums[i]) - 1);
            ans.add(prefix_sum);
            tree.update(ranks.get(nums[i]), 1);
        }
        
        Collections.reverse(ans); // 因为是从后往前访问，最后记得反转ans
        return ans;
    }
}

class Solution {
    public int minSwap(int[] A, int[] B) {
        int n = A.length;
        int[] keep = new int[n];
        int[] swap = new int[n];
        Arrays.fill(keep, Integer.MAX_VALUE);
        Arrays.fill(swap, Integer.MAX_VALUE);
        keep[0] = 0;
        swap[0] = 1;
        for (int i = 1; i < n; i++) {
            if (A[i] > A[i-1] && B[i] > B[i-1]) {
                // Good case, no swapping needed.
                keep[i] = keep[i-1];

                // Swapped A[i-1] / B[i-1], swap A[i], B[i] as well
                swap[i] = swap[i-1] + 1;
            }
            
            if (A[i] > B[i-1] && B[i] > A[i-1]) {
                // A[i-1] / B[i-1] weren't swapped.
                keep[i] = Math.min(keep[i], swap[i-1]);
                
                // Swapped A[i-1] / B[i-1], no swap needed for A[i] / B[i]
                swap[i] = Math.min(swap[i], keep[i-1] + 1);
            }
        }
        
        return Math.min(keep[n-1], swap[n-1]);
    }
}

// Two Pointer
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)    return 0;
        int n = s.length();
        int left = 0, right = 0;
        int max = 0;
        boolean[] used = new boolean[128];
        
        while (right < n) {
            if (used[s.charAt(right)] == false) {
                used[s.charAt(right)] = true;
                right++;
            }
            else {
                max = Math.max(max, right-left);
                while (left < right && s.charAt(left)!= s.charAt(right)) {
                    used[s.charAt(left)] = false;
                    left++;
                }
                // find same char
                left++;
                right++;
            }
        }
        // lastly, update max
        max = Math.max(max, right - left);
        return max;
    }
}