杭电OJ100道

2024 c语言合法标识符

There are two ways to accept all chars including space

  1. use char array, but you need to set the MaxLength for limit the length of buffer
  2. use string, it’s more convenient.

and there are two diff ways to get the length of str

  1. using < cstring > like: remember to #include <cstring> then use strlen(str) to get the length you wanted.
  2. if you use string, then you can just use the function length() like: str.length(), it will return the length of the string.
1
2
3
4
5
6
7
8
9
10
11
12
//use char array
const int MAX_LENGTH = 100;
char str[MAX_LENGTH];
cout << "Enter a string: ";
cin.getline(str, MAX_LENGTH);
cout << "You entered: " << str << endl;

//or use string
string s;
cout << "Enter a string: ";
getline(cin,s);
cout << "You entered: " << s << endl;

Use cctype to judge whether a char is num or alpha

there are three useful fun:

  1. isalpha() //check if the char is alpha , both upper and lower
  2. isdigit()
  3. isalnum() //check if the char is alpha , both upper and lower or num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isValidIdentifier(string s){
    //check if the first char is alpha or _
    if(!isalpha(s[0])&&s[0]!='_'){
        return false;
    }
    int len=s.length();
    for(int i=0;i<len;i++){
        //check the rest of the chars is a alpha , num or _
        if(!isalnum(s[i]) && s[i]!='_'){
            return false;
        }
    }
    return true;
}

Or, you can use you own way to judge it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int f=1;
int len=buffer.length();
for(int i=0;i<len;i++){
     //check if the first letter is a char or _
     if(i==0&& (buffer[i]>='a'&&buffer[i]<='z'||buffer[i]>='A'&&buffer[i]<='Z'||buffer[i]=='_')){
         f=0;
         break;
     }
     if(buffer[i]>='0'&&buffer[i]<='9'||buffer[i]>='a'&&buffer[i]<='z'||buffer[i]>='A'&&buffer[i]<='Z'||buffer[i]=='_'){
         continue;
     }
     else{
         f=0;
         break;
     }
 }
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
#include<iostream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<cctype>

using namespace std;

bool isValidIdentifier(string s){
    //check if the first char is alpha or _
    if(!isalpha(s[0])&&s[0]!='_'){
        return false;
    }
    int len=s.length();
    for(int i=0;i<len;i++){
        //check the rest of the chars is a alpha , num or _
        if(!isalnum(s[i]) && s[i]!='_'){
            return false;
        }
    }
    return true;
}

int main(){
    int n;
    string buffer;
    //ignore the space
    while(cin>>n,cin.ignore()){
        for(int j=0;j<n;j++){
            getline(cin, buffer);
            if(isValidIdentifier(buffer)){
                cout<<"yes"<<endl;
            }
            else{
                cout<<"no"<<endl;
            }
        }
    }
}

2026 将每个单词首字符变成大写

Use sstream

there are some examples to use sstream

Converting a string to other types of data

  1. We define a string variable str to receive data from input.
  2. Then we create a stringstream object ss, and pass the str into the object.
  3. Finally, we use the >> operator of the ss object to convert the data in the string to the specified data type and store it in the corresponding variable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string str = "123 4.56 true";
    stringstream ss(str);
    
    int num;
    double dbl;
    bool flag;
    
    ss >> num >> dbl >> flag;
    
    cout << num << endl; // 输出: 123
    cout << dbl << endl; // 输出: 4.56
    cout << flag << endl; // 输出: 1
    
    return 0;
}

Converting other types of data to a string

  1. we first define three variables num, dbl, and flag, which are assigned integer, double-precision floating-point, and boolean data, respectively.
  2. We then create a stringstream object ss and use the << operator of the ss object to convert these data to a string and store it in the ss object.
  3. Finally, we use the str() function of the ss object to convert the data in ss to a string and store it in the variable str, which is then outputted.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
    int num = 123;
    double dbl = 4.56;
    bool flag = true;
    
    stringstream ss;
    ss << num << " " << dbl << " " << flag;
    string str = ss.str();
    cout << str << endl; // 输出: 123 4.56 1
    return 0;
}

Here is the problems’ resolution

  1. We define a string variable str to receive data from input, then create a stringstream object ss and pass str into it.
  2. We split ss into words by space
  3. Convert the first letter into upper and prinf out the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string str;
    getline(cin,str);
    stringstream ss(str);
    string word;
    while (ss >> word) {
        word[0]=toupper(word[0]);
        cout << word << " ";
    }
    cout<<endl;
    return 0;
}

However , if we forget to use toupper, then we can converse the letter into upper one by one, like this.

1
2
3
if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] = str[i] - 'a' + 'A';
}

Here is another resolution that we find a letter which is next to a space, then convert it into upper

1
(isalpha(t[i]) && t[i-1] == ' ') ? toupper(t[i]) : t[i]);

toupper

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    string str = "aaa";
    cout<<toupper(str[1])<<endl; // get 65
    cout << char(toupper(str[0])) << endl; // 输出: A
    return 0;
}

tolower

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    // tolower returns a int variable, the "ch" will convert it into a char variable
    char ch = 'A';
    ch = tolower(ch);
    cout << ch << endl; // 输出: a
    // 
    string str = "AAA";
    //if we cout tolower(str[0]) directly , we will get 97
    cout << char(tolower(str[0])) << endl; // 输出: a
    return 0;
}

isupper

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    char ch = 'A';
    bool flag = isupper(ch);
    cout << flag << endl; // 输出: 1
    return 0;
}

isalpha

To judge if a character is a alpha

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    char ch = 'A';
    
    bool flag = isalpha(ch);
    
    cout << flag << endl; // 输出: 1
    
    return 0;
}

isdigit

To judge if a character is a digit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    char ch = '0';
    
    bool flag = isdigit(ch);
    
    cout << flag << endl; // 输出: 1
    
    return 0;
}

isalnum

To judge whether a character is a letter or a digit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    char ch = 'A';
    
    bool flag = isalnum(ch);
    
    cout << flag << endl; // 输出: 1
    
    return 0;
}

isspace

To judge if a character is space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>

using namespace std;

int main() {
    char ch = ' ';
    
    bool flag = isspace(ch);
    
    cout << flag << endl; // 输出: 1
    
    return 0;
}

2027 统计元音

count vowels

As usual,

  1. first we define a char array named vowels as {a,e,i,o,u}, and create a int array named arr to record results.
  2. we define a string valiable sentence to receive data from input
  3. use switch to judge every character in the sentence, remember to use tolower to get a lower char
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
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>

using namespace std;
const char vowels[5]={'a','e','i','o','u'};


/**
 * @brief Count the number of every vowels in a sentence
 * 
 * @param sentence 
 */
void countVowels(string sentence){
    int len=sentence.length();
    int arr[5]={0};
    for(int i=0;i<len;i++){
        //remember to get a lower letter
        switch (tolower(sentence[i]))
        {
        case 'a':
            arr[0]++;
            break;
        case 'e':
            arr[1]++;
            break;
        case 'i':
            arr[2]++;
            break;
        case 'o':
            arr[3]++;
            break;
        case 'u':
            arr[4]++;
            break;
        default:
            break;
        }
    }
    for(int i=0;i<5;i++){
        cout<<vowels[i]<<":"<<arr[i]<<endl;
    }
}

int n;
int main(){
    string sentence;
    //remember to ignore the first space after you input the number
    while(cin>>n,cin.ignore()){
        for(int i=0;i<n;i++){
            getline(cin,sentence);
            countVowels(sentence);
        }
    }
}

2028 *最小公倍数

Lowest Common Multiple

Before we solve this problem, we need to learn some new things

  1. Greatest Common Divisor(最大公约数) 【GCD】
  2. Lowest Common Multiple(最小公倍数) 【LCM】

You can use the GCD (Greatest Common Divisor) to find the LCM (Lowest Common Multiple) of two numbers using the following formula:

  1. LCM(a, b) = (a * b) / GCD(a, b)

So, we need to find GCD before we find LCM, here is an example to get gcd.

Find the GCD of 12 and 18:

  1. Divide the larger number by the smaller number and find the remainder. 18 / 12 = 1 remainder 6
  2. Divide the smaller number by the remainder and find the new remainder. 12 / 6 = 2 remainder 0
  3. The GCD is the remainder of the last division, which is 6.

Here are codes to get GCD, and there are two approaches.

  1. recursion
1
2
3
4
5
6
7
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
  1. iteration
1
2
3
4
5
6
7
8
9
int gcd(int a,int b){
	int remainder=a%b;
	while(remainder){
		a=b;
		b=remainder;
		remainder=a%b;
	}
	return remainder;
}

Here is the complete code

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
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cctype>

using namespace std;

/**
 * @brief Get the GCD object
 * 
 * @param a 
 * @param b 
 * @return int 
 */
int GCD(int a,int b){
    if(b==0)
        return a;
    int remainder=a%b;
    while(remainder){
        a=b;
        b=remainder;
        remainder=a%b;
    }
    return b;
}

/**
 * @brief Get the LCM object
 * 
 * @param a 
 * @param b 
 * @return int 
 */
int LCM(int a,int b){
    return a*b/GCD(a,b);
}

/**
 * @brief Get the LCM of a series of numbers
 * 
 * @return int 
 */
int main(){
    int n;
    while(cin>>n, n!=0){
        int *arr=new int[n];
        int res=1;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            res=LCM(res,arr[i]);
        }
        cout<<res<<endl;
    }
}

2029 回文串判断

Judge whether a string is a palidrome

Here’s a trick , if the string is a palidrom, then the loop won’t break , then i will equals to len/2 as i==len/2

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cctype>
#include<string>

using namespace std;

/**
 * @brief Judge whether a string is a palindrome
 * 
 * @param str 
 */
