当前位置：首页 > news >正文

机试备考笔记 7/31

news 2025/8/8 13:35:02

2025年8月7日
小结：省流，7道，真正有效2道，后面4道都是晚上一边被迫听小孩被骂一边写的，特别不用脑子

LeetCode

48. 旋转图像

题目
就是把一个矩阵顺时针旋转90°，要求原地操作

法一：拿个数组存一个片区（无论奇数偶数，都会是4个片区，顶多奇数的中间多一个），把被覆盖的存 tmp 里，循环做一下

法二：又是旋转

在这里插入图片描述

直接贴 demo 了

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 水平翻转for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {swap(matrix[i][j], matrix[n - i - 1][j]);}}// 主对角线翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {swap(matrix[i][j], matrix[j][i]);}}}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/rotate-image/solutions/526980/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

54. 螺旋矩阵

题目
按顺时针螺旋输出矩阵

w(ﾟДﾟ)w 刚开始理解错了，以为是螺旋移动一个，swap 都写出来了，结果是把矩阵输出就行啊

法一：模拟
这个就像机器人走路，碰壁就转向，然后发现正好是👉👇👈👆循环的四个动作，用 directions 存四个
遇到边界 or visited 的就专学
demo

class Solution {
public:vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};vector<int> updateXY(int x, int y, int now_order) {int x1 = x + directions[now_order][0];int y1 = y + directions[now_order][1];return {x1, y1};}vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> ans;int row = matrix.size(), col = matrix[0].size();// bool visited[row][col];vector<vector<bool>> visited(row, vector<bool>(col, false));int now_order = 0, cnt = 1, x = 0, y = 0, x1, y1;vector<int> tmp;ans.push_back(matrix[x][y]);while(cnt < row * col) {visited[x][y] = true;tmp = updateXY(x, y, now_order);x1 = tmp[0], y1 = tmp[1];if (x1 == row || x1 == -1 || y1 == col || y1 == -1 || visited[x1][y1]) {now_order = (now_order + 1) % 4;}tmp = updateXY(x, y, now_order);x = tmp[0], y = tmp[1];ans.push_back(matrix[x][y]);cnt++;}return ans;}
};

遇到的语法 bug 😓

二维数组初始化错误，int directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];，正确写法 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};，或嵌套vector vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};，python 你真的害惨我了…
结构化绑定错误，vector<int> updateXY() 可以返回 {x, y}，但是不能用 {x, y} = updateXY() 去接收，老实写 vector<int> tmp 去收再分给 x, y
vector<vector<int>> matrix 用 int row = matrix.size() int col = matrix[0].size() 接收行列数
不能用变量长度数组，在 3 的后面写 bool visited[row][col]; 不行，因为数组的大小必须是 常量表达式，而 row 和 col 是运行时才知道的。改成 vector<vector<bool>> visited(row, vector<bool>(col, false));

俺不想手搓法二了，cv怪

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> res;if (matrix.empty() || matrix[0].empty()) return res;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while (top <= bottom && left <= right) {// 从左到右for (int j = left; j <= right; j++) res.push_back(matrix[top][j]);top++;// 从上到下for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);right--;// 从右到左if (top <= bottom) {for (int j = right; j >= left; j--) res.push_back(matrix[bottom][j]);bottom--;}// 从下到上if (left <= right) {for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);left++;}}return res;}
};

240. 搜索二维矩阵 II

题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列，每列的元素从上到下升序排列。

用二分查找，哎呀我本来好想动态的行列一起动态的（动毛线）
最后变成粗粗的二分得到有效行，然后一行行二分一下

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {auto it = upper_bound(matrix.begin(), matrix.end(), target, [](int val, const vector<int>& row) {return val < row[0];});int row_idx;if (it == matrix.begin()) {return false;} else if (it == matrix.end()){row_idx = matrix.size() - 1;} else {row_idx = it - matrix.begin() - 1;}for (int row = 0; row <= row_idx; row++) {auto item = lower_bound(matrix[row].begin(), matrix[row].end(), target);if (item != matrix[row].end() && *item == target) {return true;}}return false;}
};

cpp 内置二分复习 头文件 <algorithm>

函数名	返回值	说明
`binary_search`	`bool`	是否存在目标值
`lower_bound`	迭代器	返回第一个 ≥ target 的元素
`upper_bound`	迭代器	返回第一个 > target 的元素

基础用法

#include <algorithm> // 引入头文件
#include <vector>vector<int> nums = {1, 2, 4, 6, 7};
int target = 4;bool found = binary_search(nums.begin(), nums.end(), target); 
// true
auto it = lower_bound(nums.begin(), nums.end(), target);      
// 指向 4
auto it2 = upper_bound(nums.begin(), nums.end(), target);     
// 指向 6//auto it用法：转成索引idx、解引用获取值value
if (it != nums.end()) {cout << "idx= " << it - nums.begin() << ", val= " << *it << endl;
}

lambda 用法
以二维 int 的 vector 为例，要在第 0 列作二分

auto it = upper_bound(matrix.begin(), matrix.end(), target,[](int val, const vector<int>& row) {return val < row[0];  // 只比较 row[0]});

[](){} 里参数列表的名字是自定义的，val 就是传入的目标值 target。我们知道 vector<int> 传入的是很多 int，这次 vector<vector<int>> 传入的自然是 vector<int>，但是我们只对第 0 列作二分，row 是从 matrix 容器里依次取出的元素（也就是 vector<int>），只取第 0 列，自然是 row[0] 了

ps. auto 很好用，但是如果要重用的话，仔细思考一下它自动承袭的是什么类型，以这题为例 upper_bound 里的是 vector<vector<int>>::iterator，lower_bound 里的是 vector<int>::iterator

160. 相交链表

题目

超 ez 思路，用 unordered_set 存，遍历存 A 链路，B 链路从头找第一个 set 里有的

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> visited;ListNode *tmp = headA;while (tmp != nullptr) {visited.insert(tmp);tmp = tmp -> next;}tmp = headB;while (tmp != nullptr) {if (visited.count(tmp)) {return tmp;}tmp = tmp -> next;}return nullptr;}
};

（基本就是官方题解的CV）

复习了指针的用法，set 里存的是 ListNode 的指针，unordered_set<ListNode*> visited;
NULL 可用，但是更推荐用 nullptr

K神的解法，离人很远，离神不远了 hhh

206. 反转链表

题目
一个单向链表，反转就行

emmm，指针忘光了，复习了一下

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *current = head, *pre = nullptr, *next;while (current != nullptr) {next = current -> next;current -> next = pre;pre = current;current = next;}return pre;}
};

234. 回文链表

题目：就是一个单向链表，让判断是不是回文的

太笨笨的题目了，cv到数组做

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* current = head;vector<int> values;int cnt = 0;while (current != nullptr) {values.push_back(current->val);current = current -> next;cnt++;}for (int i = 0, j = cnt - 1; i < cnt && j >= 0; i++, j--) {if (i >= j) return true;if (values[i] != values[j]) {return false;}}}
};

141. 环形链表

题目：就是判断一个单向链表有没有环

存个 set，重复了就是有环
记错了，有个算法可以处理负环，还以为这个环也可以呢

在这里插入图片描述

（来自主包的 Acwing）

class Solution {
public:bool hasCycle(ListNode *head) {unordered_set<ListNode*> visited;ListNode *tmp = head;while(tmp != nullptr) {if (visited.count(tmp)) return true;visited.insert(tmp);tmp = tmp -> next;}return false;}
};