leetcode每日一题43
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);}
};