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<>();
            result.add("");
            return result;
        }
        if (n == 1) {
            List<String> result = new ArrayList<>();
            result.add("0");
            result.add("1");
            result.add("8");
            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;
    }
}

Leave a comment

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;
    }
}

Leave a comment

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");
    }
}

Leave a comment

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();
 */

Leave a comment

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

上面这条命令经常用,cut -f2- -d= 是指从第二个field开始cut,以=为分界点。tr ‘,’ ‘\n’ 是指把output里面所有的’,’ 转变成

换行,grep -v ‘=0’ 是指把所有output里面不等于0的给extract出来,最后cut -f1 -d=是指以=为分界点,只需要第一个field,最后sort | uniq -c 和sql里面group by一个道理

Leave a comment

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.

 
复杂度

时间 O(N) 空间 O(1)

思路

这种给定一个规则,计算有多少种结果的题目一般都是动态规划,因为我们可以从这个规则中得到递推式。根据题意,不能有超过连续两根柱子是一个颜色,也就意味着第三根柱子要么根第一个柱子不是一个颜色,要么跟第二根柱子不是一个颜色。如果不是同一个颜色,计算可能性的时候就要去掉之前的颜色,也就是k-1种可能性。假设dp[1]是第一根柱子及之前涂色的可能性数量,dp[2]是第二根柱子及之前涂色的可能性数量,则dp[3]=(k-1)*dp[1] + (k-1)*dp[2]。

递推式有了,下面再讨论下base情况,所有柱子中第一根涂色的方式有k中,第二根涂色的方式则是k*k,因为第二根柱子可以和第一根一样。

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

Leave a comment

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<>();
        nodes.addAll(Arrays.asList(data.split(",")));
        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;
        }
        
    }
}

Leave a comment

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);
                res.add(sb.toString());
            }
            if (nums[i] - j == 1) {
                sb.append(j);
                res.add(sb.toString());
            }
            j = nums[i] + 1;
        }
        
        if (j == upper){
            res.add(String.valueOf(j));
        } else if (j < upper){
            res.add(String.valueOf(j) + "->" + String.valueOf(upper));
        }
        
        return res;
    }
}

Leave a comment

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]

Follow up:
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;
    }
}

Leave a comment

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;
    }

Leave a comment

Filed under LeetCode