Given a square matrix of pixel colors (B and W), find the largest subsquare anchored at the top-left corner with all four borders filled with black pixels. Return three values: the row, column of the top-left corner, and the side length. If no such subsquare exists, the side length is 0.
Examples:
["BBB","B B","BBB"]→"0 0 3"
解法
枚举边长 K 从 1 到 n。对每个 K，检查左上角在 (0,0) 的 K×K 子方阵四条边(顶行、底行、左列、右列)是否全为 B，记录最大通过的 K。复杂度 O(n²)。
def coding_challenge(strArr):
n = len(strArr)
best = 0
for K in range(1, n + 1):
ok = True
for j in range(K):
if strArr[0][j] != 'B' or strArr[K - 1][j] != 'B':
ok = False; break
if ok:
for i in range(K):
if strArr[i][0] != 'B' or strArr[i][K - 1] != 'B':
ok = False; break
if ok:
best = K
return f"0 0 {best}"class Solution {
static String codingChallenge(String[] strArr) {
int n = strArr.length, best = 0;
for (int K = 1; K <= n; K++) {
boolean ok = true;
for (int j = 0; j < K && ok; j++) {
if (strArr[0].charAt(j) != 'B') ok = false;
if (strArr[K - 1].charAt(j) != 'B') ok = false;
}
for (int i = 0; i < K && ok; i++) {
if (strArr[i].charAt(0) != 'B') ok = false;
if (strArr[i].charAt(K - 1) != 'B') ok = false;
}
if (ok) best = K;
}
return "0 0 " + best;
}
}#include <string>
#include <vector>
using namespace std;
string codingChallenge(vector<string>& strArr) {
int n = strArr.size(), best = 0;
for (int K = 1; K <= n; K++) {
bool ok = true;
for (int j = 0; j < K && ok; j++) {
if (strArr[0][j] != 'B') ok = false;
if (strArr[K - 1][j] != 'B') ok = false;
}
for (int i = 0; i < K && ok; i++) {
if (strArr[i][0] != 'B') ok = false;
if (strArr[i][K - 1] != 'B') ok = false;
}
if (ok) best = K;
}
return "0 0 " + to_string(best);
}Construct a binary search tree from a list of integers in the order given (no balancing, no duplicates). Then return the distance (number of edges) between two nodes with given values. If either value is missing, return -1.
Examples:
strArr = ["1","2","3","4"], u = 4, v = 2→2strArr = ["1","2","3","4"], u = 4, v = 0→-1[8,7,13,6,2,5,1,9,11,3,4,10], u = 4, v = 2→3
解法
按顺序插入构造 BST。利用 BST 性质从根下行：u 和 v 的 LCA 是首个值落在 [min(u, v), max(u, v)] 之间的节点。从 LCA 下行分别到 u 和 v 数边数，相加即路径距离。任一值缺失返回 -1。查询复杂度 O(h)，h 为树高。
class Node:
__slots__ = ('v', 'l', 'r')
def __init__(self, v):
self.v, self.l, self.r = v, None, None
def coding_challenge(strArr):
def insert(root, v):
if not root:
return Node(v)
if v < root.v:
root.l = insert(root.l, v)
elif v > root.v:
root.r = insert(root.r, v)
return root
def find(root, v):
while root:
if root.v == v:
return True
root = root.l if v < root.v else root.r
return False
def dist(lca, v):
d = 0
while lca and lca.v != v:
lca = lca.l if v < lca.v else lca.r
d += 1
return d
root = None
for s in strArr[:-2]:
root = insert(root, int(s))
u, v = int(strArr[-2]), int(strArr[-1])
if not find(root, u) or not find(root, v):
return "-1"
lca = root
while lca:
if u < lca.v and v < lca.v:
lca = lca.l
elif u > lca.v and v > lca.v:
lca = lca.r
else:
break
return str(dist(lca, u) + dist(lca, v))class Solution {
static class Node { int v; Node l, r; Node(int v) { this.v = v; } }
static Node insert(Node root, int v) {
if (root == null) return new Node(v);
if (v < root.v) root.l = insert(root.l, v);
else if (v > root.v) root.r = insert(root.r, v);
return root;
}
static boolean find(Node root, int v) {
while (root != null) {
if (root.v == v) return true;
root = v < root.v ? root.l : root.r;
}
return false;
}
static int distFromLCA(Node lca, int v) {
int d = 0;
while (lca != null && lca.v != v) {
lca = v < lca.v ? lca.l : lca.r;
d++;
}
return d;
}
static String codingChallenge(String[] strArr) {
Node root = null;
for (int i = 0; i < strArr.length - 2; i++) root = insert(root, Integer.parseInt(strArr[i]));
int u = Integer.parseInt(strArr[strArr.length - 2]);
int v = Integer.parseInt(strArr[strArr.length - 1]);
if (!find(root, u) || !find(root, v)) return "-1";
Node lca = root;
while (lca != null) {
if (u < lca.v && v < lca.v) lca = lca.l;
else if (u > lca.v && v > lca.v) lca = lca.r;
else break;
}
return Integer.toString(distFromLCA(lca, u) + distFromLCA(lca, v));
}
}#include <bits/stdc++.h>
using namespace std;
struct Node { int v; Node *l, *r; Node(int v): v(v), l(nullptr), r(nullptr) {} };
void insertNode(Node*& root, int v) {
if (!root) { root = new Node(v); return; }
if (v < root->v) insertNode(root->l, v);
else if (v > root->v) insertNode(root->r, v);
}
bool findNode(Node* root, int v) {
while (root) {
if (root->v == v) return true;
root = (v < root->v) ? root->l : root->r;
}
return false;
}
int distFromLCA(Node* lca, int v) {
int d = 0;
while (lca && lca->v != v) {
lca = (v < lca->v) ? lca->l : lca->r;
d++;
}
return d;
}
string codingChallenge(vector<string>& strArr) {
Node* root = nullptr;
int n = strArr.size();
for (int i = 0; i < n - 2; i++) insertNode(root, stoi(strArr[i]));
int u = stoi(strArr[n - 2]), v = stoi(strArr[n - 1]);
if (!findNode(root, u) || !findNode(root, v)) return "-1";
Node* lca = root;
while (lca) {
if (u < lca->v && v < lca->v) lca = lca->l;
else if (u > lca->v && v > lca->v) lca = lca->r;
else break;
}
return to_string(distFromLCA(lca, u) + distFromLCA(lca, v));
}Parse a string of form "data;rotations" into two arrays. For each number k in rotations, perform k left rotations on a fresh copy of the original data array, then output the index of the max element. Output is a space-separated list of indices.
Left rotation: first element moves to the end; everything else shifts left by 1. After 1 rotation on (10, 20, 50) → (20, 50, 10).
Examples:
"10 20 30 40 50;1 2 3"→"3 2 1""99 1 2 3 4;1 2 5"→"4 3 0"
解法
左旋 k 次后，原下标 i 的值移到 (i - k) mod n。一次找出最大元素下标 M，每个查询 k 输出 (M - k) mod n。复杂度 O(n + Q)。
def array_rotation_problem(s):
data_p, rot_p = s.split(';')
data = [int(x) for x in data_p.split()]
rots = [int(x) for x in rot_p.split()]
n = len(data)
M = max(range(n), key=lambda i: data[i])
return ' '.join(str((M - k) % n) for k in rots)class Solution {
static String arrayRotationProblem(String str) {
String[] parts = str.split(";");
String[] dataS = parts[0].trim().split("\\s+");
String[] rotS = parts[1].trim().split("\\s+");
int n = dataS.length;
int[] data = new int[n];
for (int i = 0; i < n; i++) data[i] = Integer.parseInt(dataS[i]);
int M = 0;
for (int i = 1; i < n; i++) if (data[i] > data[M]) M = i;
StringBuilder out = new StringBuilder();
for (String s : rotS) {
int k = Integer.parseInt(s);
int idx = ((M - k) % n + n) % n;
if (out.length() > 0) out.append(' ');
out.append(idx);
}
return out.toString();
}
}#include <bits/stdc++.h>
using namespace std;
string arrayRotationProblem(string str) {
auto semi = str.find(';');
string dataPart = str.substr(0, semi);
string rotPart = str.substr(semi + 1);
vector<int> data, rots;
{ stringstream ss(dataPart); int x; while (ss >> x) data.push_back(x); }
{ stringstream ss(rotPart); int x; while (ss >> x) rots.push_back(x); }
int n = data.size();
int M = max_element(data.begin(), data.end()) - data.begin();
string out;
for (int k : rots) {
int idx = ((M - k) % n + n) % n;
if (!out.empty()) out += ' ';
out += to_string(idx);
}
return out;
}