过去几天复习了一遍剑指offer,整理一下笔记方便以后复习,题目来源leetcode,题解来源acwing
/**
* 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* SearchHalfNode(ListNode* head)
{
auto fast = head;
auto slow = head;
while (fast)
{
fast = fast -> next;
slow = slow -> next;
if (fast) fast = fast->next;
}
return slow;
}
ListNode* reverseList(ListNode* node)
{
ListNode* pre = nullptr;
while (node)
{
auto next_ = node->next;
node -> next = pre;
pre = node;
node = next_;
}
return pre;
}
bool isPalindrome(ListNode* head) {
auto mid = SearchHalfNode(head);
auto end = reverseList(mid);
while (end)
{
if (head->val != end->val)
return false;
head = head->next;
end = end-> next;
}
return true;
}
}
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
for (auto x: nums)
if (x < 0 || x >= n )
return -1;
for (int i = 0; i < n; i ++)
{
while (i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);//交换i nums[i] nums[nums[i]]
if (i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];//交换位置已经有值,那么返回nums[i]
}
return -1;
}
};
#include
#include
using namespace std;
const int N = 1010;
vector<int> nums;
class Solution
{
public:
int duplicateInArray(vector<int> &nums)
{
int l = 1, r = nums.size() - 1; //最大值、最小值
while (l < r)
{
//无序数组二分
int mid = l + r >> 1; //按中位数切分成两半
// [l,mid] [mid+1,r]
int s = 0;
for (auto x : nums)
s += x >= l && x <= mid; //按区间计数
if (s > mid - l + 1) //如果左边区间的点大于区间中的点位
r = mid; //去左边查找
else
l = mid + 1; //否则去右边查找
}
return r;
}
void display()
{
cout << "this is my function!" << endl;
}
};
int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
{
int x;
cin >> x;
nums.push_back(x);
}
Solution solution;
int res;
// solution.display();
res = solution.duplicateInArray(nums);
cout << res << endl;
}
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
/*
从左下角开始查找,上边的数一定小,右边的数一定大
每次都会省略一行
*/
int m, n;
if (matrix.empty() || matrix[0].empty()) return false;
m = matrix.size();
n = matrix[0].size();
int i = m - 1, j = 0;
while (i >= 0 && j < n)
{
if (matrix[i][j] > target) i --;
else if (matrix[i][j] < target) j ++;
else return true;
}
return false;
}
};
class Solution {
public:
string replaceSpace(string s) {
string res;
for (auto x: s)
{
if (x == ' ') res += "%20";
else res += x;
}
return res;
}
};
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {} //构造函数初始化,可以传入参数x
};
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> res;
while (head)
{
res.push_back(head -> val);
head = head -> next;
}
return vector<int>(res.rbegin(), res.rend());//rbegin与begin正好相反
}
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
map <int, int> hash;
vector<int> preorder, inorder;
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
/*
根左右找到根节点的值
左根右找到根节点的位置,然后递归左子树和右子树
*/
preorder = _preorder, inorder = _inorder;
for (int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;//使用hash存储每个节点在中序遍历中的位置
return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* dfs(int pl, int pr, int il, int ir)
{
if (pl > pr) return nullptr;
auto root = new TreeNode(preorder[pl]);
int k = hash[root -> val];
auto left = dfs(pl + 1, pl + k - il, il, k - 1);//左子树k-il个元素
auto right = dfs(pl + k - il + 1, pr, k + 1, ir);
root -> left = left;
root -> right = right;
return root;
}
};
#include
struct TreeLinkNode
{
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next; // father指针
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL){}
};
class Solution
{
public:
TreeLinkNode *GetNext(TreeLinkNode *pNode)
{
//当前节点在中序遍历中的下一个节点:后继
//二叉搜索树中比当前节点大的最小节点
// next是父节点
if (pNode->right)
{
pNode = pNode->right;
while (pNode->left)
pNode = pNode->left;//如果有右子树,那么下一个节点一定是右子树的最左节点
return pNode;
}
// 如果没有右子树,中序遍历会向上看,如果是父节点的左节点那么直接返回父节点
// 如果是父节点的右节点,那么沿着父节点继向上,直到某个节点是父节点的左节点,返回父节点
// 两种情况可以统一为
while (pNode->next && pNode == pNode->next->right)
pNode = pNode->next;
return pNode->next;
}
};
class CQueue {
public:
stack<int> stk, cache;
CQueue() {}
void appendTail(int value) {
stk.push(value);
}
void copy(stack<int> &a, stack<int> &b)
{
while (a.size())
{
b.push(a.top());
a.pop();
}
}
int deleteHead() {
if (stk.size())
{
copy(stk, cache);//保存到缓存中
int res = cache.top();//删除队头
cache.pop();
copy(cache, stk);//拷贝回去
return res;
}
return -1;
}
};
class Solution {
public:
int fib(int n) {
int a = 0, b = 1;
for (int i = 1; i <= n; i ++)
{
int r = (a + b) % 1000000007;// (a + b) % c = (a % c + b % c) % c 所以可以提前取余,避免整形溢出
a = b;
b = r;
}
return a;
}
};
class Solution {
public:
int minArray(vector<int>& numbers) {
// 有序数组 搬移后仍然是有序数组
// 左数组最左边 可能 等于右数组最右边 去掉右数组的右半边
// 右边数组完全小于左边,可以找到右数组的最左元素
// 使用二分
int n = numbers.size() - 1;
if (n < 0) return -1;
while (n > 0 && numbers[0] == numbers[n]) n --;
if (numbers[0] <= numbers[n]) return numbers[0]; //只剩左数组
//二分搜索 小于numbers[0]的最左数
int l = 0, r = n;
while (l < r)
{
int mid = l + (r - l) / 2;//[l,mid] [mid+1,r]
if (numbers[mid] < numbers[0]) r = mid;//mid落在了右半
else l = mid + 1;//mid落在左半
}
return numbers[r];
}
};
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
//dfs 从首字母开始查找,如果找到立即返回
if (board.empty()) return false;
for (int i = 0; i < board.size(); i ++)
for(int j = 0; j < board[i].size(); j++)
{
if (dfs(board, word, 0, i, j)) return true;
}
return false;
}
bool dfs(vector<vector <char>> &board, string word, int u, int x, int y)
{
if (board[x][y] != word[u]) return false;
// 如果二维矩阵元素等于当前元素
if (u == word.size() - 1) return true;
// 如果当前元素相等且不是末尾元素,向下查找
char t = board[x][y];
board[x][y] = '*';
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
for (int i = 0; i < 4; i++)
{
int a = x + dx[i];
int b = y + dy[i];
//如果在范围内,寻找下一层
if (a >=0 && a < board.size() && b >= 0 && b < board[a].size())
if (dfs(board, word, u + 1, a, b)) return true;
}
board[x][y] = t;//回溯
return false;
}
};
class Solution {
public:
int get_single_sum(int x)
{
int s = 0;
while (x)
{
s += x % 10;
x /= 10;
}
return s;
}
int get_sum(pair<int, int> p) //坐标位数之和不能大于k
{
return get_single_sum(p.first) + get_single_sum(p.second);
}
int movingCount(int m, int n, int k) {
int res = 0;
if (!m || !n) return 0;
vector<vector<bool>> st(m, vector<bool>(n));
queue<pair<int, int>> q;
q.push({0, 0});//pair列表初始化
int dx[2] = {1, 0}, dy[2] = {0, 1};//只需要向下和向右查找即可
while (!q.empty())
{
auto t = q.front();
q.pop();
if (get_sum(t) > k||st[t.first][t.second]) continue;
//如果满足条件
res ++;
st[t.first][t.second] = true;
// 广度优先搜索
for (int i = 0; i < 2; i++)
{
int a = t.first + dx[i];
int b = t.second + dy[i];
if (a >= 0 && a < m &&b >= 0 && b < n)
q.push({a, b});
}
}
return res;
}
};
/*
整数拆分,使其因子乘积最大
结论:
ni%3 余1 拆出一个2*2=4,剩下被3拆分
ni%3 余2 拆出一个2,剩下被3拆分
分析过程:
假设N > 0, 正整数N拆分成m个数,N = n1 + n2 + n3 + n4 + n..+nm
1 最优解肯定没有1, 1*(x-1)< x
2 最优解可以没有4, 2*2=4 可拆 最优解2 3 >4
3 ni>5, ni必须拆成3*(ni-3),最优解不能包含大于等于5的数,最优解只包含 2和3
3 * (ni - 3) >= ni
3 * ni - 9 >= ni
2 * ni >= 9 成立,拆了更好
4 最优解若有3个2: 2 * 2 *2 < 3 * 3 最优解最多两个2
*/
class Solution {
public:
int cuttingRope(int n) {
int res = 1;
if (n <= 3) return n -1;
if (n % 3 == 1) res *= 4, n -= 4;
if (n % 3 == 2) res *= 2, n -= 2;
while (n)
{
res *= 3;
n -= 3;
}
return res;
}
};
/*两种解法:
1 lowbit 最后一位1的二进制表示的十进制数
在原来的基础上减去即可消去最右边的1,每消一次计数+1
1010 原码
0110 补码
2 直接转换为正数的原码
在原来的基础上每次右移1位,每次计数 + x&1
*/
//lowbit算法
class Solution {
public:
int hammingWeight(uint32_t n) {
int s = 0;
while (n)
{
int x = n & -n;
n -= x;
s ++;
}
return s;
}
};
//直接转化为正数
class Solution {
public:
int hammingWeight(uint32_t n) {
unsigned int n_ = n;
int s = 0;
while (n)
{
s += n & 1;
n >>= 1;
}
return s;
}
};
/*
快速幂:指数的二进制拆分
x^N = x2*x2^2*x2^3*x2^4...
N = 2^2+2^3+2^4...表示为二进制数即可。
N & 1
0 res*=x
1 res*=x*2
2 res*=x*4
3 res*=x*8
...
*/
class Solution {
public:
double myPow(double x, int n) {
//注意负指数
double res = 1;
long long N = abs(n);
while (N)
{
if (N & 1) res *= x;//二进制位=1,那么累加结果
x *= x;
N >>= 1;//指数的二进制拆分
}
if (n < 0) res = 1 / res;
return res;
}
};
class Solution {
public:
vector<int> printNumbers(int n) {
//输出所有的n位数
int m = (pow(10, n)) - 1;
vector<int> nums(m, 1);
for (int i = 1; i < m; i ++)
nums[i] = nums[i-1] + 1;
return nums;
}
};
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
//如果是头节点
if (head -> val == val) return head -> next;
//不是头节点
ListNode* cur = head;
while(cur-> next -> val != val)
cur = cur -> next;
cur -> next = cur -> next -> next;
return head;
}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// dummy 哨兵机制 头结点可能被删掉
auto dummy = new ListNode(-1);
dummy -> next = head;
// 链表双指针 dummy 1 1 1 2 2 3 3 4 4 分段看
auto p = dummy;
while (p -> next)
{
auto cur = p -> next;
while (cur -> next && cur -> val == cur -> next -> val)
cur = cur -> next;
// 如果没有重复,p移动到cur,
if (p -> next == cur) p = cur;
// 如果有重复,将p的next指针指向cur
else p -> next = cur;//cur在下一个区间
}
return dummy -> next;
}
};
class Solution {
public:
int n, m;
vector<vector<int>> f;
string s, p;
bool isMatch(string s_, string p_) {
s = s_, p = p_;
n = s.size(), m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
return dp(0, 0);
}
bool dp(int x, int y)
{
if (f[x][y] != -1)
return f[x][y];
if (y == m)
return f[x][y] = x == n; // 初始化
bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);
if (y + 1 < m && p[y + 1] == '*')
//匹配0次跳过两个匹配字符
//匹配一次以上: 当前字符匹配且f[x+1][y]后面字符也是匹配的
f[x][y] = dp(x, y + 2) || (first_match && dp(x + 1, y));
else
{
f[x][y] = first_match && dp(x + 1, y + 1);
}
return f[x][y];
}
};
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
/*双指针
第一个指针前面全是奇数
第二个指针后面全是偶数*/
int l = 0, r = nums.size() - 1;
while (l <= r)
{
while (l <= r && nums[l] % 2 == 1) l ++;
while (l <= r && nums[r] % 2 == 0) r --;
if (l < r) swap(nums[l], nums[r]);
}
return nums;
}
};
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
auto slow = head;
int idx = 0;
while (head)
{
if (idx >= k)
slow = slow -> next;
head = head->next;
idx ++;
}
return slow;
}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 链表中环的检测
auto fast = head;
auto slow = head;
bool find = false;
while (slow && fast)
{
//fast走两步
fast = fast -> next;
if (fast) fast = fast -> next;
//fast空时,无环
if (!fast) return nullptr;
//slow走一步
slow = slow -> next;
//如果相遇,那么停止
if (fast == slow)
{
find = true;
break;
}
}
//没有环
if (!find) return nullptr;
//从头开始走,直到相遇
slow = head;
while (slow && fast && slow != fast)
{
fast = fast -> next;
slow = slow -> next;
}
return slow;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//记录一个前驱节点
ListNode * pre = nullptr;
auto cur = head;
while (cur)
{
auto next = cur -> next;
cur -> next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
/**
* 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) {
//归并排序的并操作
auto dummy = new ListNode(-1);
auto cur = dummy;
while (l1 && l2)
{
if (l1 -> val <= l2 -> val)
{
cur -> next = l1;
l1 = l1 ->next;
}
else
{
cur -> next = l2;
l2 = l2 -> next;
}
cur = cur ->next;
}
if (l1) cur -> next = l1;
else cur ->next = l2;
return dummy -> next;
}
};
/**
* 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:
bool isSubStructure(TreeNode* A, TreeNode* B) {
// B恰好能覆盖A的部分节点 类似字符串匹配
// 从树根开始看,如果不是,后移一位 暴力匹配 空树不是任意子结构
if (!A || !B) return false;//某棵树为空 返回fasle
if (isPart(A, B)) return true;// 如果A\B匹配返回true
return isSubStructure(A->left, B) || isSubStructure(A->right,B);//如果不匹配 看左右子树是否匹配
}
bool isPart(TreeNode* p1, TreeNode* p2)
{
if (!p2) return true;//如果p2没有点了,匹配成功
if (!p1 || p1 -> val != p2 -> val) return false;//p1没有电,匹配失败
//如果p1 p2有点且值相等,那么当前节点匹配,看左右节点是否匹配
return isPart(p1 -> left, p2 -> left) && isPart(p1 -> right, p2 -> right);
}
};
/**
* 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:
TreeNode * mirrorTree(TreeNode* root) {
if (!root) return root;
swap(root->left, root->right);
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
};
/**
* 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:
bool isSymmetric(TreeNode* root) {
// 除了根节点
// 左节点的左儿子和右节点的右儿子 相等
// 左节点的右儿子和右节点的左儿子 相等
if (!root) return true;
// 看左右子树是否对称
return dfs(root -> left, root->right);
}
bool dfs(TreeNode* p1, TreeNode* p2)
{
if (!p1 || !p2) return !p1 && !p2;
//只有两个同时为空才返回true;
if (p1 -> val != p2 -> val) return false;
//如果两个节点相等,则递归判断两个节点的左右儿子
return dfs(p1 -> left, p2 -> right) && dfs(p1 -> right, p2 -> left);
}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector <int> res;
if (matrix.empty()) return res;
int m = matrix.size();
int n = matrix[0].size();
vector<vector<bool>> st(m, vector<bool>(n, false));
int dx[4] = {0,1,0,-1}, dy[4] = {1, 0, -1, 0};
int x = 0, y = 0, d = 0;
for (int i = 0; i < m * n; i ++)
{
res.push_back(matrix[x][y]);
st[x][y] = true;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= m || b < 0 || b >= n || st[a][b])
{
//如果走出了矩阵范围,那么回退到x,y 然后调整方向
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;//新的坐标
}
return res;
}
};
class MinStack {
public:
stack<int> stk, min_stk;
/** initialize your data structure here. */
MinStack() {
}
//单调栈
void push(int x) {
stk.push(x);
if (min_stk.empty() || x <= min_stk.top()) min_stk.push(x);
}
void pop() {
if (stk.top() == min_stk.top()) min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int min() {
return min_stk.top();
}
};
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int m = pushed.size();
int n = popped.size();
stack<int> stk;
for (int i = 0, j = 0; i < m; i ++)
{
stk.push(pushed[i]);
while (j < n && stk.size() && stk.top() == popped[j])
stk.pop(), j++;
}
if (stk.size()) return false;
return true;
}
};
/**
* 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) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
res.push_back(t -> val);
if (t -> left) q.push(t -> left);
if (t -> right) q.push(t -> right);
}
return res;
}
};
/**
* 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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
// 第一行加入null标记
// 遍历到第一行的null时,第二行自然也是null此时代表第二行结束...依次类推
queue<TreeNode*> q;
if (!root) return res;
q.push(root);
q.push(nullptr);
vector<int> level;
while (q.size())
{
auto t = q.front();
q.pop();
if (!t)
{
// 如果到达末尾
if (level.empty()) return res;
// 如果到达行尾
res.push_back(level);
level.clear();
q.push(nullptr);
continue;
}
level.push_back(t -> val);
if (t -> left) q.push(t -> left);
if (t -> right) q.push(t -> right);
}
return res;
}
};
/**
* 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<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
vector<int> level;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
bool zigzag = false;
while(q.size())
{
auto t = q.front();
q.pop();
if(!t)
{
if (level.empty()) return res;
if (zigzag) reverse(level.begin(), level.end());
res.push_back(level);
level.clear();
q.push(nullptr);
zigzag = !zigzag;
continue;
}
level.push_back(t -> val);
if (t -> left) q.push(t -> left);
if (t -> right) q.push(t -> right);
}
return res;
}
};
// 中序+后序 nlogn
class Solution {
public:
vector<int> inorder, postorder;
map<int, int> hash;
bool verifyPostorder(vector<int>& postorder_) {
postorder = postorder_;
sort(postorder_.begin(), postorder_.end());
inorder = postorder_;
for (int i = 0; i < postorder.size(); i ++) hash[inorder[i]] = i;
return dfs(0, postorder.size() - 1, 0, inorder.size() - 1);
}
int dfs(int pl, int pr, int il, int ir)
{
if (pl > pr) return true;
auto root = postorder[pr];
int k = hash[root];
if (k < il || k > ir) return false; //当前的根节点不在中序遍历的范围内
bool left = dfs(pl, pl + k- il - 1 , il, k - 1);//长度为k-il
bool right = dfs(pl + k-il, pr - 1, k+ 1, ir);
return left && right;
}
};
//只用后序遍历 n*n
class Solution {
public:
vector<int> postorder;
bool verifyPostorder(vector<int>& postorder_) {
postorder = postorder_;
return dfs(0, postorder.size() - 1);
}
bool dfs(int l, int r)
{
if (l >= r) return true;
int root = postorder[r];
int k = l;
//左子树的元素都小于根节点
while (k < r && postorder[k] < root)
k++;//右子树的第一个元素
for (int i = k; i < r; i ++)
// 右子树的元素都大于根节点
if (postorder[i] < root)
return false;
return dfs(l, k - 1) && dfs(k, r - 1);
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> path;
vector<vector<int>> ans;
vector<vector<int>> pathSum(TreeNode* root, int target) {
dfs(root, target);
return ans;
}
void dfs(TreeNode* root, int target)
{
if (!root) return;
// 单层递归逻辑
/*
1 先放入当前节点
2 检查是否为叶节点
如果是
满足和条件,直接加入答案
不满足条件,回溯 if(!root) return
如果不是,递归 if(!root) return
*/
path.push_back(root->val);
target -= root->val;
if (!root-> left && !root->right && !target)
ans.push_back(path);
dfs(root-> left, target);
dfs(root-> right, target);
path.pop_back();
}
};
/*
// 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) {
if (!head) return nullptr;
//复制链表
Node* cur = head;
while (cur)
{
Node* post = new Node(cur->val);
post-> next = cur -> next;
cur -> next = post;
cur = post -> next;
}
// 复制随机指针
cur = head;
while (cur)
{
if (cur -> random)
cur -> next -> random = cur -> random -> next;
cur = cur -> next -> next;
}
// 分离节点
auto dummy = new Node(-1);
cur = dummy;
Node* raw = head;
while (raw)
{
cur -> next = raw -> next;
raw -> next = cur -> next-> next;
cur = cur -> next;
raw = raw -> next;
}
return dummy-> next;
}
};
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root) return root;
auto slides = dfs(root);
slides.first -> left = slides.second;
slides.second -> right = slides.first;
return slides.first;
}
pair<Node*, Node*> dfs(Node* root)
{
if (!root->left && !root-> right) return {root, root};
else if (root->left && root->right)
{
//pari存储双向链表的头尾节点,经过dfs后所有子树都链接成了双向链表
// 将头尾指针连接即可得到双向循环链表
auto lslide = dfs(root->left), rslide = dfs(root->right);
lslide.second -> right = root, root-> left = lslide.second;
root-> right = rslide.first, rslide.first -> left = root;
return {lslide.first, rslide.second};
}
else if (root->left)
{
auto lslide = dfs(root->left);
lslide.second -> right = root, root-> left = lslide.second;
return {lslide.first, root};
}
else
{
auto rslide = dfs(root->right);
root-> right = rslide.first, rslide.first -> left = root;
return {root, rslide.second};
}
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec{
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root, res);
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}
void dfs_s(TreeNode* root, string& res)
{
if (!root)
{
res += "null ";
return;
}
res += to_string(root->val) + " ";
dfs_s(root->left, res);
dfs_s(root->right,res);
}
TreeNode* dfs_d(string data, int& u)
{
if (u == data.size()) return nullptr;
int k = u;
//当前节点的末尾后一位
while (data[k] != ' ') k ++;
//节点是null是null的话,空格的下一位 下一节点
if (data[u] == 'n')
{
u = k + 1;
return nullptr;
}
//如果是数字
int val = 0;
//负数
if (data[u] == '-')
{
for (int i = u + 1; i < k; i++)
val = val * 10 + (data[i]- '0');
val = -val;
}
//正数
else
{
for (int i = u; i < k; i++)
val = val * 10 + (data[i]- '0');
}
u = k + 1;
auto root = new TreeNode(val);
root-> left = dfs_d(data, u);//遍历到空节点,返回的是null
root-> right = dfs_d(data, u);//遍历到空节点,返回的是null
return root;
}
};
class Solution {
public:
vector<string> res;
string path;
vector<string> permutation(string s) {
res.clear();
path.clear();
sort(s.begin(), s.end());
vector<bool> used(s.size(), false);
dfs(s, used);
return res;
}
void dfs(string s, vector<bool>& used)
{
if (path.size() == s.size())
{
res.push_back(path);
return;
}
for (int i = 0; i < s.size(); i ++)
{
if (i > 0 && s[i] == s[i-1] && !used[i-1])
continue;
if (!used[i])
{
path += s[i];
used[i] = true;
dfs(s, used);
used[i] = false;
path.pop_back();
}
}
}
};
class Solution {
public:
int majorityElement(vector<int>& nums) {
int val, cnt;
val = -1, cnt = 0;
/*
使用其他数字去抵消超过一半的数字,剩下的就是结果
如果数字等于val,cnt++;
如果数字不等于val,cnt--
如果cnt=0,更新数字 val=nums[i], cnt = 1
*/
for (int i = 0; i < nums.size(); i ++)
{
if (!cnt) val = nums[i], cnt = 1;
else if (nums[i] == val) cnt ++;
else cnt --;
}
return val;
}
};
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
/*
维护一个大根堆:因为大根堆元素比堆顶元素小
*/
vector<int> res;
priority_queue<int> heap;
for (auto x : arr)
{
heap.push(x);
if (heap.size() > k) heap.pop();
}
for (int i = 0; i < k; i ++)
{
res.push_back(heap.top());
heap.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
MedianFinder() { }
void addNum(int num) {
max_heap.push(num);
if (min_heap.size() && max_heap.top() > min_heap.top())
{
auto maxv = max_heap.top(), minv = min_heap.top();
max_heap.pop(), min_heap.pop();
max_heap.push(minv), min_heap.push(maxv);
}
if (max_heap.size() - min_heap.size() > 1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
}
double findMedian() {
if (max_heap.size() + min_heap.size() & 1) return max_heap.top();
else return (max_heap.top() + min_heap.top()) / 2.0;
}
};
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int summ = 0;
int res = INT_MIN;
for (int i = 0; i < nums.size(); i ++)
{
//如果小于0从新开始计算数组和
//以当前为结尾的前缀和
summ = max(summ + nums[i], nums[i]);
res = max(res, summ);
}
return res;
}
};
class Solution {
public:
int countDigitOne(int n) {
/*
cur:当前位置
left:cur左边
right:cur右边
t: 10^右边的位数
左边取0~left-1(cur肯定会有1) 右边可以取全部 left*t次
左边取left的话,cur可能没有1
当前cur是0时,res+= 0
当前cur是1时,res+=right
当前cur>1时,res+=t
*/
if (!n) return 0;
vector<int> nums;
int res = 0;
while(n) nums.push_back(n % 10), n /= 10;
for (int i = nums.size() - 1; i >=0; i --)
{
int left = 0, right = 0, t = 1;
for(int j = nums.size() - 1; j > i; j --) left = left * 10 + nums[j];
for (int j = i - 1; j >=0; j --) right = right * 10 + nums[j], t *= 10;
res += left * t;
if (nums[i] == 1) res += right + 1;
else if (nums[i] > 1) res += t;
else res += 0;
}
return res;
}
};
class Solution {
public:
int findNthDigit(int n) {
//确定是几位数 n-10-90*2-900*3-9000*4-..直到小于i*s 位数*9
//确定该位数的第几个数 1000+235-1 =1234
//属于该数的第几位 1234 %
long long i = 1, s = 9, base = 1;
// 1 计算几位数i,剩下多少位n
while (n > i * s)
{
n -= i * s;
i ++;//位数+1
s*= 10;//数量级扩大十倍
base *=10; //基数扩大十倍
}
// 2 根据n,计算i位数的第多少个数字,下取整代替上取整
// 计算n,属于i位数的第几位
int number = base + (n + i - 1) / i - 1;
int r = n % i ? n % i : i;
// 3 根据i,number,r 可以定位到真实的数字
// 如果整除,那么就是最后一位,如果不整除,去掉r位后面的
for (int j = 0; j < i - r; j ++) number /= 10;
return number % 10;
}
};
class Solution {
public:
/* 定义新的比较方式
a < b <=> ab < ba
如果排好序的序列是
a1 a2 a3 a4.. an
证明 假设最小序列是
a1a2a4a3 ..an,且a4 > a3 即a4a3 > a3a4
交换a3a4的位置显然可以得到更小的一个数
a1a2|a3a4...an
*/
static bool cmp(int a, int b)
{
auto as = to_string(a), bs = to_string(b);
return as + bs < bs + as;
}
string minNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
string res;
for (auto x: nums) res += to_string(x);
return res;
}
};
class Solution {
public:
int translateNum(int num) {
/*
1 状态表示 dp[i] 前i位数字有多少中不同表示
2 状态计算
第i位数翻译成一位: dp[i-1]
i-1,i翻译成一位: dp[i-2]
必须在10~25
dp[i] = dp[i-1] + dp[i-2]
3 边界
dp[0] = 1
*/
auto s = to_string(num);
int n = s.size();
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i ++)
{
dp[i] = dp[i - 1];
int t = (s[i - 2] - '0') * 10 + (s[i-1] - '0');
if (t >=10 && t <= 25) dp[i] += dp[i - 2];
}
return dp[n];
}
};
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
/*
1状态表示dp[i,j]走到当前各自能够获得的最大价值是多少
2 状态转移
从上方dp[i-1,j] 或者从左边dp[i,j-1]的最大值
dp[i,j] = max(dp[i-1,j],dp[i, j -1]) + grid[i][j]
3 状态初始化
dp[i,0] = f[0,j] = 0;
*/
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
dp[i][j] = max(dp[i-1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
return dp[m][n];
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
/*暴力做法
先确定结尾,然后枚举前缀最长不重复子串
双指针做法:借助哈希表
如果i,j之间有重复,那么把i往后移动一位
最后取最大值
*/
unordered_map<char, int> cnt;
int res = 0;
for (int i = 0, j = 0; j < s.size(); j ++)
{
cnt[s[j]]++;
if (cnt[s[j]] > 1)
{
while (cnt[s[i]] == 1)
{
cnt[s[i]] --;
i++;
}
cnt[s[i]] --;
i++;
}
res = max(res, j- i + 1);
}
return res;
}
};
class Solution {
public:
int nthUglyNumber(int n) {
/*三路归并
假设丑数序列为a1 a2 a3 a4 a5...
设置三个序列
nums1 = a1*2 a2*2 a3*2..
nums2 = a1*3 a2*3 a3*3..
nums3 = a1*5 a2*5 a3*5..
那么这三个序列一定是丑数序列,如何避免遗漏呢?
归并排序的思想
t = min(2*dp[i],3*dp[j],5*dp[k])
*/
if (n <= 1) return n;
vector<int> dp(1, 1);
int i = 0, j = 0, k = 0;
long long t = 0;
while (--n)
{
t = min(min(2 * dp[i], 3 * dp[j]), 5 * dp[k]);
if (t == 2 * dp[i]) i ++;
if (t == 3 * dp[j]) j ++;
if (t == 5 * dp[k]) k ++;
dp.push_back(t);
}
return dp.back();
}
};
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> cnt;
char res = ' ';
for (auto x: s) cnt[x] ++;
for (auto x: s)
if (cnt[x] == 1)
{
res = x;
break;
}
return res;
}
};
class Solution {
public:
int merge_sort(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
vector<int> temp;
int i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (nums[i] > nums[j])
{
temp.push_back(nums[j++]);
res += mid - i + 1;
}
else temp.push_back(nums[i++]);
}
while (i <= mid) temp.push_back(nums[i++]);
while (j <= r) temp.push_back(nums[j++]);
i = l;
for (auto x: temp) nums[i++] = x;
return res;
}
int reversePairs(vector<int>& nums) {
//暴力做法:冒泡排序 n2
// 归并排序模板题 nlogn
return merge_sort(nums, 0, nums.size() - 1);
}
};
/**
* 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) {
/*因为不等长,所以把两个链表拼接起来就登场了
headA headB 时就相交了*/
ListNode* prea = headA;
ListNode* preb = headB;
while (prea != preb)
{
prea = prea != NULL? prea -> next: headB;
preb = preb != NULL? preb -> next: headA;
}
return prea;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
// 分为三个区间
// target
while (l < r)
{
// 只要小于k就会往右走,直到找到左端点
int mid = (l + r) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
if (nums[l] != target) return 0;
int left = l;
l = 0, r = nums.size() - 1;
while (l < r)
{
//只要小于等于k就会往右走,直到找到做端点
//l == mid时注意向上取整
int mid = (l + r + 1) / 2;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
return r - left + 1;
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = n * (n + 1) / 2; // 1~n 总共有n个数
for (auto x: nums) res -= x;
return res;
}
};
//二分查找
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] > mid) r = mid - 1;
else if (nums[mid] == mid) l = mid + 1;
else continue;
}
if (nums[l] == l) return l + 1;
return l;
}
};
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
// nums[i] - nums[i-1] >= 0
// i - i + 1 >= 0
// nums[i] - i - nums[i-1] + i + 1 >=0
// nums[i] - i 是单调递增的
int mid = l + r >>1;
if (nums[mid] - mid > 0) r = mid;
else if (nums[mid] - mid < 0) l = mid + 1;
else return mid;
}
if (nums[l] == l) return l;
return -1;
}
};
/**
* 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:
TreeNode* ans;
int kthLargest(TreeNode* root, int k) {
dfs(root, k);
return ans->val;
}
void dfs(TreeNode* root, int& k)
{
if (!root) return;
dfs(root-> right, k);
k --;
if (k == 0) ans = root;
if (k > 0 ) dfs(root->left, k);
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
// 左子树深度+右子树深度+1
if (!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
/**
* 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:
bool ans = true;
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root)
{
if (!root) return 0;
int ldepth = dfs(root->left);
int rdepth = dfs(root->right);
if (abs(ldepth - rdepth) > 1) ans = false;
return max(ldepth, rdepth) + 1;
}
};
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
// 异或操作可以得到集合中计数为1的数(只能有1个)
// 如果有两个 异或结果为 x^y 其二进制表示一定有一位为1,另一个数该位为0
// 将所有数分成1集合和0集合,然后进行异或即可找出两个集合中计数为1的数
int sum = 0;
for (auto x: nums) sum ^= x;
int k = 0;
while (!(sum >> k & 1)) k ++;
int first = 0;
for (auto x: nums)
if (x >> k & 1)
first ^= x;
return vector<int>{first, sum ^ first};
}
};
class Solution {
public:
int singleNumber(vector<int>& nums) {
// // 唯一数出现1次,其他出现3次
// // 有限状态机
// // 对于x的所有位(0,0)-> (1,0) -> (0,1) -> (0,0)
// int ones = 0, twos = 0;
// for (auto x: nums)
// {
// ones = (ones ^ x) & (~twos);
// twos = (twos ^ x) & (~ones);
// }
// // ones相当于x的所有位 因为0遇到0->0 0遇到1->1
// return ones;
int ans = 0;
for (int i = 0; i < 32; i ++)
{
int cnt = 0;
for (auto x: nums)
if (x >> i & 1) cnt ++;
if (cnt % 3)
ans = ans | 1 << i;//%3=1的必定为唯一数
}
return ans;
}
};
//两数之和
class Solution {
public:
unordered_set<int> hash;
vector<int> twoSum(vector<int>& nums, int target) {
for (auto x: nums)
{
if (hash.count(target-x)) return vector<int> {target-x, x};
else hash.insert(x);
}
return vector<int> {-1,-1};
}
};
//双指针的题目
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
for(int i = 1, j = 1 ,s = 1; i <= target; i ++)
{
while (s < target) s += ++ j;
if (s == target && j - i + 1 > 1)
{
vector<int> line;
for (int k = i; k <= j; k ++) line.push_back(k);
res.push_back(line);
}
s -= i;//每次右移需要减去i
}
return res;
}
};
class Solution {
public:
string reverseWords(string s) {
string res;
for (int i = 0; i < s.size(); i ++)
{
while (s[i] == ' ') i ++;//start of word
int j = i;
while (j < s.size() && s[j] != ' ') j ++;//end of word
string word;
for (int k = i; k < j; k ++) word += s[k];//word
if (j < s.size()) res = ' ' + word + res;
else if (j) res = word + res;
i = j;
}
return res[0] == ' '? res.substr(1) : res;
}
};
class Solution {
public:
string reverseLeftWords(string s, int n) {
// 全部翻转
// 前n-k和翻转 后k个翻转
reverse(s.begin(), s.end());
reverse(s.begin(), s.begin() + s.size() - n);
reverse(s.begin() + s.size() - n,s.end());
return s;
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> que;
for (int i = 0; i <nums.size(); i++)
{
if (que.size() && i - que.front() + 1 > k)
que.pop_front();
while (que.size() && nums[que.back()] <= nums[i])
que.pop_back();
que.push_back(i);
if (que.size() && i >= k - 1) res.push_back(nums[que.front()]);
}
return res;
}
};
// 可能的点数列表
// 背包问题:分组背包
class Solution {
public:
vector<int> numberOfDice(int n) {
vector<int> res;
vector<int> dp(6 * n + 1, 0);//可能的得分
for (int i = 1; i <= 6; i ++) dp[i] = 1;//第一次扔骰子1~6的投法都为1
for (int i = 2; i <= n; i++) //分组数
for (int j = 6 * i; j >= 0; j --) // 物品数 倒序遍历避免 当前dp[j-k]覆盖过去的dp[j-k]
{
dp[j] = 0;//清空数组,dp[j]不会由上一个同一得分求出
for (int k = 6; k >=1; k--)//价值
if (j > k)
dp[j] += dp[j-k];
}
for (int i = n; i < 6 * n + 1; i ++) res.push_back(dp[i]);
return res;
}
};
//可能的点数对应的概率
class Solution {
public:
vector<double> dicesProbability(int n) {
//取值范围为n-6n 5n + 1中可能的值
//dp[N][i] 表示有n颗骰子且和为i时的概率
//dp[1][i] = 1/ 6
//dp[2][i] = dp[1][i-1]+dp[1][i-2]...+dp[1][i-6]
//res = dp[N]
//当前骰子点数之和i+1,,i+2, i+6,只能由dp即过去的的i中递推过来
//如果反向推到会导致数组越界
vector<double> dp(6, 1.0/6.0);
for (int i = 2; i <= n; i ++)
{
vector<double> temp(5*i + 1, 0.0);
for (int j = 0; j < dp.size(); j ++)
for (int k = 0; k < 6; k ++)
temp[j + k] += dp[j] * (1.0/ 6.0);
dp = temp;
}
return dp;
}
};
class Solution {
public:
bool isStraight(vector<int>& nums) {
/*1 删掉0
2 重复
3 差<=4
*/
if (!nums.size()) return false;
sort(nums.begin(), nums.end());
int k = 0;
while (!nums[k]) k ++;
for (int i = k + 1; i < nums.size(); i ++)
if (nums[i] == nums[i-1])
return false;
return nums.back() - nums[k] <= 4;
}
};
class Solution {
public:
int lastRemaining(int n, int m) {
/*
n个人每次删去第m个,最终剩下dp[n][m]
0 1 2 ... m-1 m m+1 m+2 ...n
重新编号 . —— 0 1 2
n-1个人则是,重新编号后的dp[n-1,m] (此时原来的编号为 新的编号+m)%n右移了m位
dp[n][m] = (dp[n-1][m] + m) % n
dp[1][m] = 0
*/
// vector> dp(n + 1, vector(m + 1, 0));
// for (int i = 2; i <= n; i ++)
// for (int j = 1; j <= m; j ++)
// dp[i][j] = (dp[i-1][j] + j) % i;
// return dp[n][m];
if (n == 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int res = 0;
for (auto p: prices)
{
if (p < minPrice) minPrice = p;
res = max(res, p - minPrice);
}
return res;
}
};
class Solution {
public:
int sumNums(int n) {
int res = n;
(n >0) && (res += sumNums(n- 1));
return res;
}
};
class Solution {
public:
int add(int a, int b) {
// 位运算在计算机中的加法
// a + b = cd
// d = a^b
// c = a&b
/*
不考虑所有进位计算 a^b
再加上所有进位 a&b 有进位的地方都是1,需要把结果左移1 a&b << 1;
结果等于 a^b + a&b << 1 新的两个数相加
b中的进位总会消失
*/
while (b)
{
int sum1 = a ^ b;
unsigned int carry = (unsigned int)(a & b) << 1;
a = sum1;
b = carry;//
}
return a;
}
};
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
if (!a.size()) return vector<int>();
vector<int> res(a.size(),1);
//左半边先乘进去 1 2 3 4 5
// 1 1 2 6 24
for (int i = 0, lprod = 1; i < a.size(); i ++){
res[i] = lprod;
lprod*= a[i];
}
//右半边再乘进去
// i= 4 24*1 右边没有 rprod = 5
// i= 3 6*5 右边是5 左边是123 rprod = 20
// i= 2 2*20 左边是12 右边是45 rprod=60
// i= 1 1*60 左边是1 rprod = 120
// i= 0 120
for (int i = a.size() - 1, rprod = 1; i >= 0; i --)
{
res[i]*= rprod;
rprod*= a[i];
}
return res;
}
};
class Solution {
public:
int strToInt(string str) {
int k = 0;
while (k < str.size() && str[k] == ' ') k ++;
long long num = 0;
bool is_minus = false;
if (str[k] == '+') k ++;
else if (str[k] == '-')
{
k++;
is_minus=true;
}
while (k < str.size() && str[k] >= '0' && str[k] <= '9')
{
num = num * 10 + str[k] - '0';
k++;
if (!is_minus && num > INT_MAX) return INT_MAX;
if (is_minus && num > INT_MAX) return INT_MIN;
}
if (is_minus) num *= -1;
return (int)num;
}
};
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
/*
在左右两边,返回根节点
都在左边,公共祖先在左边
都在右边,公共祖先在右边
*/
if (!root) return nullptr;
if (root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);//查找左子树中是否存在p q节点
auto right = lowestCommonAncestor(root->right,p, q);//查找右子树中是否存在p q节点
if (left && right) return root;
else if (left) return left;
return right;
}
};