void JudgePalindromes(string str){
    int len=str.length();
    int f=1;
    int i;
    for(i=0;i<len/2;i++){
        if(str[i]!=str[len-i-1]){
            break;
        }
    }
    //Trick: if the loop is not broken, then i==len/2
    cout<<((i==len/2)?"yes":"no")<<endl;
}

int n;
int main(){
    while(cin>>n,cin.ignore(1,'\n')){
        string str;
        for(int j=0;j<n;j++){
            getline(cin,str);
            JudgePalindromes(str);
        }
    }
}

2031 *R进制转换

input a decimal number and convert it into an R-ary number

To convert a decimal number into an R-ary number, you need to follow these steps:

  1. Divide the decimal number by the radix (R) and note down the remainder.
  2. Divide the quotient obtained in step 1 by R and note down the remainder.
  3. Repeat step 2 until the quotient becomes zero.
  4. The remainders obtained in step 1, 2, and 3, when read in reverse order, form the R-ary representation of the decimal number.

Let’s take an example to understand this process. Suppose we want to convert the decimal number 37 into a binary number (R = 2).

  1. Divide 37 by 2. The quotient is 18 and the remainder is 1. Note down the remainder.
  2. Divide 18 by 2. The quotient is 9 and the remainder is 0. Note down the remainder.
  3. Divide 9 by 2. The quotient is 4 and the remainder is 1. Note down the remainder.
  4. Divide 4 by 2. The quotient is 2 and the remainder is 0. Note down the remainder.
  5. Divide 2 by 2. The quotient is 1 and the remainder is 0. Note down the remainder.
  6. Divide 1 by 2. The quotient is 0 and the remainder is 1. Note down the remainder.

Reading the remainders in reverse order, we get 100101, which is the binary representation of the decimal number 37.

convert the decimal number 37 into a hexadecimal (R=16) number.

To convert 37 into a hexadecimal number, we can follow the same process as explained earlier, but this time we will divide the decimal number by 16 instead of 2.

Here are the steps:

  1. Divide 37 by 16. The quotient is 2 and the remainder is 5. Note down the remainder.
  2. Divide 2 by 16. The quotient is 0 and the remainder is 2. Note down the remainder.

Reading the remainders in reverse order, we get 25, which is the hexadecimal representation of the decimal number 37.

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<iomanip>
#include<cctype>
#include<sstream>
using namespace std;

void Convert(int num,int R){
    stringstream ss;
    int quotient=num/R;
    //if num%R > 9 which means it's an alpha not a digit
    //remember to convert a num into an char variable
    ss<<char((num%R>9)?(num%R-10+'A'):(num%R+'0'));
    while(quotient){
        num=quotient;
        quotient=num/R;
        ss<<char((num%R>9)?(num%R-10+'A'):(num%R+'0'));
    }
    //reverse the remainders to get the right answer.
    string str=ss.str();
    reverse(str.begin(),str.end());
    cout<<str<<endl;
}

int n,R;
int main(){
    while(cin>>n>>R){
        if(n<0){
            cout<<"-";
            n=-n;
        }
        Convert(n,R);
    }
}

2032 杨辉三角

YangHuiTriangle

The rules as following

f(i, i) = f(i, 1) = 1 (i > 0)

f(i, j) = f(i-1, j) + f(i-1, j-1) (j < i)

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
#include<iostream>
using namespace std;

/**
 * @brief Output the YangHui Triangle
 * 
 * @param n 
 */
