发表于 | 分类于

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

解法1：HashMap, O(N) Time + O(N) Space

因为anagram是表示排序后A,B的字母一样，那么就可以用一个hashmap存储每一个group， group的key就是排序后的string。
string排序在java中并没有自带的函数，可以先转换成chararray，然后用Arrays.sort来排序。
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
25
26
27
28
29
30
31
32
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String str: strs) {
            String temp = sorted(str);
            if (!map.containsKey(temp)) {
                ArrayList<String> collection = new ArrayList<String>();
                collection.add(str);
                map.put(temp, collection);
            } else {
                map.get(temp).add(str);
            }
        }
        
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        
        return res;
        
    }
    
    public String sorted(String x) {
        char[] temp = x.toCharArray();
        Arrays.sort(temp);
        return new String(temp);
    }
}

发表于 | 分类于

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

解法1：BFS, Time O(26LN)

求最小路径，用BFS比较自然可以想到。关键是怎么构建一个图. 我们把每一个word改变一个字母，检查是否在已知的dict中。由于查询用hashtable是最快的，这里需要考虑用一个hashset来存放dict。
然后用一个BFS遍历就可以了。
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
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }
        
        if (beginWord.equals(endWord)) {
            return 1;
        }
        
        // To boost lookup
        Set<String> dict = new HashSet<String>();
        for (String word: wordList) {
            dict.add(word);
        }
        
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        
        queue.offer(beginWord);
        visited.add(beginWord);
        
        int res = 1;
        while(!queue.isEmpty()) {
            ++res;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String current = queue.poll();
                List<String> next = getNextWords(current, dict);
                for (String candidate: next) {
                    if (candidate.equals(endWord)) {
                        return res;
                    }              
                    if (!visited.contains(candidate)) {
                        queue.offer(candidate);
                        visited.add(candidate);
                    }
                }
            }
            
        }
        
        
        return 0;
    }
    
    private String replace(String origin, int index, char c) {
        char[] temp = origin.toCharArray();
        temp[index] = c;
        return new String(temp);
    }
    
    public List<String> getNextWords(String origin, Set<String> dict) {
        
        List<String> res = new ArrayList<String>();
        for (char i = 'a'; i <= 'z'; ++i) {
            for (int j = 0; j < origin.length(); ++j) {
                if (origin.charAt(j) == i) {
                    continue;
                }
                String temp = replace(origin, j, i);
                if (dict.contains(temp)) {
                    res.add(temp);
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

解法1：O(N + M)

这题和Matrix I的区别是上一行和下一行不是递增的，也就是说不能串起来当成一个sorted array来处理。
这题要变换下思路，考虑右上角和左下角两个点。比如左下角，比数字大就往上，比它数字小就往右。直到找到所要求的答案。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length, n = matrix[0].length;
        int x = m - 1;
        int y = 0;
        while (true) {
            if (matrix[x][y] < target) {
                ++y;
            } else if (matrix[x][y] > target) {
                --x;
            } else {
                return true;
            }
            if (x < 0 || y >= n) {
                return false;
            }
        }
    }
}

发表于 | 分类于

Description:

Count the number of prime numbers less than a non-negative number, n.

Hint:

Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?

Let’s write down all of 12’s factors:

2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12
As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countPrimes(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}
private boolean isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don’t let that name scare you, I promise that the concept is surprisingly simple.

Sieve of Eratosthenes: algorithm steps for primes below 121. “Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0.

We start off with a table of n numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?

4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, … can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?

In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, … Now what should be the terminating loop condition?

It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?

Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.

The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

解法1：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int countPrimes(int n) {
        
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        
        for (int i = 2; i * i < n; ++i) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                ++count;
            }
        }
        return count;
    }
}

发表于 | 分类于

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

1
2
3
4
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1
2
3
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1
2
3
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array won’t exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].

解法1：Two pointers, O(NlogN) Time + O(1) Space

