An image is represented as an n x n binary matrix. Transform the image by performing the following operations in sequence:
- Rotate clockwise by a specified degree (either 90, 180, or 270).
- Optionally flip it vertically (if
vertical_flip == 1). - Optionally flip it horizontally (if
horizontal_flip == 1).
Return the transformed binary matrix after applying all operations.
解法
先做 rotation // 90 次顺时针 90° 旋转(每次 M'[i][j] = M[n-1-j][i])，再按需做垂直翻转(reverse rows)或水平翻转(reverse each row)。每次操作 O(n²)。
def getFinalImage(image, rotation, vertical_flip, horizontal_flip):
n = len(image)
M = [row[:] for row in image]
def rotate90(mat):
return [[mat[n - 1 - j][i] for j in range(n)] for i in range(n)]
for _ in range(rotation // 90):
M = rotate90(M)
if vertical_flip:
M = M[::-1]
if horizontal_flip:
M = [row[::-1] for row in M]
return Mclass Solution {
static int[][] getFinalImage(int[][] image, int rotation, int vFlip, int hFlip) {
int n = image.length;
int[][] M = new int[n][n];
for (int i = 0; i < n; i++) M[i] = image[i].clone();
for (int r = 0; r < rotation / 90; r++) {
int[][] nx = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) nx[i][j] = M[n - 1 - j][i];
M = nx;
}
if (vFlip == 1) {
for (int i = 0; i < n / 2; i++) {
int[] t = M[i]; M[i] = M[n - 1 - i]; M[n - 1 - i] = t;
}
}
if (hFlip == 1) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n / 2; j++) {
int t = M[i][j]; M[i][j] = M[i][n - 1 - j]; M[i][n - 1 - j] = t;
}
}
return M;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> getFinalImage(vector<vector<int>> image, int rotation, int vFlip, int hFlip) {
int n = image.size();
for (int r = 0; r < rotation / 90; r++) {
vector<vector<int>> nx(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
nx[i][j] = image[n - 1 - j][i];
image = nx;
}
if (vFlip == 1) reverse(image.begin(), image.end());
if (hFlip == 1) for (auto& row : image) reverse(row.begin(), row.end());
return image;
}Implement a simulation for a mobile robot operating on an infinite plane, starting at the origin (0, 0). The robot's movements are controlled by a command string with these characters:
G: Move forward one stepL: Turn left in placeR: Turn right in place
The robot executes the command sequence in an infinite loop. Determine whether there exists a circle that completely contains the robot's movement path.
For each command string in input, return YES or NO.
Examples: "G" → NO, "GL" → YES, "RGRG" → YES.
解法
模拟一个完整指令周期。路径有界当且仅当一周后机器人回到原点，或朝向不再为初始正北(4 个周期内旋转闭合轨迹)。复杂度 O(|cmd|)。
def does_circle_exist(commands):
out = []
for cmd in commands:
x, y, dx, dy = 0, 0, 0, 1
for c in cmd:
if c == 'G':
x += dx; y += dy
elif c == 'L':
dx, dy = -dy, dx
elif c == 'R':
dx, dy = dy, -dx
out.append("YES" if (x, y) == (0, 0) or (dx, dy) != (0, 1) else "NO")
return outclass Solution {
static String[] doesCircleExist(String[] commands) {
String[] out = new String[commands.length];
for (int k = 0; k < commands.length; k++) {
int x = 0, y = 0, dx = 0, dy = 1;
for (char c : commands[k].toCharArray()) {
if (c == 'G') { x += dx; y += dy; }
else if (c == 'L') { int t = dx; dx = -dy; dy = t; }
else if (c == 'R') { int t = dx; dx = dy; dy = -t; }
}
out[k] = ((x == 0 && y == 0) || dx != 0 || dy != 1) ? "YES" : "NO";
}
return out;
}
}#include <vector>
#include <string>
using namespace std;
vector<string> doesCircleExist(vector<string>& commands) {
vector<string> out;
for (auto& cmd : commands) {
int x = 0, y = 0, dx = 0, dy = 1;
for (char c : cmd) {
if (c == 'G') { x += dx; y += dy; }
else if (c == 'L') { int t = dx; dx = -dy; dy = t; }
else if (c == 'R') { int t = dx; dx = dy; dy = -t; }
}
out.push_back((x == 0 && y == 0) || dx != 0 || dy != 1 ? "YES" : "NO");
}
return out;
}For a tree with n nodes rooted at node 0, each node i has a value given by values[i]. Determine the maximum sum of values along any path that starts at a node and only goes downward in the tree.
Consider only paths of the form u_1 -> u_2 -> ... -> u_k where each u_{i+1} is a child of u_i. The path can start at any node, not necessarily the root, and includes at least the start node.
Function signature: int bestSumDownwardTreePath(int parent[n], int values[n]), with parent[0] = -1.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理