void outputTriangle(int n){
    int *arr=new int[n*(n+1)/2];
    for(int i=0;i<n*(n+1)/2;i++){
        arr[i]=0;
    }
    arr[0]=1;
    for(int i=0;i<n;i++){
        for(int j=i;j>0;j--){
            //arr(i, j) = arr(i-1, j) + arr(i-1, j-1), but we can compress the space to one dimension array
            //get each row's elements by adding the previous row's elements
            arr[j]+=arr[j-1];
        }
        //output the elements of each row
        for(int j=0;j<=i;j++){
            cout<<arr[j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main(){
    int n;
    while(cin>>n){
        outputTriangle(n);
    }
}

2034 集合问题A-B

Find the elemetns in A but not in B, both A and B is a ascent set.

We can use “two pointers” to solve this problem, here is the details

  1. We define an int array to receive numbers from input
  2. Define curA initialized as 0 as the begining of set A and curB initialized as 0 as the begining of set B, they are two pointers start from different index
  3. if arr[curA]==arr[curB], it means both set A and set B has this number
  4. if arr[curA]>arr[curB], not sure whether B has the same number, so just skip arr[curB]
  5. if arr[curA]<arr[curB],it means the arr[curA] is only in set A but not in set B
  6. if setA has some numbers left, we just output them directly
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
46
47
48
49
50
#include<iostream>

using namespace std;

/**
 * @brief Find the elemetns in A but not in
 * 
 * @param arr 
 * @param n 
 * @param m 
 * @return int 
 */
void foo(int *arr,int n,int m){
    int curA=0;
    int curB=n;
    int f=0;
    for(int i=0;curA<n&&curB<m+n;i++){
        if(arr[curA]==arr[curB]){
            curA++;
            curB++;
        }else if(arr[curA]>arr[curB]){
            curB++;
        }else{
            cout<<arr[curA]<<" ";
            f=1;
            curA++;
        }
    }
    //if setA has some numbers left, we just output them
    while(curA<n){
        cout<<arr[curA]<<" ";
        f=1;
        curA++;
    }
    if(f==0)
        cout<<"NULL";
    cout<<endl;
}


int main(){
    int n,m;
    while(cin>>n>>m,n!=0&&m!=0){
        int *arr=new int[n+m];
        for(int i=0;i<m+n;i++){
            cin>>arr[i];
        }
        foo(arr,n,m);
    }
}

two pointers

PorblemA

Given a set named arr of positive decimal numbers that is sorted in ascending order and a positive integer M, the task is to find every pair of numbers in the set whose sum equals M

Here is the solution

  1. Define two pointers i and j, where i initialized as 0 and j initialized as len-1, len is the length of the set.
  2. i will shift to len-1, and j will shift to 0 until i>=j
  3. if arr [i]+arr [j]==M, it means that we find one of the answer ,then just output it.
  4. if arr [i]+arr [j]>M, it means that we need to decrease the sum of left part, the real answer will show in [i,j-1],
  5. if arr [i]+arr [j]<M, it means that we need to increase the sum of left part, the real answer will show in [i+1,j]
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
//remember that the array is sorted in ascending order.
#include<iostream>
using namespace std;

/**
 * @brief Find every pair of number in the set whose sum equals to M
 * 
 * @param arr 
 * @param n 
 * @param M 
 */
void foo(int *arr,int n,int M){
    int i=0,j=n-1;
    while(i<j){
        if(arr[i]+arr[j]==M){
            cout<<arr [i]<<" "<<arr [j]<<endl;
            i++;
            j++;
        }else if(arr[i]+arr[j]>M){
            j--;
        }else{
            i++;
        }
    }
}

int main(){
    int n;
    while(cin>>n){
        int *arr=new int[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int M;
        cin>>M;
        foo(arr,n,M);
    }
    
}

Merge

Given two sets which are sorted by ascdenting order, the task it to merge them into a new set which needs to be in ascdenting order and print out the result.

We can also use the two pointer to solve this problem.

  1. We create two arraies named arrA adn arrB to receive numbers from input, lenA and lenB are the length of array ,respectively.
  2. Define two pointer i and j ,both of them are initialized as 0
  3. While i<lenA and j<lenB, we need to judge these cases
  4. if arrA[i]<arr[B],it means we need to push arrA[i] into the new array, and i++
  5. if arrA[i]>=arr[B],it means we need to push arrB[j] into the new array, and j++
  6. then remember to push the left number into the new array if arrA or arrB has some numbers left
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
46
47
48
49
#include<iostream>
using namespace std;

/**
 * @brief Merge two sorted array into one sorted array
 * 
 * @param arrA 
 * @param arrB 
 * @param lenA 
 * @param lenB 
 * @return int* 
 */
int *merge(int *arrA,int *arrB,int lenA,int lenB){
    int i=0,j=0,cur=0;
    int *arrC=new int[lenA+lenB];
    while(i<lenA&&j<lenB){
        if(arrA[i]<arrB[j]){
            arrC[cur++]=arrA[i++];
        }else{
            arrC[cur++]=arrB[j++];
        }
    }
    while(i<lenA){
        arrC[cur++]=arrA[i++];
    }
    while(j<lenB){
        arrC[cur++]=arrB[j++];
    }
    return arrC;
}

int main(){
    int n,m;
    while(cin>>n>>m,n!=0&&m!=0){
        int *arrA=new int[n];
        int *arrB=new int[m];
        for(int i=0;i<n;i++){
            cin>>arrA[i];
        }
        for(int i=0;i<m;i++){
            cin>>arrB[i];
        }
        int *arrC=merge(arrA,arrB,n,m);
        for(int i=0;i<n+m;i++){
            cout<<arrC[i]<<" ";
        }
        cout<<endl;
    }
}

2035 集合问题A^B

Find the integer represented by the last three digits of A^B.

Explanation: A^B means “A to the power of B”

Here is a more powful fomula

1
2
3
        1	    n = 0 
m^n = 	(m^k)^2	n = 2k 
        m·m^(2k)n = 2k + 1 
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
#include<iostream>
#include<cmath>
using namespace std;

int recursion(int n,int m){
    if(m==0){
        return 1;
    }
    /*
    the pow() function does return a double type floating-point number.
    However, it is possible to cast or convert it to a long long type integer, which can then be assigned to the result variable. 
    Before doing the conversion, it's important to round the pow() function's result to the nearest integer to ensure accuracy and correctness.
    */
    long long half=pow(n,m/2);
    half = ((half % 1000) + 1000) % 1000;
    if(m%2==0){
        return (half*half)%1000;
    }else{
        return (half*half*n)%1000;
    }
}

void iteration(int n,int m){
    int mp=1;
    for(int i=0;i<m;i++){
        mp=(mp*n)%1000;
    }
    cout<<mp<<endl;
}

int main(){
    int n,m;
    while(cin>>n>>m,n!=0&&m!=0){
        iteration(n,m);
    }
}

2036 计算多边形面积

Calculate the area of polygon

The formula as following

S = 0.5 * ( (x0y1-x1y0) + (x1y2-x2y1) + …+ (xn-1yn-xnyn-1) + (xny0-x0yn) )

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
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

/**
 * @brief Calculate the area of polygon
 * 
 * @param n 
 */
void AreaOfPolygon(int n){
    int x,y;
    int x0,y0;
    int x1,y1;
    cin>>x0>>y0;
    int sum=0;
    x=x0;
    y=y0;
    for(int i=1;i<n;i++){
        cin>>x1>>y1;
        sum+=x*y1-x1*y;
        x=x1;
        y=y1;
    }
    sum+=x*y0-x0*y;
    cout<<fixed<<setprecision(1)<<abs(sum)*1.0/2<<endl;
}

int main(){
    int n;
    while(cin>>n,n!=0){
        AreaOfPolygon(n);
    }
}

2037 *贪心算法|独立区间

indenpendent intervals

If you have 24 hours to watch different TV shows , and ther are many shows which can be seen as a interval, it is best to start with the latest one to ensure that it is the last show you watch.If there are two shows that start at the same time, you should definitely pick the shorter one in order to watch as many shows as possible.

So, here’s the rule to reorder these shows.

  1. Sort the intervals(shows) in descending order by their start time.【To ensure that it is the last show you watch】
  2. If two intervals have the same start time, sort them in ascending order by their end time.【To pick the shorter one】
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

struct node{
    int start;
    int end;
    int mark;
};

/**
 * @brief First sort by left endpoint from largest to smallest, if the left endpoints are the same, sort by right endpoints from smallest to largest
 * 
 * @param a 
 * @param b 
 * @return true 
 * @return false 
 */
bool cmp(node a,node b){
    if(a.start!=b.start){
        return a.start>b.start;
    }else{
        return a.end<b.end;
    }
}

/**
 * @brief Find out every independent interval
 * 
 * @param tv 
 * @param n 
 */
void foo(node *tv,int n){
    sort(tv,tv+n,cmp);
    //count : the numbers of independent intervals we have choose, the first interval is independent
    int count=1;
    int lastLeft=tv[0].start;
    tv[0].mark=1;
    //i starts from 1 because we have already choose the first interval
    for(int i=1;i<n;i++){
        //if the next interval's right endpoint is smaller than or equals to the LastLeft, it means that this interval is independent.
        if(lastLeft>=tv[i].end){
            count+=1;
            lastLeft=tv[i].start;
            tv[i].mark=1;
        }
    }
    cout<<count<<endl;
    for(int i=0;i<n;i++){
        if(tv[i].mark==1){
            cout<<tv[i].start<<" "<<tv[i].end<<endl;
        }
    }
}

int main(){
    int n;
    while(cin>>n,n!=0){
        node *tv=new node[n];
        for(int i=0;i<n;i++){
            cin>>tv[i].start>>tv[i].end;
            tv[i].mark=0;
        }
        foo(tv,n);
    }
}

2040 亲和数

Two numbers are affine if either of them is the sum of the proper divisors of the other.

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

/**
 * @brief Judge whether a number is affinity number
 * 
 * @param x 
 * @param y 
 */
void foo(int x,int y){
    int sum1=0;
    for(int i=1;i<=x/2;i++){
        if(x%i==0){
            sum1+=i;
        }
    }
    if(sum1==y){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

int main(){
    int n;
    while(cin>>n,n!=0){
        for(int j=0;j<n;j++){
            int x,y;
            cin>>x>>y;
            foo(x,y);
        }
    }
}

2041 *斐波那契

There is a staircase with M levels. At the beginning, you are on the first level. If you can only step up one or two levels at a time, how many ways are there to get to the Mth level?

To reach second level,you can take one stop from first level.

To reach third level, you can take two steps directly from first level or you can take one step from second level.

To reach nth level , you can take one step from n-1th level or you can take two steps from n-2th level.

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
46
47
48
49
50
51
52
53
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

/**
 * @brief Fibonacci sequence by recursion
 * 
 * @param n 
 * @return int 
 */
int fbRecursion(int n){
    if(n==0|n==1)
        return 0;
    else if(n==2){
        return 1;
    }
    else if(n==3){
        return 2;
    }else{
        return fbRecursion(n-1)+fbRecursion(n-2);
    }
    
}

/**
 * @brief Fibonacci sequence by iteration
 * 
 * @param x 
 * @return int 
 */
int fbIteration(int x){
    int *dp=new int[x+1];
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x-1];
}

int main(){
    int n;
    while(cin>>n,n!=0){
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            cout<<fbIteration(x)<<endl;
        }
    }
}

2043 判断是否为强密码

Rules.

  1. The length of password should be longer than or equals to 8 but not more than 16.
  2. The characters should come from at least three of the following “character categories”

category

  1. Uppercase letters A.B.C~z
  2. Lowercase letters a.b.c~z
  3. Numbers 0.1.2~9
  4. Special characters. ~,!,@,#,$,%,^;
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
46
47
48
49
50
#include<iostream>
#include<cctype>
#include<string>

using namespace std;

/**
 * @brief judge if the string is a legal password
 * 
 * @param s 
 */
void judgeIsLegal(string s){
    int len=s.length();
    if(len>16||len<8){
        cout<<"NO"<<endl;
        return;
    }
    int countUp=0;
    int countLow=0;
    int countDig=0;
    int countSpec=0;
    for(int i=0;i<len;i++){
        if(isupper(s[i])){
            countUp=1;
        }else if(islower(s[i])){
            countLow=1;
        }else if(isdigit(s[i])){
            countDig=1;
        }else{
            countSpec=1;
        }
    }
    if(countDig+countLow+countSpec+countUp>=3){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    
}

int main(){
    int n;
    string s;
    while(cin>>n,n!=0,cin.ignore()){
        for(int x=0;x<n;x++){
            getline(cin,s);
            judgeIsLegal(s);
        }
    }
}

2044 斐波那契2

There is a trained bee that can only crawl to the adjacent hive on the right, and cannot crawl in the opposite direction. Please program to calculate the number of possible routes for bees to climb from hive a to hive b.
Among them, the structure of the hive is as follows.

Pic

To reach hive n, you can crawl from hive n-1 or hive n-2, it’s the same one like 2041.

For example, to reach hive 5 , you can crawl from hive 3 or hive 4

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
46
47
48
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

/**
 * @brief Fibonacci sequence by recursion
 * 
 * @param x 
 * @return long long 
 */
long long fbRecursion(int x){
    if(x==0|x==1)
        return 1;
    else if (x==2){
        return 2;
    }else{
        return fbRecursion(x-1)+fbRecursion(x-2);
    }
}

/**
 * @brief Fibonacci sequence by recursion
 * 
 * @param x 
 * @return long long 
 */
long long fbIteration(int x){
    int *dp=new int[x+1];
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x-1];
}

int main(){
    int n;
    while(cin>>n,n!=0){
        int a,b;
        cin>>a>>b;
        cout<<fbIteration(b-a)<<endl;
    }
}

2045 RPG问题|斐波那契3

There are n squares arranged in a row, and each square can be painted with one of three colors: Red, Pink, or Green. Any two adjacent squares cannot have the same color, and the first and last squares cannot have the same color. Find the total number of ways to color all the squares under these constraints.

  1. one square:3
  2. two squares: C(3,1)*C(2,1)=6
  3. three squares: C(3,1)*C(2,1)*C(1,1)=6
  4. four squares: there are two different situations
    1. We set F(4) initiaized as 0, F(4)=0
    2. If the first square is same as the third square :negative_squared_cross_mark::black_large_square::negative_squared_cross_mark:,then there are two color for the forth square.
      1. :negative_squared_cross_mark::black_large_square::negative_squared_cross_mark::black_large_square:or :negative_squared_cross_mark::black_large_square::negative_squared_cross_mark::white_large_square:
      2. F(4)+=F(2)*2 【Because the third square must be same as the first one, it can’t chose other color】
    3. If the first square is different from the third square :negative_squared_cross_mark::black_large_square::white_large_square:, then only one color for the forth square cuz two adjacent squares cannot have the same color and the first and last squares cannot have the same color
      1. :negative_squared_cross_mark::black_large_square::white_large_square::black_large_square:
      2. F(4)+=F(3)*1
    4. F(4)=F(3)*1 + F(2)*2
  5. N squares:F(n)=F(n-1)+F(n-2)*2;
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
#include<iostream>

using namespace std;

/**
 * @brief RPG problem
 * 
 * @param n 
 */
void RPGsolution(int n){
    int *dp=new int[n+2];
    dp[0]=3;
    dp[1]=6;
    dp[2]=6;
    for(int i=3;i<n;i++){
        dp[i]=dp[i-1]+dp[i-2]*2;
    }
    cout<<dp[n-1]<<endl;
}

int main(){
    int n;
    while(cin>>n,n!=0){
        RPGsolution(n);   
    }
}

2046 骨牌铺方格|斐波那契4

In a 2×n rectangular grid, where n is an integer, find the total number of ways to completely cover the grid using 1×2 dominoes.

To cover Nth dominos over the grid, we can add one vertical dominoe at the end of the arrangement of (N-1)th dominos.

Or we can also add two horizonal dominos at the end of the arrangement of (N-2)th , We can’t add a vertical one otherwise it will be the same as the first case.

So F(n)=F(n-1)+F(n-2)

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
#include<iostream>
#include<cmath>

using namespace std;

/**
 * @brief Pave the square
 * 
 * @param n 
 */
void PaveSquare(int n){
    int *dp=new int[n+2];
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    for(int i=4;i<=n;i++){
        dp[i]=dp[i-2]+dp[i-1]*2;
    }
    cout<<dp[n]<<endl;
}
int main(){
    int n;
    while(cin>>n,n!=0){
        PaveSquare(n);
    }
}

2047 字符串EOF的排列组合|斐波那契5

The task is to generate a string of length n consisting of only three characters “E”, “O”, and “F” (which may have only one or two of these characters, but cannot have any other characters). It is forbidden to have adjacent “O” characters in the string.

  1. We define a two-dimentional array dp
    1. dp[n][1] represents the string ending with “E” or "F"
    2. dp[n][0] represents the string ending with "O"
  2. If the former legal string ending with “E” or “F” or “O”, then we can add "E" or "F"
    1. dp[n][1]=2*(dp[n-1][1]+dp[n-1][0])
  3. If the former legal string ending with “E” or “F” but not “O”, then we can add "O"
    1. dp[n][0]=dp[n][1]

We initialize the dp[0][0] as 1 which represents “O”

and initialize dp[0][1] as 2 which represents “E” or “F”

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
#include<iostream>
#include<cmath>

using namespace std;

/**
 * @brief 
 * 
 * @param n 
 */
void foo(int n){
    int **dp=new int *[n];
    for(int i=0;i<n;i++){
        dp[i]=new int[2];
    }
    //dp[i][0] represents the number of legal strings ending with "O"
    dp[0][0]=1;
    //dp[i][1] represents the number of legal strings ending with "E" or "F"
    dp[0][1]=2;
    for(int i=1;i<n;i++){
        //We can add "O" to the end of the old legal string, so the number of new strings is the same as the number of strings of length i-1.
        dp[i][0]=dp[i-1][1];
        //We can add "E" or "F" to the end of the old legal string
        dp[i][1]=(dp[i-1][0]+dp[i-1][1])*2;
    }
    cout<<dp[n-1][0]+dp[n-1][1]<<endl;
}

int main(){
    int n;
    while(cin>>n,n!=0){
        foo(n);
    }
}

2048 *错排问题1

All permutations of N tickets may naturally be Ann = N! permutations
The problem now is that there are several ways to arrange N tickets wrongly.

  1. let’s consider that if none of the previous N-1 people took their own tickets, that is, the previous N-1 people met the wrong order, and now another person comes, and he has his own ticket in his hand.
    As long as he exchanges his ticket with any one of the other N-1 people, he can satisfy the wrong arrangement of N people. At this time, there are N-1 ways.
    1. F(n)+=(n-1)*F(n-1)
  2. In addition, we can consider the case where the first N-1 people do not satisfy the derangement, but the Nth person exchanges their ticket with one of the previous people and exactly satisfies the derangement.This situation occurs when among the original N-1 people, N-2 people satisfy the derangement and only one person holds their own ticket, and the Nth person happens to exchange with that person, which satisfies the derangement. Because in the first N-1 people, each person has a chance to hold their own ticket. Therefore, there are N-1 possibilities for the exchange.Because among the top N-1 people, everyone has a chance to hold their own ticket. So there are N-1 possible exchanges.
    1. F(n)+=(n-1)*F(n-2)
  3. Even though the formula is F(N)=(n-1)*(F(n-2)+F(n-1)), but the (n-1)'s meaning is different
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
46
47
48
#include <iostream>
using namespace std;

/**
 * @brief the derangement function uses the recursive formula to calculate the number of derangements of N elements
 * 
 * @param n 
 * @return int 
 */
int derangement(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return (n-1) * (derangement(n-1) + derangement(n-2));
}

void fooRecursion(int n){
    int sum=1;
    //sum is n!
    for(int i=1;i<=n;i++){
        sum*=i;
    }
    //res is the number of derangements of n elements
    int res=derangement(n);
    cout << res*1.0/sum<< endl;
}

/**
 * @brief the fooIteration function uses the iterative formula to calculate the number of derangements of N elements
 * 
 * @param n 
 */
void fooIteration(int n){
    int dp[21][2]={{1,0},{1,0},{2,1},{6,2}};
    for(int i=4;i<=20;i++){
        //dp[i][0] is the number of permutations of n elements
        dp[i][0]=i*dp[i-1][0];
        //dp[i][1] is the number of derangements of n elements
        dp[i][1]=(i-1)*(dp[i-1][1]+dp[i-2][1]);
    }
    cout<<dp[n][1]*1.0/dp[n][0]<<endl;
}

int main() {
    int n;
    while(cin>>n,n!=0){
        fooIteration(n);
    }
}

2049 错排问题2

Here is the explanation of the derangement problem for selecting M people from N people.

To solve the derangement problem for selecting M people from N people, we can use a similar approach as the regular derangement problem.

Firstly, the number of ways to select M people from N people is given by the formula C(N,M) = N! / (M! * (N-M)!), which is a known quantity.

Next, we consider the derangement problem for these M people, where each person is not in their original position.

Let D(M) be the number of derangements for M people, then we can use the following recurrence relation:

D(M) = (M-1) * [D(M-1) + D(M-2)]

Here, D(M-1) represents the number of derangements for M-1 people, where the Mth person cannot be in the Mth position, and D(M-2) represents the number of derangements for M-2 people, where the Mth person cannot be in the (M-1)th position. Since the Mth person cannot be in the Mth position, there are M-1 choices.

The initial conditions are D(1) = 0 and D(2) = 1, since there is no derangement problem with one person, and there is only one derangement with two people.

Finally, the number of derangements for selecting M people from N people is given by C(N,M) * D(M).

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
#include <iostream>
using namespace std;

/**
 * @brief the derangement function uses the recursive formula to calculate the number of derangements of N elements and also need to consider C(n,m)
 * 
 * @param n 
 * @param m 
 */
void fooIteration(int n,int m){
    int dp[21][2]={{1,0},{1,0},{2,1},{6,2}};
    for(int i=4;i<21;i++){
        dp[i][0]=i*dp[i-1][0];
        dp[i][1]=(i-1)*(dp[i-1][1]+dp[i-2][1]);
    }
    cout<<dp[n][0]/(dp[m][0]*dp[n-m][0])*dp[m][1]<<endl;
}

int main(){
    int n;
    while(cin>>n,n!=0){
        for(int i=0;i<n;i++){
            int a,b;
            cin>>a>>b;
            fooIteration(a,b);
        }
    }
}

2050 拆线分割平面

Before we start to solve this problem, let’s see another problem

How many pieces will get at most divided by N intersecting straight lines

When adding the n-th straight line, it can intersect with the previous n-1 straight lines at most, because if it is parallel to the n-1th straight line, it will not create new regions. Therefore, the n-th straight line can create at most n-1 new intersection points.

Meanwhile, the nth straight line divides the plane into n+1 regions. Thus, the total number of regions is the sum of the total intersection points created by the first n-1 straight lines and the new regions created by the n-th straight line.

Specifically:

  1. The total number of intersection points created by the first n-1 straight lines =
    1. 1 + 2 + 3 + … + (n-1) = n*(n-1)/2
  2. The new regions created by the n-th straight line = n+1

Therefore, the total number of regions is:

(n*(n-1)/2) + (n+1) = (n^2 + n + 2)/2

So, when adding the n-th straight line, the maximum number of regions that the plane can be divided into is (n^2 + n + 2)/2.

2053 开关灯

There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).

Each test case contains only a number n ( 0< n<= 10^5) in a line.

Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ).

Take n=16 for an examples, because it’s approximations are 1,2,4,8,16 so the 16th light will be adjusted on the 1st, 2nd, 4th, 8th and 16th operations.There are a total of 5 operations and since it starts as off status, it will end up being on.

The final status of the light depends on it’s parity of the number of approximations , if the number of divisors of n is odd, then output 1 , otherwise output 0;

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
#include<iostream>

using namespace std;

/**
 * @brief Check if the number of divisors of n is odd. If it is, output 1; otherwise, output 0.
 * 
 * @param n 
 */
void countApporximation(int n){
    int count=0;
    for(int i=1;i<=n;i++){
        if(n%i==0)
            count++;
    }
    int res=count&1;
    cout<<res<<endl;
}

int main(){
    int n;
    while(cin>>n,n!=0){
        countApporximation(n);
    }
}

To think further, if we consider n=B*A, we can observe that the number of divisors of n will be even if all the B not equals to A, it means the light end up being off.

On other hand, only the number of divisors is odd can turn on the light! Therefore, we only need to check whether the input number is a perfect square number

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @brief  check whether a number is perfect squart number. If it is, return 1,otherwise return 0.
 * 
 * @param n 
 * @return int 
 */
int checkPerfectSquareNum(int n){
    if(int(sqrt(n))*int(sqrt(n))==n){
        return 1;
    }
    return 0;
}

2054 A=B_Plus

Give you two numbers A and B, if A is equal to B, you should print “YES”, or print “NO”.

Notice that the number is not decimal or double variable, it could be a string variable or a long char type.

So we should deal with it a bit before we compare them

  1. Remote redundant zeros befrore the real effctive number, like 00001.2=1.2
  2. Remote redundant zeros at the end of the string, like 1.0010000=1.001
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<sstream>
#include<string>
using namespace std;

void RemoteZeroBeforeRealNum(string &str){
    int len=str.length();
    int i;
    //i is initiazlied to 0, i will never change because we only need to check whether the first character is '0'.
    for(i=0;i<len;){
        if(str[i]=='0'){
            str.erase(i,1);
            //The length of the string is reduced by 1 after deleting a character, 
            //and thus the position of the next character needs to be recalculated.
            len--;
        }else{
            break;
        }
    }
    if(str[i]=='.')
        str.insert(i,"0");
}

void RemoteRedundantZeroAfterPoint(string &str){
    int pos=str.find('.');
    int len=str.length();
    int i;
    //i is initialized  to len-1, but we need to reduced i by 1 each time after deleting a character.
    for(i=len-1;i>pos;i--){
        if(str[i]=='0'){
            str.erase(i,1);
            len--;
        }else {
            break;
        }
    }
    //If the last character is '.', delete it.
    if(i==pos){
        str.erase(i,1);
    }
}

void CompareTwoStringNum(string A,string B){

}

int main(){
    string str;
    getline(cin,str);
    stringstream ss(str);
    string A,B;
    ss>>A>>B;
    RemoteZeroBeforeRealNum(A);
    RemoteZeroBeforeRealNum(B);
    RemoteRedundantZeroAfterPoint(A);
    RemoteRedundantZeroAfterPoint(B);
    cout<<A<<" "<<B<<endl;
    if(A==B)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    
}

string.find()

In C++, the string class provides the find function to find the position of a substring in the original string. The find function has multiple overloaded versions, among which the commonly used versions are as follows:

1
2
3
4
copy codesize_t find(const string& str, size_t pos = 0) const; // Find the first occurrence of the string 'str' in the original string, starting the search from position 'pos
size_t find(const char* s, size_t pos = 0) const; // Find the first occurrence of the char array s in the original string, starting the search from position 'pos
size_t find(const char* s, size_t pos, size_t n) const; // Find the first occurrence of first n letter of the string 'str' in the original string, starting the search from position 'pos
size_t find(char c, size_t pos = 0) const; // Find the first occurrence of the char c in the original string, starting the search from position 'pos

The return value of all four versions above is of type size_t, which indicates the starting position of the found substring in the original string (if not found, it returns string::npos, which is -1).

2055 AEasyProblem

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
#include<iostream>
#include<sstream>
#include<string>
#include<cctype>
using namespace std;

/**
 * @brief If a is uppercase, b will add the ASCII value of a minus 65 plus 1;
 * If a is lowercase , b will substract the Ascii value of a minus 97 plus 1.
 * 
 * @param a 
 * @param b 
 */
void foo(char a,int b){
    if(isupper(a)){
        b=b+a-'A'+1;
    }else{
        b=b+(a-'a'+1)*(-1);
    }
    cout<<b<<endl;
}
int main(){
    int n;
    while(cin>>n,n!=0){
        for(int i=0;i<n;i++){
            char a;
            int b;
            cin>>a>>b;
            foo(a,b);
        }
    }
}

2056 计算重合部分的矩阵面积

Calculate the area of the intersection of two rectangles.

pic

We consider the intersection is a rectangle (sure it is).Therefore, we require the coordinates of two points on the diagonals of the rectangle.

Then we get the formula as following.

X=max(x1,x3)=max(2,3)=3

Y=max(y1,y3)=max(1,2)=2

X’=min(x2,x4)=min(5,5)=5

Y’=min(y2,y4)=min(5,7)=5

(X,Y)=(3,2) (X’,Y’)=(5,5)

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
#include<iostream>
#include<iomanip>
using namespace std;

/**
 * @brief Calculate the area of the intersection of two rectangles.
 * 
 * @param x 
 * @param y 
 * @return double 
 */
double calculateArea(double *x,double *y){
    double x1,y1,x2,y2;
    x1=max(x[0],x[2]);
    y1=max(y[0],y[2]);
    x2=min(x[1],x[3]);
    y2=min(y[1],y[3]);
    double s=(x2-x1)*(y2-y1);
    return s;
    
}

int main(){
    while(1){
        double x[4]={0};
        double y[4]={0};
        for(int i=0;i<4;i++){
            cin>>x[i]>>y[i];
        }
        cout<<fixed<<setprecision(2)<<calculateArea(x,y)<<endl;
    }

}

2058 *找到连续子段和为M

Given a sequence 1,2,3,…N, the task is to calculate all the possible sub-sequences that the sum of the sub-sequence is M

  1. Define two pointers as start and end ,initiazlied as 0 and 1 respectively, and define an array range from 1 to n;
  2. We create a decimal variable sum initialized as dp[0];
  3. While end lower than n, excute the loop until end equals to n;
  4. if sum<m, then sum+=dp[end], and move end to next num , end++
  5. if sum=m, output the result and remember to move end to the next num to search next sub-sequence , sum+=dp[end]
  6. if sum>m, sum-=dp[start], meve start to next num , start++

For example, Let’s consider N=20, M=10. dp[20] from 1 to 20, sum=1, start=0, end=1;

20 10
sum<M: excute: sum+2 end 1
sum 3 start 0 end 2
sum<M: excute: sum+3 end 2
sum 6 start 0 end 3
sum<M: excute: sum+4 end 3
sum 10 start 0 end 4
[1,4]
sum=M: sum 15 start 0 end 5
sum>M: excute: sum-1
sum 14 start 1 end 5
sum>M: excute: sum-2
sum 12 start 2 end 5
sum>M: excute: sum-3
sum 9 start 3 end 5
sum<M: excute: sum+6 end 5
sum 15 start 3 end 6
sum>M: excute: sum-4
sum 11 start 4 end 6
sum>M: excute: sum-5
sum 6 start 5 end 6
sum<M: excute: sum+7 end 6
sum 13 start 5 end 7
sum>M: excute: sum-6
sum 7 start 6 end 7
sum<M: excute: sum+8 end 7
sum 15 start 6 end 8
sum>M: excute: sum-7
sum 8 start 7 end 8
sum<M: excute: sum+9 end 8
sum 17 start 7 end 9
sum>M: excute: sum-8
sum 9 start 8 end 9
sum<M: excute: sum+10 end 9
sum 19 start 8 end 10
sum>M: excute: sum-9
sum 10 start 9 end 10
[10,10]
sum=M: sum 21 start 9 end 11
sum>M: excute: sum-10
sum 11 start 10 end 11
sum>M: excute: sum-11
sum 0 start 11 end 11

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
#include<iostream>
#include<sstream>
using namespace std;

/**
 * @brief Find all possible sub-sequences whose sum is m.
 * 
 * @param n 
 * @param m 
 */
void FindSubarray(int n,int m){
    int *dp=new int[n];
    for(int i=0;i<n;i++){
        dp[i]=i+1;
    }
    int sum=dp[0];
    //Two pointers
    int start=0,end=1;
    //if dp[start]>m stop searching.
    while(end<n&&dp[start]<=m){
        while(sum<m){
            sum+=dp[end++];
        }
        if(sum==m){
            cout<<"["<<dp[start]<<","<<dp[end-1]<<"]"<<endl;
            //Start to search the next subarray.
            sum+=dp[end++];
        }
        //sum>m, start to move the start pointer, and sum will be smaller, until sum
        while(sum>m){
            sum-=dp[start++]; 
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m,n!=0&&m!=0){
        FindSubarray(n,m);
    }
}

2059 *动态规划2

Look at 2037

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>

using namespace std;

/**
 * @brief 
 * 
 * @param n 
 * @param Distance 
 * @param vt2 
 * @param vt1 
 * @param c 
 * @param t 
 * @param vr 
 * @param p 
 */
void foo(int n,int Distance, int vt2,int vt1,int c,int t,int vr,int *p){
    double *dp=new double[n+2];
    dp[0]=0;
    for(int i=1;i<n+2;i++){
        double minT=9999999;
        for(int j=0;j<i;j++){
            int len=p[i]-p[j];
            double time;
            //if len is longer than c, it means we need to consider two parts.
            if(len>c){
                //the distance of c will at speed vt1, the rest will at speed vt2
                time=1.0*(len-c)/vt2+1.0*c/vt1;
            }else{
                time=1.0*c/vt1;
            }
            //part of dp
            time+=dp[j];
            //Plus the time of charging
            if(j)
                time+=t;
            if(minT>time)
                minT=time;
        }
        dp[i]=minT;
    }
    if(Distance*1.0/vr>dp[n+1])
        cout<<"Good job,rabbit!"<<endl;
    else
        cout<<"What a pity rabbit!"<<endl;
}

int main(){
    int Distance;
    while(cin>>Distance,Distance!=0){
        int n,c,t,vr,vt1,vt2;
        cin>>n>>c>>t>>vr>>vt1>>vt2;
        int *p=new int[n+2];
        p[0]=0;
        p[n+1]=Distance;
        for(int i=1;i<=n;i++){
            cin>>p[i];
        }
        foo(n,Distance,vt2,vt1,c,t,vr,p);
    }
}

LEECODE

二分查找

704. 二分查找

https://leetcode.cn/problems/binary-search/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid;
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }

35. 搜索插入位置

https://leetcode.cn/problems/search-insert-position/

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Please use an algorithm with time complexity O(log n).

Input: nums = [1,3,5,6], target = 5
Output: 2

Input:: nums = [1,3,5,6], target = 2
Output: 1

Input:: nums = [1,3,5,6], target = 7
Output: 4

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
#include<iostream>
#include<vector>


//35. 搜索插入位置
using namespace std;
/**
 * @brief Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
 * 
 * @param nums 
 * @param target 
 * @return int 
 */
int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        int mid;
        if(target>nums[right]){
            return right+1;
        }
        if(target<nums[0]){
            return 0;
        }
   		//Find the first element that is greater than or equal to target.
        while(left<right){
            mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
}

int main(){
    vector<int> nums={1,3,5,6};
    int target=5;
    cout<<searchInsert(nums,target)<<endl;
    return 0;
}

278. 第一个错误的版本

https://leetcode.cn/problems/first-bad-version/

You are a product manager and you are currently leading a team to develop a new product. Unfortunately, the latest version of your product failed quality testing. Since each version is developed based on the previous version, all versions after the wrong version are wrong.

Suppose you have n versions [1, 2, …, n] and you want to find the first wrong version that causes all subsequent versions to fail.

You can call the bool isBadVersion(version) interface to determine whether the version number version has an error in the unit test. Implement a function to find the first wrong version. You should minimize the number of calls to the API.

Input：n = 5, bad = 4
Output：4
Elaboration：
Call isBadVersion(3) -> false
Call isBadVersion(5) -> true
Call isBadVersion(4) -> true
Therefore，4 is the first bad version。

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
#include<iostream>
#include<vector>
using namespace std;

//Fake function
int isBadVersion(int version){
    return true;
}

int firstBadVersion(int n) {
    int left=1,right=n;
    int mid;
    //Find the first element that is greater than or equals to the target.
    while(left<right){
        //avoid overflow
        mid=left+(right-left)/2;
        if(isBadVersion(mid)==true){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return right;
}

int main(){
    int n=5;
    cout<<firstBadVersion(n)<<endl;
    return 0;
}

双指针

977. 有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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
#include<iostream>
#include<vector>
using namespace std;

/**
 * @brief Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.
 * 
 * @param nums 
 * @return vector<int> 
 */
vector<int> sortedSquares(vector<int>& nums) {
    int len=nums.size();
    int piv=0;
    for(piv=0;piv<len;piv++){
        if(nums[piv]>=0)
            break;
    }
    int p1=piv-1,p2=piv;
    vector<int>temp;
    while(p1>=0&&p2<len){
        if(nums[p1]*nums[p1]<nums[p2]*nums[p2]){
            temp.push_back(nums[p1]*nums[p1]);
            p1--;
        }else{
            temp.push_back(nums[p2]*nums[p2]);
            p2++;
        }
    }
    while(p1>=0){
        temp.push_back(nums[p1]*nums[p1]);
        p1--;
    }
    while(p2<len){
        temp.push_back(nums[p2]*nums[p2]);
        p2++;
    }
    return temp;
}

189.轮转数组

https://leetcode.cn/problems/rotate-array/

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

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
#include<iostream>
#include<vector>
using namespace std;

/**
 * @brief Given an array, rotate the array to the right by k steps, where k is non-negative.
 * 
 * @param nums 
 * @param start 
 * @param end 
 */
void reversePart(vector<int>& nums, int start,int end){
    //Two pointers
    while (start < end) {
        int temp=nums[start];
        nums[start]=nums[end];
        nums[end]=temp;
        start += 1;
        end -= 1;
    }
}

void rotate(vector<int>& nums, int k) {
    int len=nums.size();
    k%=len;
    if(len==1){
        return;
    }
    reversePart(nums,0,len-1);
    reversePart(nums,0,k-1);
    reversePart(nums,k,len-1);
}

283. 移动零

https://leetcode.cn/problems/move-zeroes/

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:

Input: nums = [0]
Output: [0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void moveZeroes(vector<int>& nums) {
    int pointZero,pointNahZero;
    pointZero=pointNahZero=0;
    int len=nums.size();
    //pointZero will only point to zero, pointNahZero will only point a positive num.
    while(pointNahZero<len){
        //When the two pointers point the same number, it will exchange too, then the pointZero will move to next number.
        if(nums[pointNahZero]){
            swap(nums[pointNahZero],nums[pointZero]);
            pointZero++;
        }
        pointNahZero++;
    }
}

167. 两数之和 II - 输入有序数组

https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

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
#include<iostream>
#include<vector>

using namespace std;

/**
 * @brief Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
 * 
 * @param nums 
 * @param target 
 * @return vector<int> 
 */
vector<int> twoSum(vector<int>& nums, int target) {
    int left=0;
    int right=nums.size()-1;
    int sum;
    vector<int>ans;
    // Find the element that is equals to the target
    while(left<right){
        sum=nums[left]+nums[right];
        if(sum>target){
            right-=1;
        }else if(sum<target){
            left+=1;
        }else{
            ans.push_back(left+1);
            ans.push_back(right+1);
            break;
        }
    }
    return ans;
}

344. 反转字符串

https://leetcode.cn/problems/reverse-string/

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = [“h”,“e”,“l”,“l”,“o”]
Output: [“o”,“l”,“l”,“e”,“h”]
Example 2:

Input: s = [“H”,“a”,“n”,“n”,“a”,“h”]
Output: [“h”,“a”,“n”,“n”,“a”,“H”]

1
2
3
4
5
6
7
8
9
void reverseString(vector<char>& s) {
        int left=0;
        int right=s.size()-1;
        while(left<right){
            swap(s[left],s[right]);
            left++;
            right--;
        }
    }

557. 反转字符串中的单词 III

https://leetcode.cn/problems/reverse-words-in-a-string-iii/

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Example 2:

Input: s = “God Ding”
Output: “doG gniD”

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
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

/**
 * @brief Given an input string, reverse the string word by word.
 * 
 * @param s 
 * @return string 
 */
string reverseWords(string s) {
    int len=s.length();
    int start=0;
    int end=0;
    while(end<len){
        while(s[end]!=' '&&end<len){
            end++;
        }
        int interEnd=end-1;
        //Reverse the word
        while(start<interEnd){
            swap(s[start],s[interEnd]);
            start++;
            interEnd--;
        }
        start=end+1;
        //Skip the space
        end++;
    }
    return s;
}

int main(){
    string s;
    getline(cin,s);
    cout<<reverseWords(s)<<endl;
}

876. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* middleNode(ListNode* head) {
    ListNode *fast,*slow;
    fast=slow=head;
    while(fast->next!=NULL){
        slow=slow->next;
        fast=fast->next;
        //Skip one more node.
        if(fast->next!=NULL){
            fast=fast->next;
        }
    }
    return slow;
}

19. 删除链表的倒数第 N 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:

Input: head = [1], n = 1
Output: []
Example 3:

Input: head = [1,2], n = 1
Output: [1]

  1. Define a node fast, slow and dummy, fast is initialized by head , slow and dummy will be initialized by the node before head, which is a fake head and don’t load any data .
  2. The node fast will move to next node for n times to make sure the fast is n-nodes ahead of slow
  3. Then let fast and slow move to their respective next node together 【fast=fast->next;slow=slow->next;】
  4. Skip the node that should be deleted. 【slow->next=slow->next->next;】
  5. return dummy's next node. 【To make sure we are able to delete the head node】

You have to consider the situation that the node-head is the n-th one like [1], n=1 which will return [], that’s reason why we return dummy's next node instead of returning head directly, otherwise, we will get [1] instead of []

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast,*slow,*dummy;
        dummy=slow=new ListNode(0, head);
        fast=head;
        for(int i=0;i<n;i++){
            fast=fast->next;
        }
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        
        ListNode *ans=dummy->next;
        delete dummy;
        return ans;
    }
};

3. 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:

Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:

Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Let’s take the string in Example 1: abcabcbb
Take abcabcbb as an example, find the longest substring starting from each character and not containing repeated characters, then the longest string among them is the answer. For the string in Example 1, we list these results, where the selected characters and the longest string are indicated in brackets:

Start with
(a)bcabcbb End with (abc)abcbb
Start with
a(b)cabcbb End with a(bca)bcbb
Start with
ab©abcbb End with ab(cab)cbb
Start with
abc(a)bcbb End with abc(abc)bb

Solution

In this solution, the purpose of hash[d]-- is to decrease the occurrence of the character pointed by the left pointer in the hash table by 1, indicating that the character is no longer in the current window. In the sliding window, as the left pointer moves one position each time, the character it points to needs to be removed from the current window.

For example, in the string "abcbac", when the left pointer points to the second character “b”, the occurrences of characters “a” and “b” are recorded in the hash table, and the occurrence of character “b” is 2, indicating that there are duplicate characters in the current window. Therefore, the left pointer needs to move to the right, removing the first “b” from the window. At this point, the operation hash['b']-- is performed, decreasing the occurrence of character “b” by 1. The value corresponding to the element with the key “b” in the hash table becomes 1, indicating that the current window contains only one character “b”.

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int len=s.length();
        if(len==0)
            return 0;
        if(len==1)
            return 1;
        int start,end;
        start=end=0;
        int res=0;
        while(end<len){
            //Record new char;
            hash[s[end]]++;
            //If the new char is redunant then remove the leftest char.
            while(hash[s[end]]>1){
                hash[s[start]]--;
                start++;
            }
            //Counting the length of the str
            res=res<(end-start+1)?(end-start+1):res;
            end++;
        }
        return res;
    }
};

567. 字符串的排列

https://leetcode.cn/problems/permutation-in-string/

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:

Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:

Input: s1 = “ab”, s2 = “eidboaoo”
Output: false

  1. We create map<char,int> need to record the count of letter appears in s1, and create map<char,int> window to record the count of letter appears in the sliding window
  2. Start to search each letter(as variable ch) in s2, if the letter is in s1(judge by need.count()), then we should update the table window, and add one in window[ch]. If window[ch] is equals to need[ch] ,then we need to inhance the possibility of success by adding one in valid.
  3. If the length of the sliding window is greater than the length of s1, we need to deal with result and remove some illegal letter from the window.
  4. If valid is equals to need.size(), which means we successfully match all letters from s1 in s2.
  5. If not, then we need to remove some illegal letters if they are in s1 too, we need to reduce valid by one if window[d]==need[d] , for example: If we consider s2=eidbxaaoo , s1=abb, there is a “x” between “b” and “aa” so we need to remove “b” from the window table, cuz it’s 100% illegal.
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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char,int>need,window;
        for(char ch:s1){
            need[ch]+=1;
        }
        int start=0;
        int end=0;
        int len=s2.length();
        int valid=0;
        while(end<len){
            char ch=s2[end++];
            //Enter the if-condition until the ch is in the s1.
            if(need.count(ch)){
                //The window table used to record the count of the letter in s2
                window[ch]++;
                //if the counts is the same, it means it's a one of the s1.
                if(window[ch]==need[ch])
                    valid++;
            }
            //If
            while((end-start)>=s1.length()){
                //Need.size may not equals to s1.size()
                if(valid==need.size())
                    return 1;
                char d=s2[start++];
                if(need.count(d)){
                    //s2=eidbxaaoo , s1=abb, there is a "x" between "b" and "aa" so we need to remove "b" from the window table, it's 100% illegal.
                    if(window[d]==need[d]){
                        valid--;
                    }
                    //Remote the letter from the slid window
                    window[d]--;
                }
            }
        }
        return 0;
    }
};

