Summary of sword finger offer (c + +)

Some are official explanations or better ideas of others, and some are written by themselves. Prepare to brush questions while sorting out, only as your own study notes!

1. Array

JZ1. Search of two-dimensional array

Title Description
In a two-dimensional array (each one-dimensional array has the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty()||array[0].empty())
            return false;
        int row=array.size(),col=array[0].size();
        int x=0,y=col-1;
        while(x<row&&y>=0)
        {
            if(array[x][y]<target)
            {
                x+=1;
            }
            else if(array[x][y]>target)
            {
                y-=1;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

tips:Dual vector I / O
vector initialization

JZ6. Minimum number of rotation array

Title Description
Moving the first elements of an array to the end of the array is called array rotation.
Enter a rotation of a non decrementing array and output the smallest element of the rotation array.
For example, if the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], the minimum value of the array is 1.
NOTE: all elements given are greater than 0. If the array size is 0, please return 0.

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int length=rotateArray.size();
        if(length<=0) return 0;
        if(length==1) return rotateArray[0];
        int pre=0,cur=1;
        int mark=1,mark2=1,min=0;
        for(int i=0;i<length-1;i++)
        {
            if(rotateArray[pre]==rotateArray[cur])
            {
                ;
            }
            else if(rotateArray[pre]>rotateArray[cur])
            {
                mark=0;
                mark2=0;
                min=rotateArray[cur];
                break;
            }
            else
            {
                mark=0;
            }    
            pre+=1;
            cur=pre+1;
        }
        if((mark==0) && (mark2==0))
            return min;
        else
            return rotateArray[0];
    }
};

JZ28. The number of times the array appears more than half

Title Description
A number in the array appears more than half the length of the array. Please find this number. For example, enter an array {1,2,3,2,2,2,2,5,4,2} with a length of 9. Since the number 2 appears five times in the array, more than half the length of the array, 2 is output. If 0 does not exist.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //Method 1: map
//         int length=numbers.size();
//         map<int,int> mp;
//         for(int i=0;i<length;i++)
//             mp[numbers[i]]++;
//         for(int i=0;i<length;i++)
//         {
//             if(mp[numbers[i]]>length/2)
//                 return numbers[i];
//         }
//         return 0;
        //Method 2
        int count=0,num=0;
        int length=numbers.size();
        for(int i=0;i<length;i++)
        {
            if(count==0)
            {
                count++;
                num=numbers[i];
            }
            else if(numbers[i]==num)
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        count=0;
        for(int i=0;i<length;i++)
            if(numbers[i]==num) count++;
        if(count>length/2)
            return num;
        else
            return 0;
    }
};

JZ29. Minimum number of k

Title Description
Enter n integers and find the smallest number of K. For example, if you enter 8 numbers: 4,5,1,6,2,7,3,8, the smallest 4 numbers will be 1,2,3,4.

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k>input.size()) return ret;
        sort(input.begin(), input.end());
        return vector<int>({input.begin(), input.begin()+k});        
    }
};

JZ32. Arrange the array into the smallest number

Title Description
Enter an array of positive integers, put all the numbers in the array together to form a number, and print the smallest of all the numbers that can be spliced. For example, if you enter the array {3, 32321}, the minimum number that these three numbers can be arranged is 321323.

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
         vector<string> str;
        for (int val : numbers) str.push_back(to_string(val));
        sort(str.begin(), str.end(), [](string a, string b) {
            return a + b < b + a;
        });
        string ret = "";
        for (string s : str) ret += s;
        return ret;       
    }
};

JZ35. Reverse order pair in array

Title Description
Two numbers in the array. If the previous number is greater than the following number, the two numbers form an inverse pair. Enter an array and find the total number of reverse pairs P in this array. And output the result of P's modulus of 100000007. I.e. output P%1000000007
Enter Description:
The title ensures that there are no identical numbers in the input array

Data range:

about%50 Data,size<=10^4

about%75 Data,size<=10^5

about%100 Data,size<=2*10^5

Big guy thinking

class Solution {
public:
    int cnt=0;
    void MergeSort(int array[], int start, int end){
        if(start>=end)return;
        int mid = (start+end)/2;
        MergeSort(array, start, mid);
        MergeSort(array, mid+1, end);
        MergeOne(array, start, mid, end);
    }
    void MergeOne(int array[], int start, int mid, int end){
        int* temp = new int[end-start+1];
        int k=0,i=start,j=mid+1;
        while(i<=mid && j<= end){
//If the preceding element is smaller than the following, it cannot form an inverse pair
            if(array[i] <= array[j])
                temp[k++] = array[i++];
            else{
//If the preceding element is larger than the following element, the elements after the preceding element can form reverse pairs with the following elements
                temp[k++] = array[j++];
                cnt = (cnt + (mid-i+1))%1000000007;
            }
        }
        while(i<= mid)
            temp[k++] = array[i++];
        while(j<=end)
            temp[k++] = array[j++];
        for(int l=0; l<k; l++){
            array[start+l] = temp[l];
        }
    }
    int InversePairs(vector<int> data) {
        int* p=new int[data.size()];
        for(int i=0;i<data.size();i++)
        {
            p[i]=data[i];
        }
        MergeSort(p, 0, data.size()-1);
        return cnt;
    }
};

JZ37. The number of times a number appears in a sorted array

Title Description
Counts the number of times a number appears in an ascending array

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int length=data.size();
        int l=0,h=data.size();
        int mid;
        while(l<h)
        {
            mid=(l+h-1)/2;
            if(data[mid]<k)
                l=mid+1;
            else
                h=mid;
        }
        int lbound=l;
        l=0;
        h=data.size();
        while(l<h)
        {
            mid=(l+h-1)/2;
            if(data[mid]<=k)
                l=mid+1;
            else
                h=mid;
        }
        int hbound=l;
        return hbound-lbound;
    }
};

JZ40. A number that appears only once in the array

Title Description
In an integer array, all but two numbers appear twice. Please write a program to find these two numbers that only appear once.

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        map<int,int> mp;
        vector<int> ans;
        for(int i=0;i<data.size();i++)
        {
            mp[data[i]]++;
        }
        for(int i:data)
        {
            if(mp[i]==1)
                ans.push_back(i);
        }
        *num1=ans[0];
        *num2=ans[1];
    }
};

