Code – 第255页

LeetCode 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p != NULL && q != NULL)
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        return p == NULL && q == NULL;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

if(p != NULL && q != NULL)

return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

return p == NULL && q == NULL;

}

};

LeetCode 237. Delete Node in a Linked List

237. Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

分析：因为删除结点本来的步骤是找到当前结点的前一个结点，然后修改前一个结点的 next 指针指向。现在只知道当前要删除的结点，而不知道要删除结点的前一个结点，所以可以通过修改当前要删除结点的值，然后将当前结点指针指向 next 的 next （也就是变成了把后一个结点的值赋给当前结点，然后删除要删除结点的下一个结点），达到删除结点的目的～

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

class Solution {

public:

void deleteNode(ListNode* node) {

node->val = node->next->val;

node->next = node->next->next;

}

};

LeetCode 226. Invert Binary Tree

Invert a binary tree.

4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* p = root;
        if(root == NULL) {
            return NULL;
        }
        
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        
        invertTree(root->left);
        invertTree(root->right);
        
        return p;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

TreeNode* p = root;

if(root == NULL) {

return NULL;

}

TreeNode* temp = root->left;

root->left = root->right;

root->right = temp;

invertTree(root->left);

invertTree(root->right);

return p;

}

};

LeetCode 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        else if(root->left == NULL && root->right == NULL)
            return 1;
        else if(root->left == NULL && root->right != NULL)
            return minDepth(root->right) + 1;
        else if(root->right == NULL && root->left != NULL)
            return minDepth(root->left) + 1;
        else {
            int leftdepth = minDepth(root->left);
            int rightdepth = minDepth(root->right);
            return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;
        }
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int minDepth(TreeNode* root) {

if(root == NULL)

return 0;

else if(root->left == NULL && root->right == NULL)

return 1;

else if(root->left == NULL && root->right != NULL)

return minDepth(root->right) + 1;

else if(root->right == NULL && root->left != NULL)

return minDepth(root->left) + 1;

else {

int leftdepth = minDepth(root->left);

int rightdepth = minDepth(root->right);

return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};

LeetCode 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        if(root->left != NULL && root->right == NULL)
            return maxDepth(root->left) + 1;
        if(root->right != NULL && root->left == NULL)
            return maxDepth(root->right) + 1;
        if(root->right != NULL && root->left != NULL) {
            int leftdepth = maxDepth(root->left);
            int rightdepth = maxDepth(root->right);
            return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
        }
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int maxDepth(TreeNode* root) {

if(root == NULL)

return 0;

if(root->left == NULL && root->right == NULL)

return 1;

if(root->left != NULL && root->right == NULL)

return maxDepth(root->left) + 1;

if(root->right != NULL && root->left == NULL)

return maxDepth(root->right) + 1;

if(root->right != NULL && root->left != NULL) {

int leftdepth = maxDepth(root->left);

int rightdepth = maxDepth(root->right);

return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};

中午闲聊时候的一道题(^0_0^)

给出两个字符串s1和s2，判断 s2里面所有的字母s1都有，有的话返回 true 否则返回 false

#include <iostream>
#include <set>
using namespace std;
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    set<char> t1, t2;
    for(int i = 0; i <= s1.length(); i++) {
        t1.insert(s1[i]);
    }
    for(int i = 0; i <= s2.length(); i++) {
        t2.insert(s2[i]);
    }
    
    set<char>::iterator it1 = t1.begin();
    set<char>::iterator it2 = t2.begin();
    while(it1 != t1.end() && it2 != t2.end()) {
        if(*it1 == *it2) {
            it2++;
        }
        it1++;
    }
    if(it2 != t2.end()) {
        cout << "false";
    } else {
        cout << "true";
    }
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

string s1, s2;

cin >> s1 >> s2;

set<char> t1, t2;

for(int i = 0; i <= s1.length(); i++) {

t1.insert(s1[i]);

}

for(int i = 0; i <= s2.length(); i++) {

t2.insert(s2[i]);

}

set<char>::iterator it1 = t1.begin();

set<char>::iterator it2 = t2.begin();

while(it1 != t1.end() && it2 != t2.end()) {

if(*it1 == *it2) {

it2++;

}

it1++;

}

if(it2 != t2.end()) {

cout << "false";

} else {

cout << "true";

}

return 0;

}

#include <iostream>
using namespace std;
int book[26];
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    for(int i = 0; i < s1.length(); i++) {
        book[s1[i] - 'A'] = 1;
    }
    for(int i = 0; i < s2.length(); i++) {
        if(book[s2[i] - 'A'] == 0) {
            cout << "false";
            return 0;
        }
    }
    cout << "true";
    return 0;
}

#include <iostream>

using namespace std;

int book[26];

