(G)扑克牌

一个扑克牌游戏，比如我手上有52张牌中的一些牌，可以用以下的方式打出：1 三张或四张数字相同，花色不同，可以一起打出。2 相同花色连续三张以上可以打出。其他任何组合都不可以打出。如果我手上有一些牌，问判断是否可以按照以上两种规则打出。面试时并没有什么太好的思路，用了dp。不知道是不是下午有些累了，写的有点慢，脑子有时候会卡壳，写了满满一面墙才勉强写完。最后没有时间继续讨论了，也没有follow up。也不知道有没有更好的方法。

DFS+记忆化搜索

Shopping Offers

特别好的一道题，top-down的方式，DFS+HashMap. 注意top-down的时候结尾的时候返回要更新map，返回当前signature所产生的值。map中一旦返回，证明这个子问题的值已经计算完毕。不需要传cur的值，传cur值是到最小子问题时更新，可以是void类型。top-down dp需要子问题的的值来打表，dfs要int 类型。

HashMap 在equals判断list element时，是判断list instances是否相等的。

在计算non-special offer的时候，可以将当前的所有needs直接计算了。原因是这么计算也不会错过最优解

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        Map<List<Integer>, Integer> dp = new HashMap<>();
        List<Integer> allZero = new ArrayList<>();
        for(int i=0;i<needs.size();i++) {
            allZero.add(0);
        }
        dp.put(allZero, 0);
        return dfs(needs, price, special, dp);
    }
    private int dfs(List<Integer> needs, List<Integer> price, List<List<Integer>> special, Map<List<Integer>, Integer> dp) {
        if(dp.containsKey(needs)) return dp.get(needs);
        int res = Integer.MAX_VALUE;
        for(List<Integer> s : special) {
            List<Integer> needsCopy = new ArrayList<>(needs);
            boolean valid = true;
            for(int i=0;i<needs.size();i++) {
                needsCopy.set(i, needsCopy.get(i) - s.get(i));
                if(needsCopy.get(i) < 0) {
                    valid = false;
                    break;
                }
            }
            if(valid) {
                res = Math.min(res, s.get(needs.size()) + dfs(needsCopy, price, special, dp));
            }
        }
        //What if we do not use specials? specials can be deceiving,
        //perhaps buying using regular prices is cheaper.
        int noSpecial = 0;
            for(int i=0;i<needs.size();i++) {
                noSpecial += needs.get(i) * price.get(i);
            }
        res = Math.min(res, noSpecial);    

        dp.put(needs, res);
        return res;
    }

}

Out of Boundary Paths

DFS +HashMap, top down DP

public class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        return dfs(m,n,N, i, j, map);
    }

    public int dfs(int m, int n, int N, int i, int j, HashMap<String, Integer> map){
        String sig = i+" " + j + " " + N;
        if(map.containsKey(sig)) {return map.get(sig);}
        if(i<0||i>=m||j<0||j>=n){
            map.put(sig, 1);
            return 1;
        }
        int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        int ans = 0;
        for(int k=0;k<4;k++){
            if(N>0)
                ans+=dfs(m,n, N-1, i+dir[k][0], j+dir[k][1],map);
            ans = ans%1000000007;
        }
        map.put(sig, ans);
        return ans;
    }

}

Minesweeper

题目看着很繁琐。实际上是根据规则来update矩阵，可以用DFS或者BFS。

public class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0]; int y = click[1];

        if(board[x][y]=='M'){
            board[x][y] = 'X'; return board;
        }
        else if(board[x][y]=='E'){
            int count = 0;
            for(int i=-1;i<2;i++)
                for(int j=-1;j<2;j++){
                    if(i==0&&j==0) continue;
                    int nx = x+i; int ny = y+j;
                    if(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length&&board[nx][ny]=='M') count++;
                }
            if(count>0)
                board[x][y] = (char)(count+'0');
            else{
                board[x][y]='B';
                for(int i=-1;i<2;i++)
                    for(int j=-1;j<2;j++){
                        int nx = x+i; int ny = y+j;
                        if(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length)
                            updateBoard(board, new int[]{nx, ny});
                    }
            }
        }
        return board;
    }
}

