水
class Solution {
public:
char findTheDifference(string s, string t) {
unordered_map<char,int> cnt;
for(auto c:s) cnt[c]++;
for(auto c:t) cnt[c]--;
for(auto [a,b]:cnt){
if(b){
return a;
}
}
return 100;
}
};
dfs
class Solution {
public:
int lengthLongestPath(string input) {
stack<int> stk;//遍历树
int res=0;
for(int i=0,sum=0;i<input.size();i++){//i++是要过掉\n
int k=0;
while(i<input.size()&&input[i]=='\t') i++,k++;//算有几层
while(stk.size()>k) sum-=stk.top(),stk.pop();//回溯先把上次遍历的吐掉
int j=i;
while(j<input.size()&&input[j]!='\n') j++;//找到结尾
int len=j-i;
stk.push(len),sum+=len;
if(input.substr(i,len).find('.')!=-1){//.文件才判断
int res1=sum+stk.size()-1;//记得算上\的长度
res=max(res,res1);
}
i=j;
}
return res;
}
};
水
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> hash;
for(auto c:s) hash[c]++;
for(int i=0;i<s.size();i++){
if(hash[s[i]]==1){
return i;
}
}
return -1;
}
};
dfs
class Solution {
public:
vector<int> res;
vector<int> lexicalOrder(int n) {
for(int i=1;i<=9;i++){//开头不能为0
dfs(i,n);
}
return res;
}
void dfs(int x,int y){
if(x<=y) res.push_back(x);//遍历树
else return;//不合法的就剪去
for(int i=0;i<=9;i++){
dfs(x*10+i,y);
}
}
};
dfs
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
NestedInteger deserialize(string s) {
int u=0;
return dfs(s,u);
}
NestedInteger dfs(string& s,int& u){
NestedInteger res;
if(s[u]=='['){
u++;//[
while(s[u]!=']') res.add(dfs(s,u));//子节点
u++;//]
if(u<s.size()&&s[u]==',') u++;//,
}else{
int k=u;
while(k<s.size()&&s[k]!=','&&s[k]!=']') k++;
res.setInteger(stoi(s.substr(u,k-u)));
if(k<s.size()&&s[k]==',') k++;//,
u=k;
}
return res;
}
};
洗牌算法
class Solution {
public:
vector<int> a;
Solution(vector<int>& nums) {
a=nums;
}
vector<int> reset() {
return a;
}
vector<int> shuffle() {
auto b=a;
int n=a.size();
for(int i=0;i<n;i++){
swap(b[i],b[i+rand()%(n-i)]);
}
return b;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/
水
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> cnt;
for(auto c:magazine) cnt[c]++;
for(auto c:ransomNote){
if(!cnt[c]) return false;
cnt[c]--;
}
return true;
}
};
上台表演算法
/**
* 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:
ListNode* h;
Solution(ListNode* head) {
h=head;
}
int getRandom() {
int c=-1,n=0;//c是台，n是有几个人了
for(auto i=h;i;i=i->next){
n++;
if(rand()%n==0) c=i->val;
}
return c;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/
设计
class RandomizedSet {
public:
unordered_map<int,int> hash;
vector<int> nums;
RandomizedSet() {
}
bool insert(int val) {
if(hash.count(val)==0){
nums.push_back(val);
hash[val]=nums.size()-1;
return true;
}
return false;
}
bool remove(int val) {
if(hash.count(val)){
int y=nums.back();
int px=hash[val],py=hash[y];
swap(nums[px],nums[py]);//先交换数组
nums.pop_back();//删数组
swap(hash[val],hash[y]);//交换hash
hash.erase(val);//删hash
return true;
}
return false;
}
int getRandom() {
return nums[rand()%nums.size()];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/
水
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> hash;
for(auto c:s) hash[c]++;
for(int i=0;i<s.size();i++){
if(hash[s[i]]==1){
return i;
}
}
return -1;
}
};