LeetCode(38) -- 860, 867, 868, 872, 874

P860. Lemonade Change (Easy)

一个柠檬汁$5，顾客可能用5元，10元，或者20元来支付，必须找给客户正确的零钱。假设一开始你没有零钱，问是否能足够支付每个客户的找零要求。

我的思路

要保存手里各种面值的纸币还剩下多少。关键的问题在于有可能我手里的钱够，但是面值太大找不开。

我的代码

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int change = 0, five = 0, ten = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] - 5 > change) {
                return false;
            }
            if (bills[i] == 20) {
                if (!(ten >= 1 && five >= 1) && five < 3) {
                    return false;
                }
                if (ten >= 1) {
                    ten--;
                    five--;
                } else {
                    five = five - 3;
                }
            } else if (bills[i] == 10) {
                if (five < 1) {
                    return false;
                }
                five--;
                ten++;
            } else {
                five++;
            }
            change += 5;
        }
        return true;
    }
}

91%

最优解

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int small = 0, med = 0, i = 0;
        while(i != bills.length){
            if(bills[i] == 10){
                if(small == 0){
                    return false;
                }else{
                    small--;
                    med++;
                }
            }else if(bills[i] == 20){
                if(small < 3 && (med < 1 || small < 1)){
                    return false;
                }else if(med >= 1){
                    med--;
                    small--;
                }else{
                    small -= 3;
                }
            }else{
                small++;
            }
            i++;
        }
        return true;
    }
}

基本逻辑跟我非常类似，只是其实不需要再保存我的余额了。只有确保有对应面值的纸币，当然是能找开的。

P867. Transpose Matrix (Easy)

给一个矩阵，做横竖反转。

我的思路

极简单

我的代码

class Solution {
    public int[][] transpose(int[][] A) {
        int row = A.length;
        int col = A[0].length;
        int[][] ans = new int[col][row];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans[j][i] = A[i][j];
            }
        }
        return ans;
    }
}

100%

最优解

class Solution {
    public int[][] transpose(int[][] A) {


        int[][] result = new int[A[0].length][A.length];

        if(A.length == 0){
            return result;
        }

        for(int i=0;i<A[0].length;i++){
            for(int j=0;j<A.length;j++){
                result[i][j]=A[j][i];
            }
        }
        return result;
    }
}

P868. Binary Gap (Easy)

一个整数的二进制表示中，两个1之间的最长距离是多少。

我的思路

把整数先化成二进制的字符串，然后挨个数最长距离。直接用位运算可能也可以。

我的代码

class Solution {
    public int binaryGap(int N) {
        String s = Integer.toBinaryString(N);
        char[] chars = s.toCharArray();
        int max = 0, prev = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '1') {
                max = Math.max(max, i - prev);
                prev = i;
            }
        }
        return max;
    }
}

53%

最优解

class Solution {
    public int binaryGap(int N) {
       int[] A = new int[32];
        int t = 0;
        for (int i = 0; i < 32; i++)
            if (((N >> i) & 1) != 0)
            { A[t] = i;
                 t++;}

        int ans = 0;
        for (int i = 0; i < t - 1; i++)
            ans = Math.max(ans, A[i+1] - A[i]);
        return ans;
    }
}

先把二进制中所有1的坐标存成一个数组，然后比较最大值。 不过我觉得其实可以用一个count来计数，在循环里不是1就++，然后找出来最大值，不需要存成数组。

答案

class Solution {
    public int binaryGap(int N) {
        int last = -1, ans = 0;
        for (int i = 0; i < 32; ++i)
            if (((N >> i) & 1) > 0) {
                if (last >= 0)
                    ans = Math.max(ans, i - last);
                last = i;
            }
        return ans;
    }
}

P872. Leaf-Similar Trees (Easy)

一个二叉树所有的叶节点组成一个序列。对比两个二叉树的叶节点序列是否相同。

我的思路

中序遍历（其实怎么遍历都可以），找出所有的叶节点。

我的代码

