## Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return `["11","69","88","96"]`.

```public class Solution {
public List<String> findStrobogrammatic(int n) {
return dfsHelper(n, n);
}

public List<String> dfsHelper(int n, int m) {
if (n == 0) {
List<String> result = new ArrayList<>();
return result;
}
if (n == 1) {
List<String> result = new ArrayList<>();
return result;
}

List<String> list = dfsHelper(n - 2, m);
List<String> res = new ArrayList<>();

for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
if (n != m) {
res.add("0" + s + "0");
}
res.add("1" + s + "1");
res.add("8" + s + "8");
res.add("6" + s + "9");
res.add("9" + s + "6");
}

return res;
}
}
```

Filed under LeetCode

## Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69”, “88”, and “818” are all strobogrammatic.

```public class Solution {
public boolean isStrobogrammatic(String num) {
Map<Character, Character> map = new HashMap<>();
map.put('6', '9');
map.put('9', '6');
map.put('8', '8');
map.put('1', '1');
map.put('0', '0');

int low = 0;
int high = num.length() - 1;
while (low <= high) {
char cLow = num.charAt(low);
char cHigh = num.charAt(high);
if (map.containsKey(cLow) && cHigh == map.get(cLow)) {
low++;
high--;
} else {
return false;
}
}

return true;
}
}
```

Filed under LeetCode

## Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

```Secret number:  "1807"
Friend's guess: "7810"
```

Hint: `1` bull and `3` cows. (The bull is `8`, the cows are `0`, `1` and `7`.)

Write a function to return a hint according to the secret number and friend’s guess, use `A` to indicate the bulls and `B` to indicate the cows. In the above example, your function should return `"1A3B"`.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

```Secret number:  "1123"
Friend's guess: "0111"
```

In this case, the 1st `1` in friend’s guess is a bull, the 2nd or 3rd `1` is a cow, and your function should return `"1A1B"`.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

```public class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;

int[] sarr = new int[10];
int[] garr = new int[10];

for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) != guess.charAt(i)) {
sarr[secret.charAt(i) - '0']++;
garr[guess.charAt(i) - '0']++;
} else {
bulls++;
}
}

for (int i = 0; i < 10; i++) {
cows += Math.min(sarr[i], garr[i]);
}

return (bulls + "A" + cows + "B");
}
}
```

Filed under LeetCode

## Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

```v1 = [1, 2]
v2 = [3, 4, 5, 6]
```

By calling next repeatedly until hasNext returns `false`, the order of elements returned by next should be: `[1, 3, 2, 4, 5, 6]`.

Follow up: What if you are given `k` 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question – Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for `k > 2` cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

```[1,2,3]
[4,5,6,7]
[8,9]
```

It should return `[1,4,8,2,5,9,3,6,7]`.

```public class ZigzagIterator {
Queue<Iterator> queue;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
queue = new LinkedList<>();
if (!v1.isEmpty()) {
queue.offer(v1.iterator());
}
if (!v2.isEmpty()) {
queue.offer(v2.iterator());
}
}

public int next() {
Iterator it= queue.poll();
int result = (Integer)it.next();
//push back to the queue.
if (it.hasNext()) {
queue.offer(it);
}

return result;
}

public boolean hasNext() {
return !queue.isEmpty();
}
}

/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/
```

Filed under LeetCode

## Some useful log query command

qlgrep IntegrationEndpointErrorCount=1 10.0.* | grep -c Time //get num of IntegrationEndpointErrorCount in last hour

grep -h AccountId 10.0.* | sort | uniq -c >all_counts //get all customers who call ES last hour
sort -n -r all_counts| head -10 //get top 10 user call execution service.

qlgrep IntegrationEndpointErrorCount=1 10.0.* | grep -h AccountId | sort | uniq -c // list num of IntegrationEndpointErrorCount each accountId has

df -h //check disk usage

qlgrep * | grep -h | sort | uniq -c

qlgrep AccountId=1234567 * | grep -h Counters= | cut -f2- -d= | tr ‘,’ ‘\n’ | grep -v ‘=0’ | cut -f1 -d= | sort | uniq -c

Filed under Linux/Unix, Miscellaneous

## Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

```public class Solution {
public int numWays(int n, int k) {
int[] dp = {0, k, k*k, 0};
if (n <= 2) {
return dp[n];
}

for (int i = 2; i < n; i++) {
dp[3] = (k - 1) * (dp[1] + dp[2]);
dp[1] = dp[2];
dp[2] = dp[3];
}

return dp[3];
}
}
```

Filed under LeetCode

## Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

```    1
/ \
2   3
/ \
4   5
```

as `"[1,2,3,null,null,4,5]"`, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

```public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}

private void buildString(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("N" + ",");
return;
}
sb.append(root.val + ",");
buildString(root.left, sb);
buildString(root.right, sb);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> nodes = new LinkedList<>();
return buildTree(nodes);
}

private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals("N")) {
return null;
} else {
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}

}
}
```

Filed under LeetCode

## Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given `[0, 1, 3, 50, 75]`, lower = 0 and upper = 99, return `["2", "4->49", "51->74", "76->99"].`

```public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
if (nums == null) {
return new ArrayList<String>();
}
int j = lower;
List<String> res = new ArrayList<>();
for (int i = 0; i < nums.length && j <= upper; i++) {
StringBuilder sb = new StringBuilder();
if (nums[i] - j > 1) {
sb.append(j);
sb.append("->");
sb.append(nums[i] - 1);
}
if (nums[i] - j == 1) {
sb.append(j);
}
j = nums[i] + 1;
}

if (j == upper){
} else if (j < upper){
res.add(String.valueOf(j) + "->" + String.valueOf(upper));
}

return res;
}
}
```

Filed under LeetCode

## 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets `i, j, k` with `0 <= i < j < k < n` that satisfy the condition `nums[i] + nums[j] + nums[k] < target`.

For example, given nums = `[-2, 0, 1, 3]`, and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

```[-2, 0, 1]
[-2, 0, 3]
```

Could you solve it in O(n2) runtime?

Solution:

The only difference between 3 sum and this question is when nums[i] + nums[k] + nums[j] < target, the number of possible result between k and j can be counted by j -k

```public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}

Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
int k = i + 1;
int j = nums.length  - 1;
while (k < j) {
if (nums[k] + nums[j] < temp) {
count += j - k;
k++;
} else {
j--;
}
}
}

return count;
}
}
```

Filed under LeetCode

## MeetingRoom II

Given an array of meeting time intervals consisting of start and end times `[[s1,e1],` `[s2,e2],...]` (si < ei), find the minimum number of conference rooms required.

For example,
Given `[[0, 30],[5, 10],[15, 20]]`,
return `2`.

Solution:

put start and end into two list, sort them. use two variable to record minimum meeting room

```public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length < 1) {
return 0;
}

int res = 0;
int[] start = new int[intervals.length];
int[] end = new int[intervals.length];
for(int i= 0; i<intervals.length; i++){
start[i] = intervals[i].start;
end[i] = intervals[i].end;
}
Arrays.sort(start);
Arrays.sort(end);

int i = 0;
int j = 0;
int rooms = 0;
while (i < start.length && j < end.length) {
if (start[i] < end[j]) {
rooms++;
i++;
res = Math.max(rooms, res);
} else {
rooms--;
j++;
}
}

return res;
}
```