JZ42. And are two numbers of S

Title Description
Input an incrementally sorted array and a number s, and find two numbers in the array so that their sum is exactly S. if the sum of multiple pairs of numbers is equal to s, output the smallest product of the two numbers.
thinking
Violence is exhaustive... But the inner loop can break by finding the first number pair.
If optimized, double pointers can be used.

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        map<int,int> mp;
        int mark=0;
        for(int i=0;i<array.size();i++)
            for(int j=i+1;j<array.size();j++)
            {
                if(array[i]+array[j]==sum)
                {
                    mp[array[i]]=array[j];
                    mark=1;
                    break;
                }
            }
        int tmp=INT_MAX;
        pair<int,int> ans;
        for(pair<int,int> i:mp)
        {
            if(i.first*i.second<tmp)
            {
                ans=i;
                tmp=i.first*i.second;
            }
        }
        vector<int> ret;
        if(!mark)
            return ret;
        ret.push_back(ans.first);
        ret.push_back(ans.second);
        return ret;
    }
};

JZ50. Duplicate number in array

Title Description
All numbers in an array of length n are in the range of 0 to n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated. I don't know how many times each number is repeated. Please find the first duplicate number in the array. For example, if you enter an array {2,3,1,0,2,5,3} with a length of 7, the corresponding output is the first repeated number 2.
Return Description:
If there are duplicate numbers in the array, the function returns true; otherwise, it returns false.
If there are duplicate numbers in the array, put the duplicate numbers in the parameter duplication[0]. (ps:duplication has been initialized and can be assigned directly.)

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        map<int,int> mp;
        if(length<=1)
            return false;
        for(int i=0;i<length;i++)
        {
            mp[numbers[i]]++;
        }
        for(int i=0;i<length;i++)
        {
            if(mp[numbers[i]]>=2)
            {
                duplication[0]=numbers[i];
                return true;
            }
        }
        return false;
    }
};

JZ51. Build product array

Title Description
Given an array A[0,1,..., n-1], please construct an array B[0,1,..., n-1], where the element B[i]=A[0]A[1]... * A[i-1]A[i+1]... * A[n-1]. Division cannot be used. (Note: it is stipulated that B[0] = A[1] * A[2] *... * A[n-1], B[n-1] = A[0] * A[1] *... * A[n-2];)
For the case where the length of A is 1, B is meaningless and cannot be constructed, so this case will not exist.

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> ans;
        if(A.size()<=1)
            return ans;
        int length=A.size();
        for(int i=0;i<length;i++)
        {
            int temp=1;
            for(int j=0;j<length;j++)
            {
                if(i!=j)
                {
                    temp*=A[j];
                }
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

2. String

JZ2. Replace spaces

Title Description
Please implement a function to replace each space in a string with "% 20". For example, when the string is We Are Happy Then the replaced string is We%20Are%20Happy.

class Solution {
public:
	void replaceSpace(char *str,int length) {
        if(str==nullptr||length<0)
            return;
        int num=0;
        for(int i=0;i<length;i++)
        {
            if(str[i] == ' ')
                num++;
        }
        int nl=length+num*2;
        for(int i=length;i>=0;i--)
        {
            if(str[i]==' ')
            {
                str[nl--]='0';
                str[nl--]='2';
                str[nl--]='%';
            }
            else{
                str[nl--]=str[i];
            }
        }
        return;
	}
};

JZ27. Arrangement of strings

Title Description
Enter a string and print out all the permutations of characters in the string in dictionary order. For example, if you enter the string abc, all strings abc,acb,bac,bca,cab and cba that can be arranged by the characters a, B and C will be printed in dictionary order

class Solution {
public:
    void perm(int f,string s,set<string> &ans)
    {
        if(f+1==s.length())
        {
            ans.insert(s);
            return;
        }
        for(int i=f;i<s.length();i++)
        {
            swap(s[f],s[i]);
            perm(f+1,s,ans);
            swap(s[f],s[i]);
        }
    }
    vector<string> Permutation(string str) {
        set<string> ans;
        if(str.size()==0)
            return {};
        perm(0,str,ans);
        return vector<string>({ans.begin(),ans.end()});
    }
};

JZ34. The first character that appears only once

Title Description
Find the first character that appears only once in a string (0 < = string length < = 10000, all composed of letters), and return its position. If not, return - 1 (case sensitive) (counting from 0)

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        map<char,int> mp;
        for(const char s:str)
        {
            mp[s]++;
        }
        for(int i=0;i<str.length();i++)
        {
            if(mp[str[i]]==1)
                return i;
        }
        return -1;
    }
};

JZ43. Left rotation string

Title Description
There is a shift instruction in assembly language called cyclic left shift (ROL). Now there is a simple task to simulate the operation result of this instruction with a string. For a given character sequence S, please output the sequence after shifting it left by K bits. For example, the character sequence S = "abcXYZdef" requires the output of the result after the cyclic left shift of 3 bits, that is, "XYZdefabc". Isn't it simple? OK, take care of it!

class Solution {
public:
    string LeftRotateString(string str, int n) {
        string s="";
        int length=str.size();
        if(n>length) return str;
        int k=n;
        for(k;k<length;k++)
        {
            s+=str[k];
        }
        for(int i=0;i<n;i++)
        {
            s+=str[i];
        }
        return s;
    }
};

JZ44. Reverse word order column

Title Description
Fish, a new employee of Niuke recently, always takes an English magazine and writes some sentences in the book every morning. Cat, a colleague, was very interested in the content written by fish. One day he borrowed it from fish, but he couldn't understand its meaning. For example, "student. a am I". Later I realized that this guy had reversed the order of sentences and words, and the correct sentence should be "I am a student.". Cat is not good at reversing the order of these words one by one. Can you help him?

