Forem: hallowaw

A solution for leetcode problem 20 "valid parentheses"

hallowaw — Mon, 15 Jul 2024 10:25:03 +0000

First we need find out what is the correct corresponding relationship for parentheses?
it is not "}" must follow "{" very closely,and we allow that situation that "{[()]}" and "{}" even "{[]}()"

And the true rule we need follow is that each ending parentheses like "),},]"need fit to the last beginning parentheses so that we have the following codes with very detailed explainations:

class Solution {
public://the requirement of the problem is to check if the parentheses is conformed by the rules and 
//the rule is that the ending parenthese must correspond to the last beginning parentheses 
    bool isValid(string s) {
        vector<char> vec1;//define a vector 
        bool result=false;//the defualt result it false 
        if(s.length()%2==1){
            return false;
        }//if the length of s is odd,then it can not have the same number of beginning parenthese and ending parenthese
        for (int i = 0; i < s.length(); i = i + 1) 
        {
            char c = s[i];//we let each element in s euqate c,
            if (c == '(' || c == '{' || c == '[') {
                vec1.push_back(c);//and if c equate the beginning parentheses we sotre it in vec1
            }
            else{
                if(vec1.empty())
                {return false;//if c do not equate beginning psrentheses and c is NULL return false 
                }
                else if(c == ')' || c == '}' || c == ']') {
                    //if c equate ending psrentheses 
                    int num=vec1.size()-1;//to make vec[num]is the last element of the vec1
                    if((vec1[num]=='{'&&s[i]=='}')||(vec1[num]=='['&&s[i]==']')||(vec1[num]=='('&&s[i]==')')){
                result=true;
                vec1.pop_back();//if the c is ending parentheses and have the corresponding relationship with the last begining parenthese ,we let result equate true and delete the last beginning parenthese from the vec1
                }
                else{
                    return false;
                }
                }
            }



        }

        if(vec1.empty()){
            return result;
            //if when we finish such operations and there is not elements in the vec1 and each begining parentheses and ending parentheses have correct relation in correct order then output the "true " result.
        }
        else{
            return false;//,maybe there are some elements remain in vec1 so must return false
        }
    }
};

One simple solution for leetcode problem 14

hallowaw — Mon, 24 Jun 2024 14:42:52 +0000

First let us figure out what should i do,we need find the common prefix for all strings in the vector

So we just need compare the char in the same position for each string
But how to denote the particular char in the particular string in a vector?
Let us use the example 1 for a explanation
So if we wanna denote the 'r' in the 'flower' ,we can use strs[0][5] to refer 'r'
So now we get the methods to make a comparison for each char,if it is the same we save it into the result string
but we also need to notice if it exit in the position of a string
We use the code to check :if(strs[j][i]=='\0')

so the full code is:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //first we define a string for storing the result
        string commonprefix="";
        int condition=1;
        for(int i=0;i<strs[0].size();i++){
            char currentchar=strs[0][i];

            for(int j=1;j<strs.size();j++)
            {
                //should require two conditions :the position of the string is not NULL and same with currentchar,here we use the contrary condition for understand easily.
                if(strs[j][i]=='\0'||strs[j][i]!=currentchar){
                    return commonprefix;
                }
            }
            commonprefix.push_back(currentchar);
        }
        return commonprefix;
    }
};

Thank you for reading!

the detailed process for sloving leetcode problem 13

hallowaw — Sat, 15 Jun 2024 13:52:57 +0000

Frist let us see the problem

To solve the question we need find the rule to calculate the sum of those roman numbers.

Let us use the LVIII as our first example,we can see that all the roman number left is not smaller than its right,so that we can add the referring integer from right to left,it is 1+1+1+5+50=58,

And there is another situation,let us use MCMXCIV as our second example,we can find I is behind V,so we should use V subtract I to 5-1=4,and next C is bigger than I so we add C 5-1+100=104,but X is smaller than C so we subtract X 5-1+100-10=94,then 94+1000-100+1000=1994,now,we have knew how to calculate the sum of one roman number,start from right and if the left is smaller than right then use right to subtract left else add the left.

But before this we need to do sth. to let each roman equal a integer to achieve it it is recommend to transfer the form of string to vector that including the integer by the sequence for each roman number so that we are easy to calculate the sum and compare which is bigger for two roman numbers.
so we have the code as following to transfer to integer vector:

       for(char ch :s){
                switch(ch){
                case 'I':
                newvec.push_back(1);
                break;
                case 'V':
                newvec.push_back(5);
                break;
                case 'X':
                newvec.push_back(10);
                break;
                case 'L':
                newvec.push_back(50);
                break;
                case 'C':
                newvec.push_back(100);
                break;
                case 'D':
                newvec.push_back(500);
                break;
                case 'M':
                newvec.push_back(1000);
                break;

            }

            }

Then we add the calculating model as following:

int size=newvec.size();
        int sum=newvec[size-1];
        for(int i=2;i<=size;i++){
            if (newvec[size-i]<newvec[size-i+1])
            {
            sum=sum-newvec[size-i];
            }
            else{
                sum=sum+newvec[size-i];
            }

        }

        return sum;

so the full codes is :

