LCR 120. 寻找文件副本
class Solution { // offer 03
public:int findRepeatDocument(vector<int>& documents) { // 方法:哈希表,查找元素是否存在unordered_set<int> vsi;for(int i=0;i<documents.size();i++){if(vsi.count(documents[i])){return documents[i];} // count()>0说明已经出现过vsi.insert(documents[i]); // set中没有就放入}return -1; // 时间O(n) , 空间O(n),n为doc.size()}
};//////////////////////////////////////////////////////////////////////
// 排序后,判断相邻是否相等?时间O(nlog),空间O(logn)
class Solution {
public:int findRepeatDocument(vector<int>& documents) {sort(documents.begin(),documents.end());for(int i=0;i<documents.size();i++){if(documents[i]==documents[i+1]){return documents[i];}}return -1;}
};
240. 搜索二维矩阵 II
class Solution { // 从左下开始找,时间O(m+n),mn问matrix行数列数,空间O(1)
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i=matrix.size()-1; // 最后一行int j=0; // 第一列while(i>=0 && j<matrix[0].size()){if(matrix[i][j]==target) return true;else if(matrix[i][j]>target) i--; // 说明右边都比target大,往上一行找else j++; // < 要往右边找}return false;}
};/*
vector<vector<int>> matrix = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}
};matrix.size() 将返回 3,因为有三行。
matrix[0].size() 将返回 4,因为第一行有四个元素。
*/
LCR 122. 路径加密(单个字符替换)
class Solution {
public:string pathEncryption(string path) {string ans=path; // 创建path副本for(auto& c:ans){if(c=='.'){ c=' ';}}return ans;}
};
类似:面试题 05. 替换空格 (多个字符替换)
题目描述: 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
示例 1:
输入:s = "We are happy."
输出:"We%20are%20happy."
#include <iostream>
#include <string>
using namespace std;class Solution {
public:string replaceSpace(string s) {string ans;for (const char& c : s) { // 遍历输入字符串 sif (c == ' ') { ans += "%20"; } // 替换空格为 "%20"else { ans += c; } // 其他字符直接追加到string}return ans;}
};int main() {const string s = "We are happy.";Solution sol;const string result = sol.replaceSpace(s);cout << result << endl; // 输出: "We%20are%20happy."return 0;
}
LCR 123. 图书整理 I 或 从尾到头打印链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution { // 将链表元素放入数组,反转数组
public:vector<int> reverseBookList(ListNode* head) {vector<int> result;ListNode* curr=head;while(curr!=nullptr){result.push_back(curr->val);curr=curr->next;}reverse(result.begin(),result.end());return result;}
};