class Solution {
public:
    string ReverseSentence(string str) {
        vector<string> ans;
        string s;
        if(str.length()<=0)
            return s;
        for(int i;i<str.length();i++)
        {
            if(str[i]!=' ')
            {
                s+=str[i];
            }
            else
            {
                ans.push_back(s);
                s="";
            }
        }
        ans.push_back(s);
        s="";
        for(int i=ans.size()-1;i>=0;i--)
        {
            s+=ans[i];
            s+= i==0?"":" ";
        }
        return s;
    }
};

JZ45. Poker shunzi

Title Description
LL is in A particularly good mood today, because he went to buy A deck of playing cards and found that there were two kings and two Xiaowang (A deck of cards was originally 54) He randomly drew five cards out of them to test his luck and see if he could draw shunzi. If so, he decided to buy A sports lottery, hehe!! "Hearts A, spades 3, Wang, Wang, Fang Pian 5", "Oh My God!" Not shunzi... LL was unhappy. He thought about it and decided that big / small Wang could be regarded as any number, and A was regarded as 1,J as 11,Q as 12 and K as 13. The above five cards can become "1,2,3,4,5" (the big and small kings are regarded as 2 and 4 respectively), "So Lucky!". LL decided to buy sports lottery tickets. Now, you are required to use this card to simulate the above process, and then tell us how lucky LL is. If the card can form A shunzi, it will output true, otherwise it will output false. For convenience, you can think that the size king is 0.
thinking
There are two cases to consider,
I If the vector does not contain 0:
So how to judge? Because it needs to be a shunzi, there can be no duplicate value first. If there is no duplicate value, the shape is as [1 2 3 4 5]
[5 6 7 8 9], it will be found that the difference between the maximum value and the minimum value should be less than 5

II If the vector contains 0:
It is found that the judgment method of the value after removing 0 is the same as that in 1.

Therefore, according to the above two conditions, the algorithm process is as follows:

Initialize a set, max_= 0, min_= fourteen
Traverse the array. If an integer greater than 0 does not appear in the set, it will be added to the set and update max_, min_
If it appears in the set, return false directly
After traversing the array, finally judge whether the difference between the maximum value and the minimum value is less than 5

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        set<int> st;
        int max_ = 0, min_ = 14;
        for (int val : numbers) {
            if (val > 0) {
                if (st.count(val) > 0) return false;
                st.insert(val);
                max_ = max(max_, val);
                min_ = min(min_, val);
            }
        }
        return max_ - min_ < 5;
    }
};

JZ49. Convert string to integer

Title Description
Converting a string to an integer requires that the library function that converts an integer from a string cannot be used. If the value is 0 or the string is not a legal value, 0 is returned
Enter Description:
Enter a string, including alphanumeric symbols, which can be empty
Output Description:
If it is a legal numeric expression, it returns the number; otherwise, it returns 0
Example 1
input
+2147483647
1a33
output
2147483647
0
thinking
Reference ideas

class Solution {
public:
    int StrToInt(string str) {
        const int length = str.length();
        int isNegtive = 1, overValue = 0;
        int digit = 0, value = 0;
 
        if (length == 0) return 0;
        else {
            int idx = 0;
            if (str[0] == '-') { isNegtive = -1; idx = 1;}
            else if (str[0] == '+') {idx = 1;}
 
            for (; idx<length; idx++) {
                digit = str[idx]-'0';
                // overValue indicates whether the current cycle will cross the boundary
                overValue = isNegtive*value - INT_MAX/10
                          + (((isNegtive+1)/2 + digit > 8) ? 1:0);
 
                if (digit<0 || digit>9) return 0;
                else if (overValue > 0) return 0;
 
                value = value*10 + isNegtive*digit;
            }
            return value;
        }
    }
};

JZ52. Regular Expression Matching

Title Description
Please implement a function to match including '‘ Regular expressions for 'and'. Character 'in mode‘ Represents any character, and '' indicates that the character before it can appear any time (including 0 times). In this question, matching means that all characters of the string match the whole pattern. For example, the string "aaa" matches the patterns "a.a" and "abaca", but not "aa.a" and "ab*a"
thinking
Reference ideas

class Solution {
public:
    bool match(char* str, char* pattern)
    {
         if(*str=='\0' && *pattern=='\0')
            return true;
        if(*str!='\0' && *pattern=='\0')
            return false;
        if(*(pattern+1)!='*'){
            if(*str==*pattern || (*str!='\0' && *pattern=='.'))
                return match(str+1,pattern+1);
            else return false;
        }
        else{
            if(*str==*pattern || (*str!='\0' && *pattern=='.'))
                return match(str,pattern+2) || match(str+1,pattern);
            else return match(str,pattern+2);
        }
    }
};

JZ53. A string representing a numeric value

Title Description
Please implement a function to judge whether the string represents a numeric value (including integer and decimal). For example, the strings "+ 100", "5e2", "123", "3.1416" and "- 1E-16" all represent numeric values. But "12e", "1a3.14", "1.2.3", "± 5" and "12e+4.3" are not.

class Solution {
public:
    bool isNumeric(char* string)
    {
        int i=0,eflag=0,dotflag=0;
        if(string[i] == '+' || string[i] == '-'){
            i++;
        }
        while(string[i] != '\0'){
            if(string[i] == 'e' || string[i] == 'E'){
                if(eflag == 1){
                    return 0;
                }
                eflag = 1;
                if(string[i+1] == '+' || string[i+1] == '-'){
                    i++;
                }
                if(string[i+1] == '\0'){
                    return 0;
                }
            }
            else if(string[i] == '.'){
                if(eflag == 1 || dotflag == 1){
                    return 0;
                }
                dotflag = 1;
            }
            else if(string[i] < '0' || string[i] > '9'){
                return 0;
            }
            i++;
        }
        return 1;
    }

};

JZ54. The first non repeating character in the character stream

Title Description
Please implement a function to find the first character that appears only once in the character stream. For example, when only the first two characters "go" are read out from the character stream, the first character that appears only once is "g". When the first six characters "google" are read from the character stream, the first character that appears only once is "l".
Return value Description:
If there is no character in the current character stream that appears once, return # character.

c++ map,find()

