Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Hint:

You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?

解法1：找规律， O（N）

本题比较简单的解法也是从找规律而来
0 -> 0
1 -> 1
2 -> 10 -> 1
3 -> 11 -> 2
4 -> 100 -> 1
5 -> 101 -> 2
对于偶数i，他的1的个数是i/2的1的个数
杜宇奇数i，他的1的个数是i/的1的个数+1

因为对于一个数除以2的操作就是一个右移操作，而偶数的最低位为0，奇数的最低位为1， 那么右移的时候偶数的1的个数不会变，奇数的1的个数会减少1. 由此写出程序。

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

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0) {
			return vector<int>{0};
		} else if (num == 1) {
			return vector<int>{0,1};
		}
		vector<int> res{0,1};
		for (int i = 2; i <= num; ++i) {
			if (i % 2 == 0) {
				res.push_back(res[i/2]);
			} else {
				res.push_back(res[i/2] + 1);
			}
		}
		return res;
    }
};

解法2： HashMap

观察现象可以发现，每一个数字如果是2的幂次，那么1的个数为1.如果不是，则 = 1 + dp[数字 - 最接近这个数的2的幂次数]
这里dp记录的是每一个数字的1的个数。

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 int[] countBits(int num) {
        if (num == 0) return new int[]{0};
        if (num == 1) return new int[]{0, 1};
        int[] res = new int[num + 1];
        res[0] = 0;
        res[1] = 1;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        int largest = 1;
        for (int i = 2; i <= num; i++) {
            if ( ( i & (i - 1)) == 0) {
                res[i] = 1;
                map.put(i, 1);
                largest = i;
            } else {
                res[i] = 1 + map.get(i - largest);
                map.put(i, res[i]);
            }
        }
        return res;
    }
}

解法3：

观察现象，如果是偶数，则结果和偶数/2一样，如果是奇数，那么是奇数/2 + 1.

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

class Solution {
    public int[] countBits(int num) {
        if (num == 0) {
            return new int[]{0};
        }
        if (num == 1) {
            return new int[]{0, 1};
        }
        int[] res = new int[num + 1];
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= num; i++) {
            res[i] = i % 2 == 0 ? res[i >> 1] : res[i >> 1] + 1;
        }
        return res;
    }
}

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

解法1：找规律， O(N)

如果把从2到10的结果写出来可以发现，最大的结果是每一个数先分解成3的和，然后和剩下的数的乘积最大。本题还有DP的解法，之后补上

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

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};

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

class Solution {
    public int integerBreak(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];  // stores the max if split the number into 2 or more numbers
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                int temp = Math.max(dp[j] * dp[i - j], j * (i - j));
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(dp[i - j], (i - j)));
            }
        }
        return dp[n];
    }
}

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

1
2
3
4

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

解法1：Binary Search O(NLogn)

因为是sorted， 用binary search很容易解决。要注意的是最后判断nums[start], nums[end]的时候如果都没有符合的，那么说明要插入的位置是array的尾巴，要返回的结果是end+1， 比如
searchInsert([0],1)这样的情况。
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:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
		int start = 0, end = nums.size() -1;
		while (start + 1 < end) {
			int mid = start + (end - start) / 2;
			if (nums[mid] > target) {
				end = mid;
			} else {
				start = mid;
			}
		}
		if (nums[start] >= target) {
			return start;
		}
		if (nums[end] >= target) {
			return end;
		}
		return end + 1;
    }
};

Java

1

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

解法1：Binary Search

这也是一题经典的binary search的题目。 难点在于怎么判断最小值是在mid的左面还是右面，以此来缩小范围。
当搜索的范围[start, end]确定了之后，mid的取值可以有几种情况

• start < end, 那么最小值在start和mid之间
• start > end, 那么最小值的位置取决于mid和start，end的关系
  • 如果mid < end, 那么最小值一定在start和mid之间
  • 如果mid > end, 那么pivot点一定在mid和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 25 26 27

    class Solution { public: int findMin(vector<int>& nums) { if (nums.size() == 0) { return -1; } int start = 0, end = nums.size() - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[start] < nums[end]) { end = mid; } else { if (nums[mid] < nums[end]) { end = mid; } else { start = mid; } } } if (nums[start] < nums[end]) { return nums[start]; } else { return nums[end]; } } };

Java

