Leaky Cauldron
0%

Posted on Edited on

题目(LeetCode #490)

由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。
给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。

你可以 假定迷宫的边缘都是墙壁（参考示例）。

示例1：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

示例2：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。

示例3：

输入：maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
输出：false

提示：

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow <= m
  • 0 <= startcol, destinationcol <= n
  • 球和目的地都在空地上，且初始时它们不在同一位置
  • 迷宫 至少包括 2 块空地

题解

本题可采用 BFS 或 DFS 求解，与岛屿问题不同的是，小球只有在碰到墙壁时才能停止并更改方向。

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) return false;

        int m = maze.length, n = maze[0].length;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int i = cur[0], j = cur[1];

            if (maze[i][j] == 2) continue;
            if (i == destination[0] && j == destination[1]) return true;
            maze[i][j] = 2;

            int l = j - 1, r = j + 1, u = i - 1, d = i + 1;
            while (l >= 0 && maze[i][l] != 1) l--;
            if (maze[i][l + 1] != 2) queue.add(new int[]{i, l + 1});

            while (r < n && maze[i][r] != 1) r++;
            if (maze[i][r - 1] != 2) queue.add(new int[]{i, r - 1});

            while (u >= 0 && maze[u][j] != 1) u--;
            if (maze[u + 1][j] != 2) queue.add(new int[]{u + 1, j});

            while (d < m && maze[d][j] != 1) d++;
            if (maze[d - 1][j] != 2) queue.add(new int[]{d - 1, j});
        }

        return false;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {

    int[][] maze;
    int[] destination;
    int m, n;

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) return false;

        this.maze = maze;
        this.destination = destination;
        m = maze.length;
        n = maze[0].length;

        return dfs(start[0], start[1]);
    }

    private boolean dfs(int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || maze[i][j] != 0) return false;

        if (i == destination[0] && j == destination[1]) return true;

        maze[i][j] = 2;
        int l = j - 1, r = j + 1, u = i - 1, d = i + 1;
        while (l >= 0 && maze[i][l] != 1) l--;
        if (dfs(i, l + 1)) return true;

        while (r < n && maze[i][r] != 1) r++;
        if (dfs(i, r - 1)) return true;

        while (u >= 0 && maze[u][j] != 1) u--;
        if (dfs(u + 1, j)) return true;

        while (d < m && maze[d][j] != 1) d++;
        if (dfs(d - 1, j)) return true;

        return false;
    }
}

Posted on Edited on

题目(LeetCode #314)

给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。

如果两个结点在同一行和列，那么顺序则为 从左到右。

示例 1:

输入: root = [3,9,20,null,null,15,7]
输出: [[9],[3,15],[20],[7]]

示例 2:

输入: root = [3,9,8,4,0,1,7]
输出: [[4],[9],[3,0,1],[8],[7]]

示例 3

输入: root = [3,9,8,4,0,1,7,null,null,null,2,5]
输出: [[4],[9,5],[3,0,1],[8,2],[7]]

提示:

  • 树中结点的数目在范围 [0, 100] 内.
  • -100 <= Node.val <= 100

题解

分别保存每个节点相对 root 节点的偏移层数，即每访问一次左子树就对其父节点偏移层数减 1，每访问一次右子树就加 1。在返回的 List 中按层数从小到大排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();

        // 使用 TreeMap 保证按 key 排序
        Map<Integer, List<Integer>> res = new TreeMap<>();
        Map<TreeNode, Integer> nodeMap = new HashMap<>();
        nodeMap.put(root, 0);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            int i = nodeMap.get(curNode);

            res.computeIfAbsent(i, k -> new ArrayList<>()).add(curNode.val);
            if (curNode.left != null) {
                queue.add(curNode.left);
                nodeMap.put(curNode.left, i - 1);
            }

            if (curNode.right != null) {
                queue.add(curNode.right);
                nodeMap.put(curNode.right, i + 1);
            }
        }

        return new ArrayList<>(res.values());
    }
}

Posted on Edited on

