Clearest LeetCode C++ Solutions. 本项目追求思路清晰,代码简洁。This project is intended to clarify the general problem solving ideas
Clearest LeetCode C++ Solutions. This project is intended to clarify the problem solving ideas. 我们追求的目标:清晰简单的思路 + 畅快巧妙的代码
以上是一张互联网公司面试中经常考察的问题类型总结的思维导图,此栏目将根据 LeetCode 中文版探索板块给出的路线制作题解,各专栏将尽力覆盖各大知识要点并总结知识点和套路。相比于题库解析部分追求代码的绝对精简,本专题追求以高可读性呈现各大专题的常规思路,为后续的题库解析部分做铺垫。俩部分题目可能重复,但专题部分会有更详细的解析,且可能运用不同解法。
遍历
和 搜索最短路径
# 1.初始化队列
# 2.选择合适的根节点压入队列
# 3.使用 while 进入队列循环,直到搜索完毕
# {
# 4.取出一个节点
# 5.放入这个节点周围的节点
# }
队列:先入先出的数据结构
代码
队列和广度优先搜索
class Solution {
public:
bool inGrid(vector<vector<char>>& grid, pair <int,int> a) //判断点是否超出边界
{
if(a.first >= 0 && a.first < grid.size() && a.second >= 0 && a.second < grid[0].size())
return true;
else
return false;
}
/* void BFS(vector<vector<char>>& grid, queue<pair<int,int>>& po) //BFS的过程
{
if(po.empty()) return;
pair <int,int> temp = po.front();
po.pop();
grid[temp.first][temp.second] = '0';
pair <int,int> up = {temp.first + 1, temp.second};
pair <int,int> down = {temp.first - 1, temp.second};
pair <int,int> left = {temp.first, temp.second - 1};
pair <int,int> right = {temp.first, temp.second + 1};
if(inGrid(grid,up) && grid[temp.first + 1][temp.second] == '1') //若拓展出去的点仍在边界之内,且是岛屿的一部分,将其push入队列内,作为之后迭代的起始点
po.push(up);
if(inGrid(grid,down) && grid[temp.first - 1][temp.second] == '1')
po.push(down);
if(inGrid(grid,left) && grid[temp.first][temp.second - 1] == '1')
po.push(left);
if(inGrid(grid,right) && grid[temp.first][temp.second + 1] == '1')
po.push(right);
return BFS(grid,po);
}
*/
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
queue <pair<int,int>> po;
if(grid.empty()) return 0; //若地图为空,直接返回0
int m = grid.size();
int n = grid[0].size();
for(int y = 0; y < m; ++y) //遍历整张地图的每个点
{
for(int x = 0; x <n; ++x)
{
if(grid[y][x] == '1') //若bool值为true,该点为新发现的岛屿的起始点
{
po.push({y,x});
//BFS(grid,po);
++ans; //岛屿数加一
while(!po.empty()) //进入广度优先搜索
{
pair <int,int> temp = po.front();
po.pop();
if(grid[temp.first][temp.second] == '0')
continue;
grid[temp.first][temp.second] = '0';
pair <int,int> up = {temp.first + 1, temp.second};
pair <int,int> down = {temp.first - 1, temp.second};
pair <int,int> left = {temp.first, temp.second - 1};
pair <int,int> right = {temp.first, temp.second + 1};
if(inGrid(grid,up) && grid[temp.first + 1][temp.second] == '1') //若拓展出去的点仍在边界之内,且是岛屿的一部分,将其push入队列内,作为之后迭代的起始点
po.push(up);
if(inGrid(grid,down) && grid[temp.first - 1][temp.second] == '1')
po.push(down);
if(inGrid(grid,left) && grid[temp.first][temp.second - 1] == '1')
po.push(left);
if(inGrid(grid,right) && grid[temp.first][temp.second + 1] == '1')
po.push(right);
}
}
}
}
return ans;
}
};
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
set<string> dead(deadends.begin(),deadends.end()); //收录死锁的数据
set<string> done; //用来记录已经遍历过的数字
string beginstr = "0000"; //记录起始数据
done.insert(beginstr);
// BFS 从这里开始--------------------------------------------------------------
queue<pair<int,string>>record; //创建队列记录当前深度和节点
record.push({0,beginstr});
if (dead.count(beginstr)) return -1; //如果死锁数据中包含起始数据,直接返回-1
while(!record.empty()) //用BSF遍历所有可能的数据
{
auto tmp=record.front(); //提取队列中第一个数据
record.pop();
if (tmp.second==target) return tmp.first; //将目标的判断放在加减操作之前,还可以判断起始数据是否是目标数据,较严谨
for (int i=0; i<4; i++) //对提取出来的数据的每一位做+1和-1的操作
{
string spls = tmp.second;
string ssbs = tmp.second;
spls[i] = (spls[i] - '0' + 1) % 10 +'0'; //用mod来处理循环的数字
ssbs[i] = ((ssbs[i] - '0') + 9) % 10 + '0';
if (!dead.count(spls) && !done.count(spls)) //若加一后的数据不存在死锁集合中,且不是之前遍历过的数据
{
record.push({tmp.first+1, spls}); //加到record队列中
done.insert(spls);
}
if (!dead.count(ssbs) && !done.count(ssbs)) //若减一后的数据不存在死锁集合中,且,不是之前遍历过的数据
{
record.push({tmp.first+1, ssbs}); // 加到record队列中
done.insert(ssbs);
}
}
}
return -1; //若无法得到目标密码,返回-1
}
};
class Solution {
public:
int numSquares(int n) {
vector <int> f (n+1,-1); //初始化 构造一个数组,容量为n+1,所有空间初始化为-1
f[0] = 0; //组成0的完全平方数的个数为0
//BFS从这里开始-------------------------
queue <int> q; 构造一个队列储存nodes,等待处理
q.push(0);
while (!q.empty())
{
int m = q.front(); //取出第一个数据
q.pop();
for(int i = 1; i*i+m <=n; i++) //最小的完全平方数是1
{
if(f[i*i+m] == -1) //若i*i+m这个数字还没有出现过
{
f[i*i+m] = f[m] + 1; //加一次完全平方数,步骤加一
q.push(i*i+m); //放入队列,接着搜索
}
}
}
return f[n];
}
};
栈:后入先出的数据结构
class MinStack {
public:
/** initialize your data structure here. */
stack<int>s; //主数据栈
stack<int>minn; //辅助数据栈
MinStack() {
}
void push(int x) {
s.push(x);
if(minn.empty()||x<=minn.top()) //关键点,见总结
minn.push(x);
}
void pop() {
if(s.top() == minn.top()) //判断数据栈的顶部是否是当前主数据栈的最小值,若是,需要将两个栈的top都pop掉
minn.pop();
s.pop();
}
int top() {
return s.top(); //返回栈的顶部
}
int getMin() {
return minn.top(); //返回最小值
}
};
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 != 0) return false; //若字符串s的字符数不为偶数,直接返回false. 不过没有也可
stack <char> a;
map <char,char> bra; //建立右括号和左括号之间的映射
bra.insert(pair<char,char>(')','('));
bra.insert(pair<char,char>(']','['));
bra.insert(pair<char,char>('}','{'));
int lo;
lo = s.size();
for(int i = 0; i < lo; i++)
{
if(s[i] == '(' || s[i] == '[' || s[i] == '{') //若是左括号,直接推入栈
a.push(s[i]);
if(s[i] == ')' || s[i] == ']' || s[i] == '}') //若是右括号,先判断栈内是否有左括号
{
if(a.empty()) //见总结*
return false;
if(bra[s[i]] == a.top()) //若右括号与栈顶的左括号匹配,pop掉栈a最上方的左括号,否则返回false
{
a.pop();
}
else
return false;
}
}
if(a.empty()) //若操作之后,栈内还有字符,返回false
return true;
else
return false;
}
};
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
vector <int> ans (T.size(), 0); //创建与气温天数相同的数组,收录答案
stack <int> res;
for(int i = T.size()-1; i >= 0; --i) //从最后一天开始往前
{
while(!res.empty() && T[i] >= T[res.top()]) res.pop(); //若当前数据大于等于栈顶数据,pop掉栈顶数据直到栈为空或当前数据小于栈顶数据
if(res.empty())
ans[i] = 0;
else
ans[i] = res.top() - i;
res.push(i); //栈顶始终是整个栈的最小数据
}
return ans;
}
};
class Solution {
public:
int str2num(string s) //将string转换为int类型的函数,在之后要调用
{
int num;
stringstream ss(s);
ss>>num;
return num;
}
int evalRPN(vector<string>& tokens) {
stack <int> s;
int n = tokens.size();
int ans;
if(tokens[0] != "+" && tokens[0] != "-" && tokens[0] != "*" && tokens[0] != "/") //防止测试数据仅有一个数字
ans = str2num(tokens[0]);
for(int i = 0; i <= n - 1 ; ++i) //运算过程
{
if(tokens[i] == "+")
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
ans = left + right;
s.push(ans);
}
else if(tokens[i] == "-")
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
ans = left - right;
s.push(ans);
}
else if(tokens[i] == "*")
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
ans = left * right;
s.push(ans);
}
else if(tokens[i] == "/")
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
ans = left / right;
s.push(ans);
}
else
{
int r = str2num(tokens[i]); //遇到数字直接push
s.push(r);
}
}
return ans;
}
};
栈和深度优先搜索
class Solution {
public:
bool inGrid(vector<vector<char>>& grid, pair <int,int> a) //判断点是否超出边界
{
if(a.first >= 0 && a.first < grid.size() && a.second >= 0 && a.second < grid[0].size())
return true;
else
return false;
}
void DFS(vector<vector<char>>& grid, stack<pair<int,int>>& po) //DFS的过程
{
if(po.empty()) return;
pair <int,int> temp = po.top();
po.pop();
grid[temp.first][temp.second] = '0';
pair <int,int> up = {temp.first + 1, temp.second};
pair <int,int> down = {temp.first - 1, temp.second};
pair <int,int> left = {temp.first, temp.second - 1};
pair <int,int> right = {temp.first, temp.second + 1};
if(inGrid(grid,up) && grid[temp.first + 1][temp.second] == '1') //若拓展出去的点仍在边界之内,且是岛屿的一部分,将其push入栈内,作为之后迭代的起始点
po.push(up);
if(inGrid(grid,down) && grid[temp.first - 1][temp.second] == '1')
po.push(down);
if(inGrid(grid,left) && grid[temp.first][temp.second - 1] == '1')
po.push(left);
if(inGrid(grid,right) && grid[temp.first][temp.second + 1] == '1')
po.push(right);
return DFS(grid,po);
}
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
stack <pair<int,int>> po;
if(grid.empty()) return 0; //若地图为空,直接返回0
int m = grid.size();
int n = grid[0].size();
for(int y = 0; y < m; ++y) //遍历整张地图的每个点
{
for(int x = 0; x <n; ++x)
{
if(grid[y][x] == '1') //若bool值为true,该点为新发现的岛屿的起始点
{
po.push({y,x});
DFS(grid,po); //进入深度优先搜索
++ans; //岛屿数加一
}
}
}
return ans;
}
};
class Solution {
public:
void DFS(vector<int>& nums, int S, int& count, int counter, int sum) //DFS函数
{
if(counter == nums.size())
{
if(sum == S)
++ count;
return;
}
DFS(nums, S, count, counter + 1, sum + nums[counter]);
DFS(nums, S, count, counter + 1, sum - nums[counter]);
}
int findTargetSumWays(vector<int>& nums, int S) {
int count = 0;
int sum = 0;
DFS(nums, S, count, 0, sum);
return count;
}
};
class Solution {
public:
vector <int> rest;
vector<int> inorderTraversal(TreeNode* root) {
if(root != NULL)
{
inorderTraversal(root -> left);
rest.push_back(root -> val);
inorderTraversal(root -> right);
}
return rest;
}
};
class MyQueue {
public:
/** Initialize your data structure here. */
stack <int> a;
stack <int> b;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
a.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int len;
len = a.size();
for(int i = 0; i < len; ++i)
{
b.push(a.top());
a.pop();
}
int cur;
cur = b.top();
b.pop();
for(int j = 0; j < len - 1; ++j)
{
a.push(b.top());
b.pop();
}
return cur;
}
/** Get the front element. */
int peek() {
int len;
len = a.size();
for(int i = 0; i < len; ++i)
{
b.push(a.top());
a.pop();
}
int cur;
cur = b.top();
for(int j = 0; j < len; ++j)
{
a.push(b.top());
b.pop();
}
return cur;
}
/** Returns whether the queue is empty. */
bool empty() {
return a.empty() && b.empty();
}
};
class MyStack {
public:
/** Initialize your data structure here. */
queue <int> q1;
queue <int> q2;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) { //保证数据全部push到同一个队列
if(q1.empty())
q2.push(x);
else
q1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
if(q1.empty())
{
int len = q2.size();
for(int i = 0; i<len - 1; ++i) //将有数据的队列的数据除了最后一个以外,全部push到另一个队列。
{
q1.push(q2.front());
q2.pop();
}
int a=q2.front();
q2.pop();
return a;
}
else
{
int len = q1.size();
for(int i = 0; i<len - 1; ++i) //同上
{
q2.push(q1.front());
q1.pop();
}
int a=q1.front();
q1.pop();
return a;
}
}
/** Get the top element. */
int top() {
if(q1.empty())
{
//q2.size()
int len = q2.size();
for(int i = 0; i<len - 1; ++i) //同上
{
q1.push(q2.front());
q2.pop();
}
int a = q2.front();
q1.push(q2.front());
q2.pop();
return a;
}
else
{
int len = q1.size();
for(int i = 0; i<len-1; ++i) //同上
{
q2.push(q1.front());
q1.pop();
}
int a = q1.front();
q2.push(q1.front());
q1.pop();
return a;
}
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty() && q2.empty();
}
};
class Solution {
public:
string decodeString(string s) {
string res = "";
stack <int> nums;
stack <string> strs;
int num = 0;
int len = s.size();
for(int i = 0; i < len; ++ i)
{
if(s[i] >= '0' && s[i] <= '9')
{
num = num * 10 + s[i] - '0';
}
else if((s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= 'A' && s[i] <= 'Z'))
{
res = res + s[i];
}
else if(s[i] == '[') //将‘[’前的数字压入nums栈内, 字母字符串压入strs栈内
{
nums.push(num);
num = 0;
strs.push(res);
res = "";
}
else //遇到‘]’时,操作与之相配的‘[’之间的字符,使用分配律
{
int times = nums.top();
nums.pop();
for(int j = 0; j < times; ++ j)
strs.top() += res;
res = strs.top(); //之后若还是字母,就会直接加到res之后,因为它们是同一级的运算
//若是左括号,res会被压入strs栈,作为上一层的运算
strs.pop();
}
}
return res;
}
};
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
queue <pair<int,int>> olds;
int old = image[sr][sc];
if(newColor == old) return image; //剪枝,若新颜色和旧色一样,直接返回原来的图像
olds.push({sr,sc});
//BFS由此开始--------------
while(!olds.empty())
{
pair<int,int> temp = olds.front();
olds.pop();
image[temp.first][temp.second] = newColor; //因为放入队列中的像素都是旧色像素,直接变成新色
vector<pair<int,int>> around = {{0,1},{0,-1},{-1,0},{1,0}}; //该像素四周的像素
for(int i = 0; i < 4; ++i)
{
int y = temp.first + around[i].first;
int x = temp.second + around[i].second;
if(0 <= y && y < image.size() && 0 <= x && x < image[0].size() && image[y][x] == old) //若在图像内,且是旧色,则压入olds队列
olds.push({y,x});
}
}
return image;
}
};
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
queue <pair<int,int>> q;
int m = matrix.size();
int n = matrix[0].size();
vector <pair<int,int>> around = {{0,1},{0,-1},{-1,0},{1,0}}; //周围节点
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(matrix[i][j] == 0) q.push({i,j}); //将元素为0 的点推入队列
else matrix[i][j] = INT_MAX;
}
}
while(!q.empty())
{
pair <int,int> temp = q.front();
q.pop();
for(int b = 0; b < 4; ++ b) //探索周围节点
{
int y = temp.first + around[b].first;
int x = temp.second + around[b].second;
//判断在图内,且新点的元素大于该点元素。
if(0 <= x && x < n && 0 <= y && y < m && matrix[temp.first][temp.second] < matrix[y][x])
{
matrix[y][x] = matrix[temp.first][temp.second] + 1;
q.push({y,x});
}
}
}
return matrix;
}
};
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
set <int> visited; //记录能进入的房间
visited.insert(0); //从第0房间开始逛
stack <int> keys; //记录房间里的钥匙
keys.push(0); //DFS从这里开始--------------
while(!keys.empty())
{
int key = keys.top(); //取出钥匙走向房间
cout << key;
keys.pop();
int rs = rooms[key].size();
for(int i = 0; i < rs; ++i) //给这个房间里的钥匙做记录,
{
if(!visited.count(rooms[key][i])) //若钥匙通向已知能进入的房间,就不再次不把这个钥匙放进口袋
{
visited.insert(rooms[key][i]);
keys.push(rooms[key][i]); //把这个房间中自己还没有的钥匙放入口袋
}
}
}
return visited.size() == rooms.size(); //如果遍历过的房间数等于实际房间数,返回true
}
};
数组和字符串
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int size = nums.size();
int lsum = 0;
int rsum = 0;
int ans = -1; //若不存在中心索引,返回初始值 -1
for(int i = 1; i<size; ++i) rsum += nums[i]; //先得到索引后边元素的和
for(int j = 0; j <size; ++j) //索引从位置0开始向右移动
{
if(lsum == rsum) //若左右相等,返回该值,跳出循环
{
ans = j;
break;
}
if(j < size - 1) //左边加上nums[j],右侧减去[j+1],此时,候补索引值为j+1
{
lsum += nums[j];
rsum -= nums[j+1];
cout << lsum << " " <<rsum << endl;
}
}
return ans;
}
};
class Solution {
public:
int dominantIndex(vector<int>& nums) {
int ans = -1; //若不存在符合要求的元素,返回-1
if(nums.size() == 1) return 0; //若只有一个元素,一定最大,直接返回它的索引
vector <int> copy(nums.begin(),nums.end()); //复制一份数组,用来找到索引
sort(nums.begin(),nums.end(),greater<int>()); //将数组从大到小排序
if(nums[0] >= 2 * nums[1]) //若符合要求
{
for(int i = 0; i < copy.size(); ++i) //查找该元素原本的索引
{
if(copy[i] == nums[0])
{
return ans = i; //返回索引
}
}
}
return ans;
}
};
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int size = digits.size();
if(digits[size-1] != 9) //若末位不等于9,正常加一
{
++digits[size-1];
}
else //若末位等于9,加一等于0
{
digits[size-1] = 0;
for(int i = size - 1; i >0; --i) //若加完一后若等于0,下一位要进一 如869
{
if(digits[i] == 0)
{
digits[i-1] = (digits[i-1] + 1) % 10;
}
else
break; //若某一位是数不需要进一,跳出循环
}
if(digits[0] == 0) //若到最后最高位也等于0,需要多一位数 如99 + 1 此时为答案为00,进行一下操作
{
digits.insert(digits.begin(),1); //在最高位插入1
}
}
return digits;
}
};
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
vector <int> ans;
if(matrix.empty()) return ans; //若矩阵为空,直接返回空的答案
int m = matrix.size();
int n = matrix[0].size();
pair <int,int> temp = {0,0}; //用来遍历的point
int flag = 1; //记录遍历过程是否过半
while(ans.size() != m*n)
{ //upward,这部分描述斜向上
while(0 <= temp.first && temp.second < n)
{
ans.push_back(matrix[temp.first][temp.second]);
-- temp.first;
++ temp.second;
}
++ temp.first;
if(flag > n/2) //当遍历过半后,要有额外的操作来将point放到正确的位置
{
-- temp.second;
++ temp.first;
}
//downward,这部分描述斜向下
while(temp.first < m && 0 <= temp.second)
{
ans.push_back(matrix[temp.first][temp.second]);
++ temp.first;
-- temp.second;
}
++ temp.second;
if(flag > m/2) ////当遍历过半后,要有额外的操作来将point放到正确的位置
{
-- temp.first;
++ temp.second;
}
if(flag == m/2 && m%2==0) //若在中间状态,比较特殊。
{
-- temp.first;
++ temp.second;
}
++ flag;
}
return ans;
}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector <int> ans;
if(matrix.empty()) return ans; //若数组为空,直接返回答案;
int u = 0; //赋值上下左右边界
int d = matrix.size() - 1;
int l = 0;
int r = matrix[0].size() - 1;
while(true)
{
for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
if(++ u > d) break; //重新设定上边界,若上边界大于下边界,则遍历遍历完成,下同
for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
if(-- r < l) break; //重新设定有边界
for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
if(-- d < u) break; //重新设定下边界
for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
if(++ l > r) break; //重新设定左边界
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans(numRows);
if(numRows == 0) return ans; //若numRows为空,返回空数组
for(int i = 0; i < numRows; ++ i ) //给数组一个个赋值
{
for(int j = 0; j <= i; ++ j)
{
if(j == 0 || j == i) //若是左右两边的边界,赋值为1
ans[i].push_back(1);
else
ans[i].push_back(ans[i-1][j-1] + ans[i-1][j]); //否则赋值为该位置左上与右上的和
}
}
return ans;
}
};
class Solution {
public:
string addBinary(string a, string b) {
int al = a.size();
int bl = b.size();
while(al < bl) //让两个字符串等长,若不等长,在短的字符串前补零,否则之后的操作会超出索引
{
a = '0' + a;
++ al;
}
while(al > bl)
{
b = '0' + b;
++ bl;
}
for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数,同位相加
{
a[j] = a[j] - '0' + b[j];
if(a[j] >= '2') //若大于等于字符‘2’,需要进一
{
a[j] = (a[j] - '0') % 2 + '0';
a[j-1] = a[j-1] + 1;
}
}
a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
if(a[0] >= '2') //若大于等于2,需要进一
{
a[0] = (a[0] - '0') % 2 + '0';
a = '1' + a;
}
return a;
}
};
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ans = "";
if(strs.empty()) return ans; //输入为空,输出空ans
int arr = strs.size();
string min = strs[0];
for(int i = 1; i < arr; ++ i) //找到最短字符串
{
if(strs[i].size() < min.size())
min = strs[i];
}
for(int j = 0; j < min.size(); ++ j) //从第一个字符开始对比,若都一样,ans加上该字符,若不一样,返回答案;
{
for(int m = 0; m < arr; ++m)
{
if(min[j] != strs[m][j])
return ans;
}
ans = ans + min[j];
}
return ans;
}
};
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0;
int j = s.size() - 1;
while(i<j)
{
swap(s[i],s[j]);
++ i;
-- j;
}
}
};
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
int ans = 0;
sort(nums.begin(), nums.end()); //将数组从小到大排列
for(int i = 0; i < nums.size(); i = i +2) //将每对的第一位数相加
ans = ans + nums[i];
return ans;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector <int> ans;
int i = 0;
int j = numbers.size() - 1;
while(i < j) //双指针,若sum太小,i增大,若sum太大,j减小
{
int sum = numbers[i] + numbers[j];
if(sum == target)
{
ans.push_back(i + 1);
ans.push_back(j + 1);
return ans;
}
else if(sum < target)
++ i;
else
-- j;
}
return ans;
}
};
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for(int i = 0; i < nums.size(); ++ i)
{
if(nums[i] != val)
{
nums[k] = nums[i];
++ k;
}
}
return k;
}
};
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int flag = 0; //记录每次连续1的个数
int ans = 0; //记录最大连续1的个数
for(int i = 0; i < nums.size(); ++ i)
{
if(nums[i] == 1)
{
++flag;
}
else
{
if(ans < flag)
{
ans = flag;
flag = 0;
}
else
flag = 0;
}
}
if(ans < flag)
ans = flag;
return ans;
}
};
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int ans = INT_MAX;
int i = 0; //滑窗的右边框
int sum = 0; //窗口间的和
int begin = 0; //滑窗的左边框
while(i < nums.size()) //滑窗的右边框不能超出界限
{
if(sum + nums[i] < s) //若滑窗之间的和小于s,右边框右移,sum增大
{
sum += nums[i];
++ i;
}
else //若滑窗之间的和大于等于s,左边框右移,sum减小
{
if(i - begin < ans) //若当前符合条件的连续子数组比ans内记录的长度更小,则更新ans值
ans = i - begin + 1;
sum = sum - nums[begin];
++ begin;
}
}
return ans == INT_MAX? 0:ans;
}
};
begin
和i
,begin
代表滑窗的左边框,i
代表滑窗的右边框。两者通过分别向右滑动,前者能使窗口之间的和减小,后者能使窗口之间的和增大。开始时二者重合,窗口的和就是重合点所在的数。i
向右滑动,使和变大。begin
向右滑动class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(k > nums.size()) k = k % nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());
}
};
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> vec(rowIndex+1); //想要第rowIndex行,由于从零开始,需要初始化rowIndex + 1行
if(rowIndex == 0) return {1}; //若需要第0行,返回1;
for(int i = 0; i <= rowIndex; ++ i) //一行一行生成
{
for(int j = 0; j <= i; ++ j)
{
if(j == 0 || j == i) //若位置在左右边界,直接填1
vec[i].push_back(1);
else
vec[i].push_back(vec[i-1][j-1] + vec[i-1][j]); //其它位置的值就是左上角与右上角的和
}
}
return vec[rowIndex]; //返回杨辉三角第rowIndex行
}
};
class Solution {
public:
string reverseWords(string s) {
string ans = ""; //用来储存答案
stack <string> mid; //记录所有单词
string temp = ""; //收集完整的单词
int i = 0;
while (s[0] == ' ') //删除字符串前的空格,可以用来检测整个字符串是否都是空格
{
s.erase(0,1);
}
if(s.empty()) return ans; //若s为空,不需要处理,直接返回空字符串
int l = s.size();
while(i <= l) //遍历当前字符串内的所有字符
{
if(s[i] == ' ' || s[i] == '\0') //当遇到空格或'\0',若temp里面有单词,压入栈mid
{
if(!temp.empty())
{
mid.push(temp);
temp = "";
}
}
else //若遇到字母,先加到temp内,使他成为一个完整的单词
{
temp = temp + s[i];
}
++ i;
}
int strsize = mid.size();
for(int j = 0; j < strsize - 1; ++ j) //将栈内的单词放入ans,加上单词间的空格
{
ans = ans + mid.top() + ' ';
mid.pop();
}
ans = ans + mid.top(); //手动添加最后一个单词,因为之前添加单词时,会在末位添加空格。最后一个不需要空格
return ans;
}
};
temp
收集完整的单词后压入栈mid
内class Solution {
public:
string reverseWords(string s) {
string ans = ""; //记录答案
string temp = ""; //记录完整的单词
int l = s.size();
for(int i = 0; i <= l; ++ i) //遍历字符串
{
if(s[i] == ' ' || s[i] =='\0') //遇到空格或字符串结束符,反转已储存单词的temp
{
reverse(temp.begin(),temp.end());
ans += temp;
ans += s[i]; //将反转后的单词拼接到ans上,加上空格或字符串结束符
temp = ""; //初始化temp
}
else
temp += s[i]; //拼接每个字母成为完整的单词
}
return ans;
}
};
ans
内class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int i = 0;
for(int j = 1; j < nums.size(); ++ j)
{
if(nums[i] != nums[j])
{
++ i;
nums[i] = nums[j];
}
}
return i + 1;
}
};
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0;
for(i = 0; i < nums.size() && nums[i] != 0; ++ i); //找到第一个0;
for(int j = i + 1; j < nums.size(); ++ j) //将第一个零之后的第一个非零数字与该0交换
{
if(nums[i] == 0 && nums[j] != 0)
{
swap(nums[i],nums[j]);
++ i;
}
}
}
};
struct Node{ //构造链表Node结构
int val;
Node *prev, *next;
Node(int val): val(val), prev(nullptr), next(nullptr) {} //初始化
};
class MyLinkedList {
public:
MyLinkedList(): head(nullptr), tail(nullptr),size(0){} //初始化链表
int get(int index) { //通过getNode函数返回第index个节点的地址,return 该节点的值
if(getNode(index))
return getNode(index) -> val;
return -1;
}
void addAtHead(int val) { //在head添加节点
auto node = new Node(val); //创建一个Node实例,下同
++ size; //链表长度加一,下同
if(head == nullptr) //如果链表为空,新加的node既是head也是tail,下同
{
head = node;
tail = node;
}
else
{
node -> next = head; //常规的添加头节点步骤,参照代码后的图解
head -> prev = node;
head = node;
}
}
void addAtTail(int val) { //在tail添加节点
auto node = new Node(val);
++ size;
if(tail == nullptr)
{
head = node;
tail = node;
}
else
{
node -> prev = tail; //常规的添加尾节点步骤,参照代码后的图解
tail -> next = node;
tail = node;
}
}
void addAtIndex(int index, int val) {
if(index > size) return; //如果索引大于链表长度,无效索引
if(index == size) //若索引等于链表长度,相当于添加尾节点,直接调用先前定义好的函数
{
addAtTail(val);
return;
}
if(index <= 0) //若索引小于链表长度,本题题目的bug,我们需要将它看成添加头节点,直接调用先前定义好的函数
{
addAtHead(val);
return;
}
auto node = new Node(val); //添加在非head非tail的位置的情况
auto nextNode = getNode(index); //过程参照代码后的图解
nextNode -> prev -> next = node;
node -> prev = nextNode -> prev;
node -> next = nextNode;
nextNode-> prev = node;
++ size;
}
void deleteAtIndex(int index) { //删除节点
if(auto node = getNode(index)) //若该节点不为nullptr,进行以下步骤
{
if(node == head) //若该节点为head,指针head更新为原来head的下一个点的位置
{
head = head -> next;
if(head != nullptr) head -> prev = nullptr; //若新head不为nullptr,将head的prev指针设为空,删除的节点的next指针设为空,即两者断开。
node -> next = nullptr;
}
if(node == tail) //若该节点为tail,与上一步类似
{
tail = tail -> prev;
if(tail != nullptr) tail -> next = nullptr;
node -> prev = nullptr;
}
//若目标节点上或下的指针还不为nullptr,说明指针还未独立出来,需要做以下操作
if(node -> next != nullptr) node -> next -> prev = node -> prev;
if(node -> prev != nullptr) node -> prev -> next = node -> next;
delete node;
-- size;
}
}
private:
Node* getNode(int index) //获得目标节点位置,因为是双向链表,通过判断目标点位置在前半段还是后半段来决定从head开始搜索还是从tail搜索
{
if(index >= size || index < 0) return nullptr;
Node* node;
int i;
if(size/2 >= index)
{
i = index;
node = head;
while(i -- > 0)
{
node = node -> next;
}
}
else
{
i = size - index - 1;
node = tail;
while(i -- > 0)
node = node -> prev;
}
return node;
}
private:
Node* head;
Node* tail;
int size;
};
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *faptr = head;
ListNode *slptr = head;
while(faptr != nullptr && faptr -> next != nullptr)
{
faptr = faptr -> next -> next;
slptr = slptr -> next;
if(faptr == slptr)
return true;
}
return false;
}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !(head -> next)) return nullptr;
ListNode *faptr = head, *slptr = head;
while(faptr && faptr -> next)
{
faptr = faptr -> next -> next;
slptr = slptr -> next;
if(faptr == slptr)
{
slptr = head;
while(slptr != faptr)
{
slptr = slptr -> next;
faptr = faptr -> next;
}
return slptr;
}
}
return nullptr;
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return nullptr;
ListNode *countA = headA;
ListNode *countB = headB;
int lA = 0;
int lB = 0;
while(countA){
++ lA;
countA = countA -> next;
}
while(countB){
++ lB;
countB = countB -> next;
}
int i = max(lA,lB) - min(lA,lB);
if(lA > lB) for(i; i > 0; -- i) headA = headA -> next;
else for(i; i > 0; -- i) headB = headB -> next;
while(headA){
if(headA == headB) return headA;
headA = headA -> next;
headB = headB -> next;
}
return nullptr;
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head || !(head -> next)) return nullptr;
ListNode *temp = head;
int i = 0;
while(temp){ //用来计算删除的点是正数第几个
++ i;
temp = temp -> next;
}
if(i == n){ //此时删除的是head节点
head = head -> next;
return head;
}
temp = head;
for(int j = i - n - 1; j > 0; -- j) temp = temp -> next; //找到该点
temp -> next = temp -> next -> next; //将它的指针指向下下个节点
return head;
}
};
ListNode *temp = head;
时,并没有创建一个新的链表,两个指针变量共用同一个链表。class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !(head -> next)) return head;
ListNode* x = head;
ListNode* y = head -> next;
ListNode* z = head -> next -> next;
x -> next = nullptr;
for(; z; z = z -> next){
y -> next = x;
x = y;
y = z;
}
y -> next = x;
return y;
}
};
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(!head) return nullptr;
while(head -> val == val){
head = head -> next;
if(!head) return nullptr;
}
ListNode* prev = head;
ListNode* cur = head -> next;
while(cur){
if(cur -> val == val){
prev -> next = cur -> next;
cur = prev -> next;
}
else{
prev = cur;
cur = cur -> next;
}
}
return head;
}
};
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(!head) return nullptr;
ListNode* even = head -> next;
ListNode* oddtemp = head;
ListNode* eventemp = even;
while(oddtemp && eventemp && eventemp -> next){
oddtemp -> next = eventemp -> next;
oddtemp = oddtemp -> next;
eventemp -> next = oddtemp -> next;
eventemp = eventemp -> next;
}
if(!eventemp){
oddtemp -> next = even;
}
else{
eventemp -> next = nullptr;
oddtemp -> next = even;
}
return head;
}
};
odd
指针指向第一个节点,even
指针指向第二个节点oddtemp
和eventemp
来分离奇偶链表odd
段链表的尾指针指向even
链表的head
。class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* count = head;
int i = 0;
stack <int> value;
while(count){
++ i;
count = count -> next;
}
if(i == 1) return true;
for(int j = i / 2; j > 0; -- j){
value.push(head -> val);
head = head -> next;
}
if(i % 2 == 1) head = head -> next;
for(int j = i / 2; j > 0; -- j){
if(value.top() != head -> val) return false;
else{
head = head -> next;
value.pop();
}
}
return true;
}
};
stack
来进行前半段和后半段对比class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
if(l1 -> val < l2 -> val){
l1 -> next = mergeTwoLists(l1 -> next, l2);
return l1;
}
else{
l2 -> next = mergeTwoLists(l1, l2 -> next);
return l2;
}
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode *begin = l1 -> val < l2 -> val ? l1 : l2;
ListNode *ll1 = l1 -> val < l2 -> val ? l1 -> next : l1;
ListNode *ll2 = l1 -> val < l2 -> val ? l2 : l2 -> next;
ListNode *cur = begin;
while(ll2){
if(ll1 && ll1 -> val <= ll2 -> val){
cur -> next = ll1;
cur = cur -> next;
ll1 = ll1 -> next;
}
else{
cur -> next = ll2;
cur = cur -> next;
ll2 = ll2 -> next;
}
}
if(ll1){
cur -> next = ll1;
}
return begin;
}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
queue <int> list1;
queue <int> list2;
queue <int> ans;
ListNode *temp1 = l1;
ListNode *temp2 = l2;
ListNode *ex = new ListNode(1);
int size1 = 0;
int size2 = 0;
while(temp1){
++ size1;
temp1 = temp1 -> next;
}
while(temp2){
++ size2;
temp2 = temp2 -> next;
}
ListNode *head = size1 < size2 ? l2 : l1;
ListNode *copyhead = head;
for(int i = size1; i > 0; -- i){
list1.push(l1 -> val);
l1 = l1 -> next;
}
for(int j = size2; j > 0; -- j){
list2.push(l2 -> val);
l2 = l2 -> next;
}
int diff = abs(size1 - size2);
if(size1 > size2) for(; diff > 0; -- diff) list2.push(0);
else for(; diff > 0; -- diff) list1.push(0);
int q = list1.size();
int flag = 0;
for(q; q > 0; -- q){
int sum = list1.front() + list2.front() + flag;
flag = 0;
list1.pop();
list2.pop();
if(sum > 9){
sum -= 10;
flag = 1;
}
ans.push(sum);
}
for(int len = ans.size() - 1; len > 0; -- len){
copyhead -> val = ans.front();
ans.pop();
copyhead = copyhead -> next;
}
copyhead -> val = ans.front();
if(flag == 1) copyhead -> next = ex;
return head;
}
};
class Solution {
public:
Node* flatten(Node* head) {
Node *temp = head;
Node *nextnode = nullptr;
Node *prevnode = head;
while(prevnode){
if(temp && temp -> child){
nextnode = temp -> next; //记录当前节点的下一个节点
temp -> child -> prev = temp;
temp -> next = flatten(temp -> child); //进入递归
temp -> child = nullptr; //注销当前节点的child;
}
prevnode = temp; //记录null节点的前一个节点
if(temp) temp = temp -> next;
if(nextnode && !temp){ //当同一级链表存在下一个节点(即,原来有child的节点的下一节点),且子链表到达null
prevnode -> next = nextnode; //连接子节点和之前记录的nextnode所指链表 ---->这一步将其中两级双向链表扁平化
nextnode -> prev = prevnode;
temp = prevnode -> next;
nextnode = nullptr; //记得清空使用过的nextnode,否则会将无限连接nextnode所指链表
}
}
return head;
}
};
递归法
child
为nllptr
,将指针移向next
节点child
不为空,进入递归,传入头节点(即,child
的第一位)nextnode
记录有child
的节点的下一个节点,用来连接在子链表的尾端nextnode
是否为nullptr
,若是,则该尾端就是第一级链表的尾端,若不是,该尾端就是子链表的尾端。(注意使用nextnode
连接子链表后,需要将nextnode
清空,否则会重复连接子链表)prevnode
用来记录temp
的前一个节点,当temp
到尾端时为null
,这时用prevnode
来连接nextnode
。class Solution {
public:
Node* flatten(Node* head) {
if(!head) return nullptr;
Node *cur;
stack <Node*> stk;
stk.push(head);
Node *pre = nullptr;
while(!stk.empty()){
cur = stk.top();
stk.pop();
if(cur -> next){
stk.push(cur -> next);
}
if(cur -> child){
stk.push(cur -> child);
cur -> child = nullptr;
}
if(pre){
pre -> next = cur;
cur -> prev = pre;
}
pre = cur;
}
return head;
}
};
stack
child
指针if
语句的顺序,先next
的节点,后child
节点。(LIFO)class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return nullptr;
Node *cohead = head;
while(cohead){
Node *copy = new Node(cohead -> val, cohead -> next, nullptr); //初始化要赋值,要不会出错
Node *temp = cohead -> next;
cohead -> next = copy;
cohead = temp;
}
cohead = head;
while(cohead){
if(cohead -> random) cohead -> next ->random = cohead -> random -> next;
cohead = cohead -> next -> next;
}
cohead = head;
Node *ans = head -> next;
while(cohead -> next){
Node *temp = cohead -> next;
cohead -> next = cohead -> next -> next;
cohead = temp;
}
return ans;
}
};
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(k == 0 || !head || !(head -> next)) return head;
ListNode *temp = head;
int len = 0;
while(temp){
++ len;
temp = temp -> next;
}
k = k % len;
temp = head;
for(int i = len - 1; i > 0; -- i) temp = temp -> next;
temp -> next = head;
temp = head;
for(int j = len - k; j > 0; -- j) temp = temp -> next;
head = temp;
for(int m = len - 1; m > 0; -- m) temp = temp -> next;
temp -> next = nullptr;
return head;
}
};
struct Node{
int val;
Node *next;
Node(int val): val(val),next(nullptr){}
};
const int len = 100;
class MyHashSet {
public:
vector<Node*> arr; //本题题点
/** Initialize your data structure here. */
MyHashSet() {
arr = vector<Node*>(len, new Node(-1));
}
void add(int key) {
int haval = key % len;
Node* temp = arr[haval];
if(temp -> val != -1){
while(temp){
if(temp -> val == key) return;
if(!(temp -> next)){
Node *node = new Node(key);
temp -> next = node;
return;
}
temp = temp -> next;
}
}
else{
temp -> val = key;
return;
}
}
void remove(int key) {
int haval = key % len;
Node* temp = arr[haval];
if(temp -> val != -1){
while(temp){
if(temp -> val == key){
temp -> val = -1;
return;
}
temp = temp -> next;
}
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int haval = key % len;
Node* temp = arr[haval];
while(temp){
if(temp -> val == key) return true;
temp = temp -> next;
}
return false;
}
};
链地址法
struct Node{
int nkey;
int nval;
Node* next;
Node(int key, int val): nkey(key), nval(val), next(nullptr){}
};
int len = 1000;
class MyHashMap {
public:
vector <Node*> arr;
/** Initialize your data structure here. */
MyHashMap() {
arr = vector<Node*> (len, new Node(-1,-1));
}
/** value will always be non-negative. */
void put(int key, int value) {
int temp = key % len;
Node* h = arr[temp];
Node* prev;
while(h){
if(h -> nkey == key){
h -> nval = value;
return;
}
prev = h;
h = h -> next;
}
Node* node = new Node(key,value);
prev -> next = node;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
int temp = key % len;
Node* h = arr[temp];
while(h){
if(h -> nkey == key) return h -> nval;
h = h -> next;
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int temp = key % len;
Node* h = arr[temp];
while(h){
if(h -> nkey == key){
h -> nval = -1;
}
h = h -> next;
}
}
};
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set <int> hashset;
for(auto i : nums){
if(hashset.count(i) > 0){
return true;
}
else{
hashset.insert(i);
}
}
return false;
}
};
unordered_set
,若还不存在该值就插入到set内,class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> bobo;
int ans;
for(auto i : nums){
if(bobo.count(i)) bobo.erase(i);
else bobo.insert(i);
}
for(auto j : bobo) ans = j;
return ans;
}
};
哈希集
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = 0, j = 1; j < nums.size(); i += 2, j += 2){
if(nums[i] != nums[j]) return nums[i];
}
return nums[nums.size() - 1];
}
};
先排序,再用双指针对比。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = nums[0];
for(int i = 1; i < nums.size(); ++ i){
ans = ans ^ nums[i];
}
return ans;
}
};
异或
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int,int> n;
int ans = 0;
for(int i = 0; i < nums.size(); ++ i){
n[nums[i]] == 1? n[nums[i]] = 2: n[nums[i]] = 1;
}
for(int j = 0; j < nums.size(); ++ j){
if(n[nums[j]] == 1) ans = nums[j];
}
return ans;
}
};
map
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> bobo;
while(!bobo.count(n)){
int sum = 0;
bobo.insert(n);
while(n != 0){
sum = sum + (n%10) * (n%10);
n /= 10;
}
n = sum;
}
return n == 1;
}
};
//递归
class Solution {
public:
unordered_set<int> bobo;
bool isHappy(int n) {
int sum = 0;
if(n == 1) return true;
else if(bobo.count(n)) return false;
else{
bobo.insert(n);
while(n != 0){
sum = sum + (n%10) * (n%10);
n /= 10;
}
n = sum;
}
return isHappy(n);
}
};
本题计算的结果就分为两种,
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hashmap;
int i = 0;
for(auto key : nums){
if(hashmap.count(target - key)){
return {hashmap[target - key],i};
}
else{
hashmap[key] = i;
++ i;
}
}
return {};
}
};
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char,char> smap;
unordered_map<char,char> tmap;
for(int i = 0; s[i] != '\0'; ++ i){
char ss = s[i];
char tt = t[i];
if(smap.count(ss)){
if(smap[ss] != tt) return false;
}
else if(tmap.count(tt)){
if(tmap[tt] != ss) return false;
}
else{
smap[ss] = tt;
tmap[tt] = ss;
}
}
return true;
}
};
class Solution {
public:
bool isIsomorphic(string s, string t) {
for(int i=0;i<s.size();i++){
if(s.find(s[i])!=t.find(t[i]))
return false;
}
return true;
}
};
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string> ans;
vector<pair<int,string>> No;
unordered_map<string,int> l1;
unordered_map<string,int> l2;
int i = 0;
int j = 0;
int count;
for(auto re1 : list1){ //将餐厅名称与索引映射
l1[re1] = i;
++ i;
}
for(auto re2 : list2){
l2[re2] = j;
++ j;
}
for(auto name : list2){ //找到两个列表内都出现的餐厅名称,并计算索引和
int sum = 0;
if(l1.count(name)){
sum = l1[name] + l2[name];
No.push_back({sum,name});
}
}
int target = INT_MAX;
for(int p = 0; p < No.size(); ++ p){ //找到最小索引和的大小
target = No[p].first < target ? No[p].first : target;
}
for(int f = 0; f < No.size(); ++ f){ //将等于最小索引和的餐厅名放入答案列表
if(No[f].first == target){
ans.push_back(No[f].second);
}
}
return ans;
}
};
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> hashmap;
for(auto i : s){
if(hashmap.count(i)) hashmap[i] += 1;
else hashmap[i] = 1;
}
for(int j = 0; s[j] != '\0'; ++ j) if(hashmap[s[j]] == 1) return j;
return -1;
}
};
根据提示使用哈希映射
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> n1;
unordered_map<int,int> n2;
vector<int> ans = {};
for(auto i : nums1){
if(n1.count(i)) n1[i] += 1;
else n1[i] = 1;
}
for(auto i : nums2){
if(n2.count(i)) n2[i] += 1;
else n2[i] = 1;
}
for(auto i : n1){
while(n1[i.first] >= 1 && n2[i.first] >= 1){
ans.push_back(i.first);
-- n1[i.first];
-- n2[i.first];
}
}
return ans;
}
};
unordered_map
记录两个数组内每个数字出现的次数class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> hashmap;
unordered_map<int,int> temp; //用来记录当前元素的上一次映射
for(int i = 0; i < nums.size(); ++ i){
if(hashmap.count(nums[i])){
if(!temp.count(nums[i])) temp[nums[i]] = i;
else{
hashmap[nums[i]] = temp[nums[i]];
temp.erase(nums[i]);
}
if(i - hashmap[nums[i]] <= k) return true;
}
else hashmap[nums[i]] = i;
}
return false;
}
};
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hashmap;
for(auto s : strs){
string temp = s;
sort(temp.begin(), temp.end());
hashmap[temp].push_back(s);
}
int len = hashmap.size();
vector<vector<string>> ans(len);
int index = 0;
for(auto i : hashmap){
ans[index] = i.second;
++ index;
}
return ans;
}
};
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_map<int,int>> row(9);
vector<unordered_map<int,int>> col(9);
vector<unordered_map<int,int>> block(9);
for(int i = 0; i < 9; ++ i){
for(int j = 0; j < 9; ++ j){
int bindex = (i / 3)* 3 + j / 3;
char cur = board[i][j];
if(cur == '.') continue;
if(row[i].count(cur) || col[j].count(cur) || block[bindex].count(cur)) return false;
row[i][cur] = 1;
col[j][cur] = 1;
block[bindex][cur] = 1;
}
}
return true;
}
};
unordered_map
,遍历数独,判断是否已经存在,若存在返回false,若不存在,将数字作为关键字插入对应行列设值为一。class Solution {
public:
int numJewelsInStones(string J, string S) {
int ans = 0;
unordered_set<char> jew;
for(auto i : J) jew.insert(i); //记录宝石类型
for(auto s : S) if(jew.count(s)) ++ ans; //若拥有的石头里有宝石,答案加一
return ans;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
for(int i = 0; s[i] != '\0'; ++ i){
unordered_set<char> str;
int len = 0;
for(int j = i; s[j] != '\0'; ++ j){
if(str.count(s[j])) break;
str.insert(s[j]);
++ len;
}
len > ans? ans = len : ans = ans;
}
return ans;
}
};
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int ans = 0;
unordered_map<int,int> ab;
for(auto a : A){
for(auto b : B){
int sum = a + b;
if(!ab.count(sum)) ab[sum] = 1;
else ab[sum] += 1;
}
}
for(auto c : C){
for(auto d : D){
int need = -(c + d);
if(ab.count(need)) ans = ans + ab[need];
}
}
return ans;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
int max = 0;
int mf = 0;
unordered_map<int,int> c;
vector<int> ans = {};
for(auto i : nums){
if(!c.count(i)) c[i] = 1;
else c[i] += 1;
}
if(c.size() == k){
for(auto key : c){
ans.push_back(key.first);
}
sort(ans.begin(),ans.end());
return ans;
}
for(int j = 0; j < k; ++ j){
int val = 0;
int flag = 0;
for(auto n : c){
if(c[n.first] > val){
val = c[n.first];
flag = n.first;
}
}
ans.push_back(flag);
c.erase(flag);
}
sort(ans.begin(),ans.end());
return ans;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
int ans = -1;
int l = 0;
int r = nums.size() - 1;
int mid = (l + r) / 2;
if(nums[0] == target) return 0; //数组仅有一位的情况或刚好第零个为目标值的情况
if(nums[mid] == target) return mid; //初始mid为目标值的情况
while(nums[mid] != target){
if(mid == l){ //当左右边界相邻时,mid的结果总是等于左边界
if(nums[mid] == target) return mid;
else if(nums[r] == target) return r;
else return -1;
}
if(nums[mid] > target){
r = mid;
}
else{
l = mid;
}
mid = (l + r) / 2;
ans = mid;
}
return ans;
}
};
class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1) return x;
int l = 0;
int r = x;
while(l <= r){
int mid = l + (r - l) /2;
int s = x / mid; //用来判断mid大于目标还是小于目标,或等于目标
int ss = x / (mid + 1);
if(x / s == s) return s; //刚好是他的算术平方根
if(s > mid && ss < mid + 1) return mid; //例如6 在2的平方以及 3的平方之间 答案为2
if(s > mid) l = mid + 1; //调整边界
if(s < mid) r = mid - 1;
}
return 0;
}
};
class Solution {
public:
int guessNumber(int n) {
int l = 1;
int r = n;
while(l <= r){
int mid = l + (r -l) / 2; //相当于(l+r)/2,但用这种写法能防止溢出
int g = guess(mid);
if(g == 0) return mid;
else if(g == -1) r = mid - 1;
else if(g == 1) l = mid + 1;
}
return 0;
}
};
根据反馈进行调整,使用二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int ans = -1;
if(nums.empty()) return ans;
int l = 0;
int r = nums.size() - 1;
int minlo = l; //储存最小值的索引
int maxlo = r; //储存最大值的索引
if(nums.size() == 1){ //如果只有一个数字,直接判断
if(nums[0] == target) return 0;
else return ans;
}
for(int i = 0, j = 1; j< nums.size(); ++ i, ++ j){ //找到数组旋转的位置
if(nums[i] > nums[j]){
minlo = j;
maxlo = i;
}
}
if(target > nums[maxlo] || target < nums[minlo]) return ans; //如果在数字范围之内
if(target >= nums[0]) r = maxlo; //重新设定边界----在左半段的情况 修改r值
else if(target <= nums[r]) l = minlo; //在右半段的情况 修改l值
else return -1;
while(l <= r){ //二分法常规模板
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
if(nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return ans;
}
};
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n;
if(isBadVersion(1)) return 1;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(!isBadVersion(mid - 1) && isBadVersion(mid)) return mid;
else if(!isBadVersion(mid)) left = mid + 1;
else right = mid;
}
// Post-processing:
// End Condition: left == right
if(isBadVersion(left) && !isBadVersion(left - 1)) return left;
return -1;
}
};
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size()-1;
if(nums.size() == 1) return 0;
if(nums.size() == 2) return nums[0] > nums[1] ? 0 : 1;
while(l <= r){
int mid = l + (r - l) / 2;
cout << mid<< endl;
if((mid == 0 && nums[mid] > nums[mid + 1]) || (mid == nums.size() - 1 && nums[mid] > nums[mid - 1]) ||(mid != 0 && mid != nums.size()-1 && nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])) return mid;
if(mid == 0 || nums[mid + 1] > nums[mid - 1]) l = mid + 1;
else r = mid - 1;
}
return -1;
}
};
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
if(nums.size() == 1) return nums[0];
while(l <= r){
int mid = l + (r - l) / 2;
cout << mid << endl;
if((mid == 0 && nums[mid] < nums[mid + 1]) || (mid == nums.size()-1 && nums[mid] < nums[mid - 1]) || (mid != 0 && mid != nums.size()-1 && nums[mid] < nums[mid-1] && nums[mid] < nums[mid+1])) return nums[mid];
if(nums[r] <nums[l] && nums[mid] < nums[r]) r = mid - 1;
else if(nums[r] > nums[l]) r = l;
else if(nums[mid] > nums[r]) l = mid + 1;
}
return -1;
}
};
通过二分查找不断缩小范围,目标值的要求是小于左右相邻的值 三个重新界定左右边界的条件
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans = {-1, -1};
if(nums.empty()) return ans; // 数组为空的情况
int l = 0, r = nums.size()-1;
if(nums[l] > target) return ans; // 若target不在数组范围内
if(nums[r] < target) return ans;
while(l < r){ // 先查找元素的第一个位置
int mid = l + (r - l)/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
} // 到出循环时,索引 l 和 r 在同一个位置,即查找元素的第一个位置
if(nums[l] == target) ans[0] = l; // 防止查找元素在数组位置内 但 数组内没有目标元素
r = nums.size(); // 不设成 nums.size() - 1 的原因是,应对数组大小为一的情况,后面操作会超出索引。
while(l < r){ // 查找元素的最后一个位置
int mid = l + (r - l)/2;
if(nums[mid] > target) r = mid;
else l = mid + 1;
}
// 到处循环时,l和r 在同一个位置,即 查找元素的最后一个位置的下一位
if(nums[l - 1] == target) ans[1] = l - 1;
return ans;
}
};
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> ans(k);
int l = 0, r = arr.size() - 1;
int i = 0;
while(l + 1 < r){ //找到最靠近x的两个数
int mid = l + (r - l) / 2;
if(arr[mid] <= x) l = mid;
else r = mid;
}
while(i < k){ // 两个数分别与x 相减,对比两个差,放进数组。
int subl,subr;
if(l < r){ // 用来处理超出边界的情况
subl = x - arr[l];
subr = arr[r] - x;
}
else{
subl = arr[l] - x;
subr = x - arr[r];
}
if(subl - subr <= 0){
ans[i] = arr[l];
-- l;
if(l == -1) l = arr.size() -1;
}
else{
ans[i] = arr[r];
++ r;
if(r == arr.size()) r = 0;
}
++ i;
}
sort(ans.begin(),ans.end()); //排序
return ans;
}
};
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0;
int right = arr.size() - k;
while(left < right)
{
int mid = (left + right) / 2;
if(x - arr[mid] > arr[mid + k] - x)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return vector<int>(arr.begin() + left, arr.begin() + k + left); // 返回左边界到距离左边界k个值得一段数组
}
};
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size()-1;
if(nums.size() == 1) return 0;
if(nums.size() == 2) return nums[0] > nums[1] ? 0 : 1;
while(l <= r){
int mid = l + (r - l) / 2;
if((mid == 0 && nums[mid] > nums[mid + 1]) || (mid == nums.size() - 1 && nums[mid] > nums[mid - 1]) ||(mid != 0 && mid != nums.size()-1 && nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])) return mid;
if(mid == 0 || nums[mid + 1] > nums[mid - 1]) l = mid + 1;
else r = mid - 1;
}
return -1;
}
};
class Solution {
public:
//二分法,不断将指数减半
double basicPow(double x, long n){
if(n == 0) return 1.0; // 顶
double half = basicPow(x, n / 2);
if(n % 2 == 0){ //根据奇偶性分
return half * half;
}
else{
return half * half * x;
}
}
double myPow(double x, int n) {
long N = n;
if(N == 0) return 1.0;
if(N < 0){ //处理指数为负数的情况
x = 1 / x;
N = - N;
}
return basicPow(x, N);
}
};
class Solution {
public:
bool isPerfectSquare(int num) {
int l = 0, r = 46340;
while(l <= r){ // 二分法找根
int mid = l + (r - l) / 2;
long power = mid * mid;
if(power > num){
r = mid -1;
}
else if(power < num){
l = mid +1;
}
else{
return true;
}
}
return false;
}
};
方法一:二分法
class Solution {
public:
bool isPerfectSquare(int num) {
long odd = 1, power = 0;
while(true){
power += odd;
odd += 2;
if(power == num) return true;
if(power > num) return false;
}
return true;
}
};
方法二:数学法
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l = 0, r = letters.size() - 1;
if(target >= letters[r] || target < letters[l]) return letters[l]; //因为是循环数组,如果target不在数组范围内,直接返回数组第一个字符
while(l + 1 < r){ // 二分法模板③,l始终在目标字符或者目标字符的左边,r 始终再目标字符的右边,当两者相遇跳出循环时,r刚好在目标字符位置的右边
int mid = l + (r - l)/2;
if(letters[mid] > target) r = mid;
else l = mid;
}
return letters[r];
}
};
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size()-1;
if(nums[0] < nums[r]) return nums[0];
while(l + 1 < r){
int mid = l + (r - l)/2;
if(nums[mid] < nums[r]) r = mid;
else if(nums[mid] > nums[r]) l = mid;
else{
-- r;
}
}
return nums[r];
}
};
--r
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size();
while(l < r){
int mid = l + (r - l) / 2;
int count = 0;
for(int i : nums){
if(i < mid) ++ count;
}
if(count < mid){
l = mid + 1;
}
else{
r = mid;
}
}
return l-1;
}
};
class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {
if(root != NULL){
ans.push_back(root -> val);
preorderTraversal(root -> left);
preorderTraversal(root -> right);
}
return ans;
}
};
root
的val
放入答案(ans)容器内。root
的左子树为root
进入递归。class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> ans;
TreeNode* temp = root;
while(temp != NULL || !stk.empty()){
while(temp != NULL) {
ans.push_back(temp -> val);
stk.push(temp);
temp = temp -> left;
}
temp = stk.top();
stk.pop();
temp = temp -> right;
}
return ans;
}
};
stack
来储存root
。root
接着遍历右子树。class Solution {
public:
vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root != NULL) {
inorderTraversal(root -> left);
ans.push_back(root -> val);
inorderTraversal(root -> right);
}
return ans;
}
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* temp = root;
while(temp || !stk.empty()){
while(temp){
stk.push(temp);
temp = temp -> left;
}
temp = stk.top();
stk.pop();
ans.push_back(temp -> val);
temp = temp -> right;
}
return ans;
}
};
rightchild
来记录右节点是否已被遍历过。若是:则说明以该点为根的子树已被遍历,输出根节点。若否:就开始遍历右节点,回到第二步。class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* cur = root;
TreeNode* rightchild = NULL;
while(cur || !stk.empty()){
while(cur != NULL){
stk.push(cur);
cur = cur -> left;
}
cur = stk.top();
if(!cur -> right|| rightchild == cur -> right){
ans.push_back(cur -> val);
stk.pop();
rightchild = cur;
cur = NULL;
}
else{
rightchild = NULL;
cur = cur -> right;
}
}
return ans;
}
};
class Solution {
public:
vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return ans;
postorderTraversal(root -> left);
postorderTraversal(root -> right);
ans.push_back(root -> val);
return ans;
}
};
flag
放在每层最后,用来分割上下两层。将每一层存入ans
容器内class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> q;
TreeNode* ptr = root;
TreeNode* flag = new TreeNode(-1);
int lvl = 0, ele = 0;
q.push(root);
q.push(flag);
vector<int> row;
while(!q.empty()){
if(q.front() == flag){
ans.push_back(row);
row.clear();
q.pop();
q.push(flag);
continue;
}
TreeNode* temp = q.front();
q.pop();
row.push_back(temp -> val);
if(temp -> left) q.push(temp -> left);
if(temp -> right) q.push(temp -> right);
if(q.size() == 1){
ans.push_back(row);
break;
}
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int count = q.size();
vector<int> row;
while(count--){
TreeNode* temp = q.front();
q.pop();
row.push_back(temp -> val);
if(temp -> left) q.push(temp -> left);
if(temp -> right) q.push(temp -> right);
}
ans.push_back(row);
}
return ans;
}
};
想说的都在注释里
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true; //常规
return box(root -> left, root -> right);
}
bool box(TreeNode* l, TreeNode* r){
if(l == NULL && r == NULL) return true;
if(l == NULL || r == NULL) return false;
return (l -> val == r -> val) //对应node的值要相同
&& (box(l -> left, r ->right)) //注意这两句,为了对称,对比左节点的左子节点和右节点的右子节点
&& (box(r -> left, l -> right)); //右节点的左子节点和左节点的右子节点
}
};
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
sum -= root -> val;
if((!root -> left) && (!root -> right)) return sum == 0;
return hasPathSum(root -> left, sum) || hasPathSum(root -> right, sum);
}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()) return NULL;
return box(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* box(vector<int>& preorder,int ps, int pe,vector<int>& inorder, int is, int ie){
if(ps > pe || is > ie) return NULL;
int flag = preorder[ps];
TreeNode* root = new TreeNode(flag);
int id = 0;
while(inorder[is + id] != flag) ++ id;
root -> left = box(preorder, ps + 1, ps + id, inorder, is, is+id -1);
root -> right = box(preorder,ps + id + 1, pe, inorder, is + id + 1, ie);
return root;
}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.empty()) return NULL;
return box(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* box(vector<int>& inorder, int iS, int iE, vector<int>& postorder, int pS, int pE){
if(iS > iE || pS > pE) return NULL;
int rooot = postorder[pE];
int id = 0;
while(rooot != inorder[id]) ++ id;
TreeNode* root = new TreeNode(rooot);
root -> left = box(inorder, iS, id - 1, postorder, pS, pS + id -iS -1);
root -> right = box(inorder,id + 1, iE, postorder, pS + id - iS, pE - 1);
return root;
}
};
class Solution {
public:
Node* connect(Node* root) {
if(!root) return root;
queue<Node*> q;
Node* flag = new Node; // 用于记录每层树的结束。
Node* last = new Node; // 用于记录上一个节点,将上一个节点的next连接当前节点。
q.push(root); // 根推入队列
q.push(flag); // 第一层结束,用flag标记位置
while(q.size() >= 2){ //队列内到最后存在一个flag,因此 >2
Node* now = q.front(); // 取出当前节点。
q.pop();
if(now == flag){ // 如果到达每层末尾,last清空,再次推入flag
//last -> next = NULL;
last = NULL;
q.push(flag);
continue;
}
if(last == NULL){ // 说明是新的一层
last = now;
}
else{ // 否则一定存在last节点
last -> next = now;
last = now; // 更新last节点
}
if(now -> left){ //压入新的节点。
q.push(now -> left);
q.push(now -> right);
}
}
return root;
}
};
now -> right -> next = now -> next -> left;
class Solution {
public:
Node* connect(Node* root) {
if(!root) return NULL;
Node* now = new Node;
Node* leftmost = new Node;
now = root;
leftmost = root;
while(now -> left){
now -> left -> next = now -> right; // 当前节点的左节点的next指向右节点
if(now -> next){ //将当前节点的右节点的next指向 下一节点的左节点
now -> right -> next = now -> next -> left;
now = now -> next; // 更新当前节点
}
else{
now = leftmost -> left; // 若当前节点没有next,更新当前节点为当前层的最左节点的左节点。
leftmost = now;
}
}
return root;
}
};
class Solution {
public:
Node* connect(Node* root) {
if(!root || !root -> left) return root;
root -> left -> next = root -> right;
Node* now = new Node;
now = root -> left;
while(now -> left){
now -> right -> next = now -> next -> left;
now = now -> right;
}
root -> left = connect(root -> left);
root -> right = connect(root -> right);
return root;
}
};
now
:记录当前处理的节点leftmost
:记录当前层最左拥有child的节点flat
:用来记录now 的next 之后的节点含有child的第一个节点temp
:使用temp遍历now 的next,直到含有child的节点。class Solution {
public:
Node* connect(Node* root) {
if(!root || (!root -> left && !root -> right)) return root; //如果root为空或root没有没有左子树和右子树,直接返回
Node* now = new Node; // 记录当前处理的节点
Node* leftmost = new Node; // 记录当前层最左拥有child的节点
now = root;
leftmost = now -> left != NULL ? now -> left : now -> right;
while(now -> left || now -> right || now ){
Node* flag = new Node;
flag = NULL; // 用来记录now 的next 之后的节点含有child的第一个节点
if(now -> left){ //当前节点有左子树,寻找右子树或者更右边的节点。
if(now -> right){ //如果有右子树,左右相连
now -> left -> next = now -> right;
}
else{ // 若没有右子树,寻找最近的👉节点
Node* temp = new Node; // 使用temp遍历now 的next,直到含有child的节点。
temp = now -> next;
while(temp){
if(temp-> left){ //有左节点就连上
now -> left -> next = temp -> left;
flag = temp;
break;
}
else if(temp-> right){ // 若没有左节点就连右节点。
now -> left -> next = temp -> right;
flag = temp;
break;
}
else temp = temp -> next; // 若都没有,接着往next方向找
}
}
}
if(now -> right){ // 右子树
Node* temp = new Node;
temp = now -> next;
while(temp){ // 直接寻找最近的👉子树
if(temp -> left){ //与上面相同,有左连做
now -> right -> next = temp -> left;
flag = temp;
break;
}
else if(temp -> right){ // 无左连右
now -> right -> next = temp -> right;
flag = temp;
break;
}
else temp = temp -> next; // 若无左右,接着往next方向找
}
}
if(flag){ // 更新now(当前处理的节点)到flag
now = flag;
}
else{ // 如果不存在flag,说明需要开始处理下一层
while(leftmost && (!leftmost -> left && !leftmost -> right)){ //找到下一层至少含有一个子节点的最左的节点
leftmost = leftmost -> next;
}
if(leftmost){ // 更新now
now = leftmost;
if(now -> left){ // 更新预备leftmost
leftmost = now -> left;
}
else leftmost = now -> right;
}
else break; //若不存在下一层的leftmost,说明遍历完成,跳出循环。
}
}
return root;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root -> left, p, q);
TreeNode* r = lowestCommonAncestor(root -> right, p, q);
if(l && r) return root;
return l ? l : r;
}
};
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) { //把树转化为字符串
if(!root) return "";
string ans = "";
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){ 遍历二叉树,BFS
TreeNode* temp = q.front();
q.pop();
if(temp){
ans += to_string(temp -> val);
ans += ","; // 分割每个node
q.push(temp -> left);
q.push(temp -> right);
}else{
ans += "null,"; // 即使是空节点也要转换成字符串,因为要将字符串还原为树,null作为占位符
}
}
return ans;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) { // 把字符串转换为树
TreeNode* root = new TreeNode; // 创建根节点
if(data.empty()) return NULL; // 传统艺能
int j = 0;
string sub = "";
for(; data[j] >= '0' && data[j] <= '9' || data[j] == '-'; ++ j){} // 找到一个完整的数字在字符串的位置
if(data[0] == '-'){ // 处理负数情况
sub = data.substr(1, j-1);
data.erase(0, j+1);
int number = stoi(sub);
root -> val = -number;
}else{
sub = data.substr(0, j);
data.erase(0, j+1);
int number = stoi(sub);
root -> val = number;
}
queue<TreeNode*> q;
q.push(root); //root处理完毕,压入队列
int a = 1;
while(!data.empty()){ //开始处理左右节点
cout << q.front() -> val << endl;
TreeNode* l = new TreeNode;
TreeNode* r = new TreeNode;
if(data[0] == 'n'){ //左节点
l = NULL;
data.erase(0, 5);
}
else{
int i = 0;
for(i; (data[i] >= '0' && data[i] <= '9') || data[i] == '-'; ++ i){}
if(data[0] == '-'){
sub = data.substr(1, i-1);
data.erase(0, i+1);
int num = stoi(sub);
l -> val = - num;
q.push(l);
}
else{
sub = data.substr(0, i);
data.erase(0, i+1);
int num = stoi(sub);
l -> val = num;
q.push(l);
}
}
if(data[0] == 'n'){ // 右节点
r = NULL;
data.erase(0, 5);
}else{
int i = 0;
for(i; (data[i] >= '0' && data[i] <= '9') || data[i] == '-'; ++ i){}
if(data[0] == '-'){
sub = data.substr(1, i-1);
data.erase(0, i + 1);
int num = stoi(sub);
r -> val = - num;
q.push(r);
}
else{
sub = data.substr(0, i);
data.erase(0, i + 1);
int num = stoi(sub);
r -> val = num;
q.push(r);
}
}
TreeNode* n = q.front();
n -> left = l; //连接root 的 左右节点
n -> right = r;
q.pop();
}
return root;
}
};
class Solution {
public:
long pre = LONG_MIN;
bool isValidBST(TreeNode* root) {
if(!root) return true; //传统艺能
if(!isValidBST(root -> left)) return false; // 向左遍历,直到叶节点
if(pre >= root -> val) return false; // 判断节点值是否大于上一个
pre = root -> val; // 更新pre
return isValidBST(root -> right); // 向右遍历
}
};
class BSTIterator {
public:
stack<TreeNode*> stk;
BSTIterator(TreeNode* root) {
box(root);
}
void box(TreeNode* root){ //压栈函数
if(!root) return;
while(root){
stk.push(root);
root = root -> left;
}
}
/** @return the next smallest number */
int next() { //获取当前值
TreeNode* now = stk.top();
stk.pop();
int ans = now -> val; // 若有右子树,压入栈内
if(now -> right) box(now -> right);
return ans;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !stk.empty();
}
};
默认已经看过题目 🤡 点击标题可跳转对应题目网址。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 1);
int l = 1;
for(int i=0; i<n; ++i){
res[i] *= l;
l *= nums[i];
}
int r = 1;
for(int j=n-1; j>=0; --j){
res[j] *= r;
r *= nums[j];
}
return res;
}
};
本题利用双指针,新数组每个位置上的值应该等于数组左边所有数字的乘积 × 数组右边所有数字的乘积
1.初始化一个新的数组res(result),包含n个1
2.初始化变量l(left)代表左边的乘积,从左到右遍历数组,每次都让新数组的值乘以它左边数字的乘积l,然后更新l。此时新数组里的所有数字就代表了nums数组中对应位置左边所有数字的乘积
3.再从右往左做一遍同样的操作,最终res[i] = 1 * nums中i左边所有数字的乘积 * nums中i右边所有数字的乘积
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0; i<nums.size(); ++i){
nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
}
vector<int> r;
for(int i=0; i<nums.size(); ++i){
if(nums[i] > 0){
r.push_back(i+1);
}
}
return r;
}
};
8
,2
,-3,-1]class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int n = board.size();
vector<unordered_map<char, int>> row(n), col(n);
vector<vector<unordered_map<char, int>>> sub(n/3, vector<unordered_map<char, int>>(n/3));
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
char c = board[i][j];
if(c == '.') continue;
if(row[i][c]++ > 0 || col[j][c]++ > 0 || sub[i/3][j/3][c]++ > 0) return false;
}
}
return true;
}
};
/**
* 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 = NULL;
while(head){
ListNode *next = head -> next;
head -> next = pre;
pre = head;
head = next;
}
return pre;
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i=0; i<n; ++i){
sum += nums[i];
}
n++;
return n * (n - 1) / 2 - sum;
}
};
总和 = (元素个数 / 2) * (首尾两数字之和)
class Solution {
public:
void reverseString(vector<char>& s) {
int i = -1, j = s.size();
while(++i < --j){
swap(s[i], s[j]);
}
}
};
class Solution {
public:
int romanToInt(string s) {
unordered_map<string, int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
int r = m[s.substr(0, 1)];
for(int i=1; i<s.size(); ++i){
string two = s.substr(i-1, 2);
string one = s.substr(i, 1);
r += m[two] ? m[two] : m[one];
}
return r;
}
};
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while(l < r){
int m = (l + r) / 2;
if(m > 0 and nums[m-1] > nums[m]){
r = m - 1;
}else if(m < nums.size() and nums[m+1] > nums[m]){
l = m + 1;
}else{
return m;
}
}
return l;
}
};
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
int p = pow(points[0][0], 2) + pow(points[0][1], 2);
vector<vector<int>> l, m, r;
for(int i=0; i<points.size(); ++i){
int v = pow(points[i][0], 2) + pow(points[i][1], 2);
if(v < p){
l.push_back(points[i]);
}else if(v == p){
m.push_back(points[i]);
}else{
r.push_back(points[i]);
}
}
if(K <= l.size()){
return kClosest(l, K);
}else if(K <= l.size() + m.size()){
l.insert(l.end(), m.begin(), m.begin() + K - l.size());
return l;
}else{
r = kClosest(r, K - l.size() - m.size());
l.insert(l.end(), m.begin(), m.end());
l.insert(l.end(), r.begin(), r.end());
return l;
}
}
};
class Solution {
public:
int hammingDistance(int x, int y) {
return bitset<32>(x ^ y).count();
}
};
class RecentCounter {
queue<int> tco;
public:
RecentCounter() {
}
int ping(int t) {
while(!tco.empty() && tco.front() <t- 3000)
{
tco.pop();
}
tco.push(t);
return tco.size();
}
};
class Solution {
public:
int numIslands(vector<vector<char>>&grid) {//本题地图上的'0','1'被当作字符录入
if (grid.empty()) return 0;
int m=grid.size();
int n=grid[0].size(); //以上两行求得地图的边界
int ans=0; //答案初始化为零
for (int y=0;y<m;y++)
for (int x = 0; x < n; x++)
{
ans=grid[y][x]-'0'+ans; //'0','1'的ASCII码值相差一,详情看代码后解析
dfs(grid,x,y,m,n); //深度优先搜索算法
}
return ans;
}
private:
void dfs(vector<vector<char>>&grid,int x,int y,int m,int n)
{
if(x<0||y<0||y>=m||x>=n||grid[y][x]=='0') //遍历的点不能超出地图边界
return;
grid[y][x]='0'; //将岛的一部分'1',转换为0
dfs(grid,x+1,y,m,n); //遍历该点的上下左右
dfs(grid,x-1,y,m,n);
dfs(grid,x,y+1,m,n);
dfs(grid,x,y-1,m,n);
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
int i,j;
for(i = 0; i < len; ++i)
{
for(j = i+1; j < len; ++j)
{
int plus = nums[i] + nums[j];
if(plus == target)
return {i,j};
}
}
return{};
}
};
注:此处贡献名单仅代表汇总搜集贡献,不代表全部原创,欢迎所有更短的解法🤓