public class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length, n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(click);

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0], col = cell[1];

            if (board[row][col] == 'M') { // Mine
                board[row][col] = 'X';
            }
            else { // Empty
                // Get number of mines first.
                int count = 0;
                for (int i = -1; i < 2; i++) {
                    for (int j = -1; j < 2; j++) {
                        if (i == 0 && j == 0) continue;
                        int r = row + i, c = col + j;
                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                        if (board[r][c] == 'M' || board[r][c] == 'X') count++;
                    }
                }

                if (count > 0) { // If it is not a 'B', stop further DFS.
                    board[row][col] = (char)(count + '0');
                }
                else { // Continue BFS to adjacent cells.
                    board[row][col] = 'B';
                    for (int i = -1; i < 2; i++) {
                        for (int j = -1; j < 2; j++) {
                            if (i == 0 && j == 0) continue;
                            int r = row + i, c = col + j;
                            if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                            if (board[r][c] == 'E') {
                                queue.add(new int[] {r, c});
                                board[r][c] = 'B'; // Avoid to be added again.
                            }
                        }
                    }
                }
            }
        }

        return board;
    }
}

Matchsticks to Square

根据火柴棍总长度算出每条边target，DFS验证能否凑出边来。一个Trick是先由高到低排序火柴棍，先判断长的，不符合时会先出来。

public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 4 != 0) return false;

        Arrays.sort(nums);
        reverse(nums);

        return dfs(nums, new int[4], 0, sum / 4);
    }

    private boolean dfs(int[] nums, int[] sums, int index, int target) {
        if (index == nums.length) {
            if (sums[0] == target && sums[1] == target && sums[2] == target) {
            return true;
            }
            return false;
        }

        for (int i = 0; i < 4; i++) {
            if (sums[i] + nums[index] > target) continue;
            sums[i] += nums[index];
            if (dfs(nums, sums, index + 1, target)) return true;
            sums[i] -= nums[index];
        }

        return false;
    }

    private void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++; j--;
        }
    }
}

Optimal Account Balancing

这是一个NP hard的问题。所有贪婪都不会得到最优解，比如每次将positive和negative最大相消。只能穷举。Google leiqi面试和面经都出现过，square也出过。

穷举时可以只用一个数组，不用pos和neg

public class Solution {

    int count = Integer.MAX_VALUE;
    public int minTransfers(int[][] transactions) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int[] t: transactions){
            map.put(t[0], map.getOrDefault(t[0], 0)-t[2]);
            map.put(t[1], map.getOrDefault(t[1], 0)+t[2]);
        }
        List<Integer> pos = new ArrayList<Integer>();
        List<Integer> neg = new ArrayList<Integer>();
        for(Integer k : map.keySet()){
            if(map.get(k)>0) pos.add(map.get(k));
            else if(map.get(k)<0) neg.add(map.get(k));
        }
        dfs(pos, neg, 0);
        return count;
    }

    public void dfs(List<Integer> pos, List<Integer> neg, int cur){
        if(pos.size()==0 && neg.size()==0){
            //System.out.println(count+ " " + cur);
            count = Math.min(count, cur);
            return;
        }

        List<Integer> curPos = new ArrayList<Integer>(pos);
        List<Integer> curNeg = new ArrayList<Integer>(neg);
        for(int i=0;i<curPos.size();i++)
            for(int j=0;j<curNeg.size();j++){
                int p = curPos.get(i); int n = curNeg.get(j); 
                if(p+n<0){
                    curPos.remove(i);
                    curNeg.set(j, p+n);
                    dfs(curPos, curNeg, cur+1);
                    curPos.add(i, p);
                    curNeg.set(j, n);
                }
                else if(p+n==0){
                    curPos.remove(i);
                    curNeg.remove(j);
                    dfs(curPos, curNeg, cur+1);
                    curPos.add(i, p);
                    curNeg.add(j, n);
                }
                else{
                    curPos.set(i, p+n);
                    curNeg.remove(j);
                    dfs(curPos, curNeg, cur+1);
                    curPos.set(i, p);
                    curNeg.add(j, n);
                }
            }
    }
}

public class Solution {
    public int minTransfers(int[][] transactions) {
    Map<Integer, Integer> net = new HashMap<>();
    for (int[] t : transactions) {
        net.put(t[0], net.getOrDefault(t[0], 0) - t[2]);
        net.put(t[1], net.getOrDefault(t[1], 0) + t[2]);
    }
    int[] a = new int[net.size()];
    int cnt = 0;
    for (int v : net.values()) {
        if (v != 0) a[cnt++] = v;
    }
    return helper(a, 0, cnt, 0);
}
int helper(int[] a, int start, int n, int num) {
    int ans = Integer.MAX_VALUE;
    while(start < n && a[start] == 0) start++;
    for (int i = start + 1; i < n; ++i) {
        if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
            a[i] += a[start];
            ans = Math.min(ans, helper(a, start + 1, n, num + 1));
            a[i] -= a[start];
        }
    }
    return ans == Integer.MAX_VALUE ? num : ans;
}
}