题目(LeetCode #340)

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.

Example 2:

Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.

Constraints:

  • 1 <= s.length <= 5 * 104
  • 0 <= k <= 50

题解

使用滑动窗口遍历字符串，统计窗口内不同字符的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;

        char[] chArr = s.toCharArray();
        int[] freqArr = new int[128]; // 没有限定是小写英文字母
        int n = s.length();
        int l = 0, r = 0;
        int count = 0, result = 0;

        while (r < n) {
            int cIdx = chArr[r] - '!';
            freqArr[cIdx]++;
            if (freqArr[cIdx] == 1) count++;

            while (count > k) {
                int tIdx = chArr[l++] - '!';
                freqArr[tIdx]--;
                if (freqArr[tIdx] == 0) count--;
            }

            result = Math.max(result, r - l + 1);
            r++;
        }

        return result;
    }
}

Posted on

题目(LeetCode #277)

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) that tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

  • n == graph.length == graph[i].length
  • 2 <= n <= 100
  • graph[i][j] is 0 or 1.
  • graph[i][i] == 1

题解

方法一

Celebrity 需要满足两个条件：

  1. 除了他以外的所有人都认识他；
  2. 他不认识其他任何人。

由此可知：

  1. 如果 knows(i, j) 为真，i 不可能是 Celebrity；
  2. 如果 knows(i, j) 为假，j 不可能是 Celebrity。

也就是两个人相比较，总能淘汰掉一个人。逐个遍历，依次将剩下的人与下一个人进行比较，即可得到唯一的可能的 Celebrity。

再从头遍历一遍以确保上述两个条件均满足，若不满足则不存在 Celebrity。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int result = 0;
        
        for (int i = 1; i < n; i++) {
            if (knows(result, i)) result = i;
        }
        
        for (int i = 0; i < n; i++) {
            if (i == result) continue;
            if (knows(result, i) || !knows(i, result)) return -1;
        }
        
        return result;
    }
}

参考题解: @Xiwen Yue

方法二

与方法一类似，区别仅在于从两端开始比较，两指针相遇之处即为可能的 Celebrity，后续验证过程相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int l = 0, r = n - 1;
        
        while (l != r) {
            if (knows(l, r)) l++;
            else r--;
        }
        
        for (int i = 0; i < n; i++) {
            if (i == l) continue;
            if (knows(l, i) || !knows(i, l)) return -1;
        }
        
        return l;
    }
}

Posted on

题目(LeetCode #1891)

You are given an integer array ribbons, where ribbons[i] represents the length of the ith ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.

For example, if you have a ribbon of length 4, you can:
Keep the ribbon of length 4,
Cut it into one ribbon of length 3 and one ribbon of length 1,
Cut it into two ribbons of length 2,
Cut it into one ribbon of length 2 and two ribbons of length 1, or
Cut it into four ribbons of length 1.
Your goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.

Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length.

Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:

  • Cut the first ribbon to two ribbons, one of length 5 and one of length 4.
  • Cut the second ribbon to two ribbons, one of length 5 and one of length 2.
  • Keep the third ribbon as it is.

Now you have 3 ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:

  • Cut the first ribbon to two ribbons, one of length 4 and one of length 3.
  • Cut the second ribbon to two ribbons, one of length 4 and one of length 1.
  • Cut the third ribbon to three ribbons, two of length 4 and one of length 1.

Now you have 4 ribbons of length 4.

Example 3:

Input: ribbons = [5,7,9], k = 22
Output: 0
Explanation: You cannot obtain k ribbons of the same positive integer length.

Constraints:

  • 1 <= ribbons.length <= 105
  • 1 <= ribbons[i] <= 105
  • 1 <= k <= 109

题解

采用二分法求解，绳子的最小长度为 0，最大长度为绳长最大值。根据当前绳长 m 所能得到的绳子段数总和与 k 进行比较来判断边界是否满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxLength(int[] ribbons, int k) {
        if (ribbons == null || ribbons.length == 0) return 0;

        int l = 0, r = 0;
        for (int ribbon : ribbons) r = Math.max(r, ribbon);

        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (check(ribbons, k, m)) l = m;
            else r = m - 1; 
        }

        return l;
    }

    private boolean check(int[] ribbons, int k, int m) {
        int sum = 0;
        for (int ribbon : ribbons) sum += ribbon / m;
        return sum >= k;
    }
}