深度/广度遍历

733. 图像渲染

https://leetcode.cn/problems/flood-fill/

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Board

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
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int m=image.size();
    int n=image[0].size();
    //Four directions
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    //Record the currentColor
    int currentColor=image[sr][sc];
    if(image[sr][sc]==color){
        return image;
    }
    //Create a queue variable and push <sr,sc> into it.
    queue<pair<int,int>> que;
    //PUSH AND PAINT
    que.emplace(sr,sc);
    image[sr][sc]=color;
    //Classic BFS code
    while(!que.empty()){
        //Pop out the head from queue.
        int x=que.front().first;
        int y=que.front().second;
        que.pop();
        //Search four directions.
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&image[nx][ny]==currentColor){
                que.emplace(nx,ny);
                image[nx][ny]=color;
            }
        }
    }
    return image;
}

Deep

As you can see, there almost no difference between dfs and bfs codes using queue and stack respectively, but the logic is a bit different.

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
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int m=image.size();
        int n=image[0].size();
        //Four directions
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        //Record the currentColor
        int currentColor=image[sr][sc];
        if(image[sr][sc]==color){
            return image;
        }
        //Create a stack variable and push <sr,sc> into it.
        stack<pair<int,int>> sta;
        //PUSH AND PAINT
        sta.push(make_pair(sr,sc));
        image[sr][sc]=color;
        //Class DFS code
        while(!sta.empty()){
            //Pop out the top from stack.
            int x=sta.top().first;
            int y=sta.top().second;
            sta.pop();
            //Search four directions.
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&image[nx][ny]==currentColor){
                    sta.push(make_pair(nx,ny));
                    image[nx][ny]=color;
                }
            }
        }
        return image;
    }
};

