Question:

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Thinking:

Firstly, count the length of the linked list. Then get the n-k th node. Finnaly, change the pointer of it and the tail.

Solution:

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null)    return head;
    ListNode p = head;
    int count = 1;
    while (p.next != null) {
        p = p.next;
        count++;
    }
    if (k == count)    return head;
    p.next = head;
    p = head;
    for (int i = 1; i < count - k%count; i++) {
        p = p.next;
    }
    ListNode nhead = p.next;
    p.next = null;

    return nhead;
}

Question:

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given “bcabc”
Return “abc”

Given “cbacdcbc”
Return “acdb”

Thinking:

Record the times characters emerges in the list and check from left to right.Record the smallest character postion of the list until find the unique character, then delete the bigger characters before smallest one and delete smallest from the rest of list.

Solution:

public String removeDuplicateLetters(String s) {
    int[] count = new int[26];
    int smallest = 0;
    if (s.length() == 0)    return "";
    for (char c: s.toCharArray())    count[c-'a']++;
    for (int i = 0; i < s.length(); i++){
        if (s.charAt(i) < s.charAt(smallest))    smallest = i;
        if (--count[s.charAt(i) - 'a'] == 0)    break;
    }
    return s.charAt(smallest) + removeDuplicateLetters(s.substring(smallest+1).replaceAll(s.charAt(smallest)+"", ""));
}

Question:

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

Beware of overflow.

Thinking:

This is question to find formula. We should notice that:

1                   1                                                                                     [1, 9]

11                 10  11  12  13  14  15  16  17  18  19                              [10, 19]

1                   21                                                                                   [20, 29]

1                   31                                                                                   [30, 39]

1                   41                                                                                   [40, 49]

1                   51                                                                                   [50, 59]

1                   61                                                                                   [60, 69]

1                   71                                                                                   [70, 79]

1                   81                                                                                   [80, 89]

1                   91                                                                                   [90, 99]

11                 100  101  102  103  104  105  106  107  108  109          [100, 109]

21                 110  111  112  113  114  115  116  117  118  119             [110, 119]

11                 120  121  122  123  124  125  126  127  128  129          [120, 129]

We should divide it into three situations in every digit division: one is bigger than 2, another is equal to 1 and the rest is less than 0.

Solution:

public int countDigitOne(int n) {
    int res = 0;
    for (long m = 1; m <= n; m*=10) {
        res += (n/m + 8) / 10 * m + (n/m % 10 == 1? n%m+1:0);
    }
    return res;
}

Reference: https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python

Question:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Thinking:

An efficient way to solve this problem is to use stack get last num for an operation. And in order to delay the operation after get the two numbers, we need a op variable to record the last op until find the second number. What’s more, accroding to their op, numbers push into the stack in different ways. Finnaly, we just need to get the element from stack and add them all.

Solution:

public int calculate(String s) {
    Stack<Long> stack = new Stack<Long>();

    int i = 0;
    char op = '+';
    long num = 0;

    while (i < s.length()) {
        if (Character.isDigit(s.charAt(i))) {
            while (i < s.length() && Character.isDigit(s.charAt(i)))
                num = num * 10 + s.charAt(i++) - '0';
        }
        else if (s.charAt(i) == ' ')
            i++;
        else {
            if (op == '+')
                stack.push(num);
            else if (op == '-')
                stack.push(-num);
            else if (op == '*')
                stack.push(stack.pop() * num);
            else if (op == '/')
                stack.push(stack.pop() / num);
            num = 0;
            op = s.charAt(i++);
        }
    }

    if (op == '+')
        stack.push(num);
    else if (op == '-')
        stack.push(-num);
    else if (op == '*')
        stack.push(stack.pop() * num);
    else if (op == '/')
        stack.push(stack.pop() / num);

    int res = 0;
    for (Long n: stack)
        res += n;

    return res;
}

Question:

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Thinking:

Because it limits the length of repeated substrings, so we can travse the list one time from the left to right. Pick substring from the list to check whether this substring emerge beofe.

Solution:

public List<String> findRepeatedDnaSequences(String s) {
    HashSet<String> set = new HashSet<String>();
    List<String> res = new ArrayList<String>();

    for (int i = 0; i+10 <= s.length(); i ++) {
        String temp = s.substring(i, i+10);
        if (!set.contains(temp)) {
            set.add(temp);
        }
        else {
            if (!res.contains(temp))
                res.add(temp);
        }
    }

    return res;
}

More efficient way:(which use the bits to represent map fucntion, reference: https://leetcode.com/discuss/25399/clean-java-solution-hashmap-bits-manipulation)

public List<String> findRepeatedDnaSequences(String s) {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    HashSet<Integer> set = new HashSet<Integer>();
    HashSet<Integer> second = new HashSet<Integer>();
    List<String> res = new ArrayList<String>();

    if (s.length() < 10)    return res;

    map.put('A', 0);
    map.put('C', 1);
    map.put('G', 2);
    map.put('T', 3);

    int v = 0;

    for (int i = 0; i < s.length(); i++) {
        v <<= 2;
        v |= map.get(s.charAt(i));
        v &= 0xfffff;
        if (i < 9)    continue;
        if (!set.add(v) && second.add(v)) {
            res.add(s.substring(i-9, i+1));
        }
    }

    return res;
}