class Solution
{
public:
  //Insert one char from stringstream
    map<char,int> mp;
    queue<char> p;
    void Insert(char ch)
    {
        map<char,int>::iterator tmp=mp.find(ch);
        if(tmp==mp.end())
        {
            p.push(ch);
        }
        ++mp[ch];
        
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while(!p.empty())
        {
            char ch;
            ch=p.front();
            if(mp[ch]==1)
                return ch;
            else
                p.pop();
        }
        return '#';
    }

};

3. Linked list

JZ3. Print linked list from end to end

Title Description
Enter a linked list and return an ArrayList from end to end

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *pre=nullptr;
        ListNode *cur=head;
        ListNode *temp=cur;
        while(cur)
        {
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        vector<int> ans;
        while(pre)
        {
            ans.push_back(pre->val);
            pre=pre->next;
        }
        return ans;
    }
};

JZ25. Replication of complex linked list

Title Description
Enter a complex linked list (each node has a node value and two pointers, one pointing to the next node and the other special pointer random pointing to a random node). Please make a deep copy of this linked list and return the copied head node. (Note: please do not return the node reference in the parameter in the output result, otherwise the problem determination program will directly return null)

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if (pHead==nullptr) return nullptr;
        RandomListNode* i=pHead, *newNode=nullptr;
        while(i!=nullptr)
        {
            newNode = new RandomListNode(i->label);
            newNode->next= i->next;
            i->next = newNode;
            i=i->next->next;
        }
        i=pHead;
        while(i!=nullptr)
        {
            newNode=i->next;
            if (i->random == nullptr) newNode->random=nullptr;
            else
                newNode->random=i->random->next;
            i=newNode->next;
        }
        i=pHead;
        newNode=pHead->next;
        RandomListNode *res = pHead->next;
        while(i!=nullptr)
        {
           newNode=i->next;
           i->next=newNode->next;
           if (newNode->next!=nullptr)
               newNode->next=newNode->next->next;
           i=i->next;
        }
        return res;        
    }
};

JZ36. The first common node of two linked lists

Title Description
Enter two linked lists and find their first common node. (note that because the incoming data is a linked list, the prompt of error test data is displayed in other ways to ensure that the incoming data is correct)
thinking
The tails of the two linked lists are spliced with each other, so that they are the same length. Directly find the common node

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *ta = pHead1, *tb = pHead2;
        while (ta != tb) {
            ta = ta ? ta->next : pHead2;
            tb = tb ? tb->next : pHead1;
        }
        return ta;        
    }
};

JZ55. The entry node of the link in the linked list

Title Description
Give a linked list. If it contains a ring, please find the entry node of the ring of the linked list. Otherwise, null will be output.
thinking
Hash or speed pointer

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
//        //Method 1: hash
//         set<ListNode*> st;
//         while (pHead) {
//             if (st.find(pHead) == st.end()) {
//                 st.insert(pHead);
//                 pHead = pHead->next;
//             }
//             else {
//                 return pHead;
//             }
//         }
//         return nullptr;
        //Method 2: speed pointer
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

JZ56. Delete duplicate nodes in the linked list

Title Description
In a sorted linked list, there are duplicate nodes. Please delete the duplicate nodes in the linked list. The duplicate nodes are not retained and the chain header pointer is returned. For example, the linked list 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5 is 1 - > 2 - > 5 after processing

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode *vhead = new ListNode(-1);
        vhead->next = pHead;
        ListNode *pre = vhead, *cur = pHead;       
        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
                while (cur->next && cur->val == cur->next->val) {
                    cur = cur->next;
                }
                cur = cur->next;
                pre->next = cur;
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        return vhead->next;
    }
};

4. Binary tree

JZ4. Rebuild binary tree

Title Description
Enter the results of preorder traversal and inorder traversal of a binary tree. Please rebuild the binary tree. It is assumed that the input pre order traversal and middle order traversal results do not contain duplicate numbers. For example, if the preorder traversal sequence {1,2,4,7,3,5,6,8} and the middle order traversal sequence {4,7,2,1,5,3,8,6} are input, the binary tree will be reconstructed and returned.
Train of thought (a Niu you)
Pre sequence plus middle sequence. The decomposition process is shown as follows (kingly data structure P120)

  1. Find the root node position gen in the middle sequence from the first pre[0] in the first sequence
  2. gen centered traversal
    0~gen left subtree
    Sub ordered sequence: 0~gen-1, put in vin_left[]
    Sub preorder sequence: 1~gen into pre_left [], + 1 can see the figure, because there is a root node in the head
    gen+1~vinlen is a right subtree
    Sub ordered sequence: gen+1 ~ vinlen-1 into vin_right[]
    Sub sequence: gen+1 ~ vinlen-1 into pre_right[]
  3. Create root node from pre sequence [0]
  4. Connect the left subtree and recurse according to the sub sequence of the left subtree (pre_left [] and vin_left [])
  5. Connect the right subtree and recurse according to the sub sequence of the right subtree (pre_right [] and vin_right [])
  6. Return root node
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int vinlen=vin.size();
        if(vinlen<=0)
            return nullptr;
        vector<int> vinleft,vinright,preleft,preright;
        TreeNode *head=new TreeNode(pre[0]);
        int gen=0;
        for(int i=0;i<vinlen;i++)
        {
            if(vin[i]==pre[0])
            {
                gen=i;
                break;
            }
        }
        for(int i=0;i<gen;i++)
        {
            vinleft.push_back(vin[i]);
            preleft.push_back(pre[i+1]);
        }
        for(int i=gen+1;i<vinlen;i++)
        {
            vinright.push_back(vin[i]);
            preright.push_back(pre[i]);
        }
        head->left=reConstructBinaryTree(preleft, vinleft);
        head->right=reConstructBinaryTree(preright, vinright);
        return head;
    }
};

JZ22. Print binary tree from top to bottom

Title Description
Each node of the binary tree is printed from top to bottom, and the nodes of the same layer are printed from left to right.

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        queue<TreeNode*> qt;
        qt.push(root);
        while(!qt.empty())
        {
            TreeNode *temp=qt.front();
            qt.pop();
            ans.push_back(temp->val);
            if(temp->left) qt.push(temp->left);
            if(temp->right) qt.push(temp->right);
        }
        return ans;
    }
};