public class E_872_LeafSimilarTrees {
    List<Integer> list = new ArrayList<>();

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        leafSequence(root1);
        Integer[] arr1 = list.toArray(new Integer[0]);
        list.clear();
        leafSequence(root2);
        Integer[] arr2 = list.toArray(new Integer[0]);
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private void leafSequence (TreeNode root) {
        if (root == null) {
            return;
        }
        leafSequence(root.left);
        if (root.left == null && root.right == null) {
            list.add(root.val);
        }
        leafSequence(root.right);
    }
}

66%

最优解

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        List<Integer> seq1 = new ArrayList<>();
        List<Integer> seq2 = new ArrayList<>();
        inOrderWalk(root1, seq1);
        inOrderWalk(root2, seq2);

        if (seq1.size() != seq2.size()) return false;

        for (int i=0; i<seq1.size(); i++) {

            int val1 = seq1.get(i);
            int val2 = seq2.get(i);

            if (val1 != val2) return false;
        }

        return true;
    }

    private void inOrderWalk(TreeNode root, List<Integer> leafSeq) {
        if (root == null) return;

        inOrderWalk(root.left, leafSeq);
        if (isLeaf(root)) leafSeq.add(root.val);
        inOrderWalk(root.right, leafSeq);
    }

    private boolean isLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }
}

把list传到函数里会稍微快一点。

答案

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList();
        List<Integer> leaves2 = new ArrayList();
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1.equals(leaves2);
    }

    public void dfs(TreeNode node, List<Integer> leafValues) {
        if (node != null) {
            if (node.left == null && node.right == null)
                leafValues.add(node.val);
            dfs(node.left, leafValues);
            dfs(node.right, leafValues);
        }
    }
}

P874. Walking Robot Simulation (Easy)

一个机器人，一开始站在(0,0)点，面向北。给它一系列指令，-2代表向左转90度，-1代表向右转90度，1到9代表沿当前方向走多少个格子。另外在地图上还有一些障碍点。如果碰到障碍点，则停在障碍点的前一个点。再继续后面的指令。

我的思路

每次前进时，都要检查途中是否有障碍点。查找时需要先根据横坐标或者纵坐标，找出这一条线上所有的障碍点，再根据我要前进的路线，找到第一个障碍点。因为障碍点最多可能有1000个，所以我打算用两个HashMap<Integer, List>来存这些障碍点（分别用横纵坐标作为key，做两个map）。找的时候，根据需要查某个横坐标和纵坐标，再用binary search找出路径上的第一个障碍点。

我的代码

public class E_874_WalkingRobotSimulation {
    public int robotSim(int[] commands, int[][] obstacles) {
        HashMap<Integer, List<Integer>> map1 = new HashMap<>();
        HashMap<Integer, List<Integer>> map2 = new HashMap<>();
        int distance = 0;
        int direction = 0, x = 0, y = 0;
        for (int i = 0; i < obstacles.length; i++) {
            if (!map1.containsKey(obstacles[i][0])) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(obstacles[i][1]);
                map1.put(obstacles[i][0], list);
            } else {
                List<Integer> list = map1.get(obstacles[i][0]);
                list.add(obstacles[i][1]);
            }
            if (!map2.containsKey(obstacles[i][1])) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(obstacles[i][0]);
                map2.put(obstacles[i][1], list);
            } else {
                List<Integer> list = map2.get(obstacles[i][1]);
                list.add(obstacles[i][0]);
            }
        }

        // direction: north = 0, east = 1, south = 2, west = 3
        for (int i = 0; i < commands.length; i++) {
            if (commands[i] == -1) {
                direction = (direction + 1) % 4;
            } else if (commands[i] == -2) {
                direction = (direction + 3) % 4;
            } else { // need to move
                if (direction == 0) {
                    if (!map1.containsKey(x)) {
                        y += commands[i];
                    } else {
                        List<Integer> list = map1.get(x);
                        int minDistance = Integer.MAX_VALUE;
                        for (Integer integer : list) {
                            if (integer > y && integer <= y + commands[i] && integer - y < minDistance) {
                                minDistance = integer - y;
                                y = integer - 1;
                            }
                        }
                        if (minDistance == Integer.MAX_VALUE) {
                            y += commands[i];
                        }
                    }
                } else if (direction == 2) {
                    if (!map1.containsKey(x)) {
                        y -= commands[i];
                    } else {
                        List<Integer> list = map1.get(x);
                        int minDistance = Integer.MAX_VALUE;
                        for (Integer integer : list) {
                            if (integer < y && integer >= y - commands[i] && y - integer < minDistance) {
                                minDistance = y - integer;
                                y = integer + 1;
                            }
                        }
                        if (minDistance == Integer.MAX_VALUE) {
                            y -= commands[i];
                        }
                    }
                } else if (direction == 1) {
                    if (!map2.containsKey(y)) {
                        x += commands[i];
                    } else {
                        List<Integer> list = map2.get(y);
                        int minDistance = Integer.MAX_VALUE;
                        for (Integer integer : list) {
                            if (integer > x && integer <= x + commands[i] && integer - x < minDistance) {
                                minDistance = integer - x;
                                x = integer - 1;
                            }
                        }
                        if (minDistance == Integer.MAX_VALUE) {
                            x += commands[i];
                        }
                    }
                } else if (direction == 3) {
                    if (!map2.containsKey(y)) {
                        x -= commands[i];
                    } else {
                        List<Integer> list = map2.get(y);
                        int minDistance = Integer.MAX_VALUE;
                        for (Integer integer : list) {
                            if (integer < x && integer >= x - commands[i] && x - integer < minDistance) {
                                minDistance = x - integer;
                                x = integer + 1;
                            }
                        }
                        if (minDistance == Integer.MAX_VALUE) {
                            x -= commands[i];
                        }
                    }
                }
            }
            distance = Math.max(distance, x * x + y * y);
        }
        return distance;
    }
}