695. 岛屿的最大面积

https://leetcode.cn/problems/max-area-of-island/

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

/**
 * @brief Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
 * 
 * @param grid 
 * @return int 
 */
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int m=grid.size();
    int n=grid[0].size();
    const int dx[4]={0,0,1,-1};
    const int dy[4]={1,-1,0,0};
    if(m==0||n==0)
        return 0;
    //If i,j is searched then skip it when see it next time.
    int **mark=new int*[m];
    for(int i=0;i<m;i++){
        mark[i]=new int[n];
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            mark[i][j]=0;
        }
    }
    //Define a que to do BFS
    queue<pair<int,int>> que;
    int MaxSum=0;
    //Start from every point
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            //If the point is land and haven't been searched.
            if(grid[i][j]!=0&&mark[i][j]==0){
                int sum=1;
                que.emplace(i,j);
                mark[i][j]=1;
                //Classic BFS code
                while(!que.empty()){
                    int x=que.front().first;
                    int y=que.front().second;
                    que.pop();
                    for(int t=0;t<4;t++){
                        int nx=x+dx[t];
                        int ny=y+dy[t];
                        if(nx<m&&ny<n&&nx>=0&&ny>=0&&grid[nx][ny]!=0&&mark[nx][ny]==0){
                            sum++;
                            que.emplace(nx,ny);
                            mark[nx][ny]=1;
                        }
                    }
                }
                MaxSum=MaxSum<sum?sum:MaxSum;
            }
        }
    }
    return MaxSum;
}

