LeetCode OJ – 第47页

LeetCode 118. Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

分析：大概是考察用 vector 创建二维数组的应用～

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> v(numRows);
        if(numRows == 0)
            return v;
        for(int i = 0; i < numRows; i++) {
            v[i].resize(i + 1);
        }
        v[0][0] = 1;
        if(numRows == 1)
            return v;
        v[1][0] = 1;
        v[1][1] = 1;
        for(int i = 2; i < numRows; i++) {
            v[i][0] = 1;
            v[i][i] = 1;
        }
        for(int i = 2; i < numRows; i++) {
            for(int j = 1; j < i; j++) {
                v[i][j] = v[i - 1][j - 1] + v[i - 1][j];
            }
        }
        return v;
    }
};

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> v(numRows);

if(numRows == 0)

return v;

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

v[i].resize(i + 1);

}

v[0][0] = 1;

if(numRows == 1)

return v;

v[1][0] = 1;

v[1][1] = 1;

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

v[i][0] = 1;

v[i][i] = 1;

}

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

for(int j = 1; j < i; j++) {

v[i][j] = v[i - 1][j - 1] + v[i - 1][j];

}

return v;

}

};

LeetCode 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

push(x) — Push element x to the back of queue.
pop() — Removes the element from in front of queue.
peek() — Get the front element.
empty() — Return whether the queue is empty.
Notes:
You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

//用两个 stack 实现队列的操作
//压入s1的元素是倒序的，把它们逐个弹出再压入s2就是正序的了
class Queue {
public:
    stack<int> s1, s2;
    // Push element x to the back of queue.
    void push(int x) {
        s1.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        s2.pop();
    }

    // Get the front element.
    int peek(void) {
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        if(s1.empty() && s2.empty()) {
            return true;
        } else {
            return false;
        }
    }
};

//用两个 stack 实现队列的操作

//压入s1的元素是倒序的，把它们逐个弹出再压入s2就是正序的了

class Queue {

public:

stack<int> s1, s2;

// Push element x to the back of queue.

void push(int x) {

s1.push(x);

}

// Removes the element from in front of queue.

void pop(void) {

if(s2.empty()) {

while(!s1.empty()) {

s2.push(s1.top());

s1.pop();

}

s2.pop();

}

// Get the front element.

int peek(void) {

if(s2.empty()) {

while(!s1.empty()) {

s2.push(s1.top());

s1.pop();

}

return s2.top();

}

// Return whether the queue is empty.

bool empty(void) {

if(s1.empty() && s2.empty()) {

return true;

} else {

return false;

}

};

LeetCode 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 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 flag = 1;
    int dfs(TreeNode* root) {
        if(root == NULL)
            return 1;
        int l, r;
        if(root->left == NULL) {
           l = 0;
        } else {
           l = dfs(root->left);
        }
        if(root->right == NULL) {
           r = 0;
        } else {
           r = dfs(root->right);
        }
        if(abs(l-r) >= 2) {
            flag = 0;
        }
        return (l > r ? l : r) + 1;
    }
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return flag;
    }
};

/**

* 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 flag = 1;

int dfs(TreeNode* root) {

if(root == NULL)

return 1;

int l, r;

if(root->left == NULL) {

l = 0;

} else {

l = dfs(root->left);

}

if(root->right == NULL) {

r = 0;

} else {

r = dfs(root->right);

}

if(abs(l-r) >= 2) {

flag = 0;

}

return (l > r ? l : r) + 1;

}

bool isBalanced(TreeNode* root) {

dfs(root);

return flag;

}

};

LeetCode 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return nums[0];
        }
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for(int i = 2; i < n; i++) {
            int temp = dp[i - 2] + nums[i];
            dp[i] = temp > dp[i - 1] ? temp : dp[i - 1];
        }
        return dp[n - 1];
    }
};

class Solution {

public:

int rob(vector<int>& nums) {

int n = nums.size();

if(n == 0) {

return 0;

}

if(n == 1) {

return nums[0];

}

vector<int> dp(n, 0);

dp[0] = nums[0];

dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];

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

int temp = dp[i - 2] + nums[i];

dp[i] = temp > dp[i - 1] ? temp : dp[i - 1];

}

return dp[n - 1];

}

};

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;

}

};