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) { // 遍历输入字符串 s
if (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;
}
};
标签:ListNode,string,int,Solution,Offer68,next,ans,Day1
From: https://www.cnblogs.com/albertmak/p/18487441