617. 合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/

BFS

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
/**
 * 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:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==NULL){
            return root2;
        }
        if(root2==NULL){
            return root1;
        }
        TreeNode *merge=new TreeNode(root1->val+root2->val);
        merge->left=mergeTrees(root1->left,root2->left);
        merge->right=mergeTrees(root1->right,root2->right);
        return merge;
    }
};

DFS

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 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:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        queue<TreeNode> que2;
        queue<TreeNode> que1;
        queue<TreeNode> que3;
        que1.emplace(root1);
        que2.emplace(root2);
        while(!que1.empty()&&!que2.empty()){
            TreeNode p2=que2.front();
            TreeNode p1=que1.front();
            que2.pop();
            que1.pop();
            if(p1!=NULL&&p2!=NULL){
                que3.emplace(TreeNode(p1->val+p2->val));
            }else if(p1==NULL){
                que3.emplace(p2);
            }else if(p2==NULL){
                que3.emplace(p1);
            }else{
                que3.emplace(NULL);
            }
        }
        while(!que1.empty()){
            TreeNode p=que1.front();
            que1.pop();
            que3.emplace(p);
        }
        while(!que2.empty()){
            TreeNode p=que2.front();
            que2.pop();
            que3.emplace(p);
        }
        TreeNode p3=que3.front();
        que3.pop();
        int i=0;
        while(!que3.empty()){
            if(i%2==0){
                p3->left=que3.front();
            }else{
                p3->right=que3.front();
            }
            i++;
            que3.pop();
        }
        return p3;
    }
};

DFS

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
46
47
48
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue.offer(merged);
        queue1.offer(t1);
        queue2.offer(t2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if (left1 != null || left2 != null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else if (left2 != null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }
}

542. 01 矩阵

https://leetcode.cn/problems/01-matrix/

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Start From Zero To One！！！！！

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
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n,m;
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        n=mat.size();
        m=mat[0].size();
        //Define a distance and initialized as INFINITE_MAX;
        vector<vector<int>> distance(n,vector<int>(m,INT_MAX));
        queue<pair<int,int>> que;
        //Add up all Zero point into a queue, and set the distance as 0 for every Zero point.
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]==0){
                    que.emplace(make_pair(i,j));
                    distance[i][j]=0;
                }
            }
        }
        //BFS
        while(!que.empty()){
            //Start from Zero point to One point
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                //Update every One point according to Zero point.
                if(nx>=0&&nx<n&&ny>=0&&ny<m){
                    if(distance[nx][ny]>distance[x][y]+1){
                        distance[nx][ny]=distance[x][y]+1;
                        que.emplace(make_pair(nx,ny));
                    }
                }
            }
        }
        return distance;
    }
};

994. 腐烂的橘子

https://leetcode.cn/problems/rotting-oranges/

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    //Multiple starting sources problem
    int orangesRotting(vector<vector<int>>& grid) {
        int n,m;
        n=grid.size();
        m=grid[0].size();
        int dx[4]={0,0,-1,1};
        int dy[4]={1,-1,0,0};
        //Define a queue to record starting sources
        queue<pair<int,int>> que;
        int freshCount=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //if grid==2, it's a source
                if(grid[i][j]==2){
                    que.emplace(make_pair(i,j));
                }
                //Record the count of fresh oranges
                if(grid[i][j]==1){
                    freshCount++;
                }
            }
        }
        //If there are no any of fresh one, return 0;
        if(freshCount==0){
            return 0;
        }
        //Record the maxstep to fresh oranges;
        int TheMax=0;
        //BFS
        while(!que.empty()){
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){
                    //If reach to a fresh orange, then trans it into rotten one.
                    if(grid[nx][ny]==1){
                        freshCount--;
                        //Increase one step.
                        grid[nx][ny]=grid[x][y]+1;
                        //Update the maxstep to fresh oranges;
                        TheMax=TheMax<grid[nx][ny]?grid[nx][ny]:TheMax;
                        //add a new rotten one into queue.
                        que.emplace(make_pair(nx,ny));
                    }
                }
            }
        }
        //If there still have any of fresh oranges , return -1;
        if(freshCount){
            return -1;
        }
        return TheMax-2;
    }
};

递归/回溯

21. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: list1 = [], list2 = []
Output: []
Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Iteration

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //Make a fake head
        ListNode* res=new ListNode(-1);
        //the p is used to add new nodes to res
        ListNode* p=res;
        while(list1!=nullptr&&list2!=nullptr){
            if(list1->val<=list2->val){
                p->next=list1;
                list1=list1->next;
            }else{
                p->next=list2;
                list2=list2->next;
            }
            p=p->next;
        }
        if(list1!=nullptr){
            p->next=list1;
        }
        if(list2!=nullptr){
            p->next=list2;
        }
        return res->next;
    }
};

Recursion

We can find the miner one and merge it with the rest of elements and the rules as following.

  1. list1[0]+merge(list1[1:],list2) list1[0]<list2[0]
  2. list2[0]+merge(list1,list2[1:]) list1[0]>=list2[0]
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr){
            return list2;
        }
        if(list2==nullptr){
            return list1;
        }
        if(list1->val<=list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

206.反转链表

https://leetcode.cn/problems/reverse-linked-list/

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Iteration

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //preHead is a fake head used to reorder the link.
        ListNode*preHead =new ListNode(-1);
        //res keep still which always point to the first element of preHead.
        ListNode*res=preHead;
        preHead->next=nullptr;
        ListNode*p=head;
        //r is used to back up the p->next for p to recover to p->next
        ListNode*r;
        while(p!=nullptr){
            //back up
            r=p->next;
            p->next=preHead->next;
            //add p to preHead's next one
            preHead->next=p;
            //recovery
            p=r;
        }
        return res->next;
    }
};

77.组合

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Backtrack with pruning

path.size() means the count of elements have been selected by us

(n-i+1) is the count of rest of elements

we need to insure that the path.size() plus (n-i+1) is more than K, otherwise , we can’t meet the condition.

For each loop, i should start at index to avoid add the numbers that have been used.

For each next backtracking , the index will start at (i+1) to make sure there is no duplicate situation like (1,2) and (2,1) cuz we consider them as the same tuple.

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n,int k,int index){
        //Receive result.
        if(path.size()==k){
            result.push_back(path);
            return;
        }
        //Classic backtracking code
        //path.size() means the count of elements have been selected by us, (n-i+1) is the count of rest of elements, we need to insure that the path.size plus the count of the rest of elements is more than K,otherwise , we can't meet the condition.
        for(int i=index;(path.size()+n-i+1)>=k;i++){
            //Add new node
            path.push_back(i);
            //Search for the rest of them. index will start at (i+1)
            backtracking(n,k,i+1);
            //Pop out one num
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
};

216. 组合总和 III

https://leetcode.cn/problems/combination-sum-iii/

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

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 {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int k,int n,int index,int sum){
        //if sum>n return directly
        if(sum>n)
            return;
        //
        if(path.size()==k){
            //Meet the condition
            if(n==sum){
                result.push_back(path);
            }
            return;
        }
        //9 means nums selected from 1 to 9
        for(int i=index;(path.size()+9-i+1)>=k;i++){
            path.push_back(i);
            sum+=i;
            //start at i+1
            backtracking(k,n,i+1,sum);
            path.pop_back();
            sum-=i;
        }

    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1,0);
        return result;
    }
};

动态规划

70. 爬楼梯

Source:https://leetcode.cn/problems/climbing-stairs/

Solution:https://programmercarl.com/0070.爬楼梯.html#思路

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps
    Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step
  1. Define a array dp, dp[i] means the ways to climb to the i level
  2. To reach to i level , we can climb from i-1 or i-2, so the ways to i level equals to the ways to i-1 plus the ways to i-2. dp[i]=dp[i-1]+dp[i-2]
  3. dp[0]=0, dp[1]=1, dp[2]=2
  4. because the i level dependent on i-1 and i-2 , so we traverse from front to rear
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
#include<iostream>
#include<vector>

using namespace std;

class Solution {
private:
    /**
     * @brief This is a utility function to calculate the number of ways to climb stairs
     * 
     * @param dp 
     * @param n 
     */
    void utility(vector<int> &dp,int n){
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
    }