JZ23. Postorder traversal sequence of binary tree

Title Description
Enter an integer array to judge whether the array is the result of post order traversal of a binary search tree. If yes, return true; otherwise, return false. Suppose that any two numbers of the input array are different from each other.

class Solution {
public:
    bool IsBST(const vector<int>& sequence, const int start, const int end){
    if (start>=end) return true;  // Start > end may occur
 
    int pivot;
    for (pivot=start; sequence[pivot]<sequence[end]; ++pivot);  // Find demarcation point
    for (int i=pivot; i<=end; ++i)
        if (sequence[i]<sequence[end]) return false;
    return IsBST(sequence, start, pivot-1) && IsBST(sequence, pivot, end-1);
}    
    bool VerifySquenceOfBST(vector<int> sequence) {
    if (!sequence.size()) return false;
    return IsBST(sequence, 0, sequence.size()-1);
    }
};

JZ24. A path with a value in a binary tree

Title Description
Enter the root node and an integer of a binary tree, and print out all paths in which the sum of node values in the binary tree is the input integer in dictionary order. Path is defined as a path from the root node of the tree down to the leaf node.

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void dfs(TreeNode* root,int num,vector<vector<int>> &ans,vector<int> &path)
    {
        path.push_back(root->val);
        if(root->val==num&&!root->left&&!root->right)
            ans.push_back(path);
        if(root->left)
            dfs(root->left,num-root->val,ans,path);
        if(root->right)
            dfs(root->right,num-root->val,ans,path);
        path.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ans;
        vector<int> path;
        if(root==nullptr)
            return ans;
        dfs(root,expectNumber,ans,path);
        return ans;
    }
};

JZ26. Binary search tree and bidirectional linked list

Title Description
Enter a binary search tree and convert the binary search tree into a sorted two-way linked list. It is required that no new nodes can be created, and only the node pointer in the tree can be adjusted.
thinking
Traverse the binary tree in the middle order, and the result is stored in the list. Modify the node pointer.

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void adjust(TreeNode* root,vector<TreeNode*> &list)
    {
        if(root->left!=nullptr)
            adjust(root->left, list);
        list.push_back(root);
        if(root->right!=nullptr)
            adjust(root->right, list);
    }
    TreeNode* get(vector<TreeNode*> &list)
    {
        for(int i=0;i<list.size()-1;i++)
        {
            list[i]->right=list[i+1];
            list[i+1]->left=list[i];
        }
        return list[0];
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr)
            return nullptr;
        vector<TreeNode*> list;
        adjust(pRootOfTree,list);
        return get(list);
    }
};

JZ38. Depth of binary tree

Title Description
Enter a binary tree and find the depth of the tree. The nodes (including root and leaf nodes) passing from root node to leaf node form a path of the tree, and the length of the longest path is the depth of the tree

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr) return 0;
        int l=TreeDepth(pRoot->left);
        int r=TreeDepth(pRoot->right);
        int m=1+((l>r)?l:r);
        return m;   
    }
};

JZ39. balanced binary tree

Title Description
Enter a binary tree to judge whether the binary tree is a balanced binary tree.

Here, we only need to consider its balance, not whether it is a sorted binary tree

class Solution {
public:
    int depth(TreeNode *root) {
        if (!root) return 0;
        int ldep = depth(root->left);
        if (ldep == -1) return -1;
        int rdep = depth(root->right);
        if (rdep == -1) return -1;
        int sub = abs(ldep - rdep);
        if (sub > 1) return -1;
        return max(ldep, rdep) + 1;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        return depth(root) != -1;
    }
};

JZ57. Next node of binary tree

Title Description
Given a binary tree and one of its nodes, please find the next node in the middle order traversal order and return. Note that the nodes in the tree contain not only left and right child nodes, but also pointers to parent nodes.
thinking
Violence solving methodorIt is solved according to the ergodic property of middle order

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(!pNode) return pNode;
        
        if(pNode->right)
        {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
 
        while(pNode->next)
        {
            TreeLinkNode* tmp=pNode->next;
            if(tmp->left == pNode)
                return tmp;
            pNode = pNode->next;
        }
        return nullptr;
    }
};

JZ58. Symmetric binary tree

Title Description
Please implement a function to judge whether a binary tree is symmetrical. Note that if a binary tree is the same as the mirror image of the binary tree, it is defined as symmetrical.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool judge(TreeNode* l,TreeNode* r)
    {
        if(!l&&!r)
            return true;
        if(!l||!r)
            return false;
        return l->val==r->val && judge(l->left,r->right)&&judge(l->right, r->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(!pRoot)
            return true;
        return judge(pRoot->left,pRoot->right);
    }

};

JZ59. Print binary tree in zigzag order

Title Description
Please implement a function to print the binary tree in zigzag, that is, the first line is printed from left to right, the second layer is printed from right to left, the third line is printed from left to right, and so on.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ret;
        if (!pRoot) return ret;
        queue<TreeNode*> q;
        q.push(pRoot);
        int level = 0;
 
        while (!q.empty()) {
            int sz = q.size();
            vector<int> ans;
            while (sz--) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
 
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++level;
            if (!(level&1)) // Reverse the even layer
                reverse(ans.begin(), ans.end());
            ret.push_back(ans);
        }
        return ret;
    }
    
};

JZ60. Print binary tree into multiple lines

Title Description
The binary tree is printed from top to bottom by layer, and the nodes of the same layer are output from left to right. Each layer outputs one line.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> ans;
            if(!pRoot)
                return ans;
            queue<TreeNode*> qt;
            qt.push(pRoot);
            while(!qt.empty())
            {
                int l=qt.size();
                vector<int> tmp;
                while(l--)
                {
                    TreeNode* p=qt.front();
                    qt.pop();
                    tmp.push_back(p->val);
                    if(p->left)
                        qt.push(p->left);
                    if(p->right)
                        qt.push(p->right);
                }
                ans.push_back(tmp);
            }
            return ans;
        }
    
};

JZ61. Serialized binary tree

Title Description
Please implement two functions to serialize and deserialize the binary tree respectively