Posted on Edited on

题目(LeetCode #1062)

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: “abcd”
Output: 0
Explanation: There is no repeating substring.

Example 2:

Input: “abbaba”
Output: 2
Explanation: The longest repeating substrings are “ab” and “ba”, each of which occurs twice.

Example 3:

Input: “aabcaabdaab”
Output: 3
Explanation: The longest repeating substring is “aab”, which occurs 3 times.

Example 4:

Input: “aaaaa”
Output: 4
Explanation: The longest repeating substring is “aaaa”, which occurs twice.

Note:

  1. The string S consists of only lowercase English letters from 'a' - 'z'.
  2. 1 <= S.length <= 1500

题解

若 S 中存在长度为 N 的重复字符串，则长度为 N - 1 的重复字符串也必然存在，故可用二分法猜最大长度的方法逼近实际结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int longestRepeatingSubstring(String s) {
        if (s == null || s.length() < 2) return 0;

        int l = 0, r= s.length() - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (exist(s, m)) l = m;
            else r = m - 1;
        }

        return l;
    }

    private boolean exist(String s, int m) {
        /* 存储字符串的 hash 值, 节省空间 */
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i <= s.length() - m; i++) {
            int j = i + m - 1;
            String sub = s.substring(i, j + 1);
            int hash = sub.hashCode();
            if (set.contains(hash)) return true;
            else set.add(hash);
        }

        return false;
    }
}

Posted on Edited on

题目(LeetCode #1060)

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:

Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.

Example 2:

Input: A = [4,7,9,10], K = 3
Output: 8
Explanation:
The missing numbers are [5,6,8,…], hence the third missing number is 8.

Example 3:

Input: A = [1,2,4], K = 3
Output: 6
Explanation:
The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

Note:

  1. 1 <= A.length <= 50000
  2. 1 <= A[i] <= 1e7
  3. 1 <= K <= 1e8

题解

方法一

逐个计算数组中的元素：

  1. k 大于等于数组中最后一个数时, 除了数组中的数全部缺失, 故相当于求以 nums[0] 开始的第 k + n 项；
  2. 若 k 小于数组中最后一个数，则逐个计算数组元素，若元素存在则数组指针右移，若遇到缺失元素则 k--。最终 num + k 即为第 k 个缺失元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int missingElement(int[] nums, int k) {
        if (nums == null || nums.length == 0) return k;

        int n = nums.length;
        if (k >= nums[n - 1]) return k + nums[0] + n - 1;

        int num = nums[0];
        int idx = 1;
        while (idx < n && k > 0) {
            if (++num == nums[idx]) idx++;
            else k--;
        }

        return num + k;
    }
}

方法二

通过二分查找，找到第 k 个缺失数字之前的值在 nums 中的索引。最终结果为 nums[0] + x + k，其中 x 为第 k 个缺失的数字前在 nums 数组中已经存在的元素个数。

使用二分法的一个关键问题在于如何缩小查找范围。若第 k 个缺失的数字在 [l, m] 之间，那么可知 nums[m] >= nums[0] + k + m。由此可反推判断条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingElement(int[] nums, int k) {
        if (nums == null || nums.length == 0) return k;

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (nums[m] >= nums[0] + k + m) r = m - 1;
            else l = m;
        }

        return nums[0] + l + k;
    }
}

Posted on Edited on

