day1
剑指 Offer 09. 用两个栈实现队列 – 力扣（LeetCode）
class CQueue {
private:
stack<int> PUSH;
stack<int>POP;
public:
void appendTail(int value) {PUSH.push(value);
}
int deleteHead() {if(POP.empty())
{
int x = 0;
while(!PUSH.empty())
{x = PUSH.top();
POP.push(x);
PUSH.pop();}
}
if(POP.empty())return -1;
int x = POP.top();
POP.pop();
return x;
}
};剑指 Offer 30. 蕴含 min 函数的栈 – 力扣（LeetCode）
class MinStack {
private:
stack<int>st;
stack<int>_min;
public:
void push(int x) {st.push(x);
if(_min.empty() || _min.top()>=x)
_min.push(x);
}
void pop() {int x = st.top();
st.pop();
if(x == _min.top())
{_min.pop();
}
}
int top() {return st.top();
}
int min() {return _min.top();
}
};day2
剑指 Offer 06. 从尾到头打印链表 – 力扣（LeetCode）
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
ListNode *t = head;
stack<int>st;
vector<int>v;
while(t != nullptr)
{st.push(t->val);
t = t->next;
}
while(!st.empty())
{int x = st.top();
v.push_back(x);
st.pop();}
return v;
}
};剑指 Offer 24. 反转链表 – 力扣（LeetCode）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
stack<int>st;
ListNode *t = head;
while(t!=nullptr)
{st.push(t->val);
t = t->next;
}
ListNode *h = new ListNode;
h ->next = NULL;
h ->val = 0;
t = h;
while(!st.empty()) {int x = st.top();
st.pop();
ListNode *temp = new ListNode;
temp->next = NULL;
temp->val = x;
t->next = temp;
t = temp;
}
return h->next;
}
};剑指 Offer 35. 简单链表的复制 – 力扣（LeetCode）
class Solution {
public:
Node* copyRandomList(Node* head)
{
Node*t = head;
unordered_map<Node*,Node*> m;
while(t != nullptr)
{m[t] = new Node(t->val);
t = t->next;
}
t = head;
while(t!=nullptr)
{m[t] ->next = m[t->next];
m[t] ->random = m[t->random];
t = t->next;
}
return m[head];
}
};day3
剑指 Offer 05. 替换空格 – 力扣（LeetCode）
class Solution {
public:
string replaceSpace(string s) {
string ans;
for(auto x : s)
{if(x == ' ')
ans += "%20";
else
ans += x;
}
return ans;
}
};
//cout<<typeid(x).name()<<endl; 得悉 x 的类型是 char剑指 Offer 58 – II. 左旋转字符串 – 力扣（LeetCode）
class Solution {
public:
string reverseLeftWords(string s, int n) {string s1 = s.substr(0,n);
string s2 = s.substr(n);
s = s2 + s1;
return s;
}
};day4
剑指 Offer 03. 数组中反复的数字 – 力扣（LeetCode）
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {int count[100006] = {0};
for(auto x:nums)
{++count[x];
if(count[x]>1)
{return x;}
}
return -1;
}
};剑指 Offer 53 – I. 在排序数组中查找数字 I – 力扣（LeetCode）
class Solution {
public:
int search(vector<int>& nums, int target) {
int ans = 0;
int pos = lower_bound(nums.begin(),nums.end(), target) - nums.begin();
cout<<pos<<endl;
while(pos != nums.size())
{if(nums[pos] == target)
{++ans;}
++pos;
}
return ans;
}
};
// 留神这个函数返回的 pos 是下标，而不是迭代器 剑指 Offer 53 – II. 0～n- 1 中缺失的数字 – 力扣（LeetCode）
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0; i <= nums.size(); ++i)
{if(i != nums[i])
{
ans = i;
break;
}
}
return ans;
}
};day5
剑指 Offer 04. 二维数组中的查找 – 力扣（LeetCode）
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int i = 0;
for(; i < matrix.size(); ++i)
{auto it = lower_bound(matrix[i].begin(), matrix[i].end(), target);
if(it != matrix[i].end()&&*it == target)// 返回的 it 也可能是野指针，咱们不能拜访野指针
break;
}
if(i < matrix.size())
return true;
return false;
}
};剑指 Offer 11. 旋转数组的最小数字 – 力扣（LeetCode）
class Solution {
public:
int minArray(vector<int>& numbers) {sort(numbers.begin(),numbers.end());
return numbers[0];
}
};剑指 Offer 50. 第一个只呈现一次的字符 – 力扣（LeetCode）
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> kv;
for(auto x:s)
{kv[x]++;
}
for(auto x:s)
{if(kv[x] == 1)
{return x;}
}
return ' ';
}
};day6
剑指 Offer 32 – I. 从上到下打印二叉树 – 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
queue<TreeNode*>q;
vector<int>ans;
if(root)q.push(root);
while(!q.empty())
{TreeNode* t = q.front();
if(t)
ans.push_back(t->val);
q.pop();
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
return ans;
}
};剑指 Offer 32 – II. 从上到下打印二叉树 II – 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*>q;
vector<vector<int>>ans;
if(root)q.push(root);
while(!q.empty())
{int size = q.size();
vector<int> temp;
for(int i=0;i<size;++i)
{TreeNode* t = q.front();
q.pop();
temp.push_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
ans.push_back(temp);
}
return ans;
}
};剑指 Offer 32 – III. 从上到下打印二叉树 III – 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*>q;
vector<vector<int>>ans;
bool f = false;
if(root)q.push(root);
while(!q.empty())
{int size = q.size();
vector<int> temp;
for(int i=0;i<size;++i)
{TreeNode* t = q.front();
q.pop();
temp.push_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
if(f==true)reverse(temp.begin(),temp.end());
ans.push_back(temp);
f = !f;
}
return ans;
}
};