LeetCode OJ – 第43页 – 柳婼の blog

LeetCode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<int> row;
        vector<vector<int>> v;
        queue<TreeNode *> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode *temp;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if(temp->left != NULL) {
                    q.push(temp->left);
                }
                if(temp->right != NULL) {
                    q.push(temp->right);
                }
            }
            v.push_back(row);
            row.clear();
        }
        return v;
    }
};

/**

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

vector<vector<int>> levelOrder(TreeNode* root) {

vector<int> row;

vector<vector<int>> v;

queue<TreeNode *> q;

if(root == NULL)

return v;

q.push(root);

TreeNode *temp;

while(!q.empty()) {

int size = q.size();

while(size--) {

temp = q.front();

q.pop();

row.push_back(temp->val);

if(temp->left != NULL) {

q.push(temp->left);

}

if(temp->right != NULL) {

q.push(temp->right);

}

v.push_back(row);

row.clear();

}

return v;

}

};

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

}

};