题目(LeetCode #644)

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Input: [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Explanation:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.

Note:

  1. 1 <= k <= n <= 10,000.
  2. Elements of the given array will be in range [-10,000, 10,000].
  3. The answer with the calculation error less than 10-5 will be accepted.

题解

本题的技巧性较强，可采用滑动窗口加二分法求解，用猜平均值的方式逼近真实值，实现的关键在于找到二分的条件。对于一个数组来说，其所有可能的子数组的最大平均值必介于最大值和最小值之间。取 mid = (min + max) / 2.0，对数组依次求长度大于等于 k 的所有可能的子数组的平均值。若平均值序列中有值大于等于 mid，则最大平均值必位于 [mid, max] 区间（即 l = mid）；若平均值序列中所有值都小于 mid，则最大平均值必位于 [min, mid] 上（即 r = mid）。其中，在计算平均值时，可将计算简化为 xi - mid 的和与 0 进行比较。

另一个 trick 是在计算数组所有可能的平均值时，不必对所有长度大于 k 的子数组再次进行遍历，只需在前 k 个元素和的基础上向右扩增，再减去前几项的和既可得到新的子数组的和。如 k = 4，当滑动窗口中包含 0 ~ 5 六个元素时，如果想得到长度为 5 和 4 的子数组的和，只需分别减去第 0 和第 0 ~ 1 个元素即可。而由于是在 mid 两侧判断是否存在子数组满足条件，故直接比较子数组的最大和与最小的前缀和的大小既可。

参考视频：【LeetCode 刷题讲解】644. Maximum Average Subarray II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        double l = min, r = max;
        while (r - l > 0.00001) {
            double mid = (l + r) / 2.0;
            if (exist(nums, k, mid)) l = mid;
            else r = mid;
        }

        return l;
    }

    private boolean exist(int[] nums, int k, double mid) {
        double sum = 0, prev = 0, minPrev = 0;
        for (int i = 0; i < k; i++) sum += nums[i] - mid;
        if (sum >= 0) return true;

        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - mid;
            prev += nums[i - k] - mid;
            minPrev = Math.min(prev, minPrev);  // 比较 子数组的最大和 与 最小的前缀和 的大小
            if (sum - minPrev >= 0) return true;
        }

        return false;
    }
}

Posted on Edited on

题目(LeetCode #1086)

Given a list of scores of different students, return the average score of each student’s top five scores in the order of each student’s id.

Each entry items[i] has items[i][0] the student’s id, and items[i][1] the student’s score. The average score is calculated using integer division.

Example 1:

1
2
3
4
5
Input:  [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation: 
The average of the student with id = 1 is 87.
The average of the student with id = 2 is 88.6. But with integer division their average converts to 88.

Note:

1 <= items.length <= 1000
items[i].length == 2
The IDs of the students is between 1 to 1000
The score of the students is between 1 to 100
For each student, there are at least 5 scores

题解

使用 PriorityQueue 分别保存每个人的分数，若 queue 长度大于 5 则去掉其中最小的分数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, Queue<Integer>> map = new HashMap<>();

        for (int[] item : items) {
            int id = item[0], score = item[1];

            Queue<Integer> curQueue = map.get(id);
            if (curQueue == null) {
                curQueue = new PriorityQueue<>(5);
                map.put(id, curQueue);
            }

            curQueue.add(score);
            if (curQueue.size() > 5) curQueue.poll();
        }

        int[][] result = new int[map.size()][2];
        int idx = 0;
        for (int k : map.keySet()) {
            Queue<Integer> curQueue = map.get(k);
            int sum = 0;
            while (!curQueue.isEmpty()) sum += curQueue.poll();
            result[idx][0] = k;
            result[idx][1] = sum / 5;
            idx++;
        }

        return result;
    }
}

Posted on Edited on

题目(LeetCode #348)

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves is allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n²) per move() operation?

题解

可使用二维数组分别保存两位选手的每一行、每一列和两条对角线上已放置的棋子数。由于每一步都是有效的且放置于空位，因此无需考虑每一行具体如何放置，记录数量即可，当行、列或对角线上的棋子数达到 n 时即有一方获胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class TicTacToe {
    private final int[][] rows;
    private final int[][] cols;
    private final int[][] diags;
    private final int n;

    public TicTacToe(int n) {
        rows = new int[2][n];
        cols = new int[2][n];
        diags = new int[2][2];
        this.n = n;
    }

    public int move(int row, int col, int player) {
        int playerIdx = player - 1;

        rows[playerIdx][row]++;
        if (rows[playerIdx][row] == n) return player;

        cols[playerIdx][col]++;
        if (cols[playerIdx][col] == n) return player;

        if (row == col) {
            diags[playerIdx][0]++;
            if (diags[playerIdx][0] == n) return player;
        }

        if (row + col == n - 1) {
            diags[playerIdx][1]++;
            if (diags[playerIdx][1] == n) return player;
        }

        return 0;
    }
}