69%

最优解

class Solution {
    private static final int[] dx = {0, 1, 0, -1};
    private static final int[] dy = {1, 0, -1, 0};

    public int robotSim(int[] commands, int[][] obstacles) {
        HashSet<Pos> walls = new HashSet<>(obstacles.length * 2);
        for (int[] obs : obstacles)
            walls.add(new Pos(obs[0], obs[1]));
        Pos pos = new Pos(0, 0);
        int incX = 0, incY = 0;
        int k, d = 0;
        int max = 0;
        for (int command : commands) {
            switch (command) {
                case -2:
                    d = (d + 3) % 4;
                    break;
                case -1:
                    d = (d + 1) % 4;
                    break;
                default:
                    incX = dx[d];
                    incY = dy[d];
                    for (k = 1; k <= command; k++) {
                        pos.x += incX;
                        pos.y += incY;
                        if (walls.contains(pos)) {
                            pos.x -= incX;
                            pos.y -= incY;
                            break;
                        }
                    }
                    max = Math.max(max, pos.dis());
            }
        }
        return max;
    }

    class Pos {
        int x, y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int hashCode() {
            return x * 31 + y;
        }

        public boolean equals(Object obj) {
            Pos p = (Pos) obj;
            return x == p.x && y == p.y;
        }

        public int dis() {
            return x * x + y * y;
        }
    }
}

想用坐标做HashMap，要自己写一个hashcode. 需要dx,dy就消除了我的重复代码，值得学习。

答案：

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        int x = 0, y = 0, di = 0;

        // Encode obstacles (x, y) as (x+30000) * (2^16) + (y+30000)
        Set<Long> obstacleSet = new HashSet();
        for (int[] obstacle: obstacles) {
            long ox = (long) obstacle[0] + 30000;
            long oy = (long) obstacle[1] + 30000;
            obstacleSet.add((ox << 16) + oy);
        }

        int ans = 0;
        for (int cmd: commands) {
            if (cmd == -2)  //left
                di = (di + 3) % 4;
            else if (cmd == -1)  //right
                di = (di + 1) % 4;
            else {
                for (int k = 0; k < cmd; ++k) {
                    int nx = x + dx[di];
                    int ny = y + dy[di];
                    long code = (((long) nx + 30000) << 16) + ((long) ny + 30000);
                    if (!obstacleSet.contains(code)) {
                        x = nx;
                        y = ny;
                        ans = Math.max(ans, x*x + y*y);
                    }
                }
            }
        }

        return ans;
    }
}