116. 填充每个节点的下一个右侧节点指针
层序遍历嘛
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* levelOder(Node* root)
{
queue<Node*> que;
if(root==NULL)
{
return root;
}
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i=0;i<size;i++)
{
Node* node = que.front();
que.pop();
if(i<size-1)
node->next=que.front();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
}
return root;
}
Node* connect(Node* root) {
return levelOder(root);
}
};
120. 三角形最小路径和
其实就是DP啦
- 确定dp数组（dp table）以及下标的含义
dp[i][j]就是三角形的第i行第j列的最小路径和 - 确定递推公式
不在三角形的腰上时，路径和由上一行的两个路径和中选更小的
dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + c[i][j]
c[i][j]为三角形第i行第j列的值
三角形的两个腰上的值是只能由上一行的腰上的值决定
dp[i][0]=c[i][0]+dp[i-1][0]
dp[i][i]=c[i][i]+dp[i-1][i-1] - dp数组如何初始化
三角形的两个腰上的值是只能由上一行的腰上的值决定
dp[0][0]=c[0][0] - 确定遍历顺序
从上到小从左到右 - 举例推导dp数组
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int size = triangle.size();
vector<vector<int>> dp(size, vector<int>(size));
dp[0][0]=triangle[0][0];
for(int i=1;i<size;i++)
{
dp[i][0] = triangle[i][0] + dp[i-1][0];
for(int j=1;j<i;j++)
{
dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
dp[i][i] = triangle[i][i]+dp[i-1][i-1];
}
int min = dp[size-1][0];
for(int i =1;i<size;i++)
{
if(min>dp[size-1][i])
min = dp[size-1][i];
}
return min;
}
};
128. 最长连续序列
直接用sort()的话是O(nlogn)
题目要求O(n)
所以我们使用一个哈希表对于数据进行快速的查找
当前数字nums[i]是序列的第一个数据的条件是找不到nums[i]-1
找到第一个数据后，递增，找下一个数据在不在哈希表里，若在，当前序列长度++
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res_len = 0;
unordered_set<int> num_set(nums.begin(), nums.end());
int cur_len;
for(int i=0;i<nums.size();i++)
{
int cur = nums[i];
if(!num_set.count(cur-1)){
cur_len = 1;
while(num_set.count(++cur))
cur_len++;
res_len = max(res_len,cur_len);
}
}
return res_len;
}
};
为什么代码里for里套了while还是O(n)呢
如果所有数字都是连续的，那么只有第一个数字会去走while，其他数字无法通过if判断，那么每个数字都只处理一次。如果所有数字都是不连续的，每个数字都去走while，但是while只会处理这个数字，相当于还是每个数字只处理一次。不是说for里面套了while就一定是平方级别的复杂度，关键在于看数组中每个元素的处理次数。
就酱
129. 求根节点到叶节点数字之和
深度搜索，前序遍历
从根节点开始，遍历每个节点，如果遇到叶子节点，则获得该路径的数字。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历，获得该节点对应的所有路径的数字之和。
- 参数及返回值
因为要用到当前路径到达父节点组成的值，所以参数不仅要当前节点，也需要父节点组成的值presum
返回值是当前节点到叶节点的数字之和，整型 - 终止条件
当前节点为根节点的时候，返回当前值
if(root->left==nullptr&&root->right==nullptr)
return sum;
因为左右节点是空的时候已经判断了，那么整个树的root节点是空的时候，返回0
if(root==nullptr)
return 0; - 单层逻辑
首先计算当前节点对应的数字int sum=preSum*10+root->val;
然后深度遍历，获得左右节点的值之和
int leftSum=0;
int rightSum=0;
if(root->left)
leftSum=preOrder(root->left,sum);
if(root->right)
rightSum=preOrder(root->right,sum);
最后将左右节点对应的路径的数字之和再求和，就是当前节点所在的所有路径的数字之和
/**
* 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:
int preOrder(TreeNode* root, int preSum)
{
if(root==nullptr)
return 0;
int sum=preSum*10+root->val;
if(root->left==nullptr&&root->right==nullptr)
return sum;
int leftSum=0;
int rightSum=0;
if(root->left)
leftSum=preOrder(root->left,sum);
if(root->right)
rightSum=preOrder(root->right,sum);
return leftSum+rightSum;
}
int sumNumbers(TreeNode* root) {
return preOrder(root,0);
}
};