可以先排序，这样找距离为k的数就好找了。用Two pointers的方法来解，left负责从左到右遍历，right负责找对应于left的距离为k的数。
这题的坑点在于有重复的值，所以left需要去重，也就是下面程序的i， 那么如果说i在循环内因为重复的问题已经向前进了，那么right进行到下一次循环的时候需要至少从i+1开始，也就是
我们的那句j = Math.max(i + 1, j)的意义。
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
25
26
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums); // first sort the input
        
        int res = 0, j = 1;
        int n = nums.length;
        for (int i = 0; i < n - 1; ++i) {
            j = Math.max(i + 1, j);
            while ( j < n && (long)nums[j] - nums[i] < k) {
                ++j;
            }
            if (j < n && (long)nums[j] - nums[i] == k) {
                ++res;
            }
            while (i < n - 1 && nums[i + 1] == nums[i]) {
                ++i;
            }
            
        }
        return res;
    }
}

解法2：HashMap, O(N) Time + O(N) Space

这个解法借用了Two sum的思路，在two sum里，我们用一个hashmap来判断对应的两个数的和是否为target。这里也一样。如果要找寻是否有两个数的差是否为k， 那么我们也可以把他们都放到map中。
所不同的地方就是这里是统计个数。那么如果k是一个正数，我们只需要判断对应的另外一个数是否在map中。如果k为0， 那么要判断现在这个数出现的次数是否大于1.
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
25
26
27
28
public class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num: nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        int res = 0;
        for (Integer key : map.keySet()) {
            if (k == 0 && map.get(key) > 1) {
                ++res;
            } 
            if (k > 0 && map.containsKey(key + k)) {
                ++res;
            }
        }
        return res;
        
    }
}

发表于 | 分类于

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解法1：O(N) Time + O(1) Complexity

如果是已经sorted的话这题就很简单了，比较容易的能想到可以用two pointers， left和right按照加和的大小不停的移动。

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
25
26
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        
        int[] res = new int[2];
        
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                ++left;
            } else if (sum > target) {
                --right;
            } else {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            }
        }
        
        return null;
    }
}

发表于 | 分类于

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1
2
3
4
5
6
7
8
9
10
11
12
13
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

解法1：

这题可以作为让你写一个Stack的class的follow up问题。
Implenment stack的时候可以用arraylist而不是用array, 这样就不用自己写一个resize function来维护底层数据的存放。
维护一个min, 可以有两个方法。一个是维护另一个arraylist， 保存对应每一个数据当前的最小值。
另一个方法是class MinStack extends Iterable, 然后需要有一个iterator(), 来返回一个Iterator的classmyiteraor，
这个myiterator implements Iterator 需要两个函数，hasNext()和next()

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class MinStack {
    /** initialize your data structure here. */
    List<Integer> data;
    List<Integer> mins;
    public MinStack() {
        data = new ArrayList<Integer>();
        mins = new ArrayList<Integer>();
    }
    
    public void push(int x) {
        data.add(x);
        if (mins.size() > 0) {
            mins.add(mins.get(mins.size() - 1) < x ? mins.get(mins.size() - 1) : x);
        } else {
            mins.add(x);
        }
    }
    
    public void pop() {
        if (data.size() > 0) {
            data.remove(data.size() - 1);
            mins.remove(mins.size() - 1);
        }
    }
    
    public int top() {
        return data.get(data.size() - 1);
    }
    
    public int getMin() {
        return mins.get(mins.size() - 1);
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

发表于 | 分类于

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

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

解法1：O(M*N) Time, O(1) Space

运用分层处理的思想。一般情况，每一层有4条边组成，顺序是按照right, down, left, up。而且每一层的最后一行和第一行， 最后一列和第一列是对应关系。意思是说如果我们从第i行开始，那么与之对应的最后一行便是m - 1 - i, 列野同理。
那么层数有多少呢？这是又行数和列数决定的. level = (min(row, col) + 1) / 2
还有一个坑是对于单行或者单列的处理需要单独计算。

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        
        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        
        int m = matrix.length, n = matrix[0].length;
        int level = (Math.min(m, n) + 1) / 2;
        
        for (int i = 0; i < level; ++i) {
            int lastrow = m - i - 1;
            int lastcol = n - i - 1;
            if (i == lastrow) {
                for (int j = i; j <= lastcol; ++j) {
                    res.add(matrix[i][j]);
                }
            } else if (i == lastcol) {
                for (int j = i; j <= lastrow; ++j) {
                    res.add(matrix[j][i]);
                }
            } else {
                // To right
                for (int j = i; j < lastcol; ++j) {
                    res.add(matrix[i][j]);
                }
                // down
                for (int j = i; j < lastrow; ++j) {
                    res.add(matrix[j][lastcol]);
                }
                // left
                for (int j = lastcol; j > i; --j) {
                    res.add(matrix[lastrow][j]);
                }
                // up
                for (int j = lastrow; j > i; --j) {
                    res.add(matrix[j][i]);
                }
            }
            
        }
        
        return res;
        
    }
}

