You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.
Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

解法1： O(logN)

一道很典型的binary search的题目，实际上这题是求最大的K， 满足1+2+… + k <= n.
记录1+2+…+k = k*(k+1)/2
那么我们就可以用二分法来求出最大的k。
要注意的是当计算乘积的时候可能会溢出，所以需要用long来存放start和end。
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

class Solution {
public:
    int arrangeCoins(int n) {
        if (n <= 0) {
            return 0;
        }
        long start = 1, end = n;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (mid * (mid + 1) / 2 < n) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (end * (end + 1) / 2 <= n) {
            return (int)end;
        }
        return (int)start;
    }
};

Java

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 int arrangeCoins(int n) {
        if (n <= 0) return 0;
        long start = 1, end = n;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if ( mid * (mid + 1) / 2 < n) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (end * (end + 1) / 2 <= n) {
            return (int)end;
        }
        return (int)start;
    }
}

Given a sequence of words, check whether it forms a valid word square.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

Note:
The number of words given is at least 1 and does not exceed 500.
Word length will be at least 1 and does not exceed 500.
Each word contains only lowercase English alphabet a-z.
Example 1:

Input:
[
“abcd”,
“bnrt”,
“crmy”,
“dtye”
]

Output:
true

Explanation:
The first row and first column both read “abcd”.
The second row and second column both read “bnrt”.
The third row and third column both read “crmy”.
The fourth row and fourth column both read “dtye”.

Therefore, it is a valid word square.
Example 2:

Input:
[
“abcd”,
“bnrt”,
“crm”,
“dt”
]

Output:
true

Explanation:
The first row and first column both read “abcd”.
The second row and second column both read “bnrt”.
The third row and third column both read “crm”.
The fourth row and fourth column both read “dt”.

Therefore, it is a valid word square.
Example 3:

Input:
[
“ball”,
“area”,
“read”,
“lady”
]

Output:
false

Explanation:
The third row reads “read” while the third column reads “lead”.

Therefore, it is NOT a valid word square.

解法1： O(M * N)

