Daily Archives: September 1, 2016

leetcode 387

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Solution. From g4g. During the first time scan,
1. Count the frequency of each char.
2. Store the position of each char where it is firstly visited
In the second time, just scan the 26 times to find the lowest position iwhere the count is 1.

public int firstUniqChar(String s) {
    int[] firstTime = new int[26], count = new int[26];
    for (int i = 0; i < s.length(); i++) {  // one time loop save the count of each char, and position of first visit.
        char ch = s.charAt(i);
        if (++count[ch - 'a'] == 1) {
            firstTime[ch - 'a'] = i;
        }
    }
    int ans = -1;
    for (int i = 0; i < firstTime.length; i++) {    // for elements which only show 1 time, get the smallest position.
        if (count[i] == 1 && firstTime[i] < ans) {
            ans = firstTime[i];
        }
    }
    return ans;
}

Check my code on github.

Assuming we have an integer array, we want to shuffle(randomly reset elements in array). One approach is like this: iterate each element from [0, …, n – 1]. For each element i, swap i with a random position within [0, …, i].

public void shuffle(int[] nums) {
    Random random = new Random();
    for (int i = 0; i < nums.length; i++) {
        int j = random.nextInt(i + 1);
        swap(nums, i, j);
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

leetcode 385.

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

Solution.

If it is ‘-‘, then sign = -1

If it is digit, then calculate digit

If it is ‘[‘, then push to stack.

If it is ‘]’, pop stack

If it is ‘,’, continue

There maybe digit before ‘,’ or ‘]’. So when there is ‘,’ or ‘]’, check if add digit

Assuming stack.peek() is curr = [4, 5, 6, [newList]], curr add 4, 5, 6 separately. When peek curr meets ‘]’, we create the newList, and add newList to curr. And newList to stack to be the top element.

public NestedInteger deserialize(String s) {
    Stack<NestedInteger> stack = new Stack();
    stack.add(new NestedInteger()); // top level is a dummy NestedInteger
    int sign = 1, digit = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '-') {
            sign = -1;
        }
        else if (Character.isDigit(ch)) {
            digit = digit * 10 + ch - '0';
        }
        else if (ch == '[') {   // peek element will include this new NestdInteger
            NestedInteger curr = new NestedInteger();
            stack.peek().add(curr);
            stack.add(curr);
        }
        else if (ch == ',' && Character.isDigit(s.charAt(i - 1))) {
            stack.peek().add(new NestedInteger(digit * sign));
            digit = 0;
            sign = 1;
        }
        else if (ch == ']') {
            if (Character.isDigit(s.charAt(i - 1))) {
                stack.peek().add(new NestedInteger(digit * sign));
                digit = 0;
                sign = 1;
            }
            stack.pop();
        }
    }
    if (s.length() > 0 && Character.isDigit(s.charAt(s.length() - 1))) {    // handle "321". Only digit
        stack.peek().add(new NestedInteger(digit * sign));
    }
    return stack.pop().getList().get(0);
}

Check my code on github.

leetcode 386.

Given an integer n, return 1 – n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

public static List<Integer> lexicalOrder(int n) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 1; i <= 9; i++) {
        dfs(i, n, ans);
    }
    return ans;
}

private static void dfs(int curr, int n, List<Integer> ans) {
    if (curr > n) {
        return;
    }
    ans.add(curr);
    for (int i = 0; i <= 9; i++) {
        dfs(curr * 10 + i, n, ans);
    }
}

Check my code on github.