解题思路

这是一道棋盘操作的模拟题,主要思路如下:

  1. 问题分析:

    • 的棋盘,每个位置是
    • 每次操作会翻转指定位置周围上下左右四个位置的值
    • 需要按顺序执行所有操作
  2. 解决方案:

    • 使用方向数组表示上下左右四个方向
    • 对每个操作位置,检查并翻转周围的棋子
    • 使用异或操作实现翻转(0变1,1变0)
  3. 实现细节:

    • 检查边界条件
    • 坐标从1开始需要转换为0开始
    • 使用异或运算简化翻转操作

代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
private:
    // 方向数组:右、左、下、上
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    
    // 翻转指定位置周围的棋子
    void flip(vector<vector<int>>& board, int row, int col) {
        for (int i = 0; i < 4; i++) {
            int newRow = row + dx[i];
            int newCol = col + dy[i];
            // 检查边界条件
            if (newRow >= 0 && newRow < 4 && newCol >= 0 && newCol < 4) {
                // 使用异或操作翻转棋子
                board[newRow][newCol] ^= 1;
            }
        }
    }
    
public:
    vector<vector<int>> flipChess(vector<vector<int>>& A, vector<vector<int>>& f) {
        // 执行每个翻转操作
        for (const auto& pos : f) {
            // 坐标从1开始,需要减1
            int row = pos[0] - 1;
            int col = pos[1] - 1;
            flip(A, row, col);
        }
        return A;
    }
};
import java.util.*;

public class Solution {
    // 方向数组:右、左、下、上
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};
    
    // 翻转指定位置周围的棋子
    private static void flip(int[][] board, int row, int col) {
        for (int i = 0; i < 4; i++) {
            int newRow = row + dx[i];
            int newCol = col + dy[i];
            // 检查边界条件
            if (newRow >= 0 && newRow < 4 && newCol >= 0 && newCol < 4) {
                // 使用异或操作翻转棋子
                board[newRow][newCol] ^= 1;
            }
        }
    }
    
    public static int[][] flipChess(int[][] board, int[][] operations) {
        // 执行每个翻转操作
        for (int[] pos : operations) {
            // 坐标从1开始,需要减1
            int row = pos[0] - 1;
            int col = pos[1] - 1;
            flip(board, row, col);
        }
        return board;
    }
}
class Solution:
    def flipChess(self , A: List[List[int]], f: List[List[int]]) -> List[List[int]]:
        def flip(board, row, col):
            # 方向数组:右、左、下、上
            dx = [0, 0, 1, -1]
            dy = [1, -1, 0, 0]
            
            # 翻转指定位置周围的棋子
            for i in range(4):
                new_row = row + dx[i]
                new_col = col + dy[i]
                # 检查边界条件
                if 0 <= new_row < 4 and 0 <= new_col < 4:
                    # 使用异或操作翻转棋子
                    board[new_row][new_col] ^= 1

        # 执行每个翻转操作
        for row, col in f:
            # 坐标从1开始,需要减1
            flip(A, row-1, col-1)
        return A

算法及复杂度

  • 算法:模拟
  • 时间复杂度: - 为操作次数,每次操作固定翻转4个位置
  • 空间复杂度: - 只需要常数额外空间