Emma wishes to give her father a bouquet for his birthday. She asks for help from her mother Rosy. Rosy gives N flower sticks numbered 1 to N to Emma and tells her to arrange them in the bouquet in a particular order. She asks Emma to arrange the first K flower sticks in the order of increasing length and the remaining sticks in the order of decreasing length. Write an algorithm to find the final arrangement of the flower sticks in the bouquet. Input The first line of the input consists of an integer - flowerStick_size, representing the number of flower sticks (N). The second line consists of N space-separated integers- flowerStick[1], flowerStick[2],...,flowerStick[N], representing the length of the flower sticks. The last line consists of an integer - random, representing the number K given by Rosy to Emma. Output Print N space-separated integers representing the final arrangement of the flower sticks in the bouquet. Constraints 0 ≤ random ≤flowerStick_size 0 6
Constraints
0 ≤ random ≤
Example 1
Input:
flowerStick_size = 8
flowerStick = [17, 7, 5, 10, 46, 23, 16, 8]
random = 3Output:
[5, 7, 11, 46, 23, 16, 10, 8]Explanation: Emma has to arrange the first three flower sticks in an increasing order of the length and remaining sticks in the decreasing order of the length. The final order of flower sticks in the bouquet is [5, 7, 11, 46, 23, 16, 10, 8].
解法
把数组拆成前 K 和剩余两部分；前段升序，后段降序，再连接。时间 O(N log N)。
from typing import List
def arrange_flower_sticks(flower_stick: List[int], K: int) -> List[int]:
return sorted(flower_stick[:K]) + sorted(flower_stick[K:], reverse=True)import java.util.*;
class Solution {
public int[] arrangeFlowerSticks(int[] flowerStick, int K) {
int[] a = Arrays.copyOfRange(flowerStick, 0, K);
int[] b = Arrays.copyOfRange(flowerStick, K, flowerStick.length);
Arrays.sort(a);
Arrays.sort(b);
int[] out = new int[flowerStick.length];
for (int i = 0; i < a.length; i++) out[i] = a[i];
for (int i = 0; i < b.length; i++) out[a.length + i] = b[b.length - 1 - i];
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> arrangeFlowerSticks(vector<int>& flowerStick, int K) {
vector<int> a(flowerStick.begin(), flowerStick.begin() + K);
vector<int> b(flowerStick.begin() + K, flowerStick.end());
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<int>());
vector<int> out = a;
for (int x : b) out.push_back(x);
return out;
}
};There are N soldiers standing in a line, with IDs from 1 to N, in ascending order. They are participating in an exercise consisting of Q actions. During the ith action, the Major calls S numbers row and col. The soldiers at the row_ith and (col_i)th positions swap places, and so on until (row_i+m Input The first line of the input consists of an integer- num, representing the number of soldiers (N). The second line consists of two space-separated integers- actions and numSoldiers, representing the number of actions (Q) and number of soldiers called by the Major (S), respectively. The next Q lines consist of S space-separated integers- row_i and col_i, representing the positions of the soldiers initially called for the ith action. The last line consists of an integer- posSoldier, representing the position of the soldier whose ID is requested to be found after Q actions (K). Output Print an integer representing the ID of the Kth position soldier in the line after Q actions. Constraints 1 ≤ posSoldier ≤ num ≤ 10⁵ 1 ≤ actions ≤ 10⁵ 1 ≤ row_i, col_i ≤ num 1 ≤ i ≤ actions
解法
用数组 pos[1..n]=i 表示位置 i 上士兵的 id。每次 action 给一对 (r, c) 就 swap pos[r] 与 pos[c]。最后输出 pos[K]。简单 O(N + Q)。
from typing import List
def find_id_of_soldier(num: int, actions_pairs: List[List[int]], pos_soldier: int) -> int:
pos = list(range(num + 1)) # pos[i] = id at position i
for r, c in actions_pairs:
pos[r], pos[c] = pos[c], pos[r]
return pos[pos_soldier]class Solution {
public int findIdOfSoldier(int num, int[][] actions, int posSoldier) {
int[] pos = new int[num + 1];
for (int i = 1; i <= num; i++) pos[i] = i;
for (int[] a : actions) {
int t = pos[a[0]]; pos[a[0]] = pos[a[1]]; pos[a[1]] = t;
}
return pos[posSoldier];
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findIdOfSoldier(int num, vector<vector<int>>& actions, int posSoldier) {
vector<int> pos(num + 1);
iota(pos.begin(), pos.end(), 0);
for (auto& a : actions) swap(pos[a[0]], pos[a[1]]);
return pos[posSoldier];
}
};The city authorities conduct a study of the houses in a residential area for a city planning scheme. The area is depicted in an aerial view and divided into an N x M grid. If a grid cell contains some part of a house roof, then it is assigned the value 1; otherwise, the cell represents a vacant plot and is assigned the value 0. Clusters of adjacent grid cells with value 1 represent a single house. Diagonally placed grids with value 1 do not represent a single house. The area of a house is the number of 1's that it spans.
Write an algorithm to find the area of the largest house.
Input
The first line of the input consists of two space-separated integers - rows and cols representing the number of rows (N) and the number of columns in the grid (M), respectively.
The next N lines consist of M space-separated integers representing the grid.
Output
Print an integer representing the area of the largest house.
Constraints
The elements of the grid consist of 0s and 1s only.
Example 1
Input:
grid = [[0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 1, 0, 0]]Output:
3Explanation: The area of the biggest house is 3. So, the output is 3.
解法
4 邻接 Flood Fill (BFS/DFS)：扫描每个 1 格，对未访问的做 BFS 统计连通块大小，取最大。时间 O(N·M)。
from collections import deque
from typing import List
def find_largest_house_area(grid: List[List[int]]) -> int:
if not grid:
return 0
n, m = len(grid), len(grid[0])
seen = [[False] * m for _ in range(n)]
best = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and not seen[i][j]:
size = 0
q = deque([(i, j)])
seen[i][j] = True
while q:
r, c = q.popleft()
size += 1
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 1 and not seen[nr][nc]:
seen[nr][nc] = True
q.append((nr, nc))
best = max(best, size)
return bestimport java.util.*;
class Solution {
public int findLargestHouseArea(int[][] grid) {
int n = grid.length, m = grid[0].length;
boolean[][] seen = new boolean[n][m];
int best = 0;
int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !seen[i][j]) {
int size = 0;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{i, j}); seen[i][j] = true;
while (!q.isEmpty()) {
int[] cur = q.poll(); size++;
for (int k = 0; k < 4; k++) {
int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 && !seen[nr][nc]) {
seen[nr][nc] = true; q.add(new int[]{nr, nc});
}
}
}
best = Math.max(best, size);
}
}
return best;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLargestHouseArea(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> seen(n, vector<bool>(m, false));
int best = 0, dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !seen[i][j]) {
int size = 0;
queue<pair<int,int>> q;
q.push({i, j}); seen[i][j] = true;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop(); size++;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 1 && !seen[nr][nc]) {
seen[nr][nc] = true; q.push({nr, nc});
}
}
}
best = max(best, size);
}
}
return best;
}
};