day6
54.二叉搜索树的第k大节点
中序遍历得到有序的节点，保存中序遍历序列，取第k大
这个思路可以优化的～
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
vector<int> path;
dfs(root,path);
return path[k-1];
}
void dfs(TreeNode* root,vector<int> &path){
if(root==NULL){
return;
}
dfs(root->right,path);
path.push_back(root->val);
dfs(root->left,path);
}
};
优化：不必保存中序遍历的序列
class Solution {
public:
int ans;
int kthLargest(TreeNode* root, int k) {
dfs(root,k);
return ans;
}
void dfs(TreeNode* root,int &k){
if(root==NULL){
return;
}
if(k) dfs(root->right,k);
k--;
if(k==0) ans=root->val;
if(k) dfs(root->left,k);
}
};
class Solution {
public:
int ans;
int kthLargest(TreeNode* root, int k) {
dfs(root,k);
return ans;
}
void dfs(TreeNode* root,int &k){
if(root==NULL || k==0){//当root为空或者已经找到了res时，直接返回
return;
}
dfs(root->right,k);
k--;
if(k==0){
ans=root->val;
return;//这里的return可以避免之后的无效迭代dfs(root.left);
}
dfs(root->left,k);
}
};
时间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 N ，占用 O(N) 时间。
空间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间。
57.和为s的两个数字(重点)
思路1:暴力搜索 时间复杂度o(n^2)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0;i<nums.size()-1&&ans.empty();i++){
for(int j=nums.size()-1;j>i&&ans.empty();j--){
if(nums[j]==target-nums[i]){
ans.push_back(nums[j]);
ans.push_back(nums[i]);
}
else if(nums[j]<target-nums[i]){
break;
}
}
}
return ans;
}
};
思路2:hash表
一次遍历，时间O(N)，空间O(N)，此方法和leetcode两数之和一样，但那道题数组无序，本题数组有序，所以肯定有更优解
class Solution {
public:
//输出：[24,24] 预期：[16,32]
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int,int> hashmap;
for(int i=0;i<nums.size();i++){
if(hashmap[target-nums[i]]!=0){
ans.push_back(nums[i]);
ans.push_back(target-nums[i]);
break;
}//为了避免错误，要先判断
hashmap[nums[i]]++;
}
return ans;
}
};
set版本
class Solution {
public:
//输出：[24,24] 预期：[16,32]
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
set<int> hashmap;
for(int i=0;i<nums.size();i++){
if(hashmap.find(target-nums[i])!=hashmap.end()){
ans.push_back(nums[i]);
ans.push_back(target-nums[i]);
break;
}
hashmap.insert(nums[i]);
}
return ans;
}
};
思路3: 使用二分，遍历数组，遍历每一个数，然后在后面的数中二分查找对应的差.
比如target=40,nums[0] = 10，那么用二分查找30。时间O(NLogN)，空间O(1)
没实现
for(int i = 0;i<nums.length;++i){
int left = i + 1,right = nums.length-1,e =target - nums[i];
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == e){
return new int[]{nums[i],nums[mid]};
}else if(nums[mid] > e){
right = mid -1;
}else if(nums[mid] < e){
left = mid + 1;
}
}
}
return new int[]{};
最优 思路4:使用双指针，时间O(N) 空间O(1)
我们先在数组中选择两个数字，如果它们的和等于输入的s，我们就找到了要找的两个数字。
如果和小于s 呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些，那么两个数字的和也要大一些， 就有可能等于输入的数字s 了。
同样， 当两个数字的和大于s时，可以选择较大数字前面的数字，因为排在前面的数字小一些。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0,j=nums.size()-1;i<j;){
if(nums[i]+nums[j]==target){
ans.push_back(nums[i]);
ans.push_back(nums[j]);
break;
}
else if(nums[i]+nums[j]>target){
j--;
}
else{
i++;
}
}
return ans;
}
};
60. n个骰子的点数(重点)
不会写
n个骰子的所有点数的排列数为6^n。
统计出每个点数和出现的次数，再除以6^n，就能得出每个点数和出现的概率。
而且值得注意的是，n个骰子的点数和的最小值为n，最大值为6n，因此一共只有6n-n+1种情况，所以可以建立一个定长数组。
思路1:基于递归求骰子点数
并不需要n重循环来到达求概率的目标，应该想到用递归即可!!!
课本p295-296
虽然超时，但是这个思路，这代码得会。
class Solution {
public:
vector<double> dicesProbability(int n) {
//int hashmap[6*n-n+1]={0};//失败，因为variable-sized object may not be initialized
//int *hashmap = new int[6*n-n+1]();//可。定义长度，同时初始化为0
vector<double> hashmap(6*n-n+1,0);
dfs(0,n,0,hashmap);
int all=pow(6,n);
for(int i=0;i<hashmap.size();i++){
hashmap[i]/=all;
}
return hashmap;
}
void dfs(int level,int& n,int sum,vector<double> &hashmap){
if(level==n){
hashmap[sum-n]++;
return;
}
for(int i=1;i<=6;i++){
dfs(level+1,n,sum+i,hashmap);
}
}
};
该思路由于是基于递归实现，有很多重复的计算，从而导致当n变大时，性能慢得无法接受。
单纯使用递归搜索解空间的时间复杂度为6^n，在本题会超时，因为存在重复子结构。
思路2:基于循环求骰子点数
可以考虑用两个数组来存储骰子点数的每个总数出现的次数。在一轮循环中，第一个数组中的第 n 个数字表示骰子和为 n 出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为 n 的骰子出现的次数应该等于上一轮循环中骰子点数和为 n-1 、 n-2 、 n-3 、 n-4 、 n-5 与 n-6 的次数的总和。所以我们把另一个数组的第 n 个数字设为前一个数组对应的第 n-1 、 n-2 、 n-3 、 n-4 、 n-5 与 n-6 之和。
总结：运用递推递进的思路来解决问题。
class Solution {
public:
vector<double> dicesProbability(int n) {
vector<double> pro1(6*n+1,0);
vector<double> pro2;
//初始化第一颗骰子
for(int i=1;i<=6;i++){
pro1[i]=1;
}
//从第二个骰子开始递推
for(int i=2;i<=n;i++){
pro2=vector<double>(6*n+1,0);
for(int j=i;j<=6*i;j++){
for(int k=1;k<=6;k++){
if(j-k>0 && j-k<=6*(i-1) ){
pro2[j]+=pro1[j-k];
}
}
}
pro1=pro2;
}
if(n==1){
pro2=pro1;
}
int all=pow(6,n);
for(int i=n;i<=6*n;i++){
pro2[i]/=all;
}
vector<double> ans(pro2.begin()+n,pro2.end());
return ans;
}
};
后续：
阅读评论区
阅读课本的解法二
阅读https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/
尤其是getcount那里(好像是与评论区和课本说的：此时和为 n 的骰子出现的次数应该等于上一轮循环中骰子点数和为 n-1 、 n-2 、 n-3 、 n-4 、 n-5 与 n-6 的次数的总和。好像是这么理解的，而不是直接从递归树看出来的)
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/java-dong-tai-gui-hua-by-zhi-xiong/
