Code – 第252页

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL || p==NULL || q==NULL) 
            return NULL;
        if((p->val >= root->val && q->val <= root ->val) || (p->val <= root->val && q->val >= root->val)) {
            return root;
        }
        if(p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        if(p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
    }
};

/**

* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if(root==NULL || p==NULL || q==NULL)

return NULL;

if((p->val >= root->val && q->val <= root ->val) || (p->val <= root->val && q->val >= root->val)) {

return root;

}

if(p->val > root->val && q->val > root->val) {

return lowestCommonAncestor(root->right, p, q);

}

if(p->val < root->val && q->val < root->val) {

return lowestCommonAncestor(root->left, p, q);

}

};

LeetCode 13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

class Solution {
public:
    int romanToInt(string s) {
        int ans = 0;
        map<char, int> m;
        char c[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        int t[] = {1, 5, 10, 50, 100, 500, 1000};
        for(int i = 0; i < 7; i++) {
            m.insert(pair<char, int> (c[i], t[i]));
        }
        for(int i = 0; i < s.length() - 1; i++) {
            if(m[s[i]] >= m[s[i + 1]]) {
                ans = ans + m[s[i]];
            } else {
                ans = ans - m[s[i]];
            }
        }
        ans = ans + m[s[s.length() - 1]];
        return ans;
    }
};

class Solution {

public:

int romanToInt(string s) {

int ans = 0;

map<char, int> m;

char c[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

int t[] = {1, 5, 10, 50, 100, 500, 1000};

for(int i = 0; i < 7; i++) {

m.insert(pair<char, int> (c[i], t[i]));

}

for(int i = 0; i < s.length() - 1; i++) {

if(m[s[i]] >= m[s[i + 1]]) {

ans = ans + m[s[i]];

} else {

ans = ans - m[s[i]];

}

ans = ans + m[s[s.length() - 1]];

return ans;

}

};

LeetCode 26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the new length.

//才明白这类题目的意思是 返回的是 length 的值 但是会检验你是不是删除了相同的数字使得符合条件。。然后他检验的时候输出的只是0~length-1的值。。后面的是否符合不用管。。。
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) {
            return 0;
        }
        int len = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i - 1]) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }
};

//才明白这类题目的意思是返回的是 length 的值但是会检验你是不是删除了相同的数字使得符合条件。。然后他检验的时候输出的只是0~length-1的值。。后面的是否符合不用管。。。

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

if(nums.size() == 0) {

return 0;

}

int len = 1;

for(int i = 1; i < nums.size(); i++) {

if(nums[i] != nums[i - 1]) {

nums[len++] = nums[i];

}

return len;

}

};

LeetCode 66. Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
            for(int i = digits.size() - 1; i >= 0; i--) {
                if(digits[i] != 9) {
                    digits[i] = digits[i] + 1;
                    return digits;
                } else {
                    digits[i] = 0;
                }
            }
            digits.insert(digits.begin(), 1);
            
            return digits;
            
    }
};

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

for(int i = digits.size() - 1; i >= 0; i--) {

if(digits[i] != 9) {

digits[i] = digits[i] + 1;

return digits;

} else {

digits[i] = 0;

}

digits.insert(digits.begin(), 1);

return digits;

}

};

LeetCode 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *p, *q, *h, *t;
        p = head;
        q = head->next;
        h = q;
        while(p != NULL && q != NULL) {
            p->next = q->next;
            q->next = p;
            t = p;
            if(p->next != NULL) {
                p = p->next;
            } else {
                return h;
            }
            if(p->next != NULL) {
                q = p->next;
                t->next = q;
            } else {
                return h;
            }
        }
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* swapPairs(ListNode* head) {

if(head == NULL || head->next == NULL) {

return head;

}

ListNode *p, *q, *h, *t;

p = head;

q = head->next;

h = q;

while(p != NULL && q != NULL) {

p->next = q->next;

q->next = p;

t = p;

if(p->next != NULL) {

p = p->next;

} else {

return h;

}

if(p->next != NULL) {

q = p->next;

t->next = q;

} else {

return h;

}

};

LeetCode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 != NULL && l2 != NULL) {
            ListNode *p = l1;
            ListNode *q = l2;
            ListNode *t, *h;//t为新链表的连接指针，h为新链表的头指针
            if(p->val > q->val) {
                t = q;
                h = q;
                q = q->next;
            } else {
                t = p;
                h = p;
                p = p->next;
            }
            while(p != NULL && q != NULL) {
                if(p->val > q->val) {
                    t->next = q;
                    t = t->next;
                    q = q->next;
                } else {
                    t->next = p;
                    t = t->next;
                    p = p->next;
                }
                
            }
            while(p != NULL && q == NULL) {
                t->next = p;
                p = p->next;
                t = t->next;
            }
            while(p == NULL && q != NULL) {
                t->next = q;
                q = q->next;
                t = t->next;
            }
            while(p == NULL && q == NULL) {
                return h;
            }
        }
        if(l1 == NULL && l2 != NULL) {
            return l2;
        }
        if(l1 != NULL && l2 == NULL) {
            return l1;
        }
        if(l1 == NULL && l2 == NULL) {
            return NULL;
        }
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

if(l1 != NULL && l2 != NULL) {

ListNode *p = l1;

ListNode *q = l2;

ListNode *t, *h;//t为新链表的连接指针，h为新链表的头指针

if(p->val > q->val) {

t = q;

h = q;

q = q->next;

} else {

t = p;

h = p;

p = p->next;

}

while(p != NULL && q != NULL) {

if(p->val > q->val) {

t->next = q;

t = t->next;

q = q->next;

} else {

t->next = p;

t = t->next;

p = p->next;

}

while(p != NULL && q == NULL) {

t->next = p;

p = p->next;

t = t->next;

}

while(p == NULL && q != NULL) {

t->next = q;

q = q->next;

t = t->next;

}

while(p == NULL && q == NULL) {

return h;

}

if(l1 == NULL && l2 != NULL) {

return l2;

}

if(l1 != NULL && l2 == NULL) {

return l1;

}

if(l1 == NULL && l2 == NULL) {

return NULL;

}

};