发表于 | 分类于

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

解法1： O（N^2) N 是numRows

很基础的题，注意第i层的第j个字符是第i-1层的第j个数和第j-1个数之和就可以了。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if (numRows == 0) {
            return res;
        }
        
        vector<int> x{1};
        res.push_back(x);
        for (int i = 1; i < numRows; ++i) {
            vector<int> temp{1};
            for (int j = 1; j < i; ++j) {
                temp.push_back(res[i - 1][j - 1] + res[i - 1][j]);
            }
            temp.push_back(1);
            res.push_back(temp);
        }
        return res;
    }
};

Java

1

发表于 | 分类于

iven an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

解法1：

16进制每一位表示4个bit的信息，4个bit可以表示0到15的数字，0~9用阿拉伯数字，10~15分别用a ~ f 表示。 那么基本思路就是每一次获取最右边的4位数，然后转化为16进制的数字。然后右移直到数字变为0。
C++
要注意的是C++ 中如果用+ 操作在string 和 string上，只能char或者string，所以如果是int则要转化为char再进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string res = "";
        
        int count = 0;
        while (num != 0 && count < 8) {
            int temp = num & 0xf;
            if (temp < 10) {
                res = to_string(temp) + res;
            } else {
                res = char('a' + temp - 10) + res;
            }
            num = num >> 4;
            ++count;
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

解法1： Stack

用一个stack先预存排序了的treenode， 每次要调用next（）和hasNext（）的时候，只需要对stack操作即可。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> data;
public:
    BSTIterator(TreeNode *root) {
        traverse(root);
    }
    
    void traverse(TreeNode* root) {
        if (!root) {
            return;
        }
        
        if (!root->right && !root->left) {
            data.push(root);
            return;
        }
        
        traverse(root->right);
        data.push(root);
        traverse(root->left);
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !data.empty();
    }
    /** @return the next smallest number */
    int next() {
        TreeNode* temp = data.top();
        int res = temp->val;
        data.pop();
        return res;
    }
};
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Java

1

解法2： Stack， 非递归的in order traversal

实际上不需要预先存储排了序的treenode，而是在寻找最小的值的时候把经过的node用stack存起来。
这里实际上考的是iterative的in order traversal

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> data;
    TreeNode* cur;
public:
    BSTIterator(TreeNode *root) {
        cur = root;
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return cur || !data.empty();
    }
    /** @return the next smallest number */
    int next() {
        while (cur) {
            data.push(cur);
            cur = cur->left;
        }
        TreeNode* temp = data.top();
        int res = temp->val;
        data.pop();
        cur = temp->right;
        return res;
    }
};
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

发表于 | 分类于

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

解法1： O（N) Time + O(1) Space

本题是用了替换的办法。由于提前知道数的范围是从1 ~ n， 那么我们可以试着把每一个数放到该存在的位置，也就是nums[i] = i + 1。 不停的调整每一个位置上的数，直到满足这个条件或者是和要调整的位置上的数相等。
由于每一个数只visit一次，所以complexity是O（N）。
比较tricky的是，在置换两个数的时候要特别小心，我一开始写了

1
2
3
int ex = nums[i];
nums[i] = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];

这是不对的，因为在第二步nums[i]的值已经换过了。
等扫描结束一遍之后，再扫描一遍vector找出位置上的数和位置不同的数。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] - 1 != i) {
                int temp = nums[nums[i] - 1];
                if (temp == nums[i]) {
                    ++i;
                } else {
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            } else {
                ++i;
            }
        }
        
        vector<int> res;
        for (int j = 0; j < nums.size(); ++j) {
            if (nums[j] - 1 != j) {
                res.push_back(j + 1);
            }
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]

解法1： DFS， O（N）

很标准的DFS的题目，要注意的是因为我们需要加入“->”， 所以写法上可以有两种办法。
一个是helper函数的起始string是“”， 那么每次加一个node的时候要判断是否str还是空，是的话不加，不是则加箭头。
另一个是一开始就赋值root->val， 这样每次碰到新node的时候一定需要加上”->”。写法上第二种办法更干净一些。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 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<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (!root) {
            return res;
        }
        helper(root, to_string(root->val), res);
        return res;
    }
    
    void helper(TreeNode* root, string s, vector<string>& res) {
        if (!root) {
            return;
        }
        
        if (!root->left && !root->right) {
            res.push_back(s);
            return;           
        }
        
        if (root->left) {
            helper(root->left, s + "->" + to_string(root->left->val), res);
        }
        
        if (root->right) {
            helper(root->right, s + "->" + to_string(root->right->val), res);
        }
        return;
    }
};