public:
    int climbStairs(int n) {
        if(n==1)return 1;
        if(n==0)return 0;
        vector<int> dp(n+1,0);
        utility(dp,n);
        return dp[n];
    }
};

int main(){
    Solution s;
    int x;
    cin>>x;
    cout<<s.climbStairs(x)<<endl;
}

746. 使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

  • Pay 15 and climb two steps to reach the top.
    The total cost is 15.
    Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

  • Pay 1 and climb two steps to reach index 2.
  • Pay 1 and climb two steps to reach index 4.
  • Pay 1 and climb two steps to reach index 6.
  • Pay 1 and climb one step to reach index 7.
  • Pay 1 and climb two steps to reach index 9.
  • Pay 1 and climb one step to reach the top.
    The total cost is 6.
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
#include<iostream>
#include<vector>

using namespace std;

class Solution {
private:
    int utility(vector<int> &cost,int n){
        //dp means the minimum cost to reach the ith level
        vector<int> dp(n,0);
        //cost menns the cost to climb from ith level to ith+1 level or ith+2 level
        dp[0]=0;
        dp[1]=0;
        //Why i end with n, not n-1? Because we need to calculate the cost of the Top level
        for(int i=2;i<=n;i++){
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        return utility(cost,n);
    }
};

int main(){
    Solution s;
    vector<int> cost={10,15,20};
    cout<<s.minCostClimbingStairs(cost)<<endl;
}

62. 不同路径

https://leetcode.cn/problems/unique-paths/

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28
Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right -> Down -> Down
  2. Down -> Down -> Right
  3. Down -> Right -> Down
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
#include<iostream>
#include<vector>
using namespace std;
class Solution {
private:
    //This is a utility function to calculate the number of unique paths
    int utility(int m,int n){
        //dp means the ways to reach the x,y grid.
        //The first row and the first column are all 1
        vector<int> dp(n,1);
        //This is a compressed version of the DP solution.
        for(int j=1;j<m;j++){
            for(int i=1;i<n;i++){
                //uncompressed version:dp[j][i]=dp[j-1][i]+dp[j][i-1];
                dp[i]=dp[i]+dp[i-1];
            }
        }
        return dp[n-1];
    }
public:
    int uniquePaths(int m, int n) {
        return utility(m,n);
    }
};

int main(){
    Solution s;
    int m,n;
    cin>>m>>n;
    cout<<s.uniquePaths(m,n)<<endl;
}

63. 不同路径 II

https://leetcode.cn/problems/unique-paths-ii/

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

When we initialize the first row and col at dp, we should stop initialize the rest of elements in the row or col when we meet a obstacle.

And when we transerve the grid, if there’s a obstacle in [i][j], then we should set dp[i][j] as zero.

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
#include<iostream>
#include<vector>
using namespace std;
class Solution {
private:
    int utility(vector<vector<int>>& obstacleGrid,int m,int n){
        if(obstacleGrid[m-1][n-1]==1||obstacleGrid[0][0]==1)return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        //Trick: when we initialize the first row and col, if we meet obstacle we should stop initialize the rest of elements in the row or col
        //And this is the biggest difference between normal one
        for(int i=0;i<n&&obstacleGrid[0][i]!=1;i++){
            dp[0][i]=1;
        }
        for(int i=0;i<m&&obstacleGrid[i][0]!=1;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]!=1){
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }else{
                    //if there is a obstacle then we set dp[i][j] as zero it means we can't pass here.
                    dp[i][j]=0;
                }
            }
        }
        return dp[m-1][n-1];
    }
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        return utility(obstacleGrid,obstacleGrid.size(),obstacleGrid[0].size());
    }
};

