Prepare for the second test, three questions a day
Topic 1: incremental ternary subsequence (leetcode 1.12 daily)
Give you an integer array nums to judge whether there is an increasing subsequence with length of 3 in this array.
If such a triple subscript (i, j, k) exists and I < J < K is satisfied, so that num [i] < num [J] < num [k], return true; Otherwise, false is returned.
Example 1:
Input: num = [1,2,3,4,5]
Output: true
Explanation: any triple of I < J < K satisfies the meaning of the question
Example 2:
Input: num = [5,4,3,2,1]
Output: false
Explanation: there is no triplet satisfying the meaning of the question
Example 3:
Input: num = [2,1,5,0,4,6]
Output: true
Explanation: triples (3, 4, 5) satisfy the meaning of the question because num [3] = = 0 < num [4] = = 4 < num [5] = = 6
Tips:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
Advanced: can you implement a solution with time complexity O(n) and space complexity O(1)?
Source: LeetCode
Link: https://leetcode-cn.com/problems/increasing-triplet-subsequence
After writing for the first time, I found that I didn't fully understand the meaning of the question and thought it was satisfied only by increasing three consecutive elements (the example is also given in this way). The result passed the use case: 62 / 76 (infeasible)
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;
}
};
After realizing this, of course, the first thought is triple for brute force cracking (not feasible)
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;
}
};
The results exceed the time limit, which is also reasonable. When the data scale is large, the comparison times are too many
Then improve, judge in advance, reduce the data scale and then compare (still defective)
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;
}
};
The above algorithm can solve the vast majority of use cases. When the data scale is very large, and it is 121212... Such a sequence, it will still exceed the time limit.
Positive solution: greedy algorithm
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3){
return false;
}
//Two variables are used to save the first and second elements of the incremental subsequence, initially infinite
//As long as there is an increasing ternary subsequence, the first and second elements should be as small as possible
int a=INT_MAX;
int b=INT_MAX;
for(int i=0;i<nums.size();i++){
//If the current element is less than a, the value of a is updated
if(nums[i]<=a){
a=nums[i];
//If the current element is greater than a but less than b, the value of b is updated
}else if(nums[i]<=b){
b=nums[i];
//If the current element is greater than a and b, the condition is met and the increasing ternary subsequence is found
}else{
return true;
}
}
return false;
}
};
Topic 2: Roman numerals to integers
Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
Character value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, the Roman numeral 2 is written as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.
Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:
I can be placed to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Given a Roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4
Example 3:
Input: s = "IX"
Output: 9
Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3
Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4
Tips:
1 <= s.length <= 15
s contains only characters ('I ',' V ',' X ',' L ',' C ','D','M ')
The title data ensures that s is a valid Roman numeral and represents an integer in the range [1, 3999]
The test cases given in the title comply with the Roman numeral writing rules, and there will be no cross position and so on.
Examples such as IL and IM do not meet the title requirements. 49 should write XLIX and 999 should write CMXCIX.
For detailed writing rules of Roman numerals, please refer to Roman numerals - Mathematics.
Source: LeetCode
Link: 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;
}
};
Translate directly according to the title requirements, with simple ideas and repetitive contents
After reading the solution, the idea is really ingenious. The essence is to put a small value to the left of a large value, that is, subtraction, otherwise it is addition. For example, IV is 5-1 = 4, and VI is 5 + 1 = 6
Topic 3: the same tree
Give you the root nodes p and q of two binary trees and write a function to check whether the two trees are the same.
If two trees are structurally identical and the nodes have the same value, they are considered to be the same.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Tips:
The number of nodes on both trees is in the range [0, 100]
-104 <= Node.val <= 104
Source: LeetCode
Link: https://leetcode-cn.com/problems/same-tree
Simple recursive thinking
/**
* 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;
}
}
};