137.位运算
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one=0,two=0;
for(auto x:nums){
one=(one^x)&~two;
two=(two^x)&~one;
}
return one;//背过
}
};
138.链表
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
for(auto p=head;p;p=p->next->next){//复制小弟
auto q=new Node(p->val);
q->next=p->next;
p->next=q;
}
for(auto p=head;p;p=p->next->next){//复制小弟指随机的小弟
if(p->random)
p->next->random=p->random->next;
}
auto dummy=new Node(-1),cur=dummy;
for(auto p=head;p;p=p->next){//把小弟链表扯出来
auto q=p->next;
cur=cur->next=q;
p->next=q->next;
}
return dummy->next;
}
};
139.dp+字符串哈希
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// int N=s.size();
// vector<int> dp=vector<int>(N+1,0);//表示当前子串能不能拆
// dp[0]=1;
// for(int i=1;i<=N;i++){
// for(int j=0;j<i;j++){
// if(dp[j]&&find(wordDict.begin(),wordDict.end(),s.substr(j,i-j))!=wordDict.end()){
// // 子串左边部分能并且右边也在字典里
// dp[i]=1;//当前子串可拆
// break;
// }
// }
// }
// return dp[N];
typedef unsigned long long ULL;
const int P=131;
unordered_set<ULL> hash;
for(auto& word:wordDict){
ULL h=0;
for(auto& c:word) h=h*P+c;
hash.insert(h);
}
int n=s.size();
vector<bool> f(n+1);//表示s[i]之前的字符串可以拆分
f[0]=true;//0表空
s=' '+s;
//遍历以字典里随便一个字符串结尾看能不能拆
for(int i=0;i<=n;i++){//遍历结尾字符串的起点
if(f[i]){//点之前可拆才能作起点
ULL h=0;
for(int j=i+1;j<=n;j++){//找起点之后可拆的部分标记
h=h*P+s[j];
if(hash.count(h)) f[j]=true;
}
}
}
return f[n];
}
};
142.链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL||head->next==NULL) return NULL;
auto slow=head->next,fast=head->next->next;
while(slow!=fast){
if(slow==NULL||fast==NULL||fast->next==NULL||fast->next->next==NULL) return NULL;
slow=slow->next,fast=fast->next->next;
if(slow==fast){//快慢指针
fast=head;
while(slow!=fast){
slow=slow->next,fast=fast->next;
}
return slow;
}
}
return slow;
}
};
143.链表
/**
* 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:
void reorderList(ListNode* head) {
if(!head) return;
int n=0;
for(auto p=head;p;p=p->next) n++;
auto mid=head;
for(int i=0;i<(n+1)/2-1;i++) mid=mid->next;
auto a=mid,b=a->next;
a->next=NULL;//尾指向空
for(int i=0;i<n/2;i++){//翻转后半段
auto c=b->next;
b->next=a,a=b,b=c;
}
auto p=head,q=a;
for(int i=0;i<n/2;i++){//后半段插入前半段
auto o=q->next;
q->next=p->next;
p->next=q;
p=q->next,q=o;
}
}
};
146.链表
class LRUCache {
public:
struct Node{
int key,value;
Node* left,* right;
Node(int x,int y){
left=NULL;
right=NULL;
key=x;
value=y;
}
}*L,*R;
int n;
map<int,Node*>hash;
void remove(Node* p){
p->right->left=p->left;
p->left->right=p->right;
}
void add(Node* p){
p->right=L->right;
p->left=L;
L->right->left=p;
L->right=p;
}
LRUCache(int capacity) {
n=capacity;
L=new Node(1,1),R=new Node(1,1);
L->right=R;
R->left=L;
}
int get(int key) {
if(hash.count(key)!=0){
int tmp=hash[key]->value;
remove(hash[key]);
add(hash[key]);
return tmp;
}else{
return -1;
}
}
void put(int key, int value) {
if(hash.count(key)){
Node* tmp=hash[key];
tmp->value=value;
remove(tmp);
add(tmp);
}else{
if(hash.size()==n){
auto p=R->left;
remove(p);
hash.erase(p->key);
Node* tmp=new Node(key,value);
hash[key]=tmp;
add(tmp);
}else{
Node* tmp=new Node(key,value);
hash[key]=tmp;
add(tmp);
}
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
150.栈
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for (int i = 0; i < n; i++) {
string token = tokens[i];
if (!(token == "+" || token == "-" || token == "*" || token == "/")) {
stk.push(atoi(token.c_str()));
} else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
switch (token[0]) {
case '+':
stk.push(num1 + num2);
break;
case '-':
stk.push(num1 - num2);
break;
case '*':
stk.push(num1 * num2);
break;
case '/':
stk.push(num1 / num2);
break;
}
}
}
return stk.top();
}
};
151.双指针+排序
162.二分
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=(l+r)/2;
if(nums[mid]<=nums[mid+1]){//如果小于右边，右边一定有，如果小于左边左边一定有
l=mid+1;
}else{
r=mid;
}
}
return l;
}
};
165.双指针
class Solution {
public:
int compareVersion(string v1, string v2) {
for(int i=0,j=0;i<v1.size()||j<v2.size();){
int a=i,b=j;
while(a<v1.size()&&v1[a]!='.') a++;
while(b<v2.size()&&v2[b]!='.') b++;
int x=a==i?0:stoi(v1.substr(i,a-i+1));
int y=b==j?0:stoi(v2.substr(j,b-j+1));
if(x<y) return -1;
if(x>y) return 1;
i=a+1,j=b+1;
}
return 0;
}
};