发表于 | 分类于

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解法1：

这题有几个坑：一个是分母有可能是0， 这种情况要判断dividend的正负而返回。一个是INT_MIN/(-1) > INT_MAX, 所以这种条件下会overflow。还有一个是分子分母有可能符号不同。
除法的基本算法是把被除数A分拆成A = B*(2^n1 + 2^n2 + ….), 每一次找出比A小的最大的B的2的倍数，也就是求出Ni。这里每一次B乘以2的操作可以用左位移表示。
这里引出了另外一个坑，就是往左移的时候可能会溢出，所以一开始要把他们转化为long型再操作。
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
25
26
27
28
29
public class Solution {
    public int divide(int dividend, int divisor) {
		if (divisor == 0) {
			return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
		}
		if (dividend == Integer.MIN_VALUE && divisor == -1) {
			return Integer.MAX_VALUE;
		}
		
		boolean neg = false;
	    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
	        neg = true;
	    }
		int res = 0;
		long x = Math.abs((long)dividend);
		long y = Math.abs((long)divisor);
		while ( x >= y) {
			int shift = 1;
			while (x >= (y<<shift)) {
				++shift;
			}
			x -= y << (shift - 1);
			res += 1 << (shift - 1);
		}
		
		return neg ? 0 - res : res;         
    }
}

发表于 | 分类于

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

1
2
3
4
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:
N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

解法1：Priority Queue

这里感觉是要用一个带下标的排序，那么我们可以自己实现一个带下标的排序，或者可以使用已有的可排序的数据结构。对于可排序的比较熟悉的就是PriorityQueue了。
每一个放入的元素都会自动排序，那么我们只需要全部放入然后一个个读出同时判断是第几个元素就可以解决medal的归属问题。
用一个辅助class记录data和index，同时实现一个comparator，来比较这两个pair。

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class pair {
    int data;
    int index;
    public pair(int d, int i) {
        this.data = d;
        this.index = i;
    }
};
public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        Comparator<pair> comparator = new Comparator<pair>() {
            public int compare(pair a, pair b) {
                if (a.data < b.data) {
                    return -1;
                } else if (a.data == b.data) {
                    return 0;
                } else {
                    return 1;
                }
            }
        };
        PriorityQueue<pair> queue = new PriorityQueue<pair>(nums.length, comparator);
        for (int i = 0; i < nums.length; ++i) {
            queue.offer(new pair(nums[i], i));
        }
        
        String[] res = new String[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            pair temp = queue.peek();
            if (queue.size() > 3) {
                res[temp.index] = Integer.toString(queue.size());
            } else if (queue.size() == 3) {
                res[temp.index] = "Bronze Medal";
            } else if (queue.size() == 2) {
                res[temp.index] = "Silver Medal";
            } else {
                res[temp.index] = "Gold Medal";
            }
            queue.poll();
        }
        return res;
    }
}