1

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解法1：Binary Search, O(logN)

看到在sorted array里找元素的问题，首先想到可以用binary search。 这里用两次binarysearch， 一次找到range的起始点，一次找到最后一个点。
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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return vector<int>{-1,-1};
		int start = searchFirst(nums, target);
		int end = searchLast(nums, target);
		return vector<int>{start, end};
    }
	int searchFirst(vector<int>& nums, int target) {
		int start = 0, end = nums.size() - 1;
		while (start + 1 < end) {
			int mid = start + (end - start) / 2;
			if (nums[mid] < target) {
				start = mid;
			} else {
				end = mid;
			}
		}
		if (nums[start] == target) {
			return start;
		} else if (nums[end] == target) {
			return end;
		} else {
			return -1;
		}
	}
	int searchLast(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else {
            return -1;
        }
	}
};

Java

1

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

解法1： Bucket sort/counting sort, O(N) Time with two passes

Bucket sort, 统计0,1,2的个数然后再逐个写入
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:
    void sortColors(vector<int>& nums) {
        // bucket sort
        int red = 0, white = 0, blue = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) {
                red++;
            } else if (nums[i] == 1) {
                white++;
            } else {
                blue++;
            }
        }
        int i = 0;
        for (int j = 1; j <= red; j++) {
            nums[i++] = 0;
        }
        for(int j = 1; j <= white; j++) {
            nums[i++] = 1;
        }
        for (int j = 1; j <= blue; j++) {
            nums[i++] = 2;
        }
    }
};

Java

1

解法2： One pass O(N)

类似于双指针的思路,这里用了一个low记录0的位置,用了一个high记录2的位置,然后从左往右扫描. 如果是0或者2就知道该插入在什么地方,如果是1那么就往前移动.
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

class Solution {
public:
    void sortColors(vector<int>& nums) {
        if (nums.size() <= 1) {
            return;
        }
        int low = 0, high = nums.size() -1;
        int mid = 0;
        while (mid < nums.size() && mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                ++low;
                ++mid;
            } else if (nums[mid] == 2) {
                swap(nums, high, mid);
                --high;
            } else {
                ++mid;
            }
        }
        return;
    }
    void swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] =temp;
    }
};

###解法3: One pass O(N) ###
用两个指针记录zero和one插入的位置。
对于每一个新数字，先插入最大的数字。因为如果是其他数字的话在之后的操作中会被覆盖。
然后从大到小的判断当前数字为哪一个。如果是1那么只移动one的位置并插入。
如果是zero，那么需要先移动one并且赋值，然后移动zero再赋值。如果zero插入的位置原本是一个1，那么被覆盖的1就被one的指针找回了。
Java

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

public class Solution {
    public void sortColors(int[] nums) {
        int zero = -1;
        int one = -1;
        for (int k = 0; k < nums.length; ++k) {
            int v = nums[k];
            nums[k] = 2;    // no matter what, set this to 2
            if (v == 0) {
                nums[++one] = 1;
                nums[++zero] = 0;
            } else if (v == 1) {
                nums[++one] = 1;    // advance one
            }
        }
        return;
    }
}

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

1
2
3

A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

解法1： Greedy, O(N) Time

一个贪心的解法, 主要是维护一个variable叫reach, 他记录目前为止能达到的最远的距离. 然后扫描vector,如果当前的位置是不能达到的,则返回false.
否则更新reach的值,进入下一个元素.
C++

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

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        if (nums.size() == 0) {
            return false;
        }
        
        int reach = 0;
        
        int i = 0;
        for (; i < nums.size() && reach >= i; ++i) {
            reach = max(reach, i + nums[i]);
        }
        return i == nums.size();
    }
};

Java

1

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法1： O(N) Time

一个固定的解法,可以写出来几个答案然后从当中找结论.
解法是:
从右往左找到第一个数字使得num[i] < num[i + 1], 设i为pivot
从右往左找到第一个数字使得num[j] > num[pivot], 记录j
将pivot和j指向的item互换
将pivot右边的数组reverse