Java

1

发表于 | 分类于

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

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).”

    _______3______
   /              \
___5__          ___1__

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

Show Company Tags
Show Tags
Show Similar Problems

解法1： O（N）

这题和Lowest Common Ancestor of a Binary Search Tree (235)的不同之处在于这里的条件比较松，只知道是一个binary tree。所以当root不是其中一个node的时候，需要同时计算left和right是否有存在的LCA。
那么递归的返回条件就是只要找到root和其中之一相等的时候，就返回当前的node。
这样就会出现种情况，
root 不是两个node的任何一个，

  1. LCA可以存在于left tree中
  2. 也可以存在于right tree中
  3. 也可以是当前的root（因为左右各含一个node）。
    对于1，2两种情况，其中一个tree会返回空值
    对于第三种情况，left和right的值都不同，以此就可以区分而得出我们想要的结果。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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 || root == p || root == q) {
            return root;
        }
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left == NULL) {
            return right;
        }
        
        if (right == NULL) {
            return left;
        }
        
        return root;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        
        if (right == null) {
            return left;
        }
        
        return root;
    }
}

发表于 | 分类于

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

Note: Your solution should be in logarithmic time complexity.

解法1： O（N）， N is number of 5

一道老题了， 主要就是有一个5就会对应一个trailing zero， 题目要求的就变成从1到n有多少个数含有5的因子。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        int count = 0;
        while (n > 0) {
            count += n / 5;
            n = n / 5;
        }
        return count;
    }
};

Java

1

发表于 | 分类于

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

解法1： O（N） Time + O（1） Space

基本思路就是从中间断开，然后把其中一段reverse，再同时遍历判断两个字列是否一致。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
    
        if (!head || !head->next) {
            return true;
        }
        
        int count = 0;
        ListNode* ptr = head;
        while (ptr) {
            ++count;
            ptr = ptr->next;
        }
        
        ptr = head;
        ListNode* preMidPtr = preMid(ptr);
        ListNode* right;
        if (count % 2 == 0) {
            // even number
            right = preMidPtr->next;
            preMidPtr->next = NULL;
            
        } else {
            right = preMidPtr->next->next;
            preMidPtr->next = NULL;
        }
        
        right = reverse(right);
        while (head && right) {
            if (head->val != right->val) {
                return false;
            }
            head = head->next;
            right = right->next;
        }
        return head == NULL && right == NULL;
    }
    
    ListNode* preMid(ListNode* root) {
        ListNode* fast = root->next;
        while (fast && fast->next && fast->next->next) {
            root = root->next;
            fast = fast->next->next;
        }
        return root;
    }
    
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head) {
            ListNode* temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    
    
};

Java

1

发表于 | 分类于

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

解法1： O(logN * logN）

这题参考了Discussion的解法， 用遍历的方法的话，复杂度是O（N）， 但并没有用到complete BT的性质，显然最后的结果是TLE。
在巧妙的解法里，运用complete tree的一个性质是： 如果从一个root出发，最左面和最右面的高度一致的话，那么一定是一个complete tree，他的节点个数是pow(2, k) - 1, k是高度。
这个的运算的复杂度是O(logN).
如果高度不一致的话，那么可以对左右各做一次操作， 也就是一个递归操作。
复杂度分析
T（n) = T(n/2) + clogN = T（n/4) + clogN + c1(logN - 1) = … = T(1) + c[logN + logN - 1 + logN - 2 + … + 1] => O(logN logN)

logN*logN是比N好很多的，比如1024， logN = 10， N = 1024， 显然这个解法的复杂度好很多。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 countNodes(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        int left = 0, right = 0;
        TreeNode* toleft = root, *toright = root;
        while (toleft) {++left; toleft = toleft->left;}
        while (toright) {++right; toright = toright->right;}
        if (left == right) return (1 << left) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

Java

1

发表于 | 分类于

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Show Company Tags
Show Tags
Show Similar Problems

解法1： Two pointers, O(N)

用双指针很简单。要注意的是要跳过非alphanumeric的数字，这里C++里面判断是否是alphanumeric的数字的时候是用的isalnum（x)。 转化为lowercase的时候用的是tolower（x)
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) {
            return true;
        }
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !isalnum(s[i])) { ++i;}
            while (i < j && !isalnum(s[j])) { --j;}
            if (i < j) {
                if (tolower(s[i]) != tolower(s[j])) {
                    return false;
                } else {
                    ++i;
                    --j;
                }
            }
        }
        
        return true;
    }
};

Java

1