字符串
左旋转字符串
- 申请空间，取模运算
class Solution {
public:
string reverseLeftWords(string s, int n) {
string ans=s;
for(int i=0;i!=s.size();++i)
{
ans[(i-n+s.size())%s.size()]=s[i];
}
return ans;
}
};
- 子串合并
class Solution {
public:
string reverseLeftWords(string s, int n) {
return s.substr(n,s.size()-n)+s.substr(0,n);
}
};
状态机
剑指 Offer 20. 表示数值的字符串
剑指 Offer 67. 把字符串转换成整数
链表
反转
- 头插法
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
ListNode* h = new ListNode;
while(head)
{
auto temp = h->next;
h->next=head;
auto next = head->next;
head->next=temp;
head=next;
}
vector<int>ans;
h=h->next;
while(h)
{
ans.push_back(h->val);
h=h->next;
}
return ans;
}
};
- 栈
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
deque<ListNode*>que;
while(head)
{
que.push_back(head);
head=head->next;
}
vector<int> ans;
while(!que.empty())
{
ans.push_back(que.back()->val);
que.pop_back();
}
return ans;
}
};
- 递归
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
if(!head) return {};
auto temp = reversePrint(head->next);
temp.push_back(head->val);
return temp;
}
};
- 头插法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* h = new ListNode;
while(head)
{
auto hnext = h->next;
auto headnext = head->next;
h->next=head;
head->next=hnext;
head=headnext;
}
return h->next;
}
};
- 递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
auto h = reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return h;
}
};
- 栈
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head)return head;
deque<ListNode*>que;
while(head)
{
que.push_back(head);
head=head->next;
}
ListNode* ans = nullptr;
ans = que.back();
que.pop_back();
auto p =ans;
while(!que.empty())
{
p->next=que.back();
p=p->next;
que.pop_back();
}
p->next = nullptr;
return ans;
}
};
复杂链表复制
- 拼接拆分
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)
return nullptr;
for(Node* i=head;i!=nullptr;i=i->next->next)
{
Node* newNode = new Node(i->val);
newNode->next=i->next;
i->next=newNode;
}
for(Node*i=head;i!=nullptr;i=i->next->next)
{
i->next->random=(i->random==nullptr)?nullptr:i->random->next;
}
Node* outNode = head->next;
for(Node*i=head;i!=nullptr;i=i->next)
{
Node* newNode = i->next;
i->next=newNode->next;
newNode->next=(newNode->next==nullptr)?nullptr:newNode->next->next;
}
return outNode;
}
};
双指针
删除链表节点
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* h = new ListNode;
h->next = head;
auto pre = h;
while(head)
{
if(head->val == val)
{
pre->next=head->next;
return h->next;
}
pre=pre->next;
head=head->next;
}
return h->next;
}
};
链表中倒数第k个节点
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
auto p1=head;
for(int i=0;i!=k;++i) p1=p1->next;
auto p2 = head;
while(p1)
{
p1=p1->next;
p2=p2->next;
}
return p2;
}
};
合并有序链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode;
auto p =head;
while(l1 && l2)
{
if(l1->val<l2->val)
{
p->next = l1;
p=p->next;
l1=l1->next;
}
else
{
p->next = l2;
p=p->next;
l2=l2->next;
}
}
if(l1)
{
p->next = l1;
}
if(l2)
{
p->next = l2;
}
return head->next;
}
};
两个链表的第一个公共节点
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto p1=headA;
auto p2=headB;
while(p1!=p2)
{
p1=p1?p1->next:headA;
p2=p2?p2->next:headB;
}
return p1;
}
};
调整数组顺序使奇数位于偶数前面
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int l=0;
int r=nums.size()-1;
while(l<r)
{
while(l<r && nums[l]%2==1) ++l;
while(l<r && nums[r]%2==0) --r;
swap(nums[l],nums[r]);
}
return nums;
}
};
和为s的两个数字
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int l=0;
int r=nums.size()-1;
while(l<r)
{
while(l<r && nums[l]+nums[r]<target) ++l;
while(l<r && nums[l]+nums[r]>target) --r;
if(l<r && nums[l]+nums[r]==target) return {nums[l],nums[r]};
}
return {};
}
};
翻转单词顺序
class Solution {
public:
string reverseWords(string s) {
if(s.empty()) return s;
int i=s.size()-1;
int j=s.size()-1;
while(i>=0 && s[i]==' ')
{
--i;--j;
}
string ans;
while(j>=0)
{
while(i>=0 && s[i]!=' ') --i;
ans+=s.substr(i+1,j-i);
ans+=" ";
while(i>=0 && s[i]==' ') --i;
j=i;
}
if(!ans.empty()) ans.pop_back();
return ans;
}
};
栈与队列
辅助栈
class CQueue {
public:
stack<int>q1;
stack<int>q2;
CQueue() {
}
void appendTail(int value) {
q2.push(value);
}
int deleteHead() {
if(!q1.empty())
{
auto ans = q1.top();
q1.pop();
return ans;
}
while(!q2.empty())
{
q1.push(q2.top());
q2.pop();
}
if(!q1.empty())
{
auto ans = q1.top();
q1.pop();
return ans;
}
else
{
return -1;
}
}
};
class MinStack {
public:
/** initialize your data structure here. */
stack<int>que;
stack<int>minque;
MinStack() {
minque.push(INT_MAX);
}
void push(int x) {
que.push(x);
minque.push(minque.top()<x?minque.top():x);
}
void pop() {
que.pop();
minque.pop();
}
int top() {
return que.top();
}
int min() {
return minque.top();
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>que;
vector<int> ans;
for(int i=0;i!=nums.size();++i)
{
while(!que.empty() && que.back()<nums[i]) que.pop_back();
que.push_back(nums[i]);
if(i>=k && que.front()==nums[i-k]) que.pop_front();
if(i>=k-1) ans.push_back(que.front());
}
return ans;
}
};
class MaxQueue {
public:
deque<int>que;
deque<int>maxque;
MaxQueue() {
}
int max_value() {
if(que.empty())return -1;
return maxque.front();
}
void push_back(int value) {
while(!maxque.empty() && maxque.back()<value) maxque.pop_back();
maxque.push_back(value);
que.push_back(value);
}
int pop_front() {
if(que.empty()) return -1;
if(maxque.front()==que.front()) maxque.pop_front();
auto ans = que.front();
que.pop_front();
return ans;
}
};
模拟
顺时针打印矩阵
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.empty())return {};
int l=0,r=matrix[0].size()-1,up=0,down=matrix.size()-1;
vector<int>ans;
while(l<=r && up<=down)
{
for(int i=l;i<=r;++i)
{
ans.push_back(matrix[up][i]);
}
if(++up>down) break;
for(int i=up;i<=down;++i)
{
ans.push_back(matrix[i][r]);
}
if(--r<l)break;
for(int i=r;i>=l;--i)
{
ans.push_back(matrix[down][i]);
}
if(--down<up)break;
for(int i=down;i>=up;--i)
{
ans.push_back(matrix[i][l]);
}
if(++l>r)break;
}
return ans;
}
};
栈的压入、弹出序列
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int>que;
int i=0;
for(auto num:pushed)
{
que.push(num);
while(i<popped.size() && !que.empty() && popped[i]==que.top())
{
++i;
que.pop();
}
}
return que.empty();
}
};