要注意的是,在第二步中由于pviot右面的数组一定是sorted(从大到小), 所以我们在寻找第一个比pivot数字大的时候可以采用binary search来提供一些小的optimization.

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        
        if (nums.size() <= 1) {
            return;
        }
        
        int pivot = -1;
        for (int i = nums.size() - 1; i >= 1; --i) {
            if (nums[i - 1] < nums[i]) {
                pivot = i - 1;
                break;
            }
        }
        
        if (pivot == -1) {
            std::reverse(nums.begin(), nums.end());
            return;
        }
        
        // find the first element that is larger than nums[pivot]
        int ex = bsearch(nums, pivot + 1, nums.size() - 1, nums[pivot]);
        int temp = nums[pivot];
        nums[pivot] = nums[ex];
        nums[ex] = temp;
        
        // reverse ex + 1 ~ end
        std::reverse(nums.begin() + pivot + 1, nums.end());
        return;
        
    }
    
    int bsearch(vector<int>& nums, int start, int end, int ref) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > ref) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] > ref) {
            return end;
        }
        return start;
    }
};

Java

1

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

解法1： Two pointers, O(N) Time, One pass

比较典型的two pointers的题目. 主要思路是, 一个container的面积是(right- left) * (左右两块挡板较短的那一块的长度)
那么要maximize一个面积,可以做的是增长距离,或者是增长板的长度.
设两个指针,从左右边界开始,这个时候,我们的长度是最长的.计算一下当前的面积
如果要提高这个面积, 因为只能缩小长度,则我们必须要提高短板的长度.
那么不停的移动左右指针(哪一根指针指向的板较短就移哪一根)
C++

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

class Solution {
public:
    int maxArea(vector<int>& height) {
        int area = INT_MIN;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            area = max(area, (right - left) * (min(height[left], height[right])));
            if (height[left] <= height[right]) {
                ++left;
            } else {
                --right;
            }
        }
        return area;
    }
};

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

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int area = Integer.MIN_VALUE;
        int left = 0, right = height.length - 1;
        while (left < right) {
            area = Math.max(area, (right - left) * (min(height[left], height[right])))'
            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }
        }
        return area;
    }
}

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

1
2
3
4
5
6
7

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

解法1： 剪叶子的思路

每当遇到两个连续的”#”的时候,并且前一个字符不是”#”的时候,可以判断这是一个叶子.如果我们把每一个叶子剪掉并且替换成”#”的话,我们实际上在不停的从下往上的砍叶子直到砍完为止.
这样的思路对于binary tree在其他题目中似乎也见过.那么对于一个valid的binary tree,最后一定是能砍光的. 以此可以得出如下的算法.
C++
注意的是这里用vector当成一个stack用,因为我们需要access前面的2个元素,用vector效率较高.

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

class Solution {
public:
    bool isValidSerialization(string preorder) {
        std::istringstream ss(preorder);
        vector<string> s;
        string item;
        while (getline(ss, item, ',')) {
            s.push_back(item);
            while (s.size() >= 3 && item == "#" && s[s.size() - 2] == "#" && s[s.size() -3] != "#") {
                s.pop_back();
                s.pop_back();
                s.pop_back();
                s.push_back(item);
            }
        }
        return s.size() == 1 && s[0] == "#";
    }
};

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

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return true;
        }
        Stack<String> stack = new Stack<>();
        String[] nodes = preorder.split(",");
        for (String ch : nodes) {
            while (ch.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();
                if (stack.isEmpty()) return false;
                stack.pop();
            }
            stack.push(ch);            
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

解法2: outbound - inbound

这个解法的核心是. 首先把所有的NULL NODE看成是valid node. 每一个node的inbound/outbound的connection可以统计如下:

1. 每一个非NULL节点都有两个outbound和一个inbound (除了root)
2. 每一个NULL节点都有一个inbound和0个outbound
3. 一个valid的树如果计算所有的outbound和inbound的差,一定是等于0的,并且从root到任意一节点, outbound - inbound都一定不是负数.
   有了这个结论之后, code写起来很直白.
   C++

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

   class Solution { public: bool isValidSerialization(string preorder) { std::istringstream ss(preorder); string item; int diff = 1; while (getline(ss, item, ',')) { if (--diff < 0) return false; if (item != "#") diff += 2; } return diff == 0; } };

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

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int diff = 1;   // calculate outdegree - indegree
        for (int i = 0; i < nodes.length; i++) {
            diff--;
            if (diff < 0) return false;
            if (!nodes[i].equals("#")) diff += 2;
        }
        return diff == 0;
    }
}