剑指 Offer 05. 替换空格
class Solution {
public:
string replaceSpace(string s) {
int len = s.size();
string g;
for(int i = 0; i < len; i++)
{
if(s[i] == ' ')
{
g += "%20";
continue;
}
g += s[i];
}
return g;
}
};
剑指 Offer 58 - II. 左旋转字符串
class Solution {
public:
void Reverse(string &a,int left,int right)
{
while(left < right)
{
char temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
string reverseLeftWords(string s, int n) {
int len = s.size();
if(n >= len)
{
n %= len;
}
Reverse(s,0,n-1);
Reverse(s,n,len-1);
Reverse(s,0,len-1);
return s;
}
};
剑指 Offer 67. 把字符串转换成整数❤️
class Solution {
public:
int strToInt(string str)
{
int len = str.size();
int i = 0;
int flag = 1;//标记正负
long long num = 0;//返回转化后的数字
while(str[i] == ' ')//去掉前导空格
{
i++;
}
if(str[i] == '+'||str[i] == '-')
{
if(str[i] =='-')
flag = -flag;
i++;
}
while(i < len && str[i] >= '0' && str[i] <= '9')
{
num = num*10+(str[i]-'0')*flag;
i++;
if(flag == -1 && num < INT_MIN )
{
return INT_MIN;
}
if(flag == 1 && num > INT_MAX )
{
return INT_MAX;
}
}
if(i != len)//没有遍历完就是错误,直接返回当前的值
{
return num;
}
return num;
}
};
剑指 Offer 06. 从尾到头打印链表
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int>ret;
while(head!=NULL)
{
ret.insert(ret.begin(),head->val);
head = head->next;
}
return ret;
}
};
剑指 Offer 24. 反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr)
{
return nullptr;
}
ListNode * n1 = nullptr;
ListNode * n2 = head;
ListNode * n3 = head->next;
while(n2 != nullptr)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3 != nullptr)
{
n3 = n3->next;
}
}
return n1;
}
};
剑指 Offer 35. 复杂链表的复制
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) {
Node * cur = head;
while(cur)
{
Node * ne = cur->next;
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->val = cur->val;
newNode->next = ne;
cur->next = newNode;
cur = ne;
}
cur = head;
while(cur)
{
Node * ne = cur->next;
Node * nene = cur->next->next;
if(cur->random == nullptr)
{
cur->next->random = nullptr;
}
else
{
cur->next->random = cur->random->next;
}
cur = nene;
}
Node * newNode1 =nullptr;
Node * tail = nullptr;
cur = head;
while(cur)
{
Node * ne = cur->next;
Node * nene = cur->next->next;
if(newNode1 == nullptr)
{
newNode1 = tail = ne;
}
else
{
tail->next = ne;
tail = tail->next;
}
cur->next = nene;
cur = nene;
}
return newNode1;
}
};
剑指 Offer 18. 删除链表的节点
/*
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode * cur = head;
ListNode * prev = nullptr;
while(cur)
{
ListNode * ne = cur->next;
if(cur->val == val)
{
if(head == cur)//头删
{
head = ne;
cur = head;
}
else
{
prev->next = ne;
cur = prev->next;
}
}
else
{
prev = cur;
cur = ne;
}
}
return head;
}
};
剑指 Offer 22. 链表中倒数第k个节点
/*
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//快慢指针法
ListNode * slow = head;
ListNode * fast = head;
while(k--)
{
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
剑指 Offer 25. 合并两个排序的链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
ListNode * newHead = (ListNode*)malloc(sizeof(ListNode));
newHead->next = nullptr;
ListNode * tail = newHead;
while(l1 != nullptr && l2 != nullptr)
{
if(l1->val <= l2->val)
{
tail->next = l1;
tail = tail->next;
l1 = l1->next;
}
else
{
tail->next = l2;
tail = tail->next;
l2 = l2->next;
}
}
if(l1 != nullptr)
{
tail->next = l1;
}
if(l2 != nullptr)
{
tail->next = l2;
}
return newHead->next;
}
};
剑指 Offer 52. 两个链表的第一个公共节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * curA = headA;
ListNode * curB = headB;
int countA = 0;
int countB = 0;
while(curA)
{
curA = curA->next;
countA++;
}
while(curB)
{
curB = curB->next;
countB++;
}
if(countA > countB)
{
countA -= countB;
while(countA--)
{
headA = headA->next;
}
}
else
{
countB -= countA;
while(countB--)
{
headB = headB->next;
}
}
while(headA != nullptr && headB != nullptr)
{
if(headA == headB)
{
return headA;
}
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
};
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
class Solution {
public:
void exchange(vector<int>&nums,int len)
{
int * ret = (int*)malloc(sizeof(int) * (len + 1));
int j = 0;
for(int i = 0; i < len; i++)
{
if((nums[i] & 1) == 1)
{
ret[j++] = nums[i];
}
}
for(int i = 0; i < len; i++)
{
if((nums[i] & 1 )== 0)
{
ret[j++] = nums[i];
}
}
for(int i = 0; i < len; i++)
{
nums[i] = ret[i];
}
}
vector<int> exchange(vector<int>& nums) {
int len = nums.size();
exchange(nums,len);
return nums;
}
};
剑指 Offer 57. 和为s的两个数字
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
unordered_map<int,int>hash;
vector<int>ret;
for(int i = 0; i < len; i++)
{
int num = target - nums[i];
if(hash.count(num))
{
ret.push_back(num);
ret.push_back(nums[i]);
break;
}
hash.insert({nums[i],i});
}
return ret;
}
};
剑指 Offer 59 - I. 滑动窗口的最大值
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int len = nums.size();
deque<int>q;
vector<int>ret;
for(int i = 0; i < nums.size(); i++)
{
if(!q.empty() && i - k + 1 > q[0]) q.pop_front();//下标小于滑动窗口则头删
//形成单调递增的队列
while(!q.empty() && nums[q[q.size()-1]] <= nums[i]) q.pop_back();
q.push_back(i);
if(i >= k - 1)
{
ret.push_back(nums[q[0]]);
}
}
return ret;
}
};
剑指 Offer 58 - I. 翻转单词顺序
class Solution {
public:
string reverseWords(string s) {
string ret;
int i = 0;
int num = s.size();
while(i < num)//处理前置空格
{
if(s[i] != ' ')
{
break;
}
i++;
}
while(s.size() > 0)//处理后置空格
{
int num = s.size();
if(s[num-1] != ' ')
{
break;
}
s.pop_back();
}
int len = s.size();
if(len == 0) return s;
while(i < len)
{
int cnt = 0;
int begin = ret.size();
while(i < len && s[i] != ' ')
{
ret += s[i];
i++;
}
int end = ret.size();
reverse(ret.begin()+begin,ret.begin()+end);//部分反转
while(i < len && s[i] == ' ')
{
cnt++;
if(cnt == 1)
{
ret += s[i];
}
i++;
}
}
int num1 = ret.size();
reverse(ret.begin(),ret.end());
return ret;
}
};
剑指 Offer 09. 用两个栈实现队列
class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
p_push.push(value);
}
int deleteHead() {
if(p_push.empty() && p_pop.empty())
{
return -1;
}
if(!p_pop.empty())
{
int top = p_pop.top();
p_pop.pop();
return top;
}
else
{
while(!p_push.empty())
{
p_pop.push(p_push.top());
p_push.pop();
}
}
int top = p_pop.top();
p_pop.pop();
return top;
}
private:
stack<int>p_push;
stack<int>p_pop;
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
剑指 Offer 30. 包含min函数的栈❤️
class MinStack {
stack<int>x_push;
stack<int>min_push;
public:
/** initialize your data structure here. */
MinStack() {
min_push.push(INT_MAX);
}
void push(int x)
{
x_push.push(x);
min_push.push(std::min(min_push.top(),x));//每次插入插最小的值进去,和最小值的栈顶比较。
}
void pop() {
x_push.pop();
min_push.pop();
}
int top() {
return x_push.top();
}
int min() {
return min_push.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
剑指 Offer 59 - II. 队列的最大值❤️
class MaxQueue {
public:
deque<int>val;
deque<int>vmax;
MaxQueue() {
}
int max_value() {
if(vmax.empty())
{
return -1;
}
return vmax.front();
}
void push_back(int value) {
while((!vmax.empty()) && (vmax.back() < value))//单调递减的队列
{
vmax.pop_back();
}
val.push_back(value);
vmax.push_back(value);
}
int pop_front() {
if(val.empty())
{
return -1;
}
int ans = vmax.front();
if(ans == val.front())//只有和最大值相等才需要删除,跟滑动窗口差不多
{
vmax.pop_front();
}
int front = val.front();
val.pop_front();
return front;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
剑指 Offer 29. 顺时针打印矩阵❤️
class Solution {
private:
bool flag[110][110]= {false};
int d[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>ret;
if (matrix.size() == 0 || matrix[0].size() == 0) return ret;
int rows = matrix.size(),cols = matrix[0].size();
int sum = rows * cols;
int tal = 0;
int row = 0,col = 0;
int dir = 0;
for(int i = 0; i < sum; i++)
{
ret.push_back( matrix[row][col]);
flag[row][col] = true;
int a = row + d[dir][0],b = col + d[dir][1];
//如果越界或者,或者已经插入的数据那么就走向量的下一个
if(a < 0 || a >= rows || b < 0 || b >= cols || flag[a][b])
{
dir = (dir + 1) % 4;
}
//一直往某个方向走,直至不合法才进入上面的判定
row += d[dir][0];
col += d[dir][1];
}
return ret;
}
};
剑指 Offer 31. 栈的压入、弹出序列
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int>st;
int n = pushed.size();
int j = 0;
for(int i = 0; i < n; i++)
{
st.push(pushed[i]);
while(!st.empty() && st.top() == popped[j])
{
j++;
st.pop();
}
}
return st.empty();
}
};
剑指 Offer 03. 数组中重复的数字
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_map<int,int>hash;
int k = 0;
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]))//hash判断该数有没有出现过
{
k = i;
return nums[k];
}
hash.insert({nums[i],i});
}
return nums[k];
}
};
剑指 Offer 53 - I. 在排序数组中查找数字 I
//遍历法
class Solution {
public:
int search(vector<int>& nums, int target) {
int count = 0;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] > target)
{
break;
}
if(nums[i] == target)
{
count++;
}
}
return count;
}
};
//二分法
// class Solution {
// public:
// int search(vector<int>& nums, int target) {
// if(nums.size() == 0) return 0;
// int a = 0,b = 0;
// int left = 0,right = nums.size() - 1;
// while(left < right)
// {
// int mid = left + right >> 1;
// if(nums[mid] >= target) right = mid;
// else left = mid + 1;
// }
// if(nums[left] != target) return 0;
// a = left;
// left = 0,right = nums.size() - 1;
// while(left < right)
// {
// int mid = left + right + 1>> 1;
// if(nums[mid] <= target) left = mid;
// else right = mid - 1;
// }
// b = left;
// return b - a + 1;
// }
// };
剑指 Offer 53 - II. 0~n-1中缺失的数字
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i = 1; i <= n; i++)
{
sum += i;
}
for(int i = 0 ; i < n; i++)
{
sum -= nums[i];
}
return sum;
}
};
剑指 Offer 04. 二维数组中的查找
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) return false;
int n = 0,m = matrix[0].size() - 1;
while(n < matrix.size() && m >=0)
{
if(matrix[n][m] > target) m--;
else if(matrix[n][m] < target) n++;
else return true;
}
return false;
}
};
剑指 Offer 11. 旋转数组的最小数字❤️
class Solution {
public:
int minArray(vector<int>& numbers) {
//这是一个左旋数组
int n = numbers.size();
//二分查找法
int left = 0,right = n - 1;
while(left < right)
{
int mid = left + right >> 1;
if(numbers[mid] > numbers[right]) left = mid + 1;
else if(numbers[mid] < numbers[right]) right = mid;
//当出现nums[m] = nums[j] 时,一定有区间[i, m] 内所有元素相等 或 区间[m, j] 内所有元素相等(或两者皆满 足)。对于寻找此类数组的最小值问题,可直接放弃二分查找,而使用线性查找替代。
else right--;
}
return numbers[left];
}
};
剑指 Offer 50. 第一个只出现一次的字符
class Solution {
public:
char firstUniqChar(string s) {
if(s.size() == 0) return ' ';
vector<int>h;
int arr[26] = {0};
for(int i = 0; i < s.size(); i++)
{
arr[s[i] - 'a']++;
}
for(int i = 0; i < s.size(); i++)
{
if(arr[s[i] - 'a'] == 1)//找到所有只出现一次的字符
{
return s[i];
}
}
return ' ';
}
};
//哈希法
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<int, int> frequency;
for (char ch: s) {
++frequency[ch];
}
for (int i = 0; i < s.size(); ++i) {
if (frequency[s[i]] == 1) {
return s[i];
}
}
return ' ';
}
};
剑指 Offer 32 - I. 从上到下打印二叉树
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
if(root == nullptr)
{
return {};
}
queue<TreeNode*>q;
vector<int>ret;
q.push(root);
while(q.size())
{
TreeNode * front = q.front();
ret.push_back(front->val);
q.pop();
if(front->left != nullptr)
{
q.push(front->left);
}
if(front->right != nullptr)
{
q.push(front->right);
}
}
return ret;
}
};
剑指 Offer 32 - II. 从上到下打印二叉树 II
//自己写的
class Solution {
public:
int RootSize(TreeNode * root)
{
if(root == nullptr)
{
return 0;
}
int leftmax = RootSize(root->left);
int rightmax = RootSize(root->right);
return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == nullptr)
{
return {};
}
int num = RootSize(root);//求深度
typedef pair<TreeNode*,int>PII;
const int N = 1010;
PII q[N];
int hh = 0, tt = 0;
int i = 0;
vector<vector<int>>ret(num);
q[tt] = {root,i};
while(hh <= tt)
{
PII t = q[hh++];
TreeNode * front = t.first;
int k = t.second;
ret[k].push_back(front->val);
if(front->left != nullptr)
{
q[++tt] = {front->left,k + 1};
}
if(front->right != nullptr)
{
q[++tt] = {front->right,k + 1};
}
}
return ret;
}
};
//官方题解
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ret;
if (!root) {
return ret;
}
queue <TreeNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector <int> ());
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front(); q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};
剑指 Offer 32 - III. 从上到下打印二叉树 III
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == nullptr) return {};
queue<TreeNode*>q;
vector<vector<int>>ret;
q.push(root);
while(!q.empty())
{
int num = q.size();
ret.push_back(vector<int>());
for(int i = 0; i < num; i++)
{
auto node = q.front();
q.pop();
ret.back().push_back(node->val);//在尾部进行尾插,因为插入了二维空vector
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
int k = ret.size();
for(int i = 0; i < k; i++)
{
if(i % 2 != 0)//奇数反转
{
reverse(ret[i].begin(),ret[i].end());
}
}
return ret;
}
};
剑指 Offer 26. 树的子结构❤️
//我写的
class Solution {
public:
bool IsSame(TreeNode * A,TreeNode * B)
{
if(B == nullptr) return true;//如果子结构为空那就是真
if(A == nullptr) return false;//子结构不空,主结构空就false
if(A->val == B->val)
{
//只有子结构完全匹配才是true
return IsSame(A->left, B->left) && IsSame(A->right, B->right);
}
return false;
}
void TraverseTree(TreeNode * A,TreeNode * B,bool &flag)
{
if(A == nullptr) return;
TraverseTree(A->left,B,flag);//递归到最底部
if(flag) return;//如果flag变成了真就直接返回了,不需要继续递归
TraverseTree(A->right,B,flag);
if(A->val == B->val)
{
flag = IsSame(A,B);
}
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A == nullptr || B == nullptr) return false;
bool flag = false;//最初是false
TraverseTree(A,B,flag);
return flag;
}
};
//题解:
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A == NULL || B == NULL) return false;
if (A->val == B->val) {
if (dfs_isEqual(A, B)) {
return true;
}
}
return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool dfs_isEqual(TreeNode* A, TreeNode* B) {
if (B == NULL) return true;
if (A == NULL) return false;
if (A->val == B->val) {
return dfs_isEqual(A->left, B->left) && dfs_isEqual(A->right, B->right);
} else {
return false;
}
}
};
剑指 Offer 27. 二叉树的镜像
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root == nullptr)
{
return root;
}
mirrorTree(root->left);
mirrorTree(root->right);
if(root->left != nullptr || root->right != nullptr)
{
TreeNode * tmp = root->left;
root->left = root->right;
root->right = tmp;
}
return root;
}
};
剑指 Offer 28. 对称的二叉树
//我写的
class Solution {
public:
void mirrorTree(TreeNode * root)
{
if(root == nullptr) return;
mirrorTree(root->left);
mirrorTree(root->right);
if(root->left != nullptr || root->right != nullptr)
{
TreeNode * tmp = root->left;
root->left = root->right;
root->right = tmp;
}
return;
}
bool IsEmpty(TreeNode * A,TreeNode * B)
{
if(A == nullptr && B == nullptr) return true;
if(A == nullptr || B == nullptr) return false;
if(A->val == B->val)
{
return IsEmpty(A->left,B->left) && IsEmpty(A->right,B->right);
}
return false;
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
mirrorTree(root->right);
bool flag = IsEmpty(root->left,root->right);
return flag;
}
};
//官方题解
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
剑指 Offer 12. 矩阵中的路径❤️
class Solution {
public:
//DFS算法
bool IsEmpty(vector<vector<char>>& board, vector<vector<int>>&visited,
int rows,int cols,string word,int k)
{
int a = board.size(),b = board[0].size();
if(board[rows][cols] != word[k]) return false;//如果字符不同为假
else if(k == word.size()-1) return true;//匹配成功返回
visited[rows][cols] = true;
bool result = false;
for(int i = 0; i < 4; i++)
{
int x = rows + dx[i],y = cols + dy[i];
if(x >= 0 && x < a && y >= 0 && y < b)//判断边界
{
if(!visited[x][y])//判断是否访问过
{
bool flag = IsEmpty(board, visited, x, y, word, k + 1);
if(flag) return true;//如果成功直接返回
}
}
}
visited[rows][cols] = false;//跳出循环要取消标记
return result;
}
bool exist(vector<vector<char>>& board, string word) {
int row = board.size(),col = board[0].size();
vector<vector<int>>visited(row,vector<int>(col));
bool flag = false;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
{
flag = IsEmpty(board,visited,i,j,word,0);
if(flag) return true;
}
return false;
}
private:
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
};
剑指 Offer 13. 机器人的运动范围❤️
//我写的dfs
class Solution {
public:
int get(int x)
{
int sum = 0;
while(x > 0)
{
sum += x % 10;
x /= 10;
}
return sum;
}
void check(vector<vector<int>>&ans, int row, int col, int k, int &res, int sum, int o)
{
if(sum > k) return;
res++;
int a = ans.size(),b = ans[0].size();
ans[row][col] = true;//走过就不要走了
for(int i = 0; i < 2; i++)
{
int x = row + dx[i], y = col + dy[i];
if(x >= 0 && x < a && y >= 0 && y < b && !ans[x][y])
{
int q = get(x), p = get(y);
int sum1 = p + q;
check(ans,x,y,k,res,sum1,o+1);
}
}
}
int movingCount(int m, int n, int k)
{
if(k == 0) return 1;
vector<vector<int>>ans(m,vector<int>(n));
int res = 0;//表示走格子的最大值
int o = 1;
int sum = 0;//记录数位和
check(ans,0,0,k,res,sum,o);
return res;
}
private:
int dx[4] = {1,0};//优化成下和右
int dy[4] = {0,1};
};
//官方题解bfs
class Solution {
// 计算 x 的数位之和
int get(int x) {
int res=0;
for (; x; x /= 10) {
res += x % 10;
}
return res;
}
public:
int movingCount(int m, int n, int k) {
if (!k) return 1;
queue<pair<int,int> > Q;
// 向右和向下的方向数组
int dx[2] = {0, 1};
int dy[2] = {1, 0};
vector<vector<int> > vis(m, vector<int>(n, 0));
Q.push(make_pair(0, 0));
vis[0][0] = 1;
int ans = 1;
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
for (int i = 0; i < 2; ++i) {
int tx = dx[i] + x;
int ty = dy[i] + y;
if (tx < 0 || tx >= m || ty < 0|| ty >= n
|| vis[tx][ty]||get(tx)+get(ty) > k) continue;
Q.push(make_pair(tx, ty));
vis[tx][ty] = 1;
ans++;
}
}
return ans;
}
};
剑指 Offer 34. 二叉树中和为某一值的路径❤️
class Solution {
public:
vector<vector<int>>ret;
vector<int>path;
void dfs(TreeNode * root,int target)
{
if(root == nullptr) return;
path.emplace_back(root->val);
target -= root->val;
//只有是叶子节点的路径并且目标值为0才插入路径
if(root->left == nullptr && root->right == nullptr && target == 0)
{
ret.emplace_back(path);
}
dfs(root->left,target);
dfs(root->right,target);
path.pop_back();//回退时删除该路径的值
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(root == nullptr) return {};
dfs(root,target);
return ret;
}
};
剑指 Offer 54. 二叉搜索树的第k大节点❤️
//利用优先队列做法
class Solution {
public:
priority_queue<int,vector<int>>q;
void PreInorder(TreeNode * root)
{
if(root == nullptr) return;
q.push(root->val);
PreInorder(root->left);
PreInorder(root->right);
}
int kthLargest(TreeNode* root, int k) {
PreInorder(root);
int maxi = -1e9;
while(k--)
{
maxi = q.top();
q.pop();
}
return maxi;
}
};
17. 电话号码的字母组合
class Solution {
char * str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//绝对映射
public:
void dfs(string digits,vector<string>&v,int di,string conbina)
{
if(di == digits.size())
{
v.push_back(conbina);
return;
}
int num = digits[di] - '0';//取出数字
string s = str[num];
for(auto ch : s)
{
dfs(digits,v,di + 1,conbina + ch);//conbina不用+=的好处时栈峥回退不用尾删
}
}
vector<string> letterCombinations(string digits) {
vector<string>v;
if(digits.empty()) return v;
int di = 0;
string conbina;
dfs(digits,v,di,conbina);
return v;
}
};
剑指 Offer 36. 二叉搜索树与双向链表
class Solution {
public:
//二叉搜索树是左小右大,所以进行中序遍历
void dfs(Node * cur)
{
if(cur == nullptr) return;
dfs(cur->left);
if(head == nullptr)
{
head = tail = cur;//无数据要先插入
}
else
{
//双链表的相互指向
tail->right = cur;
cur->left = tail;
tail = cur;
}
dfs(cur->right);
}
Node* treeToDoublyList(Node* root)
{
if(root == nullptr) return nullptr;
dfs(root);
//设置为循环链表
head->left = tail;
tail->right = head;
return head;
}
private:
Node * head = nullptr;
Node * tail = nullptr;
};
剑指 Offer 55 - I. 二叉树的深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
int leftmax = maxDepth(root->left);
int rightmax = maxDepth(root->right);
return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
}
};
剑指 Offer 55 - II. 平衡二叉树
class Solution {
public:
int maxDepth(TreeNode * root)
{
if(root == nullptr) return 0;
int leftmax = maxDepth(root->left);
int rightmax = maxDepth(root->right);
return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
}
bool isBalanced(TreeNode* root)
{
if(root==NULL)
{
return true;
}
int leftmax = maxDepth(root->left);
int rightmax = maxDepth(root->right);
return abs(leftmax-rightmax)<2 && isBalanced(root->left) && isBalanced(root->right);
}
};
剑指 Offer 64. 求1+2+…+n
class Solution {
public:
int sumNums(int n) {
n && (n += sumNums(n - 1));
return n;
}
};
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
class Solution {
public:
vector<TreeNode*>GetPath(TreeNode * root,TreeNode *target)
{
vector<TreeNode*>ret;
while(root != target)
{
ret.push_back(root);
if(root->val > target->val)
{
root = root->left;
}
else
{
root = root->right;
}
}
ret.push_back(root);
return ret;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*>path_p = GetPath(root,p);//保存路径
vector<TreeNode*>path_q = GetPath(root,q);
TreeNode * res = nullptr;
for(int i = 0; i < path_p.size() && i < path_q.size(); i++)
{
if(path_p[i] == path_q[i])//寻找最近的公共祖先
{
res = path_p[i];
}
else{
break;
}
}
return res;
}
};
剑指 Offer 68 - II. 二叉树的最近公共祖先
class Solution {
public:
bool GetPath(vector<TreeNode*>&path,TreeNode*root,TreeNode * target)
{
if(root == nullptr) return false; //没找到
if(root == target)
{
path.push_back(root);//找到将找到的也要插进去
return true;
}
path.push_back(root);
bool left1 = GetPath(path,root->left,target);
if(left1) return true;
bool right1 = GetPath(path,root->right,target);
if(right1) return true;
path.pop_back();//没找到退出的时候要删除路径
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*>path_p;
vector<TreeNode*>path_q;
bool p1 = GetPath(path_p,root,p);
bool q1 = GetPath(path_q,root,q);
TreeNode * res = nullptr;
for(int i = 0; i < path_p.size() && i < path_q.size(); i++)
{
if(path_p[i] == path_q[i])//寻找最近的公共祖先
{
res = path_p[i];
}
else{
break;
}
}
return res;
}
};
剑指 Offer 37. 序列化二叉树❤️
class Codec {
public:
void rserialize(TreeNode * root,string & ret)
{
//前序遍历转为字符串
if(root == nullptr)
{
ret += "#,";
return;
}
ret += to_string(root->val);//字符转换函数
ret += ",";
rserialize(root->left,ret);
rserialize(root->right,ret);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string ret;
rserialize(root,ret);
return ret;
}
// Decodes your encoded data to tree.
TreeNode* rdeserialize(list<string>&dateArray)
{
if(dateArray.front() == "#")
{
dateArray.erase(dateArray.begin());
return nullptr;
}
TreeNode * root = new TreeNode(stoi(dateArray.front()));//将字符串转为数字
dateArray.erase(dateArray.begin());//插入后删除
root->left = rdeserialize(dateArray);
root->right = rdeserialize(dateArray);
return root;
}
TreeNode* deserialize(string data) {
list<string>dateArray;//用链表存字符串
string str;
for(auto& c : data)
{
if(c == ',')
{
dateArray.push_back(str);
str.clear();
}
else
{
str.push_back(c);
}
}
if(!str.empty()) //如果后面有节点就需要插入在清空
{
dateArray.push_back(str);
str.clear();
}
return rdeserialize(dateArray);
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
剑指 Offer 38. 字符串的排列❤️
//我写的
class Solution {
public:
unordered_map<string,int>hash;
void dfs(string s,vector<string>& ret,int len,string str,vector<int>&flag)
{
if(str.size() == len)
{
if(!hash.count(str))
{
ret.push_back(str);
hash.insert({str,1});
}
return;
}
for(int i = 0; i < s.size(); i++)
{
if(!flag[i])
{
flag[i] = true;
dfs(s,ret,len,str + s[i],flag);
flag[i] = false;
}
}
}
vector<string> permutation(string s) {
int len = s.size();
vector<string>ret;
vector<int>flag;
flag.resize(len);
string str;
dfs(s,ret,len,str,flag);
return ret;
}
};
//官方题解
// class Solution {
// public:
// vector<string> rec;
// vector<int> vis;
// void backtrack(const string& s, int i, int n, string& perm) {
// if (i == n) {
// rec.push_back(perm);
// return;
// }
// for (int j = 0; j < n; j++) {
// if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
// continue;
// }
// vis[j] = true;
// perm.push_back(s[j]);
// backtrack(s, i + 1, n, perm);
// perm.pop_back();
// vis[j] = false;
// }
// }
// vector<string> permutation(string s) {
// int n = s.size();
// vis.resize(n);
// sort(s.begin(), s.end());
// string perm;
// backtrack(s, 0, n, perm);
// return rec;
// }
// };
剑指 Offer 17. 打印从1到最大的n位数
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int>ret;
if(n == 0) return ret;
int k = 1;
while(n--)
{
k *= 10;
}
for(int i = 1; i < k; i++)
{
ret.push_back(i);
}
return ret;
}
};
剑指 Offer 51. 数组中的逆序对
class Solution {
public:
int merge(vector<int>&nums,int left,int right,vector<int>&tmp)
{
if(left >= right) return 0;
int mid = (left + right) >> 1;
int res = merge(nums,left,mid,tmp) + merge(nums,mid+1,right,tmp);
int k = 0,i = left,j = mid + 1;
while(i <= mid && j <= right)
{
if(nums[i] <= nums[j])
{
tmp[k++] = nums[i++];
}
else
{
tmp[k++] = nums[j++];
//只有q[i]>q[j]时才是逆序对,若是它大于q[j]了,那么mid-i+1的数都会大于q[j],都属于逆序对,这是进行扫尾
res += mid - i + 1;
}
}
while(i <= mid)
{
tmp[k++] = nums[i++];
}
while(j <= right)
{
tmp[k++] = nums[j++];
}
for(int i = left,j = 0; i <= right; i++, j++)
{
nums[i] = tmp[j];
}
return res;
}
int reversePairs(vector<int>& nums) {
if(nums.size() == 0) return 0;
vector<int>tmp;
int len = nums.size();
tmp.resize(len+1);
return merge(nums,0,len-1,tmp);
}
};
剑指 Offer 07. 重建二叉树
class Solution {
private:
unordered_map<int, int> hash;
public:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,
int in_begin,int in_end)
{
if(in_begin > in_end)
return nullptr;
TreeNode* root = new TreeNode(preorder[prei++]);
int root_size = hash[root->val];
root->left = _buildTree(preorder,inorder,prei,in_begin,root_size-1);
root->right = _buildTree(preorder,inorder,prei,root_size+1,in_end);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0; i < inorder.size(); i++)
{
hash.insert({inorder[i],i});
}
int i = 0;
return _buildTree(preorder,inorder,i,0,inorder.size()-1);
}
};
剑指 Offer 16. 数值的整数次方
class Solution {
public:
double Pow(double x,long long n)
{
if(n == 0) return 1.0;
double y = Pow(x,n / 2);//快速幂算法
//如果n为偶数就是返回的结果的平方,否则就是返回的结果多乘x
return n % 2 == 0? y * y : y * y * x;
}
double myPow(double x, int n)
{
if(n == 0) return 1.0;
long long N = n;//防止越界
return N >= 0 ? Pow(x,N) : 1 / Pow(x,-N);
}
};
剑指 Offer 45. 把数组排成最小的数❤️
class Solution {
public:
void quick_sort(vector<string>&str, int left, int right)
{
if(left >= right) return;
int i = left,j = right;
while(i < j)
{
//找小
while(i < j && str[j] + str[left] >= str[left] + str[j]) j--;//必须先从右往左
//找大
while(i < j && str[i] + str[left] <= str[left] + str[i]) i++;
if(i < j) swap(str[i],str[j]);
}
swap(str[left],str[j]);
quick_sort(str,left,j - 1);
quick_sort(str,j + 1,right);
}
string minNumber(vector<int>& nums) {
vector<string>str;
int len = nums.size();
for(int i = 0; i < len; i++)
{
str.push_back(to_string(nums[i]));
}
quick_sort(str,0,len-1);
string ret;
for(auto ch : str)
{
ret += ch;
}
return ret;
}
};
剑指 Offer 61. 扑克牌中的顺子
class Solution {
public:
bool isStraight(vector<int>& nums) {
//大小王相当于赖子,只要最大值和最小值的差小于5肯定是顺子
int maxi = 0, mini = 14;
unordered_map<int,int>hash;
for(int i = 0; i < 5; i++)
{
if(nums[i] == 0) continue;//遇到大小王跳过
maxi = ::max(nums[i],maxi);
mini = ::min(nums[i],mini);
if(hash.count(nums[i]))//如果重复则不是顺子
{
return false;
}
hash.insert({nums[i],i});
}
if(maxi - mini < 5) return true;
return false;
}
};
剑指 Offer 40. 最小的k个数
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int>ret;
priority_queue<int,vector<int>,greater<int>>q;
for(auto ch : arr)
{
q.push(ch);
}
while(k--)
{
int top = q.top();
q.pop();
ret.push_back(top);
}
return ret;
}
};
150. 逆波兰表达式求值
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int>st;
for(auto& ch : tokens)
{
if(ch == "+" || ch == "-" || ch == "*" || ch == "/")
{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
char str = ch[0];
int num;
switch(str)
{
case '+':
num = left + right;
st.push(num);
break;
case '-':
num = left - right;
st.push(num);
break;
case '*':
num = left * right;
st.push(num);
break;
case '/':
num = left / right;
st.push(num);
break;
}
}
else
{
st.push(stoi(ch));
}
}
return st.top();
}
};
剑指 Offer 10- I. 斐波那契数列
class Solution {
public:
int fib(int n) {
long long * dp = new long long [110];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);
}
return(int)dp[n];
}
};
剑指 Offer 10- II. 青蛙跳台阶问题
class Solution {
public:
int numWays(int n) {
long long * dp = new long long [110];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
dp[i] = (dp[i - 1] + dp[i - 2])%(1000000007);
}
return(int)dp[n];
}
};
剑指 Offer 63. 股票的最大利润❤️
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
int mini = 0x3f3f3f3f;//买股票的最小值
int maxi = 0;//卖股票的最大值
for(auto price : prices)
{
maxi = max(maxi,price - mini);
mini = min(mini,price);
}
return maxi;
}
};
剑指 Offer 42. 连续子数组的最大和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int>dp(nums.size(),0);
dp[0] = nums[0];
for(int i = 1; i < nums.size(); i++)
{
dp[i] = max(dp[i - 1] + nums[i],nums[i]);
}
int maxi = -0x3f3f3f3f;
for(int i = 0; i < nums.size(); i++)
{
maxi = max(dp[i],maxi);
}
return maxi;
}
};
剑指 Offer 47. 礼物的最大价值❤️
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
//动态规划
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(i > 0)//只有大于0,才有向上走的那一步
{
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
if(j > 0)//只有大于0,才有向左走的那一步
{
dp[i][j] = max(dp[i][j],dp[i][j -1]);
}
dp[i][j] += grid[i][j];//确定了当前位置的上一步后就可以加当前的价值了
}
}
return dp[m - 1][n - 1];
}
};
剑指 Offer 46. 把数字翻译成字符串
class Solution {
public:
int translateNum(int num) {
string str = to_string(num);
int len = str.size();
vector<int>dp(len+1,0);
//类似青蛙跳台阶问题,青蛙可以一直跳一个台阶,跳两个台阶要分情况
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= len; i++)
{
string sub = str.substr(i - 2,2);//从第几位开始取多少位字符串
if(sub <= "25" && sub >= "10")
{
dp[i] = dp[i - 1] + dp[i - 2];
}
else
{
dp[i] = dp[i - 1];
}
}
return dp[len];
}
};
剑指 Offer 64. 求1+2+…+n
class Sum
{
public:
Sum()
{
_sum += _i;
_i++;
}
static int get()
{
return _sum;
}
void Destroy()
{
_sum = 0;
_i = 1;
}
private:
static int _i;
static int _sum;
};
int Sum::_sum = 0;
int Sum::_i = 1;
int func(int n)
{
Sum *s = new Sum[n];
int ret = s->get();
s->Destroy();//因为leetcode是全部测试用例用完才销毁,要重置,并且不能用析构
return ret;
}
class Solution {
public:
int sumNums(int n) {
return func(n);
}
};
剑指 Offer 48. 最长不含重复字符的子字符串❤️
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
if(len == 0) return 0;
if(len == 1) return 1;
vector<int>dp(len,0);
dp[0] = 1;
int maxlen = 0;
int tmp = 0;
for(int i = 1; i < len; i++)
{
int j = i - 1;
while(j >= 0 && s[i] != s[j]) j--;
if(dp[i-1] < i - j) dp[i] = dp[i-1] + 1;//第j个字符不在dp[i-1]的区间之内
else dp[i] = i - j;//第j个字符在dp[i-1]的区间之内
if(dp[i] > maxlen) maxlen = dp[i];
}
return maxlen;
}
};
264. 丑数 II
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<double,vector<double>,greater<double>>q;
double ans = 1;
for(int i = 1; i < n; i++)
{
q.push(ans*2);
q.push(ans*3);
q.push(ans*5);
ans = q.top();
q.pop();
while(!q.empty() && q.top() == ans) q.pop();
}
return ans;
}
};
剑指 Offer 15. 二进制中1的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n)
{
n = n & (n - 1);
count++;
}
return count;
}
};
剑指 Offer 65. 不用加减乘除做加法
class Solution {
public:
int add(int a, int b) {
while (b != 0) {
unsigned int carry = (unsigned int)(a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};
剑指 Offer 56 - I. 数组中数字出现的次数
class Solution {
public:
vector<int> GetNum(vector<int>&nums, int sz)
{
vector<int>ret;
int k = 0;
for(int i = 0; i < 31; i++)
{
if((sz >> i) & 1 == 1)
{
k = i;
break;
}
}
int a = 0, b = 0;
for(int i = 0; i < nums.size(); i++)
{
if(((nums[i] >> k) & 1) == 0)
{
a ^= nums[i];
}
else
{
b ^= nums[i];
}
}
ret.push_back(a);
ret.push_back(b);
return ret;
}
vector<int> singleNumbers(vector<int>& nums)
{
vector<int>ret;
int sz = 0;
for(int i = 0; i < nums.size(); i++)
{
sz ^= nums[i];
}
return GetNum(nums,sz);
}
};
剑指 Offer 56 - II. 数组中数字出现的次数 II
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
sort(nums.begin(),nums.end());
for(int i = 1; i < nums.size()-1; i++)
{
if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
{
return nums[i];
}
}
if(nums[0] != nums[1]) return nums[0];//边界问题
return nums[nums.size() - 1];//两个边界另外处理
}
};
剑指 Offer 39. 数组中出现次数超过一半的数字
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
sort(nums.begin(),nums.end());
int count = 1;
int sz = nums[0];
int len = nums.size() / 2;
for(int i = 1; i < nums.size(); i++)
{
if(count > len)
{
break;
}
if(sz == nums[i])
{
count++;
}
else
{
sz = nums[i];
count = 1;
}
}
return sz;
}
};
剑指 Offer 66. 构建乘积数组
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
vector<int>ret;
if(a.size() == 0) return ret;
int len = a.size();
vector<int>left(len,0);
vector<int>right(len,0);
left[0] = 1;//因为左侧没有元素,所以赋值为1
for(int i = 1; i < len; i++)
{
left[i] = a[i - 1] * left[i - 1];
}
right[len - 1] = 1;//因为len- 1右侧没有元素,所以赋值为1
for(int i = len - 2; i >= 0; i--)
{
right[i] = a[i + 1] * right[i + 1];
}
for(int i = 0; i < len; i++)
{
ret.push_back(left[i] * right[i]);
}
return ret;
}
};
剑指 Offer 57 - II. 和为s的连续正数序列❤️
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>>ret;
int i = 1;//滑动窗口左边界
int j = 1;//滑动窗口右边界
int sum =0;
while(i <= target / 2) // 超过它的两倍是容纳不了两个数的
{
if(sum > target)
{
sum -= i;
i++;
}
else if(sum < target)
{
sum += j;
j++;
}
else
{
vector<int>res;
for(int k = i; k < j; k++)
{
res.push_back(k);
}
ret.push_back(res);
sum -= i;
i++;
}
}
return ret;
}
};
剑指 Offer 62. 圆圈中最后剩下的数字
//超时
// class Solution {
// public:
// int lastRemaining(int n, int m) {
// if(n == 1) return 0;
// vector<int>res;
// for(int i = 0; i < n; i++)
// {
// res.push_back(i);
// }
// int cnt = n;
// int num = 0;
// while(cnt != 1)
// {
// for(int i = 0; i < res.size(); i++)
// {
// if(res[i] != -1)
// {
// num++;
// if(num == m)
// {
// num = 0;
// res[i] = -1;
// cnt--;
// if(cnt == 1) break;
// }
// }
// }
// }
// for(int i = 0; i < res.size(); i++)
// {
// if(res[i] != -1)
// {
// num = i;
// break;
// }
// }
// return num;
// }
// };
class Solution {
public:
int lastRemaining(int n, int m) {
/*
方法2:计算法(参考题解区->想吃火锅的木易)
假设有一圈数字[0,1,2,3,4,5],m=3
我们令删除后的元素的后一个元素放在最前面方便计数
1.删除2->[3,4,5,0,1]
2.删除5->[0,1,3,4]
3.删除3->[4,0,1]
4.删除1->[4,0]
5.删除4->[0]
尝试反推:
如何从最后剩下的元素的索引0反推至第一轮元素索引呢?
注意到:2->1的过程是将删除的的元素5补在尾巴上变成[0,1,3,4,5],然后再总体向右移动m位
变成:[3,4,5,0,1];同样地,此时的最终活下来的元素0的索引由0->3
显然这是(idx+m)%len的结果,idx为删除5后的索引,len为补上删除元素后数组的长度
*/
// 最后的位置必然为0
int pos = 0;
// 这里的i为还原后数组的长度,范围为[2,n]
for(int i = 2; i <= n; i++) {
// 经过推断可知新的pos=(旧的pos + m) % len
// 其中pos表示索引,len表示还原后的数组长度,即i
pos = (pos + m) % i;
}
// 数组为[0,1,2,...,n-1],因此数组索引=元素
return pos;
}
};
剑指 Offer 44. 数字序列中某一位的数字❤️
class Solution {
public:
int findNthDigit(int n) {
//当n=0不存在。
//分段
//第一段(1-9)数字1-10 个,长度 9*1
//第二端(10-99)数字(100-10)个,长度(100-10)*2 = 90*2
//第三段(100-999)数字(1000-100)个, 长度(1000-100)*3 =900*3
//n=1,返回1 。n=10 对应第二段的第一个数字10。取第一位为1
int i=1;//分段 第1段开始
while(n > 9*pow(10,i-1) *i)//找到n在第几段 ,如第二段有90*2 个字符
{
n = n - 9*pow(10,i-1) *i;
i++;
}
//到这里已经知道是第几段i。 且是这一段的第几个字符
int min_num = pow(10,i-1);//这一段的最小值。比如第二段,最小为10
int cur_num = min_num + (n-1)/i;//知道是属于哪个数字 每个数字长度为i 第0数字是它本身
int cur_bit = (n-1)%i;//看是这个数字的第几位
string s = to_string(cur_num);
return s[cur_bit]-'0';//返回这一位的数字
}
};
剑指 Offer 33. 二叉搜索树的后序遍历序列❤️
class Solution {
public:
bool PostOrder(vector<int>& postorder, int start, int end)
{
/* 递归终止条件 */
if(start >= end) return true;
int index = start;
/* 中间处理逻辑 */
while(postorder[index] < postorder[end]) index++;
/* 记录分割点 */
int min_index = index;
while(postorder[index] > postorder[end]) index++;
/* 递归左右子树 */
bool left = PostOrder(postorder,start,min_index - 1);
bool right = PostOrder(postorder,min_index,end-1);
return index == end && left && right;
}
bool verifyPostorder(vector<int>& postorder) {
return PostOrder(postorder, 0, postorder.size()-1);
}
};
文章来源地址https://www.toymoban.com/news/detail-483240.html
文章来源:https://www.toymoban.com/news/detail-483240.html
到了这里,关于【leetcode刷题】剑指offer基础版(完结)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!