就是遍历一遍每个字母，对每个字母判断是否有对应的字母。如果没有，则为false
C++

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:
    bool validWordSquare(vector<string>& words) {
        int m = words.size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < words[i].size(); ++j) {
                char cur = words[i][j];
                if (j >= m) {
                    return false;
                }
                if (words[j].size() <= i) {
                    return false;
                }
                if (words[j][i] != words[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Java

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 boolean validWordSquare(List<String> words) {
        if (words == null || words.size() == 0) {
            return false;
        }
        // Only need to search for the top diagonal
        int n = words.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < words.get(i).length(); j++) {
                if (j >= n) {
                    return false;
                }
                if (words.get(j).length() <= i || words.get(j).charAt(i) != words.get(i).charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

5

/ \
3 6
/ \ \
2 4 7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5

/ \
4 6
/ \
2 7

Another valid answer is [5,2,6,null,4,null,7].

5

/ \
2 6
\ \
4 7

解法1：

此题比较复杂，参考了这篇的解法。主要的思路是把要删除的节点分情况讨论。
基本的思路是： 对于一个要删除的节点，找出大于他的最小的node作为新的子root，或者是选出小于他的最大的node作为新的root。
解决此题的步骤如下：

1. 找出要删除的节点的父节点。
2. 如果删除节点是leaf， 那么直接把父节点相应的连接设为null
3. 如果删除节点只有一个子树， 那么把父节点指向唯一的那个子树
4. 如果删除节点有两个子树， 那么找出大于删除节点的最小节点（设为x), 然后把删除节点的数值设为x的值，然后重新运行一遍删除操作。
5. 上一步中，程序一定会终止因为最左节点一定是只有小于等于1个子节点。
   等找出最小的大于他的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 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 70 71 72 73 74

   /** * 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* deleteNode(TreeNode* root, int key) { TreeNode* dummy = new TreeNode(0); dummy->left = root; TreeNode* parent = findNode(dummy, root, key); TreeNode* node; if (parent->left && parent->left->val == key) { node = parent->left; } else if (parent->right && parent->right->val == key) { node = parent->right; } else { // can't find the node return dummy->left; } deleteNode(parent, node); TreeNode* res = dummy->left; delete dummy; return res; } TreeNode* findNode(TreeNode* parent, TreeNode* cur,int key) { if (!cur || cur->val == key) { return parent; } if (cur->val < key) { return findNode(cur, cur->right, key); } else { return findNode(cur, cur->left, key); } } void deleteNode(TreeNode* parent, TreeNode* node) { // delete the node, giving the parent if (!node->right) { if (parent->left == node) { parent->left = node->left; } else { parent->right = node->left; } } else if (!node->left) { if (parent->left == node) { parent->left = node->right; } else { parent->right = node->right; } } else { TreeNode* father = node; TreeNode* child = node->right; while (child->left) { father = child; child = child->left; } node->val = child->val; deleteNode(father, child); } } };

Java

1

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

click to show spoilers.

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.

解法1： Reverse integer O（N）， N is the number of digits

用一个循环来反转数字，最后比较数字和反转的是否相等即可。
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(int x) {
        if (x < 0) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        
        int copy = x;
        int re = 0;
        while (x != 0) {
            re = re*10 + x % 10;
            x /= 10;
        }
        if (copy == re) {
            return true;
        } else {
            return false;
        }
    }
};

Java

1

解法2： Without overflow

比较最左边和最右边的两个数，这样就不会有overflow的问题了。 取得左边的数的时候我们需要的是一个除数，这个可以先用O(N)的时间求出。
然后每次求出最右位和最左位。然后每次消掉两位数，相应的div也要缩小100
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

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        
        int div = 1;
        while ( x / div >= 10) {
            div *= 10;
        }
        
        while (x != 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) {
                return false;
            }
            x = (x % div) / 10; // 消掉两位
            div /= 100;	// 除数缩小100
        }
        return true;
        
    }
};

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

解法1： Divide & Conquer

关于树的题目，先考虑试试分治的思想，对于一个root，要找出最接近他的数值，可能比他小也可能比他大。所以如果他本身不等于target的话需要比较left 和right。似乎分治行得通。
由于题目给出guarantee有一个解，则不需要考虑空树的情况。 那么只要分三种情况考虑：

1. 左右子树都有， 那么比较左右子树的closestvalue和自身哪一个更close
2. 左子树
3. 右子树
   其中2，3 只要比较root和其中一个子树算出来的结果就可以了。

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

/**
 * 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 closestValue(TreeNode* root, double target) {
        if (!root->left && !root->right) {
            return root->val;
        }
        
        if (root->val == target) {
            return target;
        }
        
        int child;
        
        if (root->left && root->right) {
            int left = closestValue(root->left, target);
            int right = closestValue(root->right, target);
            child = abs(left - target) <= abs(right - target)? left : right;
        } else if (root->left) {
            child = closestValue(root->left, target);
        } else if (root->right) {
            child = closestValue(root->right, target);   
        }
        
        return abs(child - target) <= abs(root->val - target) ? child: root->val;              
    }
};

Java

1

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,
1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].

解法1： BFS, O（N）

这题也是考察BFS算法的一个变形，题意是要求每一层最右边的node。那么我们按层遍历，对于每一层只取第一个（最右边）的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

/**
 * 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<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int k = q.size();
            for (int i = 0; i < k; ++i) {
                TreeNode* cur = q.front();
                if (i == 0) {
                    res.push_back(cur->val);    
                }
                q.pop();
                if (cur->right) {
                    q.push(cur->right);
                } 
                if (cur->left) {
                    q.push(cur->left);
                }
            }
        }
        return res;
    }
};

Java

1

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL

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

运用此前perfect tree的解法，此题任然有效。
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

void connect(TreeLinkNode *root) {
    if (!root) {
        return;
    }
    queue<TreeLinkNode*> q;
    q.push(root);
    while(!q.empty()) {
        int number = q.size();
        TreeLinkNode* prev = NULL;
        for (int i = 0; i < number; ++i) {
            TreeLinkNode* cur = q.front();
            q.pop();
            cur->next = prev;
            prev = cur;
            if (cur->right) {
                q.push(cur->right);
            }
            if (cur->left) {
                q.push(cur->left);
            }
        }
    }
    return;
}

Java

1

解法2： Iterative， O（N） Time + O（1） Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummy = new TreeLinkNode(0);   // point to the next level's first node
        TreeLinkNode prev = dummy;
        while (root != null) {
            if (root.left != null) {
                prev.next = root.left;
                prev = prev.next;
            }
            if (root.right != null) {
                prev.next = root.right;
                prev = prev.next;
            }
            root = root.next;
            if (root == null) {
                // end of current level, move to the next level
                root = dummy.next;
                prev = dummy;
                dummy.next = null;
            }
        }
    }
}

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
Show Company Tags
Show Tags
Show Similar Problems

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

按照题目意思，似乎是一层一层的要连起来，第一个反应就是用BFS， 按层遍历。遍历的时候最好是从右往左，这样头node可以指向prev，之后不停的更新prev。实现起来没有难度。
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

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) {
            return;
        }
        queue<TreeLinkNode*> q;
        q.push(root);
        while(!q.empty()) {
            int number = q.size();
            TreeLinkNode* prev = NULL;
            for (int i = 0; i < number; ++i) {
                TreeLinkNode* cur = q.front();
                q.pop();
                cur->next = prev;
                prev = cur;
                if (cur->right) {
                    q.push(cur->right);
                }
                if (cur->left) {
                    q.push(cur->left);
                }
            }
        }
        return;
    }
};

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
29
30

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeLinkNode prev = null;
            for (int i = 0; i < size; i++) {
                TreeLinkNode current = queue.poll();
                if (prev != null) {
                    prev.next = current;
                }
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
                prev = current;
            }
        }
        return;        
    }
}

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

实际上上面的解法是不符合空间复杂度要求的，要求是constant。用递归的办法可以解决。对于每一层，用当前的信息去connect下一层，再对left和right分别进行递归就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            root.left.next = root.right;
            if (root.next != null) {
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
    }
}

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解法1： BFS， O（N),

典型的用BFS的题，按层遍历，只要找到一个为叶子的节点，则当前记录的层数一定是最小层。 用一个queue来完成BFS。
C++
用到了queue 的push(), front() 和pop()

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

/**
 * 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 minDepth(TreeNode* root) {
        int count = 0;
        if (!root) {
            return count;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            ++count;
            int k = q.size();
            for (int i = 0; i < k; ++i) {
                TreeNode* temp = q.front();
                q.pop();
                if (!temp->left && !temp->right) {
                    return count;
                }
                if (temp->left) {
                    q.push(temp->left);
                }
                if (temp->right) {
                    q.push(temp->right);
                }
            }
        }
        return count;
        
    }
};

Java

1

解法2： Recursive, Divide and Conquer, O(N)

一个数的最小层数是min（leftMin， rightMin） + 1, 用分治法和递归解决， code可以做到很简洁。
关于BFS和分治两者的复杂度分析，应该是一样的，参考九章的一个解答
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

/**
 * 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 minDepth(TreeNode* root) {
        
        if (!root) {
            return 0;
        }
        
        return helper(root);
    }
    
    int helper(TreeNode* root) {
        if (!root) {
            return INT_MAX;
        }
        
        if (!root->left && !root->right) {
            return 1;
        }
        
        return min(helper(root->left), helper(root->right)) + 1;
    }
};

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?

解法1： 重复利用Array, O(k^2) Time + O（K） Space

题目要求节省空间，想到的办法就是不停的修改当前的array。这里要注意的是：

1. 修改array的时候要从后往前修改，这样在计算前面的数值的时候不会受到已经修改过的数值的影响。
2. 在修改array的时候是从1到当前的最后一个。因为当修改完毕之后array的大小才会增加。如果不注意这一点会出现[1,1,1]这样的结果。
   C++

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution { public: vector<int> getRow(int rowIndex) { vector<int> res; res.push_back(1); for (int i = 0; i < rowIndex; ++i) { for (int j = res.size(); j >= 1; --j) { res[j] += res[j - 1]; } res.push_back(1); } return res; } };

Java

1