class Solution {
public:
    int romanToInt(string s) {
         vector<int>vec;

         vector<int>newvec;
            for(char ch :s){
                switch(ch){
                case 'I':
                newvec.push_back(1);
                break;
                case 'V':
                newvec.push_back(5);
                break;
                case 'X':
                newvec.push_back(10);
                break;
                case 'L':
                newvec.push_back(50);
                break;
                case 'C':
                newvec.push_back(100);
                break;
                case 'D':
                newvec.push_back(500);
                break;
                case 'M':
                newvec.push_back(1000);
                break;

            }

            }



        int size=newvec.size();
        int sum=newvec[size-1];
        for(int i=2;i<=size;i++){
            if (newvec[size-i]<newvec[size-i+1])
            {
            sum=sum-newvec[size-i];
            }
            else{
                sum=sum+newvec[size-i];
            }

        }

        return sum;

    }
};

My idea and submission for problem 9 on Leetcode(very detailed)

hallowaw — Mon, 10 Jun 2024 05:18:01 +0000

The photo of the problem

1. the analysis of the problem:

First we can easily know if the number smaller than 0,it can not be the palindrome number.
We can not compare with the first digit with the last digit,so we need come up with a method to transfer the form so that we can compare easily,then if we transfer the number to an array or vector sucessfully,we can compare the beginning digits with the ending digits easily,
but before this, we need divide it into two situations:
the number of the digit of the number is the odd or even.
we assume size=the number of the digit(same as the length of vector),

and then
if the size is odd:
we compare the vec[0]with vec[size-1],vec[1]with vec[size-2]......vec[(size-1)/2]with vec[(size+3)/2],leave size[n+1] alone.
if all comparisions equate so the number is palindrome number.
so we have codes as:

if(size%2!=0){
            int mid=(size+1)/2;
            for (int i=0;i<mid;i++){
                if (vec[i]!=vec[size-1-i]){
                    return false;
                }
            }
            return true;
        }

if the size is even:
we campare the vec[0]with vec[size-1],vec[1]with vec[size-2]......vec[size/2]withvec[(size/2)+1],if all comparisions equate so the number is palindrome number.

int mid=size/2;
        for (int i=0;i<=mid;i++){
            if(vec[i]!=vec[size-1-i]){
                return false;
            }
        }
        return true;

so totally we have the complete codes as:

class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0){
            return false;
        }//the situation of minus

        string str=to_string(x);
        vector<int>vec;
        for(char digit :str){
        vec.push_back(digit-'0');
        }
        int size=vec.size();
        if(size==1){
            return true ;
        }//the situation of one-digit

        if(size%2!=0){
            int mid=(size+1)/2;
            for (int i=0;i<mid;i++){
                if (vec[i]!=vec[size-1-i]){
                    return false;
                }
            }
            return true;
        }//the situation of odd

        int mid=size/2;
        for (int i=0;i<=mid;i++){
            if(vec[i]!=vec[size-1-i]){
                return false;
            }
        }
        return true;

        //the situation of even

    }
};



//fist discuss the situation od minus,if the number smaller tham 0,then it can not be a palindrome

//we use the function 'string str= to_string(x)' to change the form of x from int to string

//then define a vector 'vecctor<int>vec;

//then we need get each char digit from str

//by using 'result.push_back(digit-'0')' we can get a vector full of integers.

//if there is only one element in the vector ,then it should fit the requirement and is a palindrome.

My idea and submission for problem 1 on Leetcode(very detailed)

hallowaw — Sun, 09 Jun 2024 22:06:35 +0000

1. the analysis of the problem

Now we get some information from the question:
A array named nums,it includeds some intergers；
An integer named target；
What should we do:we need add two numbers from the nums to make it euqates target then return the indices(or indexs)of the two numbers；

example:Input: nums = [2,7,11,15], target = 9
Output: [0,1]
when the array nums=[2,7,11,15],we found that only 2+7=9,so we need return the indices of "2" and "7",which is 0 and 1,so the output is [0,1]
Precondition:only one solution in the array given to us,so it won't happen the situation like nums=[1,2,3,4],target=5,because the answer can be 1+4 or 2+3,so it won't happen.and we also can not use the same number for twice,
like in the example:
Input: nums = [3,3], target = 6
Output: [0,1]
we can not use the first "3" twice so we can not get the answer[0,0]

2.the method to find the two number

I guess most of us will consider about calculating all possibilities

so let us use the example of nums = [2,7,11,15], target = 9, at first we need add 2+7,then 2+11,2+15,7+11,7+15,11+15,and check the sum whether equate the target 9,once we find the equal relationship we can end the calculation cause there is only one solution exactly,

so how we can do this by codes?
we can start with the nums[0]

0 is the indice of the array,and it start from 0 in any array,it symbols the number in the position of "0+1",in the array nums it is 2

and then we add the nums[0] with nums[1],it represent 2+7,
then add the nums[0] with nums[2],it represent 2+11,then nums[0]+nums[3] ,nums[1]+nums[2],nums[1]+nums[3] ,nums[2]+nums[3]

so we can find the rules:
1.fisrt number start from nums[0] to nums[length -2].(we define the lenghth is the quantity of the numbers in the array)
2.the indice of second number is always 1 greater than first number.

so we have key codes as;

        int n=nums.size();//define n as the length of array nums[]
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return {i,j};

then we add this to the given code to spell into a complete code.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //num is the array which we need find two elements to get the right answer.vector is the similar form of array,we can ignore the difference right now.
        //first we make a integer
        int n=nums.size();
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {};//no solution found
    }
};