int main(){
    Solution s;
    vector<vector<int>> obstacleGrid={{0,0,0},{0,1,0},{0,0,0}};
    cout<<s.uniquePathsWithObstacles(obstacleGrid)<<endl;
}

0-1背包

dp[i][j] means the biggest value that we select a any count of items from item_0 to item_i and put them into a package whose capacity is j

if we don’t select item_i, then the maximum value of this package is dp[i-1][j]

if we do select item_i, then the maximum value of this package is value[i]+dp[i-1][j-weight[i]], which means we reserve some space(weight[i]) for item_i and we will find the biggest value(dp[i-1][j-weight[i]]) in such a condition , then we add the value of item_i with that value

In a short,

If we don’t select item_i, dp[i][j]=dp[i-1][j]

If we select item_i, dp[i][j]=dp[i-1][j-weight[i]]+value[i]

Then we should select the maximum one of the two value max( dp[i-1][j],dp[i-1][j-weight[i]]+value[i] ), it’s bit of long.

Weight Value
Item1 1 15
Item2 3 20
Item3 4 30

DP

0 1 2 3 4 5
Item1 0 15 15 15 15 15
Item2 0 15 15 20 35 35
Item3 0 15 15 20 35 45 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Traverse items first ,however we also can traverse capacity first
// i start from 1 beacuse we have set dp[0][] we can skip item_1
for(int i=1;i<items;i++){
    //j means the j capacity 
	for(int j=0;j<cap;j++){
        //if j>=weight[i] which means the package can afford the item_i
        if(j>=weight[i]){
            //then we need to decide whether we should add item_i into package.
            dp[i][j]=max( dp[i-1][j],dp[i-1][j-weight[i]]+value[i] );
        }else{
            dp[i][j]=dp[i-1][j];
        }
    }
}

We also can compress dp into one-dimension

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

dp[j] is still mean the maximum value in j capacity, i means the item_i

Here’s the code,

  1. why we traverse from rear to front?

    Once we traverse in positive order, the item_1 will be added multiple times!

    For example：Item_1 :weight[0] = 1，[0] = 15

    If we consider traverse in positive order, here’s the result.

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    dp[2] = dp[2 - weight[0]] + value[0] = 30

    dp[2] will get 30 which means we put item_1 twice!!!

  2. how to initiazlie the dp

    we should initialize dp with all zero , if we set dp as other positive number like 10000, the initiazlied num will cover the new number we calculated in the future. dp[j] - 10000 may will always bigger than dp[j-weight[i]]+value[i] - other new number

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
#include<iostream>
#include<vector>

using namespace std;
void printDP(vector<int> dp){
        for(int i=0;i<dp.size();i++){
            cout<<dp[i]<<" ";
        }
        cout<<endl;
    }
void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int items=3;
    int bagWeight = 4;

    //Initialize dp as all zero , one dimensional array with "cap" elements
    vector<int> dp(bagWeight+1,0);
    for(int i=0;i<items;i++){
        for(int j=bagWeight;j>=weight[i];j--){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
        printDP(dp);
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

416. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

This problem is a bit of special: weight[i]=value[i]

  1. First , we should calculate the sum of array, if sum%2==1, which means it can’t split to two sub-arrays.
  2. If not, the we set variable target=sum/2
  3. Define a array dp, dp[j] means the maximum value in j capacity.
  4. If dp[j]==target we can fill up the j capacity with some numbers whose sum is also j ,that means we can get two sub-arrays.
    1. For example, Input: nums = [1,5,11,5], we consider dp[11]==target=11 as [1,5,5]=target=11 when we grap three number into package with 11 capacity and their sum is also 11.It’s a bit of puzzying, but it’s true.
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
#include<iostream>
#include<vector>
using namespace std;

class Solution {
private:
    void printDP(vector<int> dp){
        for(int i=0;i<dp.size();i++){
            cout<<dp[i]<<" ";
        }
        cout<<endl;
    }
    bool utility(vector<int>& nums,int sum,int n){
        if(sum%2==1){
            return false;
        }
        int target=sum/2;
        //n equals to capacity
        vector<int> dp(target+1,0);
        for(int i=0;i<n;i++){
            for(int j=target;j>=nums[i];j--){
                //The first nums[i] is the weight[i], and the latter one is value[i]
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            // printDP(dp);
        }
        return dp[target]==target?true:false;
    }
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        return utility(nums,sum,n);
    }
};

int main(){
    Solution s;
    vector<int> nums={1,2,3,5};
    cout<<s.canPartition(nums)<<endl;