2025年8月14日
小結：（17號整理14號的筆記，這輩子真是有了w(ﾟДﾟ)w）昨天摔了跤大的，今天好媽媽在家，松弛。省流：6道中等，明天只學了10分鐘嘻嘻

LeetCode

221. 最大正方形

221. 最大正方形

題目
在一個由 ‘0’ 和 ‘1’ 組成的二維矩陣內，找到只包含 ‘1’ 的最大正方形，并返回其面積。

f[i][j] 表示以 [i, j] 為右下角的最大正方形的邊長（動態規劃）
（前題 matrix[i][j] = 1）轉移方程：f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int I = matrix.size(), J = matrix[0].size(), ans = 0;int f[I + 1][J + 1];memset(f, '\0', sizeof(f));for (int i = 0; i < I; i++) {if (matrix[i][0] == '1') {f[i][0] = 1;ans = 1;}}for (int j = 0; j < J; j++) {if (matrix[0][j] == '1') {f[0][j] = 1;ans = 1;}}for (int i = 1; i < I; i++) {for (int j = 1; j < J; j++) {if (matrix[i][j] == '0') continue;f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;ans = max(ans, f[i][j]);}}return ans*ans;}
};

補充一下 cpp 中用函數初始化

方法	適用值	一維/二維寫法	特點 & 注意事項
memset	只能精確賦單字節重復的模式：0、-1、true、false、'\0' 其他整數比如 1、99 會出錯	memset(arr, val, sizeof(arr));	? 最快的批量賦值方法（底層 memset 匯編優化） ? 對于非字節重復模式（比如 99、1234）會把字節模式重復到整個 int，導致值錯誤
fill（一維）	任意可賦值類型（int、char、double、struct 等）	fill(arr.begin(), arr.end(), val);	? 支持任意值，安全可靠 ? 比 memset 慢一點，但基本 O(n)，大數組也夠快
fill（二維數組 && 原生數組）	任意可賦值類型	fill(&arr[0][0], &arr[0][0] + N*M, val);	? 一次性對整個二維賦值，避免嵌套循環 ? 必須確保是連續內存的原生數組（vector<vector<T>> 的每行不連續，要逐行 fill）

215. 數組中的第K個最大元素

215. 數組中的第K個最大元素

題目
給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設計并實現時間復雜度為 O(n) 的算法解決此問題。

qsort 的思路只是是單遍 qsort

class Solution {
public:int qsort(vector<int>& nums, int l, int r, int k) {if (l >= r) return nums[l];int i = l - 1, j = r + 1;int x = nums[(i + j) / 2];while (i < j) {do i++; while (nums[i] < x);do j--; while (nums[j] > x);if (i < j) swap(nums[i], nums[j]);}// [..., (l, ..., i=j=x_idx, ..., r), ...]// 要在 (l, ..., r) 里找到第k大的// i=j=x_idx 是 第 j-l+1 大 的if (j - l + 1 >= k) return qsort(nums, l, j, k);else return qsort(nums, j + 1, r, k - (j - l + 1));}int findKthLargest(vector<int>& nums, int k) {return qsort(nums, 0, nums.size() - 1, nums.size() - k + 1);}
};

Trie

208. 實現 Trie(前綴樹)
不喜歡 lc 那么生硬的（好吧其實是我不會 cpp
喜歡 y 總的，貼了 Acwing

#include <iostream>
#include <string.h>
#include <algorithm>using namespace std;
int node[100005][26], point = 1, cnt[100005];void insert(string str) {int strl = str.length(), nidx = 0;for (int i = 0; i < strl; i++) {int idx = str[i] - 'a';if (node[nidx][idx] == -1) {node[nidx][idx] = point++;}nidx = node[nidx][idx];}cnt[nidx]++;
}int query(string str) {int strl = str.length(), nidx = 0;for (int i = 0; i < strl; i++) {int idx = str[i] - 'a';if (node[nidx][idx] == -1) return 0;nidx = node[nidx][idx];}return cnt[nidx];
}int main() {int N;cin >> N;string op, str;fill(&node[0][0], &node[0][0] + 100005 * 26, -1);memset(cnt, 0, sizeof(cnt));while (N--) {cin >> op >> str;// cout << str << endl;if (op == "I") insert(str);else cout << query(str) << endl;}return 0;
}

207. 課程表

207. 課程表

題目
排課，有前置課程，實質就是個拓撲排序

維護入度們，依次用入度為0的

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> ne(numCourses);vector<int> frontcnt(numCourses, 0); // 入度數組// 建圖for (auto &pre : prerequisites) {int a = pre[0], b = pre[1]; ne[b].push_back(a); // b -> afrontcnt[a]++;}// 棧實現拓撲排序vector<int> st;for (int i = 0; i < numCourses; i++) {if (frontcnt[i] == 0) st.push_back(i);}int visited = 0;while (!st.empty()) {int u = st.back();st.pop_back();visited++;for (int v : ne[u]) {frontcnt[v]--;if (frontcnt[v] == 0) st.push_back(v);}}return visited == numCourses;}
};

200. 島嶼數量

200. 島嶼數量

題目
給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。

1. 并查集（如下 demo
2. 染色（dfs/bfs），把每輪的島嶼染成海洋

我能想到并查集也是個人物了つ﹏? 那么復雜，把二維先展開成一維（哎，一想也很好理解了

class Solution {
public:int rows, col, f[90005];int root(int idx) {if (idx != f[idx]) {f[idx] = root(f[idx]);}return f[idx];}void Union(int idx1, int idx2) {int root1 = root(idx1), root2 = root(idx2);if (root1 != root2) {f[root1] = root2;}}void P(int rows, int col){for (int i = 0; i < rows * col; i++) {if (f[i] == -1) cout << "-1" << ", ";else cout << root(i) << ", ";// ans_set.insert(f[i]);}cout << endl;}int numIslands(vector<vector<char>>& grid) {rows = grid.size(), col = grid[0].size();int direcions[2][2] = {{1, 0}, {0, 1}};for (int i = 0; i < rows; i++) {for (int j = 0; j < col; j++) {f[j + i * col] = j + i * col;}}for (int i = 0; i < rows; i++) {for (int j = 0; j < col; j++) {if (grid[i][j] == '0') {f[j + i * col] = -1;continue;}for (int d = 0; d < 2; d++) {int x = i + direcions[d][0], y = j + direcions[d][1];if (x >= rows || y >= col) continue;if (grid[x][y] == '0') continue;Union(j + col * i, x * col + y);}// P(rows, col);}}unordered_set<int> ans_set;for (int i = 0; i < rows * col; i++) {if (f[i] == -1) continue;ans_set.insert(root(i));}return ans_set.size();}
};

198. 打家劫舍

198. 打家劫舍

題目
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。

很簡單的 DP，f[i][0/1] 偷/不偷

class Solution {
public:int rob(vector<int>& nums) {int cnt = nums.size();int f[100][2];memset(f, 0, sizeof(f));f[0][0] = 0, f[0][1] = nums[0];for (int i = 1; i < cnt; i++) {f[i][0] = max(f[i - 1][0], f[i - 1][1]);f[i][1] = f[i - 1][0] + nums[i];}int ans = 0;for (int i = 0; i < cnt; i++) {ans = max(max(ans, f[i][0]), f[i][1]);}return ans;}
};

Acwing

xxx