317. Shortest Distance from All Buildings

317. Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

--------------------------------------
难道在有障碍，所以最后选择了brute force, 从每一个building出发做bfs，把所有点的结果加起来找一个最小值。O(k * m * n)，k为building的个数，m、n为长宽
隐藏的一个附加条件是，从最后的点必须能走到所有的building，所有额外用了一个参数来记录当前处理过的building的个数，每一次bfs都只尝试之前已经被走过的点。

class Solution {
    public int shortestDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] rt = new int[m][n];
        
        int building = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    building--;
                    bfs(i, j, rt, grid, building);
                }
            }
        }

        return findTheShortest(rt, grid, building - 1);
    }
    
    private int findTheShortest(int[][] rt, int[][] grid, int building) {
        int shortest = Integer.MAX_VALUE;
        boolean found = false;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == building) {
                    shortest = Math.min(rt[i][j], shortest);
                    found = true;
                }
            }
        }
        
        return found ? shortest : -1;
    }
    
    private void bfs(int row, int col, int[][] rt, int[][] grid, int building) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<Tuple> que = new LinkedList<>();
        que.add(new Tuple(row, col, 0));
        grid[row][col] = building;
        
        while (!que.isEmpty()) {
            Tuple top = que.poll();

            if (isNotValid(top, m, n, grid, visited, building)) {
                continue;
            }
            
            rt[top.row][top.col] += top.dis;
            visited[top.row][top.col] = true;
            grid[top.row][top.col] = building - 1;
            que.add(new Tuple(top.row + 1, top.col, top.dis + 1));
            que.add(new Tuple(top.row, top.col + 1, top.dis + 1));
            que.add(new Tuple(top.row - 1, top.col, top.dis + 1));
            que.add(new Tuple(top.row, top.col - 1, top.dis + 1));
        }
        
        grid[row][col] = 1;
    }
    
    private boolean isNotValid(Tuple t, int m, int n, int[][] grid, boolean[][] visited, int building) {
        int i = t.row, j = t.col;

        return i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] != building;
    }
}

class Tuple{
    public int row;
    public int col;
    public int dis;
    public Tuple(int row, int col, int dis) {
        this.row = row;
        this.col = col;
        this.dis = dis;
    }
}

349, 350 Intersection of Two Arrays, Intersection of Two Arrays II

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.
• The result can be in any order.

------------------------

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = getSet(nums1);   
        Set<Integer> rt = new HashSet<>();
        
        for (int num : nums2) {
            if (set.contains(num)) {
                rt.add(num);
            }
        }
        
        int[] rtArr = new int[rt.size()];
        int i = 0;
        for (int num : rt) {
            rtArr[i] = num;
            i++;
        }
        
        return rtArr;
    }
    
    private Set<Integer> getSet(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            set.add(num);
        }
        
        return set;
    }
}

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

--------------------------------
Same idea, but with Map

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = getMap(nums1);
        
        List<Integer> rt = new ArrayList<>();
        
        for (int num : nums2) {
            if (map.containsKey(num) && map.get(num) > 0) {
                rt.add(num);
                map.put(num, map.get(num) - 1);
            }
        }
        
        int[] rt_arr = new int[rt.size()];
        for (int i = 0; i < rt.size(); i++) {
            rt_arr[i] = rt.get(i);
        }
        
        return rt_arr;
    }
    
    private Map<Integer, Integer> getMap(int[] nums1) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        return map;
    }
}

560. Subarray Sum Equals K

560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

----------------------------
注意一些特殊情况,（会对代码的顺序有一点影响）
sum == k
k == 0

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        int sum = 0;
        map.put(0, 1);
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        
        return count;
    }
}

647. Palindromic Substrings

647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won't exceed 1000.

-----------------------------
manacher's algorithm。p[i]记录的是以i为中点，最长的回文字符串向左或向右扩张的长度，包括i。也就是把字符串对折之后的长度
注意p[i]的取值，和right的更新
也可以写作

p[i] = Math.min(right - i + 1, p[mirror])

但同时要修改

if (i + p[i] - 1 > right) {
    center = i;
    right = i + p[i] - 1;
}

class Solution {
    public int countSubstrings(String s) {
        String ss = "#";
        for (int i = 0; i < s.length(); i++) {
            ss += s.charAt(i) + "#";
        }
        
        int center = 0;
        int right = 0;
        int[] p = new int[ss.length()];
        
        for (int i = 1; i < ss.length(); i++) {
            int mirror = center - (i - center);

            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            while (i - p[i] >= 0 && p[i] + i < ss.length() && ss.charAt(i + p[i]) == ss.charAt(i - p[i])) {
                p[i]++;
            }
            
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        
        int count = 0;
        for (int i : p) {
            count += i / 2;
        }
        
        return count;
    }
}

同类型的题：http://shibaili.blogspot.com/2013/11/day-51-5-longest-palindromic-substring.html
阅读：https://www.felix021.com/blog/read.php?2040

477. Total Hamming Distance

477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

----------------------------
某一位上1的个数 ＊ 该位上0的个数 ＝ 该位上的hamming distance。遍历所有数字的32位，则得到结果

class Solution {
    public int totalHammingDistance(int[] nums) {
        int[] bits = new int[32];
        
        for (int num : nums) {
            
            int i = 0;
            while (num > 0) {
                if ((num & 0x1) == 1) {
                    bits[i]++;
                }
                num >>= 1;
                i++;
            }
        }
        
        int rt = 0;
        for (int bit : bits) {
            rt += bit * (nums.length - bit);
        }
        
        return rt;
    }
}

398. Random Pick Index

398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

------------------------
很直接的Reservoir sampling, 看总结

class Solution {

    private int[] nums;
    private Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        rand = new Random();
    }
    
    public int pick(int target) {
        int size = 0;
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                size++;
                if (rand.nextInt(size) == 0) {
                    index = i;
                }
            }
        }
        
        return index;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

785. Is Graph Bipartite?

785. Is Graph Bipartite?

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

Note:

• graph will have length in range [1, 100].
• graph[i] will contain integers in range [0, graph.length - 1].
• graph[i] will not contain i or duplicate values.
• The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

--------------------------
垂直一条线把graph分为2半，每一半的node只能有链接通向对面一半，不能跟相同一半的node有链接。

把2半分别标记别true跟false

Solution #1 DFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            if (!map.containsKey(i) && !dfs(map, graph, i, true)) return false;
        }
        
        return true;
    }
    
    private boolean dfs(Map<Integer, Boolean> map, int[][] graph, int node, boolean flag) {
        if (map.containsKey(node) && map.get(node) == flag) return false;
        if (map.containsKey(node)) return true;
        
        map.put(node, !flag);
        for (int neighbor : graph[node]) {
            if (!dfs(map, graph, neighbor, !flag)) return false;
        }
        
        return true;
    }
}

Solution #2 BFS

class Solution {
    
    public boolean isBipartite(int[][] graph) {
        Map map = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            if (!map.containsKey(i) && !bfs(map, graph, i)) return false;
        }
        
        return true;
    }
    
    private boolean bfs(Map map, int[][] graph, int node) {
        
        Queue que = new LinkedList<>();
        
        que.add(node);
        map.put(node, true);
        
        while (!que.isEmpty()) {
            int top = que.poll();
            for (int neighbor : graph[top]) {
                if (!map.containsKey(neighbor)) {
                    que.add(neighbor);
                    map.put(neighbor, !map.get(top));
                }else if (map.containsKey(neighbor) && map.get(neighbor) == map.get(top)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
}