Serialization of binary tree refers to saving the result of traversal of a binary tree as a string in a certain format, so that the binary tree established in memory can be saved for a long time. Serialization can be modified based on the binary tree traversal method of first order, middle order, second order and sequence. The result of serialization is a string. During serialization, an empty node (#) is represented by a symbol to! Indicates the end of a node value (value!).

Deserialization of binary tree refers to reconstructing the binary tree according to the serialized string result str obtained in a certain traversal order.

For example, we can serialize a binary tree with a root node of 1 as "1", and then parse it back through our own function

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if (!root) {
            return "#";
        }

        string res = to_string(root->val);
        res.push_back(',');

        char* left = Serialize(root->left);
        char* right = Serialize(root->right);

        char* ret = new char[strlen(left)+strlen(right)+res.size()];
        // If it is a string type, directly use operator + =, where char * needs a function
        strcpy(ret,res.c_str());
        strcat(ret,left);
        strcat(ret,right);

        return ret;
    }
    // Parameters use references &, to achieve the purpose of global variables
    TreeNode* deseri(char *&s) {
        if (*s == '#') {
            ++s;
            return nullptr;
        }

        // Construct root node value
        int num = 0;
        while (*s != ',') {
            num = num * 10 + (*s - '0');
            ++s;
        }
        ++s;
        // Recursive construction tree
        TreeNode *root = new TreeNode(num);
        root->left = deseri(s);
        root->right = deseri(s);

        return root;
    }

    TreeNode* Deserialize(char *str) {
        return deseri(str);
    }
};

JZ62. The k-th node of binary search tree

Title Description
Given a binary search tree, please find the k-th smallest node. For example, in (5, 3, 7, 2, 4, 6, 8), the value of the third node in the order of node value is 4.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    void range(TreeNode* root,vector<TreeNode*> &t)
    {
        if(!root)
            return;
        range(root->left,t);
        t.push_back(root);
        range(root->right,t);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(!pRoot)
            return nullptr;
        vector<TreeNode*> t;
        range(pRoot,t);
        if(k>=1&&t.size()>=k)//If this judgment condition is not written for the first time, and the error is reported, the recursive overflow should still pay attention to the robustness of the program
            return t[k-1];
        return nullptr;
    }

    
};

5. Stack

JZ5. Two stacks implement queues

Title Description
Two stacks are used to implement a queue to complete the Push and Pop operations of the queue. The element in the queue is of type int

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ret=stack2.top();
        stack2.pop();
        return ret;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

JZ21. Push pop sequence of stack

Title Description
Enter two integer sequences. The first sequence represents the push in order of the stack. Please judge whether the second sequence may be the pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the pressing sequence of a stack, and sequence 4,5,3,2,1 is a pop-up sequence corresponding to the pressing sequence, but 4,3,5,1,2 cannot be the pop-up sequence of the pressing sequence. (Note: the length of these two sequences is equal)

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {     
        int length=pushV.size();
        if(length<=0)
            return false;
        stack<int> st;
        int i=0,j=0;
        while(i<length)
        {
            if(pushV[i]==popV[j])
            {
                i++;j++;
                while(!st.empty()&&st.top()==popV[j])//Remember, the order of these two judgment conditions cannot be reversed, otherwise an error will be reported when the stack is empty
                {
                    st.pop();
                    j++;
                }
            }
            else
            {
                st.push(pushV[i++]);
            }
        }
        return st.empty();
//         int length=pushV.size();
//         if(length<=0)
//             return false;
//         stack<int> st;
//         int p=0,q=0;
//         while(q<5)
//         {
//             if(!st.empty()&&st.top()==popV[q])
//             {
//                 while(st.top()==popV[q]&&!st.empty())
//                 {
//                     st.pop();
//                     q++;
//                     if(q==5)
//                         return true;
//                 }
//                 if(q<5&&p>=5)
//                     return false;
//             }
//             else if(!st.empty()&&st.top()!=popV[q])
//             {
//                 while(st.top()!=popV[q]&&p<5)
//                 {
//                     st.push(pushV[p]);
//                     p++;
//                 }
//                 if(p>=5&&st.top()!=popV[q])
//                     return false;
//             }
//             else
//             {
//                 if(p>5)
//                     return false;
//                 do
//                 {
//                     st.push(pushV[p++]);
//                 }while(st.top()!=popV[q]&&p<5);
//                 if(p>5&&st.top()!=popV[q])
//                     return false;
//             }
//         }
//         return false;
    }
};

6. Dynamic planning

JZ7. Fibonacci sequence

Title Description
We all know the Fibonacci sequence. Now it is required to input an integer n. please output the nth item of the Fibonacci sequence (starting from 0, item 0 is 0, and item 1 is 1).
n<=39

class Solution {
public:
    int Fibonacci(int n) {
        if(n<0) return -1;
        if(n==0) return 0;
        if(n==1) return 1;
        vector<int> f(n+1,0);//Remember to initialize, otherwise you will be prompted that the array is out of bounds
        f[0]=0;
        f[1]=1;
        for(int i=2;i<=n;i++)
            f[i]=f[i-1]+f[i-2];
        return f[n];
    }
};

JZ7. Frog jumping steps

Title Description
A frog can jump up one step or two steps at a time. How many frogs jump up the steps in different order.

class Solution {
public:
    int jumpFloor(int number) {
//         if(number==0)
//             return 0;
//         if(number==1)
//             return 1;
//         if(number==2)
//             return 2;
//         return jumpFloor(number-1)+jumpFloor(number-2);
        if(number==0||number==1)
            return number;
        int a=1,b=1,c;
        for(int i=2;i<=number;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};

JZ30. Maximum sum of continuous subarrays

Title Description
HZ occasionally uses some professional questions to fool those non computer majors. Today, after the meeting of the test group, he said again: in the ancient one-dimensional pattern recognition, it is often necessary to calculate the maximum sum of continuous sub vectors. When the vectors are all positive, the problem is well solved. However, if the vector contains negative numbers, should it contain a negative number and expect the positive number next to it to make up for it? For example: {6, - 3, - 2,7, - 15,1,2,2}, the maximum sum of continuous sub vectors is 8 (from 0 to 3). Give an array and return the sum of its largest continuous subsequence. Will you be fooled by it? (the length of the subvector is at least 1)

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()<=0) return 0;
        int max=array[0],b=0;
        for(int i=0;i<array.size();i++)
        {
            if(array[i]+b<0) 
            {
                b=0;
                if(array[i]>max)
                    max=array[i];
            }
            else
            {
                b=b+array[i];
                if(b>max)
                    max=b;
            }
        }
        return max;
    }
};

