汇总区间
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<string> res;
string str = to_string(nums[0]);
int start = nums[0];
int gap = 1;
for (int i = 1; i < n; i++) {
if (start + gap == nums[i]) {
gap++;
} else {
if (gap > 1) {
str += "->";
str += to_string(start + gap - 1);
}
res.push_back(str);
str = to_string(nums[i]);
start = nums[i];
gap = 1;
}
}
// 处理最后一个数字
if (gap > 1) {
str += "->";
str += to_string(nums[n-1]);
}
res.push_back(str);
return res;
}
};
最小栈
设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。
辅助栈
在每个元素入栈时，把当前最小值m存储起来
- 当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得最小值，将这个最小值插入到辅助栈。
- 当一个元素要出栈时，把辅助栈的栈顶元素一并弹出。
- 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
逆波兰表达式求值
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for(int i=0; i<tokens.size(); i++){
string str = tokens[i];
if(str == "+"){
int val1 = stk.top();
stk.pop();
int val2 = stk.top();
stk.pop();
stk.push(val2+val1);
}else if(str == "-"){
int val1 = stk.top();
stk.pop();
int val2 = stk.top();
stk.pop();
stk.push(val2-val1);
}else if(str == "*"){
int val1 = stk.top();
stk.pop();
int val2 = stk.top();
stk.pop();
stk.push(val2*val1);
}else if(str == "/"){
int val1 = stk.top();
stk.pop();
int val2 = stk.top();
stk.pop();
stk.push((int)val2/val1);
}else{
stk.push(stoi(str));
}
}
return stk.top();
}
};
有效的数独
请判断一个9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字1-9在每一列只能出现一次。
- 数字1-9在每一列只能出现一次。
- 数字1-9在每一个以粗实线分割的3x3宫内只能出现一次。
一次遍历
可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rows[9][9];
int columns[9][9];
int subboxes[3][3][9];
memset(rows, 0, sizeof(rows));
memset(columns, 0, sizeof(columns));
memset(subboxes, 0, sizeof(subboxes));
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
char c = board[i][j];
if(c != '.'){
int index = c-'0'-1;
rows[i][index]++;
columns[j][index]++;
subboxes[i/3][j/3][index]++;
if(rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i/3][j/3][index] > 1){
return false;
}
}
}
}
return true;
}
};
生命游戏
给定一个包含mxn个格子的面板，每个细胞都具有一个初始状态：
- 活细胞
- 死细胞
复制原数组进行模拟
这个问题看起来简单，但有一个陷阱，如果直接根据规则更新原始数组，那么就做不到题目中所说的同步更新。
二叉搜索树迭代器
/**
* 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:
void preOrder(TreeNode* root, vector<int>& arr){
if(!root){
return;
}
arr.push_back(root->val);
preOrder(root->left, arr);
preOrder(root->right, arr);
}
void flatten(TreeNode* root) {
vector<int> arr;
preOrder(root, arr);
TreeNode* temp = root;
for(int i=1; i<arr.size(); i++){
temp->right = new TreeNode(arr[i]);
temp->left = nullptr;
temp = temp->right;
}
// root->left = nullptr;
}
};
不同路径二
动态规划
用f(i,j)来表示从坐标(0, 0)到坐标(i, j)的路径总数，u(i,j)表示坐标(i,j)是否可行，如果坐标(i,j)有障碍物，u(i,j)=0,否则u(i,j)=1。
机器人每次只能向下或者向右移动一步，所以从坐标(0,0)到坐标(i,j)路径总数的值只取决于从坐标(0,0)到坐标(i-1,j)的路径总和和从坐标(0,0)到坐标(i,j-1)的路径总数。
若u(i,j)=0，则f(i,j)=0
若u(i,j)=1，则f(i,j) = f(i-1,j) + f(i,j-1)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// 障碍物为1，空位置为0
vector<vector<int>> dp(m, vector<int>(n, 0));
if (obstacleGrid[0][0] == 1) {
return 0;
}
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
continue;
}
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
}
return dp[m - 1][n - 1];
}
};
三角形最小路径和
给定一个三角形triangle，找出自顶向下的最小路径和。
相邻结点只能是与上一层结点下标相等，或者+1。
0,0
1,0 1,1
2,0 2,1 2,2
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
int n = triangle[0].size();
vector<vector<int>> dp(m);
for(int i=0; i<m ;i++){
dp[i] = vector<int>(i+1,0);
}
dp[0][0] = triangle[0][0];
for(int i=1; i<m; i++){
for(int j=0; j<=i; j++){
if(j == 0){
dp[i][j] = dp[i-1][j] + triangle[i][j];
}else if(j == i){
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}else{
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
}
}
}
return *std::min_element(dp[m-1].begin(), dp[m-1].end());
}
};
最小路径和
从左上角到右下角找一个路径最小。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i == 0 && j == 0){
continue;
}
if(i == 0){
dp[i][j] = dp[i][j-1] + grid[i][j];
}else if(j == 0){
dp[i][j] = dp[i-1][j] + grid[i][j];
}else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
}
return dp[m-1][n-1];
}
};
最长回文子串
动态规划
对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
例如对于字符串“ababa”，如果我们已经知道“bab”是回文串，那么“ababa”一定是回文串，这是因为它的首尾两个字母都是“a”。
根据这样的思路，我们可以用动态规划的方法解决本题。
我们用P(i,j)表示字符串s的第i到j个字母组成的串是否为回文串。
最长递增子序列
动态规划
dp[i]为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度，nums[i]必须被选取。
零钱兑换
动态规划
采用自下而上的方式进行思考，仍定义F(i)为组成金额i所需最少的硬币数量，假设在计算F(i)之前，已经计算出F(0)到F(i-1)的答案。
枚举所有硬币，如果有硬币面额小于等于i
dp[i] = min(dp[i], dp[i-coins[j]]+1);
爬楼梯
class Solution {
public:
int climbStairs(int n) {
if(n < 2){
return n;
}
//dp[n]：到达第n阶的方法数量
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
使用最小花费爬楼梯
给一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦支付此费用，即可选择向上爬一个或者两个台阶。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//dp[i]爬到第i个楼梯所需的最小费用
int n = cost.size();
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<=n; i++){
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[n];
}
};