SafetyKit

01Image Transformations on Binary Matrix

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 M

class 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;
}

02Robot Circle Existence (Infinite Loop Boundedness)

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 step
L: Turn left in place
R: 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 out

class 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.

解法

后序 DFS 算 f(u) = values[u] + max(0, max_c f(c))，在所有 f(u) 上取全局最大。复杂度 O(N)。

import sys
sys.setrecursionlimit(200000)

def bestSumDownwardTreePath(parent, values):
    n = len(parent)
    children = [[] for _ in range(n)]
    root = -1
    for i, p in enumerate(parent):
        if p == -1:
            root = i
        else:
            children[p].append(i)

    ans = float('-inf')

    def dfs(u):
        nonlocal ans
        best_child = 0
        any_child = False
        for c in children[u]:
            v = dfs(c)
            if v > best_child:
                best_child = v
            any_child = True
        cur = values[u] + (best_child if any_child and best_child > 0 else 0)
        ans = max(ans, cur)
        return cur

    dfs(root)
    return ans

import java.util.*;

class Solution {
    long ans = Long.MIN_VALUE;
    List<List<Integer>> children;
    long[] vals;

    long dfs(int u) {
        long best = 0;
        boolean any = false;
        for (int c : children.get(u)) {
            long v = dfs(c);
            if (v > best) best = v;
            any = true;
        }
        long cur = vals[u] + (any && best > 0 ? best : 0);
        if (cur > ans) ans = cur;
        return cur;
    }

    long bestSumDownwardTreePath(int[] parent, long[] values) {
        int n = parent.length;
        vals = values;
        children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        int root = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) root = i;
            else children.get(parent[i]).add(i);
        }
        ans = Long.MIN_VALUE;
        dfs(root);
        return ans;
    }
}

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

class Solution {
    long long ans;
    vector<vector<int>> children;
    vector<long long> vals;

    long long dfs(int u) {
        long long best = 0;
        bool any = false;
        for (int c : children[u]) {
            long long v = dfs(c);
            if (v > best) best = v;
            any = true;
        }
        long long cur = vals[u] + (any && best > 0 ? best : 0);
        ans = max(ans, cur);
        return cur;
    }

public:
    long long bestSumDownwardTreePath(vector<int>& parent, vector<long long>& values) {
        int n = parent.size();
        vals = values;
        children.assign(n, {});
        int root = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) root = i;
            else children[parent[i]].push_back(i);
        }
        ans = LLONG_MIN;
        dfs(root);
        return ans;
    }
};

01Image Transformations on Binary Matrix

解法

02Robot Circle Existence (Infinite Loop Boundedness)

解法

03Best Sum Downward Tree Path

解法