解题思路
这是一道棋盘操作的模拟题,主要思路如下:
-
问题分析:
的棋盘,每个位置是
或
- 每次操作会翻转指定位置周围上下左右四个位置的值
- 需要按顺序执行所有操作
-
解决方案:
- 使用方向数组表示上下左右四个方向
- 对每个操作位置,检查并翻转周围的棋子
- 使用异或操作实现翻转(0变1,1变0)
-
实现细节:
- 检查边界条件
- 坐标从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个位置
- 空间复杂度:
- 只需要常数额外空间