JZ67. dynamic programming

Title Description
Here is a rope with a length of N. please cut the rope into m segments of integer length (M and N are integers, n > 1 and M > 1, m < = n). The length of each segment of rope is recorded as k[1],..., k[m]. What is the possible maximum product of k[1]x... xk[m]? For example, when the length of the rope is 8, we cut it into three sections with lengths of 2, 3 and 3 respectively. At this time, the maximum product is 18.
thinking
dynamic programming

Other methods

class Solution {
public:
    int cutRope(int number) {
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }
 
        vector<int> f(number + 1, -1);
        for (int i = 1; i <= 4; ++i) {
            f[i] = i;
        }
        for (int i = 5; i <= number; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = max(f[i], j * f[i - j]);
            }
        }
        return f[number];
    }
};

7. Find

JZ31. Number of occurrences of 1 in an integer

Title Description
Find the number of occurrences of 1 in 113 integers, and calculate the number of occurrences of 1 in 1001300 integers? Therefore, he specially counted the numbers 1, 10, 11, 12 and 13 in 1 ~ 13, so they appeared six times, but he had no way to solve the following problems. ACMer hopes you can help him and make the problem more general. You can quickly find the number of occurrences of 1 in any non negative integer interval (from 1 to 1 in n).
thinking

A clearer idea

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int digit=1,ans=0;
        int high=n/10,cur=n%10,low=0;
        while(high||cur)
        {
            if(cur==0)
            {
                ans+=high*digit;
            }
            else if(cur==1)
            {
                ans+=high*digit+low+1;
            }
            else
            {
                ans+=(high+1)*digit;
            }
            low=cur*digit+low;
            digit*=10;
            cur=high%10;
            high/=10;
        }
        return ans;
    }
};
//         digit, res = 1, 0
//         high, cur, low = n // 10, n % 10, 0
//         while high != 0 or cur != 0:
//             if cur == 0: res += high * digit
//             elif cur == 1: res += high * digit + low + 1
//             else: res += (high + 1) * digit
//             low += cur * digit
//             cur = high % 10
//             high //= 10
//             digit *= 10
//         return res

other

JZ33. Ugly number

Title Description
N umbers containing only qualitative factors 2, 3 and 5 are called ugly numbers. For example, 6 and 8 are ugly numbers, but 14 is not because it contains a quality factor of 7. Traditionally, we regard 1 as the first Ugly Number. Find the nth Ugly Number in the order from small to large.
thinking

Refer to a great God idea

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index <= 0)return 0;
        int p2=0,p3=0,p5=0;//Initialize three points to three locations that potentially become the smallest ugly number
        int* result = new int[index];
        result[0] = 1;//
        for(int i=1; i < index; i++){
            result[i] = min(result[p2]*2, min(result[p3]*3, result[p5]*5));
            if(result[i] == result[p2]*2)p2++;//In order to prevent repetition, all three if's need to be able to go
            if(result[i] == result[p3]*3)p3++;//In order to prevent repetition, all three if's need to be able to go
            if(result[i] == result[p5]*5)p5++;//In order to prevent repetition, all three if's need to be able to go 
        }
        return result[index-1];    
    }
};

JZ41. Continuous positive sequence with sum s

Title Description
Xiao Ming likes math very much. One day when he was doing his math homework, he asked to calculate the sum of 9 ~ 16. He immediately wrote the correct answer is 100. But he is not satisfied with this. He is wondering how many kinds of continuous positive number sequences have a sum of 100 (including at least two numbers). Before long, he got another set of sequences with a continuous positive sum of 100: 18, 19, 20, 21, 22. Now let'S leave the problem to you. Can you quickly find all the continuous positive sequences with sum S? Good Luck!

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ans;
        for(int j=1;j<=sum/2;j++)
            for(int i=j+1;i<sum;i++)
            {
                if((i*(i+1)/2-j*(j-1)/2)==sum)
                {
                    vector<int> temp;
                    int k=j;
                    while(k<=i)
                    {
                        temp.push_back(k++);
                    }
                    ans.push_back(temp);
                } 
            }
        return ans;
    }
};

JZ46. Children's games

Title Description
Every International Children's Day, Niuke prepares some small gifts to visit the children in the orphanage. This year is the same. As a senior veteran of Niuke, HF has naturally prepared some small games. Among them, there is a game like this: first, let the children form a big circle. Then, he randomly assigned a number m and asked the child with number 0 to start counting. Every time the child who cries out to m-1 wants to line up and sing a song, and then you can choose any gift in the gift box and don't go back to the circle. Starting from his next child, continue to count 0... m-1... This way... Until the last child is left, you don't need to perform, and get the valuable "famous detective Conan" Collection Edition of Niuke (the quota is limited!!). Please try to think about which child will get this gift? (Note: Children's numbers are from 0 to n-1)
thinking
Final winner of sequence with length n f[n]:
f[1] = 0
f[2] = (f{1] + m) % 2
f[3] = (f[2] + m) % 3
...
f[n] = (f[n-1] + m) % n

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n <= 0) return -1;
        int index = 0;
        for (int i=2; i<=n; ++i) {
            index = (index + m) % i;
        }
        return index;
//         if(n<=0||m<1)
//             return -1;
//         int k=n,num=0,count=0;
//         map<int,int> mp;
//         for(int i=0;i<n;i++)
//             mp[i]=0;
//         while(k>1)
//         {
//             while(count<=m)
//             {
//                 if(mp[num]==0)
//                 {
//                     count++;
//                     num=(num+1)%k;
//                 }
//             }
//             mp[num-1]=1;
//             k--;
//             count=0;
//         }
//         return k;
    }
};