int main() {

string s1, s2;

cin >> s1 >> s2;

for(int i = 0; i < s1.length(); i++) {

book[s1[i] - 'A'] = 1;

}

for(int i = 0; i < s2.length(); i++) {

if(book[s2[i] - 'A'] == 0) {

cout << "false";

return 0;

}

cout << "true";

return 0;

}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

double toSum(char*, int*);
int isPrime(int number);
void twertySixPrimeNumber(int *numbers);
double isContain(double d1, double d2);

int main(int arg, char** argvs) {
    char *s1 = "BAZZY";
    char *s2 = "YA";
    int primeNumbers[26] = { 0 };
    twentySixPrimeNumber(primeNumbers);

    double d1 = toSum(s1, primeNumbers);
    double d2 = toSum(s2, primeNumbers);

    double r = isContain(d1, d2);
    printf("s1: %s s2:%s \n", s1, s2);
    if (r) {
        printf("YES");
    } else {
        printf("NO");
    }
}

double isContain(double d1, double d2) {
    double a = d1 / d2;
    double intpart;
    return 0 == modf(a, &intpart) ? 1 : 0;
}

double toSum(char *s1, int *numbers) {
    double sum = 1;
    for(int i = 0; i < strlen(s1) ; i++ ) {
        char c = toupper(s1[i]);
        int temp = c - 65;
        int primeNumber = numbers[temp];
        sum *= primeNumber;
    }
    return sum;
}

void twentySixPrimeNumber(int *numbers) {
    int counter = 26;
    for (int i = 2 ; i < INT_MAX; i++) {
        if (!counter) break;
        if ( isPrime(i) ) {
            numbers[26-counter] = i;
            counter--;
        }
    }
}

int isPrime(int number) {
    if ( 1 == number ||  2 == number || 3 == number) return 1;
    for (int i = 2; i < sqrt(number); i++) {
        if (!(number % i))
          { return 0;}
        else { return 1;}
    }
}

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <limits.h>

double toSum(char*, int*);

int isPrime(int number);

void twertySixPrimeNumber(int *numbers);

double isContain(double d1, double d2);

int main(int arg, char** argvs) {

char *s1 = "BAZZY";

char *s2 = "YA";

int primeNumbers[26] = { 0 };

twentySixPrimeNumber(primeNumbers);

double d1 = toSum(s1, primeNumbers);

double d2 = toSum(s2, primeNumbers);

double r = isContain(d1, d2);

printf("s1: %s s2:%s \n", s1, s2);

if (r) {

printf("YES");

} else {

printf("NO");

}

double isContain(double d1, double d2) {

double a = d1 / d2;

double intpart;

return 0 == modf(a, &intpart) ? 1 : 0;

}

double toSum(char *s1, int *numbers) {

double sum = 1;

for(int i = 0; i < strlen(s1) ; i++ ) {

char c = toupper(s1[i]);

int temp = c - 65;

int primeNumber = numbers[temp];

sum *= primeNumber;

}

return sum;

}

void twentySixPrimeNumber(int *numbers) {

int counter = 26;

for (int i = 2 ; i < INT_MAX; i++) {

if (!counter) break;

if ( isPrime(i) ) {

numbers[26-counter] = i;

counter--;

}

int isPrime(int number) {

if ( 1 == number || 2 == number || 3 == number) return 1;

for (int i = 2; i < sqrt(number); i++) {

if (!(number % i))

{ return 0;}

else { return 1;}

}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int judge(int vector, int vectorS2);
int toVector(char*);

int main(int arg, char** argvs)
{
    char *s1 = "ACBSDEREJASLKDASD";
    char *s2 = "jbd";

    int v1 = toVector(s1);
    int v2 = toVector(s2);
    int v3 = v1 & v2;

    if ( 1 == judge(v3, v2) ) {
        printf("%s is in the %s ", s2, s1);
    } else {
        printf("%s was not in the %s ", s2, s1);
    }
}

int judge(int vector, int vectorS2) {
    if (abs((vector - vectorS2)) < 0.1) {
        return 1;
    } else {
        return vector == 0 ? -1 : 0;
    }
}

int toVector(char *s1) {
    int vector = 0;
    for(int i = 0; i < strlen(s1) ; i++ ) {
        char c = toupper(s1[i]);
        int temp = c - 65;
        vector |= (1 << temp);
    }
    return vector;
}

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

int judge(int vector, int vectorS2);

int toVector(char*);

int main(int arg, char** argvs)

{

char *s1 = "ACBSDEREJASLKDASD";

char *s2 = "jbd";

int v1 = toVector(s1);

int v2 = toVector(s2);

int v3 = v1 & v2;

if ( 1 == judge(v3, v2) ) {

printf("%s is in the %s ", s2, s1);

} else {

printf("%s was not in the %s ", s2, s1);

}

int judge(int vector, int vectorS2) {

if (abs((vector - vectorS2)) < 0.1) {

return 1;

} else {

return vector == 0 ? -1 : 0;

}

int toVector(char *s1) {

int vector = 0;

for(int i = 0; i < strlen(s1) ; i++ ) {

char c = toupper(s1[i]);

int temp = c - 65;

vector |= (1 << temp);

}

return vector;

}