lcp343

保龄球游戏的获胜者

方法一：模拟

class Solution {
    public int isWinner(int[] player1, int[] player2) {
        int sum1 = 0, sum2 = 0;
        int flag1 = 0, flag2 = 0;
        for (int i = 0; i < player1.length; ++i) {
            sum1 += player1[i] + (flag1-- > 0 ? player1[i] : 0);
            sum2 += player2[i] + (flag2-- > 0 ? player2[i] : 0);
            if (player1[i] == 10)
                flag1 = 2;
            if (player2[i] == 10)
                flag2 = 2;
        }
        if (sum1 == sum2)
            return 0;
        return sum1 > sum2 ? 1 : 2;
    }
}

找出叠涂元素

方法一：HashMap

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                map.put(mat[i][j], new int[]{i, j});
        int[] countR = new int[m], countC = new int[n];
        Arrays.fill(countR, n);
        Arrays.fill(countC, m);
        for (int i = 0; i < m * n; ++i) {
            int[] rc = map.get(arr[i]);
            if (--countR[rc[0]] == 0)
                return i;
            if (--countC[rc[1]] == 0)
                return i;
        }
        return m * n - 1;
    }
}

2662. 前往目标的最小代价

方法一：dijkstra

Debug两小时的原因

1. int vx = (int) minIndex >> 32应该加括号int vx = (int) (minIndex >> 32)，前者先把minIndex转成int，再右移

2. map里的节点不一定是specialRoads.length + 2个，可能有重复节点，所以要while(true)

3. 初始化时，如果specialRoads有到达起点的点，那么所有点的距离都是max，所以dist.put(startLong, 0);要在此之后

   for (int i = 0; i < specialRoads.length; ++i)
       dist.put((long) specialRoads[i][2] << 32 | specialRoads[i][3], Integer.MAX_VALUE);
   dist.put(startLong, 0);

代码

class Solution {
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        return dijkstra(start, target, specialRoads);
    }

    private int dijkstra(int[] start, int[] target, int[][] specialRoads) {
        Map<Long, Integer> dist = new HashMap<>();
        // key: 64位，前32位表示横坐标，后32位表示纵坐标;
        // val: 距离targetLong的最短距离
        // 大小为2 + specialRoads.length，顶点为：起点，target，specialRoads的所有终点
        long targetLong = (long) target[0] << 32 | target[1], startLong = (long) start[0] << 32 | start[1];
        dist.put(targetLong, Integer.MAX_VALUE);
        for (int i = 0; i < specialRoads.length; ++i)
            dist.put((long) specialRoads[i][2] << 32 | specialRoads[i][3], Integer.MAX_VALUE);
        dist.put(startLong, 0);
        Set<Long> visited = new HashSet<>();
        while (true) {
            int minDist = Integer.MAX_VALUE;
            long minIndex = -1;
            for (Long key : dist.keySet()) {
                if (!visited.contains(key) && dist.get(key) < minDist) {
                    minDist = dist.get(key);
                    minIndex = key;
                }
            }
            if (minIndex == targetLong)
                return minDist;
            visited.add(minIndex);
            int vx = (int) (minIndex >> 32), vy = (int) minIndex & Integer.MAX_VALUE;
            // 更新终点的最短距离
            dist.merge(targetLong, minDist + Math.abs(target[0] - vx) + Math.abs(target[1] - vy), Math::min);
            for (int[] sr : specialRoads) {
                long node = (long) sr[2] << 32 | sr[3];
                int manhattanDist = minDist + Math.min(Math.abs(vx - sr[0]) + Math.abs(vy - sr[1]) + sr[4], Math.abs(vx - sr[2]) + Math.abs(vy - sr[3]));
                if (manhattanDist < dist.get(node))
                    dist.put(node, manhattanDist);
            }
        }
    }
}

字典序最小的美丽字符串

方法一：贪心

class Solution {
    public String smallestBeautifulString(String s, int k) {
        char[] chars = s.toCharArray();
        k =  (char) ('a' + k);
        int n = s.length(), i = n - 1;
        ++chars[i];
        while (i < n) {
            if (chars[i] == k) {
                if (i == 0)
                    return "";
                // 进位
                chars[i] = 'a';
                ++chars[--i];
            }
            else if ((i > 0 && chars[i] == chars[i - 1]) || (i > 1 && chars[i] == chars[i - 2])) 
                ++chars[i];
            else 
                ++i;
        }
        return new String(chars);
    }
}