柳婼の blog – 第258页 – 我不管，反正我最萌～

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;

}

};

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

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

构造性二难推理：(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)).