Code – 第251页

LeetCode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 1; i = i + 2) {
            if(nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.size() - 1];
    }
};

class Solution {

public:

int singleNumber(vector<int>& nums) {

sort(nums.begin(), nums.end());

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

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

return nums[i];

}

return nums[nums.size() - 1];

}

};

LeetCode 172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

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

题目大意：在logn的时间内找到n！末尾有几个零

//5*2 = 10出现一个0，n*(n-1)*(n-2)...1当中能被5整除的数少于能被2整除的数
//所以能被5整除的5的个数就是0的个数
//比如25！,25 = 5 * 5有两个5，20，15，10，5各含一个5，这六个5分别和2结合相乘就能得到末尾6个0
//所以只要count每个因子中5的个数就行

class Solution {
public:
    int trailingZeroes(int n) {
        int cnt = 0;
        while(n != 0) {
            cnt = cnt + n / 5;
            n = n / 5;
        }
        return cnt;
    }
};

//5*2 = 10出现一个0，n*(n-1)*(n-2)...1当中能被5整除的数少于能被2整除的数

//所以能被5整除的5的个数就是0的个数

//比如25！,25 = 5 * 5有两个5，20，15，10，5各含一个5，这六个5分别和2结合相乘就能得到末尾6个0

//所以只要count每个因子中5的个数就行

class Solution {

public:

int trailingZeroes(int n) {

int cnt = 0;

while(n != 0) {

cnt = cnt + n / 5;

n = n / 5;

}

return cnt;

}

};

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];

}

};