JZ47. Find 1 + 2 +... + n

Title Description
For 1 + 2 + 3 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.
thinking
f (n==1) return 1;

Deformation recursion:
If n==1, the recursion needs to be terminated, so we think of the logical and & & connectors.
A & & B means that if a is true, execute B; otherwise, if a is not true, do not execute B
So we can. When n > 1, the recursive function is executed

class Solution {
public:
    int Sum_Solution(int n) {
        bool x=n>1 && (n+=Sum_Solution(n-1));
        return n;
    }
};

JZ48. No addition, subtraction, multiplication and division

Title Description
Write a function and find the sum of two integers. It is required that the four operation symbols +, -, *, / shall not be used in the function body.
thinking
utilize Bit operation

class Solution {
public:
    int Add(int num1, int num2)
    {
        while (num2 != 0) {
            // A negative number shifted to the left will complement 1 in the low order, so it is converted to an unsigned integer
            int c = ((unsigned int)(num1 & num2)) << 1;
            num1 ^= num2;
            num2 = c;
        }
        return num1;
    }
};

JZ63. Median in data stream

Title Description
How to get the median in a data stream? If an odd number of values are read out from the data stream, the median is the value in the middle after all values are sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers after all values are sorted. We use the Insert() method to read the data stream and the GetMedian() method to get the median of the current read data.

class Solution {
    vector<double> data;
public:
    void Insert(int num)
    {
        data.push_back(num);
        sort(data.begin(),data.end());
    }
    double GetMedian()
    {
        int length = data.size();
        if(length%2==0){
            return (data[length/2]+data[length/2-1])/2;
        }
        else{
            return data[(length/2)];
        }
    }
};

JZ64. Maximum value of sliding window

Title Description
Given an array and the size of the sliding window, find the maximum value in all sliding windows. For example, if you enter the array {2,3,4,2,6,2,5,1} and the size 3 of the sliding window, there are six sliding windows, and their maximum values are {4,4,6,6,5}; There are six sliding windows for array {2,3,4,2,6,2,5,1}: {[2,3,4], 2,6,2,5,1}, {2, [3,4,2], 6,2,5,1}, {2,3, [4,2,6], 2,5,1}, {2,3,4, [2,6,2], 5,1}, {2,3,4,2, [6,5,5], 1}, {2,3,4,2,6, [2,5,1]}.
When the window is larger than the length of the array, null is returned.

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ans;
        if(size>num.size()||!num.size()||size<1)
            return ans;
        for(int i=0;i<num.size()-size+1;i++)
        {
            int temp=num[i];
            for(int j=i;j<i+size;j++)
            {
                if(num[j]>temp)
                {
                    temp=num[j];
                }
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

JZ65. Path in matrix

Title Description
Please design a function to judge whether there is a path containing all characters of a string in a matrix. The path can start from any grid in the matrix, and each step can move one grid left, right, up and down in the matrix. If a path passes through a lattice in the matrix, the path cannot enter the lattice again.

class Solution {
public:
    char *mat = 0;
    int h = 0, w = 0;
    int str_len = 0;
    int dir[5] = {-1, 0, 1, 0, -1};
 
    bool dfs(int i, int j, int pos, char *str) {
        // Because there is no boundary check before dfs call,
        // So the first step is to check the boundary,
        // Because you need to access the elements in mat later, you cannot access beyond the boundary
        if (i < 0 || i >= h || j < 0 || j >= w) {
            return false;
        }
 
        char ch = mat[i * w + j];
        // Determine whether you have visited
        // If not, judge whether it matches the string str[pos]
        if (ch == '#' || ch != str[pos]) {
            return false;
        }
 
         // If it matches, judge whether it matches the last character
        if (pos + 1  == str_len) {
            return true;
        }
 
        // Indicates that the current characters match successfully. Mark it and you can't enter again next time
        mat[i * w + j] = '#';
        for (int k = 0; k < 4; ++k) {
            if (dfs(i + dir[k], j + dir[k + 1], pos + 1, str)) {
                return true;
            }
        }
        // If none of the four directions can match str[pos + 1]
        // Then trace back and restore '#' to ch         
        mat[i * w + j] = ch;
        // This indicates that the match was unsuccessful
        return false;  
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        mat = matrix;
        h = rows, w = cols;
         str_len = strlen(str);
 
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(i, j, 0, str)) {
                    return true;
                }
            }
        }
        return false;
    }
};

JZ66. Range of motion of robot

Title Description
There is a square with m rows and n columns on the ground. A robot starts to move from the grid with coordinates 0 and 0. Each time, it can only move one grid in the left, right, upper and lower directions, but it cannot enter the grid where the sum of digits of row coordinates and column coordinates is greater than k. For example, when k is 18, the robot can enter the grid (35,37) because 3 + 5 + 3 + 7 = 18. However, it cannot enter the grid (35,38) because 3 + 5 + 3 + 8 = 19. How many grids can the robot reach?

class Solution {
public:
    int dir[5] = {-1, 0, 1, 0, -1};
 
    int check(int n) {
        int sum = 0;
 
        while (n) {
            sum += (n % 10);
            n /= 10;
        }
 
        return sum;
    }
 
    void dfs(int x, int y, int sho, int r, int c, int &ret, vector<vector<int>> &mark) {
        // Check subscript and access
        if (x < 0 || x >= r || y < 0 || y >= c || mark[x][y] == 1) {
            return;
        }
        // Check whether the current coordinates meet the conditions
        if (check(x) + check(y) > sho) {
            return;
        }
        // The code goes here, indicating that the current coordinates meet the conditions
        mark[x][y] = 1;
        ret += 1;
 
        for (int i = 0; i < 4; ++i) {
            dfs(x + dir[i], y + dir[i + 1], sho, r, c, ret, mark);
        }
 
 
 
    }
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }
 
        vector<vector<int>> mark(rows, vector<int> (cols, -1));
        int ret = 0;
        dfs(0, 0, sho, rows, cols, ret, mark);
        return ret;
    }
};

Tags: C++

Posted by Ab on Sun, 08 May 2022 06:13:08 +0300