备战复试,每日三题
题目一:递增的三元子序列(leetcode1.12每日一题)
给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
示例 2:
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组
示例 3:
输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
进阶:你能实现时间复杂度为 O(n) ,空间复杂度为 O(1) 的解决方案吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/increasing-triplet-subsequence
第一遍写,发现未完全理解题意,以为是连续三个元素递增的才满足(样例也是这样给出的) 结果通过用例:62/76 (不可行)
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3){
return false;
}
for(int i=0;i<nums.size()-2;i++){
if(nums[i]<nums[i+1]&&nums[i+1]<nums[i+2]){
return true;
}
}
return false;
}
};
认识到这一点后,最先想到的当然是三重for暴力破解 (不可行)
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3){
return false;
}
for(int i=0;i<nums.size()-2;i++){
for(int j=i+1;j<nums.size()-1;j++){
for(int k=j+1;k<nums.size();k++){
if(nums[i]<nums[j]&&nums[j]<nums[k]){
return true;
}
}
}
}
return false;
}
};
结果超出时间限制,这也合乎情理,当数据规模较大时,比较次数过多
接着改进,提前判断,缩小数据规模后再比较 (仍有缺陷)
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3){
return false;
}
for(int i=0;i<nums.size()-2;i++){
for(int j=i+1;j<nums.size()-1;j++){
if(nums[i]<nums[j]){
for(int k=j+1;k<nums.size();k++){
if(nums[j]<nums[k]){
return true;
}
}
}
}
}
return false;
}
};
上述算法能解决绝大多数用例,担当数据规模特别大时,且为121212…这样的序列时,仍会超出时间限制。
正解:贪心算法
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3){
return false;
}
//用两个变量来保存递增子序列的第一个和第二个元素,初始为无穷大
//因为只要存在递增的三元子序列就好,所以,第一第二个元素要尽可能小
int a=INT_MAX;
int b=INT_MAX;
for(int i=0;i<nums.size();i++){
//若当前元素小于a,则更新a的值
if(nums[i]<=a){
a=nums[i];
//若当前元素大于a但小于b,则更新b的值
}else if(nums[i]<=b){
b=nums[i];
//若当前元素大于a和b,则满足条件,找到了递增的三元子序列
}else{
return true;
}
}
return false;
}
};
题目二: 罗马数字转整数
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。
示例 1:
输入: s = “III”
输出: 3
示例 2:
输入: s = “IV”
输出: 4
示例 3:
输入: s = “IX”
输出: 9
示例 4:
输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/roman-to-integer
class Solution {
public:
int romanToInt(string s) {
int sum=0;
for(int i=0;i<s.length();i++){
if(s[i]=='I'){
if(i==s.length()-1){
sum+=1;
}
else if(s[i+1]=='V'){
sum+=4;
i++;
}else if(s[i+1]=='X'){
sum+=9;
i++;
}else{
sum+=1;
}
}else if(s[i]=='V'){
sum+=5;
}else if(s[i]=='X'){
if(i==s.length()-1){
sum+=10;
}
else if(s[i+1]=='L'){
sum+=40;
i++;
}else if(s[i+1]=='C'){
sum+=90;
i++;
}else{
sum+=10;
}
}else if(s[i]=='L'){
sum+=50;
}else if(s[i]=='C'){
if(i==s.length()-1){
sum+=100;
}
else if(s[i+1]=='D'){
sum+=400;
i++;
}else if(s[i+1]=='M'){
sum+=900;
i++;
}else{
sum+=100;
}
}else if(s[i]=='D'){
sum+=500;
}else{
sum+=1000;
}
}
return sum;
}
};
直接按照题目要求翻译,思路简单,都是重复性的内容
看了题解,思路确实巧妙,本质就是把一个小值放在大值的左边,就是做减法,否则为加法。如 IV 就是5-1=4,而VI 就是5+1=6
题目三: 相同的树
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3]
输出:true
示例 2:
输入:p = [1,2], q = [1,null,2]
输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2]
输出:false
提示:
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/same-tree
简单递归思路
/**
* 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:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr&&q==nullptr){
return true;
}else if(p==nullptr&&q!=nullptr){
return false;
}else if(p!=nullptr&&q==nullptr){
return false;
}else{
if(p->val==q->val){
if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right)){
return true;
}
}
return false;
}
}
};