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

LeetCode 101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.

/**
 * 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:
    bool func(TreeNode *left, TreeNode *right) {
        if(left == NULL && right == NULL)
            return true;
        if(left != NULL && right != NULL && left->val == right->val) {
            return func(left->left, right->right) && func(left->right, right->left);
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        return func(root->left, root->right);
    }
};

/**

* 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:

bool func(TreeNode *left, TreeNode *right) {

if(left == NULL && right == NULL)

return true;

if(left != NULL && right != NULL && left->val == right->val) {

return func(left->left, right->right) && func(left->right, right->left);

}

return false;

}

bool isSymmetric(TreeNode* root) {

if(root == NULL)

return true;

return func(root->left, root->right);

}

};

LeetCode 9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        int len = 1;
        while(x / len >= 10) {
            len = len * 10;
        }
        while(x) {
            int left = x / len;
            int right = x % 10;
            if(left != right) {
                return false;
            }
            x = x % len;
            x = x / 10;
            len = len / 100;
        }
        return true;
    }
};

class Solution {

public:

bool isPalindrome(int x) {

if(x < 0)

return false;

int len = 1;

while(x / len >= 10) {

len = len * 10;

}

while(x) {

int left = x / len;

int right = x % 10;

if(left != right) {

return false;

}

x = x % len;

x = x / 10;

len = len / 100;

}

return true;

}

};

LeetCode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

class Solution {
public:
    int uniquePaths(int m, int n) {
        int a[100][100];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0)
                    a[i][j] = 1;
                else
                    a[i][j] = a[i - 1][j] + a[i][j - 1];
            }
        }
        return a[m - 1][n - 1];
    }
};

class Solution {

public:

int uniquePaths(int m, int n) {

int a[100][100];

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

for(int j = 0; j < n; j++) {

if(i == 0 || j == 0)

a[i][j] = 1;

else

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

}

return a[m - 1][n - 1];

}

};

LeetCode 119. Pascal’s Triangle II

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> v(rowIndex + 1);
        v[0] = 1;
        for(int i = 1; i <= rowIndex; i++) {
            v[i] = (long long int)v[i - 1] *(long long int)(rowIndex - i + 1) / i;
        }
        return v;
    }
};

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int> v(rowIndex + 1);

v[0] = 1;

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

v[i] = (long long int)v[i - 1] *(long long int)(rowIndex - i + 1) / i;

}

return v;

}

};

LeetCode 189. Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II

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

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        for(int i = 0; i <= (n - 1 - k) / 2; i++) {
            swap(nums[i], nums[n - 1 - k - i]);
        }
        for(int i = n - k; i <= (n - 1 + n - k) / 2; i++) {
            swap(nums[i], nums[n - 1 + n - k - i]);
        }
        for(int i = 0; i <= (n - 1) / 2; i++) {
            swap(nums[i], nums[n - 1 - i]);
        }
    }
};

class Solution {

public:

void rotate(vector<int>& nums, int k) {

int n = nums.size();

k = k % n;

for(int i = 0; i <= (n - 1 - k) / 2; i++) {

swap(nums[i], nums[n - 1 - k - i]);

}

for(int i = n - k; i <= (n - 1 + n - k) / 2; i++) {

swap(nums[i], nums[n - 1 + n - k - i]);

}

for(int i = 0; i <= (n - 1) / 2; i++) {

swap(nums[i], nums[n - 1 - i]);

}

};

LeetCode 204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

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

Hint:

Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?

Let’s write down all of 12’s factors:

2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12
As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

class Solution {
public:
    int countPrimes(int n) {
        vector<int> book(n, 1);
        for(int i = 2; i * i < n; i++) {
            if(book[i] == 1)
                for(int j = i * i; j < n; j = j + i)
                    book[j] = 0;
        }
        int cnt = 0;
        for(int i = 2; i < n; i++) {
            if(book[i] == 1)
                cnt++;
        }
        return cnt;
    }
};

class Solution {

public:

int countPrimes(int n) {

vector<int> book(n, 1);

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

if(book[i] == 1)

for(int j = i * i; j < n; j = j + i)

book[j] = 0;

}

int cnt = 0;

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

if(book[i] == 1)

cnt++;

}

return cnt;

}

};