liuchuo – 第258页 – 我不管，反正我最萌～

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;

}

};

离散数学：构造性二难推理和破坏性二难定理的解释

二难推理是由两个假言判断和一个有两个选言支持的选言判断做前提构成的推理。假言选言推理的主要形式。其结论可以是直言判断，也可以是选言判断。因为这种推理有时反映左右为难的困境，故称。

构造性二难推理：(A→B)∧(C→D)∧(A∨C)⇒(B∨D)

破坏性二难推理：(A → B)∧(C→D)∧(┐B∨┐D)⇒ (┐A ∨┐C)

举个栗子~：

父亲对他那喜欢到处游说的儿子说，“你不要到处游说。如果你说真话，那么富人恨你；如果你说假话，那么穷人恨你。既然游说只会招致大家恨你，你又何苦为之呢?”在这里，父亲劝儿子就使用了一个二难推理，形式是：

如果你说真话，那么富人恨你；

如果你说假话，那么穷人恨你；

或者你说真话，或者你说假话；

总之，有人恨你。

构造性二难推理的意思就是，构造出一个二难的境地，比如：

A 能推出 B，C 能推出 D，【(A→B)∧(C→D)】

但是 B 和 D 这两个结论都令你很难受，（所以叫二难推理）可是

A 和 C 至少要有一个是成立的，【A∨C】

所以 B 和 D 至少有一个是成立的。【B∨D】

破坏性二难推理的意思是，

A 能推出 B，C 能推出 D，【(A→B)∧(C→D)】

但是 B 和 D 这两个结论都令你很难受，可是

至少你想让其中一个不成立【(┐B∨┐D)】

这样就能说明 A 和 C 至少有一个是不成立的【(┐A ∨┐C)】

还有一个栗子~：

《红楼梦》第六十四回载：贾宝玉从林黛玉的丫环雪雁处得知林黛玉在私室内用瓜果私祭时想：“大约必是七月，因为瓜果之节，家家都上秋季的坟，林妹妹有感于心，所以在私室自己奠宗……”，怎么呢?贾宝玉又想：“但我此刻走去，见她伤感，必极力劝解，又怕她烦恼郁结于心；若不去，又恐她过于伤感，无人劝止，两件皆足致疾……”如果我们将贾宝玉的后一段想法稍加简化，那么，就可构成如下一个简单构成式的二难推理：

如果我去林妹妹处，足以致疾；如果我不去林妹妹处，也足以致疾，

或者我去林妹妹处，或者我不去林妹妹处，

总之，皆足以致疾。

离散数学中输出律的证明：(P∧Q→R)恒等于(P→(Q→R))

证明(P∧Q→R)恒等于(P→(Q→R))：
因为： 蕴含式 A->B 的一条性质是：当且仅当 A 真 B 假时，(A->B) 为假

①：所以： (P∧Q→R)可以表述为：当且仅当 (P∧Q) 真 R 假时，(P∧Q→R)为假
//(P∧Q) 真等价于 P 真且 Q 真
所以：当且仅当(P真，Q真，R假)时，(P∧Q→R)为假

②：所以：(P→(Q→R))可以表述为：当且仅当 P 真 Q->R 假时，(P→(Q→R))为假
//Q->R 假等价于 Q 真且 R 假（根据第一句蕴含式的性质）
所以：当且仅当(P真，Q真，R假)时，(P→(Q→R))为假

所以：(P∧Q→R)恒等于(P→(Q→R)).

中午闲聊时候的一道题(^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;

}