![](https://pic.rmb.bdstatic.com/5da751880d6acc39c36604bcb09da63f.jpeg)
每日一刷,每日一结
五月每日一题
5.09 母亲节,制作m束花所需要的最少天数
这一题主要是先对题目做一个概览性的分析:
1、只要花的数量小于总数,必然无返回,只要花的数量大于或等于总数,则必然有结果
2、存在那么一个days,当大于days必然有连续数组满足,小于days必然不满足,是一个关于days的递增函数,我们就是要找到这个突变点
关于days满不满足,这就是判断不超过days限定条件的最多长度为k的连续子数组的数量
下面给出代码分析:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class Solution { public: bool checkDays(vector<int> bloomDay,int days,int m,int k) { int kun=0; int flowers=0; int length=bloomDay.size(); for(int i=0;i<length&&kun<m;i++) { if(bloomDay[i]<=days) { flowers++; if(flowers==k) { kun++; flowers=0; } } else flowers=0; } return kun>=m; } int minDays(vector<int>& bloomDay, int m, int k) { int length=bloomDay.size(); if(m*k>length) return -1; int largestday=0; for(int i=0;i<length;i++) { if(bloomDay[i]>=largestday) largestday=bloomDay[i]; } int left=1; int right=largestday; while(left<right) { int days=(left+right)/2; if(checkDays(bloomDay,days,m,k)) right=days; else left=days+1; } return left; } };
|
05.10 二叉树的叶子的遍历:叶子相似的树
给定两棵二叉树,首先通过递归方法遍历得到叶子节点,然后比较两颗树的叶子节点是否完全一样
- 首先定义两个vector对叶子节点进行存储
- 然后写一个dfs进行二叉树叶子节点遍历存储
- 1、注意通过引用进行vector的地址传递‘
- 2、如果为空,结束标志
- 3、否则如果左右孩子均为空,则说明为叶子,放入vector
- 4、用dfs继续操作左右孩子
- 判断两个vector是否相同
给出代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: void dfs(TreeNode* root,vector<int> &temp) { if(root==nullptr) return ; if(root->left==nullptr&&root->right==nullptr) temp.push_back(root->val); dfs(root->left,temp); dfs(root->right,temp); } bool leafSimilar(TreeNode* root1, TreeNode* root2) { vector<int> temp1; vector<int> temp2; dfs(root1,temp1); dfs(root2,temp2); return (temp1==temp2); } };
|
05.11位操作,根据异或的加密结果求原码值
描述一种加密方式:pre有奇数个元素(元素为1-n),相邻两个异或操作可以得到encoded数组,现在给出encoded数组,需要求出原本的pre数组
- 这道题目最关键的要点在于:若是知道pre第一个数字,其他的结果可以立刻求得。而pre第一个元素的获取方法比较特殊:由于,pre_all=pre_0异或pre_剩余,pre_all可以知道,pre_剩余可以知道(为encode中所有奇数位上元素的异或)。因此pre_0可以知道。
- 然后即可通过pre_0和encode求得pre所有元素。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public: vector<int> decode(vector<int>& encoded) { int n=encoded.size()+1; int without_first=0; int all=0; for(int i=1;i<encoded.size();i+=2) { without_first=without_first^encoded[i]; } for(int i=1;i<=n;i++) { all=all^i; } vector<int>per; int per_first=without_first^all; per.push_back(per_first); for(int i=1;i<n;i++) { per.push_back(per[i-1]^encoded[i-1]); } return per; } };
|
05.13停留在原地的方案数目(动态规划大法)
给定步数step,给定移动数组长度len;每次可以选择不动,向左移动一次,向右移动一次,原地保持不动。求最终回到原点的方案数目
- 刚接触到这道题目,自己感觉应该是动态规划,但是没有想到状态转移方程怎么去写,其实对于这类题目,状态转移方程是比较容易定义的。dp数组定义dp[i] [j] 表示在i步操作到达 j位置的方案数,有了这个定义就可以往下面去一步步推理了。
- dp[i] [j]中首先将能到达位置范围缩小一下:j的最大值是选择len和step中较小的那一个 int maxcolumm=min( len-1,steps ) 所以dp的定义 vector<vector>dp( steps+1,vector( maxcolumn+1,0];
- 然后就是初始条件和状态转移矩阵的定义:A:都可以为原地保持不动操作;B:向右走得到;C:向左走得到。
- 然后就是初始条件
这里给出代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public: const int MODULO = 1000000007;
int numWays(int steps, int arrLen) { int maxColumn = min(arrLen - 1, steps); vector<vector<int>> dp(steps + 1, vector<int>(maxColumn + 1)); dp[0][0] = 1; for (int i = 1; i <= steps; i++) { for (int j = 0; j <= maxColumn; j++) { dp[i][j] = dp[i - 1][j]; if (j - 1 >= 0) { dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO; } if (j + 1 <= maxColumn) { dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO; } } } return dp[steps][0]; } };
|
05.14整数转罗马数字(类似一种贪心算法)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: string intToRoman(int num) { int son_nums[]={1000,900,500,400,100,90,50,40,10,9,5,4,1}; string son_str[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; string ans; for(int i=0;i<13;i++) { while(num>=son_nums[i]) { num=num-son_nums[i]; ans+=son_str[i]; } } return ans;
} };
|
05.15罗马数字转整数
本题与5.14整数转罗马数字是一类题目,结题思路也基本一致,属于字符串的基本操作,包括字符串选择性擦除,字符串取子串等。
- 首先,定义所有的子罗马数字情况,从大到小排列,以及这些罗马文字对应的阿拉伯数字
- 然后通过遍历取解决,遍历的关键在于判断当前字符串s的头部串是否有罗马数组当前i对应的字符串相同。相同就将ans加上对应的阿拉伯数字,然后通过erase进行剔除当前罗马字符串
实践复杂度为O(n),执行超过了100%,内存方面多了两个数组,以及申请了一个temp串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: int romanToInt(string s) { string son_str[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; int son_num[]={1000,900,500,400,100,90,50,40,10,9,5,4,1}; int ans=0; for(int i=0;i<13;i++) { string temp=s.substr(0,son_str[i].size()); while(temp==son_str[i]) { ans+=son_num[i]; s=s.erase(0,son_str[i].size()); temp=s.substr(0,son_str[i].size()); } } return ans; } };
|
05.20前K个高频单词
给定一个非空单词列表,返回前K个出现次数最多的单词,返回单词出现频率由高到低,相同频率按字母顺序排序
- 通过使用map,可以统计次数,由于map是按照键进行排序,我们需要对value进行排序。所以引入vector<pair<string,int>>进行对map进行copy,然后通过sort和cmp进行排序,这是本题最为关键的地方。
- 巧用pair<string,int>。复习map中的first和second不带括号,为啥不带括号,你用ListNode和TreeNode的思维来考虑就可以了,说白了,也就是一种类似于结构体的东西。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| class Solution { public: static bool cmp(pair<string,int> wordlist1,pair<string,int> wordlist2) { if(wordlist1.second==wordlist2.second) { return wordlist1.first<wordlist2.first; } return wordlist1.second>wordlist2.second; } vector<string> topKFrequent(vector<string>& words, int k) { map<string,int>wordlist; for(auto c:words) { wordlist[c]++; } vector<pair<string,int>> PairMap; for(auto c:wordlist) { PairMap.push_back(pair<string,int>(c.first,c.second)); } sort(PairMap.begin(),PairMap.end(),cmp); vector<string> ans; for(int i=0;i<k;i++) { ans.push_back(PairMap[i].first); } return ans; } };
|
05.21不相交的线(动态规划-三叶姐姐教你如何做人)
刷题的最高境界就是像三叶这样的大佬,能够将本题立刻联想到动态规划系列经典题目最长递增子序列。此题满足动态规划类型的特征:
- 两个数组(字符串)类型,然后是求最值。dp数组dp[i] [j]也比较容易理解,表示前一个数组的前i个元素,和后一个数组前j个元素所能连线的最大值。
- 动态规划最关键的状态转移:首先dp数组初始化均为0,然后就是第如果末尾相同,直接连在一起,那肯定是都不连的最大值加一;如果末尾不相同,那肯定是取二者退一个中较大的那个。
动态规划的特征:动态规划就是一种典型的穷举思想,这是计算机最擅长的事情,而且你要求最值,那我就从最初状态的最值,通过题目条件一步步的去靠近你那个最终状态的最值,靠近的法则就是准确地描述状态转移方程。
动态规划要素:状态矩阵,初始化,状态转移循环矩阵,状态转移条件,最终值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int longestCommonSubsequence(string text1, string text2) { const int lengtha=text1.size(); const int lengthb=text2.size(); vector<vector<int>>dp(lengtha+1,vector<int>(lengthb+1,0)); for(int i=1;i<=lengtha;i++) { for(int j=1;j<=lengthb;j++) { if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } return dp[lengtha][lengthb]; } };
|
**05.26栈栈栈栈栈:反转每对括号间的子串
括号是成对出现的,你要反转没两个括号间的字符串,这题方法比较直接,就是遇到左括号将临时字符串入栈,然后将临时字符串清空。遇到字符就把字符加进来,知道遇到了又括号,此时就要翻转临时字符串,同时将栈顶部的元素加上反转后的临时字符串,然后将栈顶部元素pop出去。
总结起来就是:定义一个临时栈和字符串,遇到左括号就全部入栈,并清空,非括号创建字符串,右括号翻转然后将栈顶串加到子串。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public: string reverseParentheses(string s) { string temp; stack<string> st; for(auto &c:s) { if(c=='('){ st.push(temp); temp=""; } else if(c==')') { reverse(temp.begin(),temp.end()); temp=st.top()+temp; st.pop(); } else{ temp+=c; } } return temp; } };
|