LeetCode上面的题目更新很快，而且题目是越来越不好做了。我把最新的155到226题目的思考和解答过程放在下面，解法有好有坏，有问题我们可以讨论。老规矩，有一些题目是要买一个特定的电子书才可以在线做题的，我就跳过去了。
【题目】Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9
to
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
【解答】这个段子已经在互联网上广为流传了，实际事情的背景我们不得而知。不过如果真是就根据这样一道题来确定一个人的面试结果的话实在有些鲁莽。
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root==null)
return null;
TreeNode left = root.left;
TreeNode right = root.right;
root.left = right;
root.right = left;
if (left!=null)
invertTree(left);
if (right!=null)
invertTree(right);
return root;
}
}
【题目】Implement the following operations of a stack using queues.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- empty() — Return whether the stack is empty.
Notes:
- You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
- Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
【解答】基本思路是用两个Queue，每次出栈都需要在两个队列里面来回倒腾。这题到不了medium难度。
class MyStack {
private Queue<Integer> q1 = new LinkedList<Integer>();
private Queue<Integer> q2 = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
if (!q1.isEmpty()) {
q1.add(x);
} else {
q2.add(x);
}
}
// Removes the element on top of the stack.
public void pop() {
if (!q1.isEmpty()) {
while(q1.size()>1) {
int val = q1.poll();
q2.add(val);
}
q1.poll();
return;
}
if (!q2.isEmpty()) {
while(q2.size()>1) {
int val = q2.poll();
q1.add(val);
}
q2.poll();
return;
}
}
// Get the top element.
public int top() {
if (!q1.isEmpty()) {
int val = 0;
while(!q1.isEmpty()) {
val = q1.poll();
q2.add(val);
}
return val;
}
if (!q2.isEmpty()) {
int val = 0;
while(!q2.isEmpty()) {
val = q2.poll();
q1.add(val);
}
return val;
}
return 0; // invalid
}
// Return whether the stack is empty.
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
【题目】Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
【解答】建立一个类Result，其中pos指向当前操作数在整个字符串中的位置，val放置操作数的值。然后创建eval方法，从左向右遍历字符串，空格就跳过，如果遇到左括号就递归调用eval，遇到右括号就是程序出口。如果是数字，就继续往下试探，必须把这个数的全部数位取出，转化成实际的数以后再往下走。
class Result {
public int pos;
public int val;
public Result(int pos, int val) {
this.pos = pos;
this.val = val;
}
}
public class Solution {
public int calculate(String s) {
return eval(s, 0).val;
}
private Result eval(String s, int i) {
Integer total = null;
char op = 0;
while (i<s.length()) {
char ch = s.charAt(i);
if (ch==' ') {
i++;
continue;
}
if (ch=='(') {
Result result = eval(s, i+1);
i = result.pos;
if (total==null)
total = result.val;
else
total = cal(op, total, result.val);
} else if (ch==')') {
return new Result(i+1, total);
} else if (ch=='+' || ch=='-') {
op = ch;
i++;
} else {
int start = i;
i++;
while (i!=s.length() && s.charAt(i)>='0' && s.charAt(i)<='9')
i++;
int val = Integer.parseInt(s.substring(start, i).replaceAll(" ", ""));
if (total==null)
total = val;
else
total = cal(op, total, val);
}
}
return new Result(s.length(), total);
}
private int cal(char op, int total, int val) {
if (op=='+')
return total + val;
else
return total - val;
}
}
【题目】Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Assume that the total area is never beyond the maximum possible value of int.
【解答】这个题目主要需要注意的是几种矩形放置情况，考虑二者位置之间的关系。先计算两个矩形的面积之和，考虑到计算过程中的溢出可能，使用long存储中间结果。如果没有重叠，直接返回；如果有重叠，那么给所有x轴坐标排序，也给y坐标排序，两个序列各自中间的两个数构成了重叠部分的面积，减掉即可。
public class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
// beware of overflow
long total = Math.abs((long)((D-B)*(C-A))) + Math.abs((long)((G-E)*(H-F)));
// no overlap
if (
(A<E && A<G && C<E && C<G)
||
(A>E && A>G && C>E && C>G)
||
(B<F && B<H && D<F && D<H)
||
(B>F && B>H && D>F && D>H)
)
return (int)total;
int[] xs = new int[]{A, C, E, G};
int[] ys = new int[]{B, D, F, H};
Arrays.sort(xs);
Arrays.sort(ys);
int overlap = Math.abs((xs[1]-xs[2]) * (ys[1]-ys[2]));
return (int)(total-overlap);
}
}
【题目】Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
【解答】要数完全二叉树的节点数，那么如果直接计算，不利用这棵二叉树“完全”的特点，是会超时的：
public class Solution {
public int countNodes(TreeNode root) {
if (root==null)
return 0;
List<TreeNode> list = new ArrayList<>();
list.add(root);
return count(list);
}
private int count(List<TreeNode> list) {
List<TreeNode> newList = new ArrayList<>();
int count = 0;
for (TreeNode node : list) {
count++;
if (node.left!=null)
newList.add(node.left);
if (node.right!=null)
newList.add(node.right);
}
if (newList.isEmpty())
return count;
else
return count + count(newList);
}
}
接着观察完全二叉树的特点，假设高度为h（计数从1开始），除去最后一层，每一层都是满节点，且第x层的元素个数为2的(x-1)次方；而到第x层为止的满二叉树的总结点数为2的x次方。
因此最直观的思维是，对于任意h高度的完全二叉树，先计算h-1部分层数的二叉树的节点总数量，在来单独计算最后一层的数量，这样就需要找到最后一层最末一个元素的位置。但是按照这个思路来看，要寻找这个元素的位置，似乎并不是很好办。
于是换个思路，
判断从根节点每次都取左孩子，一路到底得到的左边沿高度为left，从根节点每次都取右孩子，一路到底得到的右边沿高度为right，如果left==right，那么显然当前所求是满二叉树，应用上面的公式可得；
如果当前不是，那我至少可以在左子树和右子树里继续递归判断是否是满二叉树，一个显而易见的结论是，这个左子树和右子树两个中至少存在一个满二叉树，这样这个满二叉树就可以公式求解（一刀干掉一半），剩下的这个不满的二叉树继续递归求解，这样的复杂度就是log n级别。
public class Solution {
public int countNodes(TreeNode root) {
if (root==null)
return 0;
int left = 1;
TreeNode node = root;
while (node.left!=null) {
node = node.left;
left++;
}
int right = 1;
node = root;
while (node.right!=null) {
node = node.right;
right++;
}
if (left==right)
return (int)(Math.pow(2, left))-1;
else
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
【题目】Given a 2D binary matrix filled with 0′s and 1′s, find the largest square containing all 1′s and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Return 4.
【解答】要找一个全部为1的最大矩形。大致思路是，从上往下逐行分析，用一个数组row存放累加结果，如果当前数x为0，那么row[x]为0，否则为上一行这个位置的结果+1，即累加和。比如题中的例子，
- 截止第一行的累加和是：[1,0,1,0,0]
- 截止第二行的累加和是：[2,0,2,1,1]
- 截止第三行的累加和是：[3,1,3,2,2]
- 截止第四行的累加和是：[4,0,0,3,0]
这样每构造完一行的累加数组，就可以遍历这一行内的区间[i,j]，寻找区间跨度j-i+1的最大值，并且满足row[x], x∈[i,j]中所有的x≥j-i+1。
public class Solution {
public int maximalSquare(char[][] matrix) {
if (null==matrix || matrix.length==0 || matrix[0].length==0)
return 0;
int max = 0;
int[] row = new int[matrix[0].length];
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[0].length; j++) {
if (matrix[i][j]=='0')
row[j] = 0;
else
row[j] += 1;
}
int val = maxInRow(row);
if (val>max)
max = val;
}
return max;
}
private int maxInRow(int[] row) {
int max = 0;
for (int i=0; i<row.length; i++) {
int minH = row[i];
for (int j=i; j<row.length; j++) {
if (row[j]==0)
break;
if (row[j]<minH)
minH = row[j];
int len = Math.min(minH, (j-i+1));
int area = len * len;
if (area>max)
max = area;
}
}
return max;
}
}
【题目】Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
【解答】终于有一道红黑树的题目了。首先在脑海里整理题意，相当于有一个窗口，窗口大小不得超过k，在窗口移动的过程中，寻找窗口内部元素不超过t的情况。
用一个TreeSet来存放窗口内的元素们，每来一个新元素，就：
- 使用floor方法去找是否已存在小于等于新元素的元素，如果找到，就加上t看看是否能够等于或超过新元素，如果是，就说明这两个元素差值小于等于t；
- 使用ceiling方法去找是否已存在大于等于新元素的元素，如果找到，就减掉t看看是否能够等于或者小于新元素，如果是，也说明这两个元素差值小于等于t。
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k <= 0 || t < 0)
return false;
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
int val = nums[i];
if (set.floor(val) != null && val <= t + set.floor(val))
return true;
if (set.ceiling(val) != null && set.ceiling(val) <= t + val)
return true;
set.add(val);
if (i >= k)
set.remove(nums[i - k]);
}
return false;
}
}
【题目】Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between iand j is at most k.
【解答】首先要理解题意，其实就是在一个长长的数组中，有一个大小可伸缩的滑动窗口，但是这个窗口的宽度不得超过j-i+1，在滑动这个窗口的过程中，如果发现两个数相等，那就返回true。因此使用一个map来存放滑动期间收集到的信息，key是该数，value是该数最后一次出现的位置。如果某次迭代发现该数再次出现，且两次出现的间距符合要求，就返回。
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (null==nums || nums.length<=1 || k<=0)
return false;
Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
int num = nums[i];
if (!map.containsKey(num)) {
map.put(num, i);
} else {
int diff = i - map.get(num);
if (diff<=k)
return true;
else
map.put(num, i);
}
}
return false;
}
}
【题目】A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri – Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
- The number of buildings in any input list is guaranteed to be in the range [0, 10000].
- The input list is already sorted in ascending order by the left x position Li.
- The output list must be sorted by the x position.
- There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]
【解答】这道题简直是LeetCode里面最难的一道了吧。一开始我的思路是用红黑树（在Java里面则是TreeMap），key是点的横坐标，value是高度，扫描一遍数组就可以，但是这种做法遇到的case极其多极其绕，做起来非常难受。网上有多种不同方法的解答，有DP等等。下面这个方法也是红黑树，但是key是高度，value是同样为止的各种楼的数目。最巧妙的地方有两点，一是排序的标准，二是TreeMap的使用。
首先创建分界点Node，x、y分别是横纵坐标，start变量表示是楼房的开始还是结束边界。
接着排序，优先比较x的位置，其次比较是否二者都是开始边界或都是结束边界，最后根据开始或者结束的情况来比较y。在排序以后，这些分界点就满足了这样的顺序：
- 横坐标从小到大；
- 横坐标相同时，楼房左边沿在前，右边沿在后；
- 边沿情况也相同时，如果都为左边沿，高度低的在前，如果都为右边沿，高度高的在前。
这样就保证了从左往右遍历的过程中，高度高的大楼可以覆盖掉高度低的大楼，从而形成合理的天际线。
最后说整个node list的遍历，x、y变量记录下最近一次访问的位置和高度，
- 如果是大楼左边沿，map相应entry的值+1，并且如果出现了不曾有的新高度，更新到最新位置和高度；
- 如果是大楼右边沿，map相应entry的值-1，之后如果map为空，说明到地面了；如果不为空，找map中最高大楼的entry（TreeMap的作用就体现在这里，entry有序），更新y为最高大楼的高度（矮楼要被高楼覆盖），而x使用当前位置。
public class Solution {
class Node {
boolean start;
int x;
int y;
public Node(int x, int y, boolean start) {
this.x = x;
this.y = y;
this.start = start;
}
}
public List<int[]> getSkyline(int[][] buildings) {
// build ordered node list
ArrayList<Node> list = new ArrayList<Node>();
for (int[] building : buildings) {
Node node = new Node(building[0], building[2], true);
list.add(node);
node = new Node(building[1], building[2], false);
list.add(node);
}
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node left, Node right) {
// 1. x is larger
if (left.x != right.x)
return left.x - right.x;
// 2. not start
if (left.start != right.start)
return left.start ? -1 : 1;
// 3. left and right are all of the same x and same start, then
// compare y
return left.start ? right.y - left.y : left.y - right.y;
}
});
// traverse
List<int[]> result = new ArrayList<int[]>();
// key: height, value: rectangle number
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
// last starting x and last y
int x = 0, y = 0;
for (Node node : list) {
if (node.start) {
// value++
int newVal = map.containsKey(node.y) ? map.get(node.y) + 1 : 1;
map.put(node.y, newVal);
// record for new height
if (node.y > y) {
x = node.x;
y = node.y;
result.add(new int[] { x, y });
}
} else {
// value--
Integer currentVal = map.get(node.y);
if (currentVal == 1) {
map.remove(node.y);
} else {
map.put(node.y, currentVal - 1);
}
// height==0
if (map.isEmpty()) {
x = node.x;
y = 0;
result.add(new int[] { x, 0 });
} else {
Integer last = (int) map.lastKey();
if (last != y) {
x = node.x;
y = last;
result.add(new int[] { x, y });
}
}
}
}
return result;
}
}
【题目】Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
【解答】用一个HashSet来查重。
public class Solution {
public boolean containsDuplicate(int[] nums) {
if (null==nums)
return false;
Set<Integer> set = new HashSet<>();
for (int n : nums) {
if (set.contains(n))
return true;
set.add(n);
}
return false;
}
}
【题目】Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
【解答】基本上就是回溯法解，出口有两个情况，一个是走到底了，没法再走了；还有一个是已经使用了全部的数了（参数k），无法再加别的数了。
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> total = new ArrayList<>();
if (k<=0 || n<=0)
return total;
com(new ArrayList<>(), 1, k, n, total);
return total;
}
private void com(List<Integer> list, int i, int k, int n, List<List<Integer>> total) {
if (i==10 || i>n || k==0)
return;
com(list, i+1, k, n, total);
List<Integer> newList = new ArrayList<>(list);
newList.add(i);
if (i==n && k==1)
total.add(newList);
else
com(newList, i+1, k-1, n-i, total);
}
}
Kth Largest Element in an Array
【题目】Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
【解答】要找第k大。当然可以排序，那样复杂度就是n(log n)，下面这个办法可以做到复杂度n阶，做法类似于快排，但是每次选择一个pivot之后，只需要看这个pivot的位置，如果正好是k，那就皆大欢喜；如果比k大，那就说明需要继续迭代寻找左侧；如果比k小则是右侧。
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || k <= 0 || k > nums.length)
throw new IllegalArgumentException();
return search(nums, nums.length - k, 0, nums.length - 1);
}
public int search(int[] nums, int k, int left, int right) {
if (left >= right)
return nums[left];
int mid = partition(nums, left, right);
if (mid == k)
return nums[mid];
if (mid < k)
return search(nums, k, mid + 1, right);
else
return search(nums, k, left, mid - 1);
}
public int partition(int[] nums, int left, int right) {
int x = nums[left];
int pivot = left;
int cur = left + 1;
while (cur <= right) {
if (nums[cur] < x) {
pivot++;
swap(nums, pivot, cur);
}
cur++;
}
swap(nums, left, pivot);
return pivot;
}
private void swap(int[] nums, int left, int right) {
if (left == right)
return;
nums[left] ^= nums[right];
nums[right] ^= nums[left];
nums[left] ^= nums[right];
}
}
【题目】Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
【解答】需要考虑奇数回文串和偶数回文串两种情况。从需要补充的字符序列最少的情况开始考虑，逐步增加。迭代中首先确定疑似回文串的中心位置。
public class Solution {
public String shortestPalindrome(String s) {
if (s.length()==1)
return s;
int mid = s.length()/2;
for (int i=mid; i>=0; i--) {
String result = getPalindrome(s, i, false);
if (result!=null)
return result;
result = getPalindrome(s, i, true);
if (result!=null)
return result;
}
return null; // unreachable
}
private String getPalindrome(String s, int mid, boolean odd) {
String prepend = "";
int left;
int right;
if (odd) {
left = mid-2;
right = mid;
} else {
left = mid-1;
right = mid;
}
while (right<s.length()) {
if (left<0) {
prepend = s.charAt(right) + prepend;
right++;
} else {
if (s.charAt(left) != s.charAt(right)) {
return null;
} else {
left--;
right++;
}
}
} // while
return prepend + s;
}
}
【题目】Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
【解答】基于House Robber的题目，这个街道现在变成了一个环。因此特殊的地方在于，首尾相邻，因此本来的递归出口现在没法成立了。于是这样考虑，设最末一个房子下标为n，如果我分别看[0, n-1]和[1, n]这样两个区间，我可以保证这两个区间的情况下无论怎样抢劫，一定不会出现首尾都被抢的情况。于是给它们分别求得最大值，那么这两个最大值中的最大值，就为所求。
public class Solution {
public int rob(int[] nums) {
if (nums==null || nums.length==0)
return 0;
if (nums.length==1)
return nums[0];
Integer[] cache = new Integer[nums.length];
int res1 = rob1(nums, nums.length-2, cache);
cache = new Integer[nums.length];
int res2 = rob2(nums, nums.length-1, cache);
return Math.max(res1, res2);
}
private int rob1(int[] nums, int i, Integer[] cache) {
if (i==0)
return nums[i];
else if (i==1)
return Math.max(nums[0], nums[1]);
if (cache[i]!=null)
return cache[i];
int result = Math.max(rob1(nums, i-1, cache), rob1(nums, i-2, cache) + nums[i]);
cache[i] = result;
return result;
}
private int rob2(int[] nums, int i, Integer[] cache) {
if (i==1)
return nums[i];
else if (i==2)
return Math.max(nums[2], nums[1]);
if (cache[i]!=null)
return cache[i];
int result = Math.max(rob2(nums, i-1, cache), rob2(nums, i-2, cache) + nums[i]);
cache[i] = result;
return result;
}
}
【题目】Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
【解答】大体上有两种思路，一种是把words数组里面的每个单词取出来，分别到board里面去找；另一种是把board里面的单词取出来，挨个去words里面找。我采用的是后一种。但是，直接匹配的效率肯定过低，所以把words根据之前Trie树的经验，构造成一棵大的Trie树，然后以board里面以每一个元素作为单词起点，到这棵大Trie树中去匹配，优先考虑前缀匹配，如果前缀匹配失败，就不需要继续往下走了；如果匹配成功，再考虑完整单词匹配。
class TrieNode {
public char ch;
public Map<Character, TrieNode> subs = new HashMap<Character, TrieNode>();
// Initialize your data structure here.
public TrieNode() {
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (null == word)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!node.subs.containsKey(ch)) {
TrieNode newNode = new TrieNode();
newNode.ch = ch;
node.subs.put(ch, newNode);
}
node = node.subs.get(ch);
}
node.subs.put('\0', new TrieNode());
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (null == word)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!node.subs.containsKey(ch))
return false;
node = node.subs.get(ch);
}
return node.subs.containsKey('\0');
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (null == prefix)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if (!node.subs.containsKey(ch))
return false;
node = node.subs.get(ch);
}
return true;
}
}
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<String>();
if (board == null || board.length == 0 || board[0].length == 0
|| words == null || words.length == 0)
return result;
// build trie tree
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
boolean visited[][] = new boolean[board.length][board[0].length];
Set<String> resultSet = new HashSet<String>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
traverse(board, resultSet, "", i, j, visited, trie);
}
}
for (String word : resultSet) {
result.add(word);
}
return result;
}
private void traverse(char[][] board, Set<String> result, String word,
int i, int j, boolean[][] visited, Trie trie) {
if (i < 0 || j < 0 || i == board.length || j == board[0].length
|| visited[i][j])
return;
word = word + board[i][j];
// try this first to end most cases, or else there will be a TLE
if (!trie.startsWith(word)) {
return;
}
if (trie.search(word)) {
result.add(word);
}
visited[i][j] = true;
traverse(board, result, word, i + 1, j, visited, trie);
traverse(board, result, word, i, j + 1, visited, trie);
traverse(board, result, word, i - 1, j, visited, trie);
traverse(board, result, word, i, j - 1, visited, trie);
visited[i][j] = false;
}
}
Add and Search Word – Data structure design
【题目】Design a data structure that supports the following two operations:
void addWord(word) bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
【解答】就是实现一棵前缀树（我使用美元符作为一个单词的结束），但是需要考虑句点这种通配符。
class Node {
public char ch = '$';
public Map<Character, Node> subs = new HashMap<>();
}
public class WordDictionary {
private Node root = new Node();
// Adds a word into the data structure.
public void addWord(String word) {
if (word==null || word.length()==0)
return;
Node node = root;
for (int i=0; i<word.length(); i++) {
char ch = word.charAt(i);
if (!node.subs.containsKey(ch)) {
Node newSub = new Node();
newSub.ch = ch;
node.subs.put(ch, newSub);
}
node = node.subs.get(ch);
}
// string end
if (!node.subs.containsKey('$'))
node.subs.put('$', new Node());
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
if (word==null)
return false;
if (word.length()==0)
return true;
return search(word, 0, root);
}
private boolean search(String word, int i, Node node) {
if (i==word.length())
return node.subs.containsKey('$');
char ch = word.charAt(i);
if (ch=='.') {
for (Node sub : node.subs.values()) {
if (search(word, i+1, sub))
return true;
}
return false;
} else {
if (!node.subs.containsKey(ch)) {
return false;
} else {
return search(word, i+1, node.subs.get(ch));
}
}
}
}
【题目】There are a total of n courses you have to take, labeled from 0 to n – 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
【解答】这道题的是图论的题目，寻找一个拓扑序列，很有典型意义。我的思路大致是这样的，首先准备如下的数据结构：
- 创建一个outDegreeMap（名字取得不太好），本质上是个邻接表，key为出发节点，value为直接相邻的节点集合；
- 创建一个入度数组，记录每个节点的入度；
- 创建一个set，存放当前入度为0的节点。
这里有一个很显然，但是很重要的结论，那么当前的状况下，如果要绘制图，只有当前入度为0的节点才有资格作为起始节点。
接着，只要set不为空，就可以循环：
每次从set中取出一个节点i，这个i的入度为0，写入结果数组，然后把从这个节点指向的所有节点入度全部减一（其实就是把这个节点的所有边全部删掉，但是因为这个entry只会访问一次，因此不需要真的把边删掉），并且判断这些被指向的节点有没有出现入度为0的情况，如果有，放入set中。
在循环结束以后，如果结果数组的大小等于课程数，说明得到了解答，找到了一个合法的序列，否则说明图中存在环路。
值得注意的是，这道题中有一些陷阱：
- 在构建入度数组的时候，要判别prerequisites里面是否存在重复元素，如果存在，要跳过。
- 这个set是一个存放入度为0的，在循环的过程中不断变化的集合。一开始我拿所有元素的集合做set，每次从set中拿出元素还要判断是否入度为0，结果超时了。
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (null == prerequisites || numCourses == 0)
return new int[] {};
// to store the nodes to scan and delete
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < numCourses; i++) {
set.add(i);
}
// relations
Map<Integer, Set<Integer>> outDegreeMap = new HashMap<Integer, Set<Integer>>();
int[] inDegrees = new int[numCourses];
for (int[] pair : prerequisites) {
int from = pair[1];
int to = pair[0];
if (!outDegreeMap.containsKey(from))
outDegreeMap.put(from, new HashSet<Integer>());
if (outDegreeMap.get(from).contains(to))
continue;
outDegreeMap.get(from).add(to);
inDegrees[to]++;
set.remove(to);
}
List<Integer> resList = new ArrayList<Integer>();
while (!set.isEmpty()) {
int i = set.iterator().next();
set.remove(i);
resList.add(i);
Set<Integer> outSet = outDegreeMap.get(i);
if (outSet != null) {
for (int n : outSet) {
inDegrees[n]--;
if (inDegrees[n] == 0)
set.add(n);
}
}
} // while
if (resList.size() != numCourses)
return new int[] {};
// build result
int[] resArr = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
resArr[i] = resList.get(i);
}
return resArr;
}
}
【题目】Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
【解答】是个双指针的题，并且也是一个滑动窗口和活动窗口的题。这种题目有一个共同的套路就是：
- 用一个左指针和一个右指针控制住窗口大小和位置，然后逐步右移，通常不走回头路，因此指针移动的复杂度在n阶；
- 同时用一个合适的数据结构记录窗口内关心的内容，能够做到左右指针变化时，这个内容可以增量变化。
左指针和右指针最开始都在下标0的位置，如果当前区域[left,right]的和小于s，右指针右移；如果大于等于s，记录当前长度，并且尝试左指针右移（如果左右指针重叠则二者同时右移，因为左指针不能跑到右指针右边去）。
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums==null || nums.length==0)
return 0;
int left=0, right=0;
int sum = nums[0];
int minLen = 0;
while (true) {
if (sum>=s) {
if (minLen==0 || right-left+1<minLen)
minLen = right-left+1;
if (left!=right) {
sum -= nums[left];
left++;
} else {
left++;
right++;
if (left<nums.length)
sum = nums[left];
else
break;
}
} else {
right++;
if (right<nums.length)
sum += nums[right];
else
break;
}
}
return minLen;
}
}
【题目】Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
【解答】前缀树的实现，用’\0’来表示字符串的结束。
class TrieNode {
public char ch;
public Map<Character, TrieNode> subs = new HashMap<>();
// Initialize your data structure here.
public TrieNode() {
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (null==word)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i=0; i<word.length(); i++) {
char ch = word.charAt(i);
if (!node.subs.containsKey(ch)) {
TrieNode newNode = new TrieNode();
newNode.ch = ch;
node.subs.put(ch, newNode);
}
node = node.subs.get(ch);
}
node.subs.put('\0', new TrieNode());
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (null==word)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i=0; i<word.length(); i++) {
char ch = word.charAt(i);
if (!node.subs.containsKey(ch))
return false;
node = node.subs.get(ch);
}
return node.subs.containsKey('\0');
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (null==prefix)
throw new IllegalArgumentException();
TrieNode node = root;
for (int i=0; i<prefix.length(); i++) {
char ch = prefix.charAt(i);
if (!node.subs.containsKey(ch))
return false;
node = node.subs.get(ch);
}
return true;
}
}
【题目】There are a total of n courses you have to take, labeled from 0 to n – 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
【解答】本质上就是一个有向图，然后要寻找图中是否存在环路。我的做法是对每一个节点，都存放从它出发可达的下一个节点的列表。然后以每个节点为起始，尝试DFS，借由一个visited布尔变量来标识是否曾走过，从而识别出环（循环依赖）。LeetCode上面图的题目太少，这是其中的一道，这道题出来之前好像总共就只有一道。
class Node {
public int id = 0;
public boolean visited = false;
public Set<Node> toList = new HashSet<>();
@Override
public boolean equals(Object node) {
return ((Node)node).id == this.id;
}
}
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses<0)
return false;
if (numCourses==0 || prerequisites==null)
return true;
Node[] nodes = new Node[numCourses];
for (int i=0; i<numCourses; i++) {
nodes[i] = new Node();
nodes[i].id = i;
}
for (int i=0; i<prerequisites.length; i++) {
int from = prerequisites[i][0];
int to = prerequisites[i][1];
if (!nodes[from].toList.contains(nodes[to]))
nodes[from].toList.add(nodes[to]);
}
for (int i=0; i<nodes.length; i++) {
if (!traverse(nodes[i]))
return false;
}
return true;
}
private boolean traverse(Node node) {
if (node.visited)
return false;
node.visited = true;
for(Node to : node.toList) {
if (!traverse(to))
return false;
}
node.visited = false;
return true;
}
}
【题目】Reverse a singly linked list.
【解答】需要三个指针，两个用来给掉转指针指向，另一个用来占住下一个元素的位置。
public class Solution {
public ListNode reverseList(ListNode head) {
if (head==null)
return null;
if (head.next==null)
return head;
ListNode last = null;
ListNode first = head;
ListNode second = first.next;
while (second.next!=null) {
first.next = last;
ListNode newSecond = second.next;
second.next = first;
last = first;
first = second;
second = newSecond;
}
second.next = first;
first.next = last;
return second;
}
}
【题目】Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note:
You may assume both s and t have the same length.
【解答】其实就是要判断字符串是否模式相同，比如egg和add都满足ABB型。用一个map来存放字符相应的匹配信息，key是字符，value是字符出现的位置。当某个字符第二次在字符串s中出现时，到map中寻找它的位置，和相应在t中这次出现的字符在map中的位置比较一下，如果不匹配就返回false。
public class Solution {
public boolean isIsomorphic(String s, String t) {
if (s==null && t==null)
return true;
if (s==null || t==null || s.length()!=t.length())
return false;
Map<Character, Integer> mapS = new HashMap<>();
Map<Character, Integer> mapT = new HashMap<>();
for (int i=0; i<s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (!mapS.containsKey(sc)) {
if (mapT.containsKey(tc)) {
return false;
} else {
mapS.put(sc, i);
mapT.put(tc, i);
}
} else {
if (!mapT.containsKey(tc)) {
return false;
} else {
if (!mapS.get(sc).equals(mapT.get(tc))) {
return false;
} else {
mapS.put(sc, i);
mapT.put(tc, i);
}
}
}
}
return true;
}
}
【题目】Description:
Count the number of prime numbers less than a non-negative number, n.
【解答】prime number是质数，求小于n的质数个数。下面这个方法叫填空法，从2开始，找到一个没有填空的数（false），把它作为质数，然后把它的倍数全部填上（置为true）。
public class Solution {
public int countPrimes(int n) {
boolean[] m = new boolean[n];
int count = 0;
for (int i=2; i<n; i++) {
if (m[i])
continue;
count++;
for (int j=i; j<n; j=j+i)
m[j] = true;
}
return count;
}
}
【题目】Remove all elements from a linked list of integers that have value val.
Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5
【解答】使用一个fake head可以让条件判断更简单。
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode fakeHead = new ListNode(0);
fakeHead.next = head;
ListNode current = fakeHead;
while (current.next!=null) {
if (current.next.val==val)
current.next = current.next.next;
else
current = current.next;
}
return fakeHead.next;
}
}
【题目】Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
【解答】用一个set来存放出现过的数，如果迭代的过程中出现了一个曾经遇到的数，说明出现了循环，那么永远也不会回到1的。
public class Solution {
public boolean isHappy(int n) {
if (n<=0)
return false;
Set<Integer> set = new HashSet<>();
while (true) {
if (n==1)
return true;
if (set.contains(n))
return false;
set.add(n);
n = cal(n);
}
}
private int cal(int n) {
int result = 0;
while (n>0) {
int remainder = n%10;
result += Math.pow(remainder, 2);
n = n/10;
}
return result;
}
}
【题目】Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
【解答】刨去符号位，从最高位开始一位一位看，用掩码去掉其它位以后，剩下的就是被观察的那一位，把这一位结果放到result里面去。但是这个结果不是m和n相与的结果，而是m到n这个区间内所有数相与的结果，那怎样记录这么多数的操作结果呢？显然每个数都过一遍是不可能的。写几个数的二进制数观察一下，就能发现，其实只需要从最高位开始比较，只要有某一位上面，m和n的值不同（一个为0而另一个为1），那么可以确定的是，后面的每一位上，在m到n这个区间里面，一定既存在0，又存在1，也就是说相与的结果一定为0，因此就不用考察了。
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int mask = 1 << 30;
int result = 0;
do {
int bitM = m&mask;
int bitN = n&mask;
if ( bitM>0 && bitN>0 )
result |= mask;
else if (bitM==0 && bitN==0)
;
else
break;
mask >>= 1;
} while (mask>0);
return result;
}
}
【题目】Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110110101100000000
Answer: 1
Example 2:
11000110000010000011
Answer: 3
【解答】我的做法看起来稍微有点啰嗦。先给所有的陆地标号：
- 如果它的左侧和上面都是水，那就给它一个新的编号；
- 如果只有左侧是陆地，它的编号和左侧相同；
- 如果只有上面是陆地，它的编号和上面相同；
- 如果左侧和上面都是陆地，它的编号和左侧相同，且建立一个左侧陆地和上面陆地编号等价的关系，存放到map中。
注意在创建等价关系的map的时候，要存放双向关系，比如编号1和编号2等价，那么要能根据1找到2，也要能根据2找到1。完毕以后，遍历所有的等价关系，每次遍历都把所有的等价数全部标记一遍，然后继续寻找没有标记过的下一个数，这样就找到了实际存在的互不等价的数的个数，也即岛屿的个数。
public class Solution {
public int numIslands(char[][] grid) {
if (null == grid || grid.length == 0 || grid[0].length == 0)
return 0;
Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
char number = '2';
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '0')
continue;
// left neighbor
char left = '0';
if (j > 0)
left = grid[i][j - 1];
// upper neighbor
char top = '0';
if (i > 0)
top = grid[i - 1][j];
if (left == '0' && top == '0') {
grid[i][j] = number;
map.put(number, new HashSet<Character>());
number++;
} else if (left == '0' && top != '0') {
grid[i][j] = top;
} else if (left != '0' && top == '0') {
grid[i][j] = left;
} else { // left!=0 && top!=0
grid[i][j] = left;
if (left == top) {
if (!map.containsKey(left))
map.put(left, new HashSet<Character>());
} else {
if (!map.containsKey(top))
map.put(top, new HashSet<Character>());
if (!map.containsKey(left))
map.put(left, new HashSet<Character>());
map.get(top).add(left);
map.get(left).add(top);
}
}
}
}
boolean[] dedup = new boolean[number - '2'];
int count = 0;
for (int i = 0; i < dedup.length; i++) {
if (checkNewIsland(i, dedup, map))
count++;
}
return count;
}
private boolean checkNewIsland(int i, boolean[] dedup,
Map<Character, Set<Character>> map) {
if (dedup[i])
return false;
char ch = (char) ('2' + i);
dedup[i] = true;
Set<Character> valueSet = map.get(ch);
for (char value : valueSet) {
checkNewIsland(value - '2', dedup, map);
}
return true;
}
}
【题目】Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <--- / \ 2 3 <--- \ \ 5 4 <---
You should return [1, 3, 4].
【解答】层序遍历，并且收集每一层的最右侧元素。
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (null==root)
return ret;
List<TreeNode> list = new ArrayList<>();
list.add(root);
while (!list.isEmpty()) {
ret.add(list.get(list.size()-1).val);
List<TreeNode> newList = new ArrayList<>();
for (TreeNode node : list) {
if (node.left!=null)
newList.add(node.left);
if (node.right!=null)
newList.add(node.right);
}
list = newList;
}
return ret;
}
}
【题目】You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
【解答】动态规划，用一个整型数组来存储当street长度为i的时候（比如为f），能抢劫的最大money数量。所以有递推关系f(i) = max(f(i-1), f(i-2)+nums[i])。
如果你和我一样，可能会说，不对啊，这个递推关系有点问题，上式中f(i-1)的这种情况下，如果第i个房子并未被抢劫，那么上面的式子应该变成f(i) = max(f(i-1)+nums[i], f(i-2)+nums[i])啊。
没错，但是这种case下，f(i-1)不正等于f(i-2)么？因此这种case其实也被原递推关系式覆盖到了！
这个问题想通以后，写代码就很顺利了。
public class Solution {
public int rob(int[] nums) {
if (nums==null || nums.length==0)
return 0;
Integer[] cache = new Integer[nums.length];
return rob(nums, nums.length-1, cache);
}
private int rob(int[] nums, int i, Integer[] cache) {
if (i==0)
return nums[i];
else if (i==1)
return Math.max(nums[0], nums[1]);
if (cache[i]!=null)
return cache[i];
int result = Math.max(rob(nums, i-1, cache), rob(nums, i-2, cache) + nums[i]);
cache[i] = result;
return result;
}
}
【题目】Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.
【解答】首先处理符号位，负数的时候，数据是以补码形式存放的，与上一个Integer.MAX_VALUE可以保留除了符号位以外的全部1的非负数，注意不要直接取反，因为绝对值相同的正负数的符号位以外的数据表示是不相同的。处理完负数以后，就可以不断用除和取余来统计1的个数了。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
if (n<0) {
count++;
n &= Integer.MAX_VALUE;
}
while (n>0) {
count += n%2;
n = n/2;
}
return count;
}
}
【题目】Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?
Related problem: Reverse Integer
【解答】无符号整型，但是Java里面没有这样的数据类型，只能用一个普通整型来模拟它。和上面那道方法类似，首先还是处理负数，把它转成正数以后来处理。然后把各个位上面是1还是0统计下来，放到数组里面。最后用不断左移来构造新数。不要忘记符号位。
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
boolean[] cache = new boolean[32];
if (n<0) {
cache[31] = true;
n &= Integer.MAX_VALUE;
}
for (int i=0; i<=30 ;i++) {
if (n%2>0)
cache[i] = true;
n /= 2;
}
// build the new number
int res = 0;
for (int i=1; i<=31; i++) {
res = res << 1;
if (cache[i])
res += 1;
}
// sign
if (cache[0])
res |= Integer.MIN_VALUE;
return res;
}
}
【题目】Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Related problem: Reverse Words in a String II
【解答】有一个比较巧的办法。比如题中的例子：1, 2, 3, 4, 5, 6, 7，
- 先左边部分左右反向：1,2,3,4变成4,3,2,1；
- 再右边部分左右反向：5, 6, 7变成7, 6, 5，这样整体就变成了4, 3, 2, 1, 7, 6, 5；
- 最后整体左右反向：5, 6, 7, 1, 2, 3, 4。
注意两点，
- k要对数组长度取余；
- 注意左右部分的分界线位置。
public class Solution {
public void rotate(int[] nums, int k) {
int remainder = k % nums.length;
if (remainder == 0)
return;
reverse (nums, 0, nums.length-1-remainder);
reverse (nums, nums.length-remainder, nums.length-1);
reverse (nums, 0, nums.length-1);
}
private void reverse (int[] nums, int start, int end) {
int mid = (start+end)/2;
for (int i=start; i<=mid; i++)
swap ( nums, i, start+(end-i) );
}
private void swap (int[] nums, int i, int j) {
if (i==j)
return;
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
}
Best Time to Buy and Sell Stock IV
【题目】Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
【解答】这道题真难，即便能够想到应该是类似DP的做法，还是很难找递推关系式。下面的办法也不是我独立思考，而是借鉴而来的，很巧妙。首先考虑当k比prices价格还大的情况，问题就变成了《Best Time to Buy and Sell Stock II》那道题了，再来看剩下的情况，这个DP的递推关系式是，假设profits(x)表示完成x次交易时的最大收益，那么：
profits(x) = profits(x-1) + prices(i)*factor, 其中i∈[0, prices.length) 且 (若x为奇数，factor为-1；若x为偶数，factor为1）
具体说：
- 整体方法还是动态规划，但是问题需要理解成：其实就是从prices数组里面依次挑价格，并把它们按照一正一负的作用效果来组成一个整型数组，其中奇数为负，偶数为正，总交易额为它们的和。
- 于是设一个长度为2k+1的整型数组profits，其中profits[i]表示第i次交易完成时，获得的最大总收益。
- 对于prices每个元素，对于j从1到尽可能大的值，都尝试profits[j-1] + prices[i]*factor，其中factor只是起到一个正负号的作用，在这时第i个元素prices[i]扮演了“当时的最后一次交易的价格”的角色。在这一次的循环中只留下一个最大的profit。
- 最后，profits[2k]即为所求。
public class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0 || prices.length==1)
return 0;
if(k>prices.length/2)
return maxProfitForBigK(prices);
Integer[] profits = new Integer[2*k+1];
profits[0] = 0;
for (int i=0; i<prices.length; i++) {
for (int j=1; j<=Math.min(2*k, i+1); j++) {
int factor = j%2!=0 ? -1 : 1;
int profit = profits[j-1]+prices[i]*factor;
if (profits[j]==null || profits[j]<profit)
profits[j] = profit;
}
}
return profits[2*k];
}
private int maxProfitForBigK(int[] prices) {
int total = 0;
for (int i=0; i<prices.length-1; i++)
if(prices[i+1]-prices[i]>0)
total += prices[i+1]-prices[i];
return total;
}
}
【题目】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"].
【解答】这道题的基本思路是在从左往右遍历的过程中，要存放所有连续出现的十个字母到一个集合中，每次新的连续十个字母出现时，就到集合中寻找是否已经出现过。
但特殊的地方在于，只是这样某些case会超时的，而题目有一个特点是，s中可能出现的字符只有四种可能：A、C、G、T。正好，如果有一个2 bit的数，正好可以用1、2、3、4来分别表示，那么10个数就用掉20 bit而已。而一个整型数有32 bit，用来表示十个数是绰绰有余了。
值得注意的一点是，在这个容纳十个字符的滑动窗口向右移动的过程当中，需要注意不要每次都全部重新计算得出新10个字符所对应的整数，而是使用增量的方式，先所有数整体左移两位，再把超过20位的两位数用掩码干掉，最低两位放进新的字母所代表的数。
这道题纯粹就是位运算了，可以总结一下位运算常见的考点：
- 掩码的使用；
- 左移、右移；
- 与、或和异或；
- 正整数和负整数的二进制表示。
public class Solution {
private static int MASK = ((int)Math.pow(2, 18))-1;
public List<String> findRepeatedDnaSequences(String s) {
List<String> list = new ArrayList<>();
if (s.length()<=10)
return list;
Set<Integer> set = new HashSet<>();
Set<Integer> resultSet = new HashSet<>();
Integer num = null;
for (int i=0; i<s.length()-9; i++) {
if (num==null)
num = toInteger(s, i);
else
num = toIntegerIncremental(s, i-1, num);
if (set.contains(num))
resultSet.add(num);
else
set.add(num);
}
for (int resultNum : resultSet) {
String str = toString(resultNum);
list.add(str);
}
return list;
}
private String toString(int num) {
String res = "";
for (int i=0; i<10; i++) {
int item = num & 3;
if (item==0)
res = 'A' + res;
else if (item==1)
res = 'C' + res;
else if (item==2)
res = 'G' + res;
else if (item==3)
res = 'T' + res;
num = num >> 2;
}
return res;
}
private int toInteger(String s, int start) {
int result = 0;
for (int i=0; i<10; i++) {
char ch = s.charAt(start+i);
result = result << 2;
if (ch=='A')
result |= 0;
else if (ch=='C')
result |= 1;
else if (ch=='G')
result |= 2;
else if (ch=='T')
result |= 3;
}
return result;
}
private int toIntegerIncremental(String s, int removedPos, int baseInteger) {
baseInteger &= MASK;
baseInteger = baseInteger << 2;
char ch = s.charAt(removedPos+10);
if (ch=='A')
baseInteger |= 0;
else if (ch=='C')
baseInteger |= 1;
else if (ch=='G')
baseInteger |= 2;
else if (ch=='T')
baseInteger |= 3;
return baseInteger;
}
}
【题目】Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
【解答】我开始的做法是，转化成字符串比较，但是遇到 12 和 123 这样一个串是另一个串的前缀怎么办？我就做法就是把长串靠前面的共同短串截取，之后的那个字符和它本来前面那个字符比较，如果更大，这个长串要往前放；反之往后放。比如 12 和 123 中，3要大于2，因此123往前放，因此最后结果是12312；再比如 32 和 321 ，1要小于2，因此321要往后放，因此最后结果是32321。
public class Solution {
public String largestNumber(int[] num) {
Integer[] numbers = new Integer[num.length];
for (int i=0; i<num.length; i++) {
numbers[i] = num[i];
}
Arrays.sort(numbers, new Comparator<Integer>(){
@Override
public int compare(Integer left, Integer right) {
String ls = left + "";
String rs = right + "";
// return -ls.compareTo(rs);
int ll = ls.length();
int rl = rs.length();
for (int i=0; i<Math.min(ll, rl); i++) {
if (ls.charAt(i)>rs.charAt(i))
return -1;
else if (ls.charAt(i)<rs.charAt(i))
return 1;
}
if (ll>rl) {
char base = ls.charAt(rl-1);
int i=rl;
while (i<ll) {
char ch = ls.charAt(i);
if (ch>base)
return -1;
else if(ch<base)
return 1;
i++;
}
} else if (ll<rl) {
char base = rs.charAt(ll-1);
int i=ll;
while (i<rl) {
char ch = rs.charAt(i);
if (ch>base)
return 1;
else if (ch<base)
return -1;
i++;
}
}
return 0;
}
});
StringBuilder sb = new StringBuilder();
boolean headingZero = true;
for (int n : numbers) {
if (headingZero) {
if (n==0)
continue;
else
headingZero = false;
}
sb.append(n);
}
String ret = sb.toString();
if ("".equals(ret))
return "0";
return ret;
}
}
可是遇到这个case的时候傻眼了：
Input: [824,938,1399,5607,6973,5703,9609,4398,8247] Output: "9609938824782469735703560743981399" Expected:"9609938824824769735703560743981399"
这个case其实可以简化成 824 和 8247 这两个数，就能重现问题。原来我原有的判定逻辑就不正确。
我觉得正确的做法应该把较小的那个串作为循环节，较大串去掉较小串以后，相当于较小串指针移到头部继续比较，比如 1212123 和 12 进行比较时，1212123 把 12 重复了三遍，之后那个数是3，要比1大，因此结果应是121212312。
public class Solution {
public String largestNumber(int[] num) {
Integer[] numbers = new Integer[num.length];
for (int i = 0; i < num.length; i++) {
numbers[i] = num[i];
}
Arrays.sort(numbers, new Comparator<Integer>() {
@Override
public int compare(Integer left, Integer right) {
String ls = left + "";
String rs = right + "";
// return -ls.compareTo(rs);
int ll = ls.length();
int rl = rs.length();
for (int i = 0; i < Math.min(ll, rl); i++) {
if (ls.charAt(i) > rs.charAt(i))
return -1;
else if (ls.charAt(i) < rs.charAt(i))
return 1;
}
if (ll > rl) {
int li = rl;
int ri = 0;
while (li < ll) {
if (ri == rl)
ri = 0;
if (ls.charAt(li) < rs.charAt(ri))
return 1;
else if (ls.charAt(li) > rs.charAt(ri))
return -1;
ri++;
li++;
}
} else if (ll < rl) {
int ri = ll;
int li = 0;
while (ri < rl) {
if (li == ll)
li = 0;
if (ls.charAt(li) < rs.charAt(ri))
return 1;
else if (ls.charAt(li) > rs.charAt(ri))
return -1;
ri++;
li++;
}
}
return 0;
}
});
StringBuilder sb = new StringBuilder();
boolean headingZero = true;
for (int n : numbers) {
if (headingZero) {
if (n == 0)
continue;
else
headingZero = false;
}
sb.append(n);
}
String ret = sb.toString();
if ("".equals(ret))
return "0";
return ret;
}
}
可是结果依然是错误的：
Input: [121,12] Output: "12112" Expected:"12121"
原因在于，当较长串扣除若干个较短串了以后，剩下的部分，如果依然是循环节的一部分，这种情况会比较复杂。虽然也能继续下去，但是显然这已经不是一个好的解决办法了。
一个比较好的思路是，我根本不要去比较两个数个体之间的前后关系，那样太困难，因为二者长度不同，不变检查；但是我去比较这两个数不同前后排列组合后形成的数的前后关系，比如 12 和 123，我不比较他们谁在前面，而是比较不同的前后排列组合，即 12312 和 12123 谁更大，这带来的好处就是，两个数长度相等，比较显而易见，于是代码变得非常简洁：
public class Solution {
public String largestNumber(int[] num) {
Integer[] numbers = new Integer[num.length];
for (int i = 0; i < num.length; i++) {
numbers[i] = num[i];
}
Arrays.sort(numbers, new Comparator<Integer>() {
@Override
public int compare(Integer left, Integer right) {
String s1 = "" + left + right;
String s2 = "" + right + left;
return s2.compareTo(s1);
}
});
StringBuilder sb = new StringBuilder();
boolean headingZero = true;
for (int n : numbers) {
if (headingZero) {
if (n == 0)
continue;
else
headingZero = false;
}
sb.append(n);
}
String ret = sb.toString();
if ("".equals(ret))
return "0";
return ret;
}
}
【题目】The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0′s) or contain magic orbs that increase the knight’s health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
Notes:
- The knight’s health has no upper bound.
- Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
【解答】这让我想起了龙与地下城的游戏啊。一看就想到是DP，但是DP的构造递推关系是关键，我一开始没有想对，导致走上了一条又复杂又做不对的路上：我想“把起点固定在(0, 0)，用arr[i][j]表示终点在(i,j)时，起点所需最小的HP”，但是问题在于，在这种情况下如果我知道arr[i-1][j]和arr[i][j-1]，我其实是很难得到arr[i][j]的。举个例子：
1, -3, 3, 0, -2, 0, -3,-3,-3
看这样一个矩阵，要求arr[2][2]，但是arr[2][1]为2，arr[1][2]为2，考虑到dungeon[2][2]=-3，求得arr[2][2]=5。这是错的，正确答案应该是arr[2][2]=3。错误的原因就是在于递推关系的考察上面，arr[i-1][j]以及arr[i][j-1]，这两者其实并无法推出arr[i][j]。
后来把思路倒过来，“把终点固定在(dungeon.length-1, dungeon[0].length-1)，而arr[i][j]表示起点为(i, j)所需的最小HP”，这时问题就豁然开朗了：arr[i][j] = min(arr[i-1][j], arr[i][j-1]) – dungeon[i][j]。当然需要注意生命值在任何时候都不能小于1。
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
Integer[][] arr = new Integer[dungeon.length][dungeon[0].length];
return calculate(dungeon, 0, 0, arr);
}
// return the min HP from (i, j) to the end (dungeon.length-1, dungeon[0].length-1)
private int calculate(int[][] dungeon, int i, int j, Integer[][] arr) {
if (arr[i][j] != null)
return arr[i][j];
if (dungeon.length-1==i && dungeon[0].length-1==j) {
arr[i][j] = Math.max(1, -dungeon[i][j]+1);
return arr[i][j];
}
int fromRow = Integer.MAX_VALUE;
if (i<dungeon.length-1) {
int past = calculate(dungeon, i+1, j, arr);
fromRow = Math.max(1, past-dungeon[i][j]);
}
int fromCol = Integer.MAX_VALUE;
if (j<dungeon[0].length-1) {
int past = calculate(dungeon, i, j+1, arr);
fromCol = Math.max(1, past-dungeon[i][j]);
}
arr[i][j] = Math.min(fromRow, fromCol);
return arr[i][j];
}
}
虽然看起来不新鲜，但其实这道题收获还是挺大的。
【题目】Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
【解答】注意root为空的情况。用一个stack放置parent节点，构造方法里面，循环往左孩子节点顺下去，一顺到底；对每个节点访问以后，都尝试寻找右孩子节点，如果找到，就从右孩子节点开始，循环往它的做孩子节点顺下去，一顺到底，如果没有右孩子节点，就尝试出栈。
public class BSTIterator {
private Stack<TreeNode> stack = new Stack<>();
private TreeNode node;
public BSTIterator(TreeNode root) {
node = root;
while (node!=null && node.left!=null) {
stack.push(node);
node = node.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return node!=null;
}
/** @return the next smallest number */
public int next() {
int ret = node.val;
if (node.right!=null) {
node = node.right;
while (node.left!=null) {
stack.push(node);
node = node.left;
}
} else if (!stack.isEmpty()) {
node = stack.pop();
} else {
node = null;
}
return ret;
}
}
【题目】Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
【解答】要找末尾0的个数，0只可能由2乘以5造出来，如果你说10也可能啊，但是10也是2乘以5。因此，我只需要统计2和5的个数，选择这两个个数中较小的一个即可。于是我对每个数统计2和5的个数，并累加：
public class Solution {
public int trailingZeroes(int n) {
int twos = 0;
int fives = 0;
for (int i=1; i<=n; i++) {
int num = i;
while (num%2==0) {
twos++;
num = num/2;
}
while (num%5==0) {
fives++;
num = num/5;
}
}
return Math.min(twos, fives);
}
}
结果，Time Limit Exceeded。我只能继续想法子改进：
以求5的个数为例，2的个数求法也是类似的。给定一个数，比如6，那么6的阶乘中，5的个数是6/5，为1，因为只有这个数是5或者5的倍数的时候才会出现因子5，这里不整除没有关系，只需要找整数部分即可。但是如果这个数是26呢，26/5，结果为5，但是26的阶乘里面却有6个5，因为26/5的结果5本身也是5的倍数，因此可见这里有一个递归求5的个数的过程在里面：
public class Solution {
public int trailingZeroes(int n) {
if (n==0)
return 0;
int fives = n/5;
fives += trailingZeroes(fives);
int twos = n/2;
twos += trailingZeroes(twos);
return Math.min(fives, twos);
}
}
【题目】Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
【解答】没什么说的。
public class Solution {
public int titleToNumber(String s) {
if (null==s || s.equals("")) {
return 0;
}
int total = 0;
for (int i=s.length()-1; i>=0; i--) {
int n = s.charAt(i) - 'A' + 1;
total += Math.pow(26, s.length()-i-1)*n;
}
return total;
}
}
【题目】Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
【解答】没啥说的。
public class Solution {
public int majorityElement(int[] num) {
Map<Integer, Integer> map = new HashMap<>();
int cap = num.length/2;
for (int n : num) {
if (!map.containsKey(n))
map.put(n, 1);
else
map.put(n, map.get(n)+1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue()>cap) {
return entry.getKey();
}
}
return 0; // unreachable
}
}
【题目】Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
【解答】看着挺简单，但是还是没能一遍做对。看起来就是一个从十进制转成二十六进制的题目，但是它的起始数值是1，而不是0，这就意味着，循环中每一轮，拿到一个数的时候，都要先把它减一，才能继续按照自己习惯的二十六进制的思路来进行。
public class Solution {
public String convertToTitle(int n) {
String s = "";
while (true) {
n = n-1;
int remainder = n%26;
n = n/26;
s = (char)(remainder+'A') + s;
if (n==0)
break;
}
return s;
}
}
【题目】Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
- Given numerator = 1, denominator = 2, return “0.5″.
- Given numerator = 2, denominator = 1, return “2″.
- Given numerator = 2, denominator = 3, return “0.(6)”.
【解答】首先，要知道这样一件事情，在不断做除法往后求小数位数的时候，如果遇到某一位的计算，商和余数都在前面某一位上出现过，这就意味着循环节已经寻找完毕。知道这一点以后，就有思路并且可以写代码了。大致思路是，用一个map来存放之前小数计算过程中遇到过数值，key是商和余数组成的对象，值是当时出现这个情况的小数位数（从0开始）。但是这道题陷阱我还是踩了，就是整型溢出的问题，尤其是求绝对值的代码如果写成Math.abs(numerator)的话，要知道Math.abs(Integer.MIN_VALUE)会导致溢出的，无法得到正确的正数，因此需要Math.abs((long)(numerator))。因此谁都知道要当心整数溢出，可实际使用中还是会遇上。同事说简单的题目要写bug free的代码如何如何，可真要写bug free的代码真是太难了，即便是很简单的题目。
class Item {
long quotient;
long remainder;
public Item(long quotient, long remainder) {
this.quotient = quotient;
this.remainder = remainder;
}
@Override
public boolean equals(Object p) {
Item another = (Item) p;
return another.quotient == this.quotient
&& another.remainder == this.remainder;
}
@Override
public int hashCode() {
return (int) (new Long(this.quotient).hashCode() ^ new Long(
this.remainder));
}
}
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().fractionToDecimal(1, 6));
}
public String fractionToDecimal(int numerator, int denominator) {
String negative = "";
if ((numerator < 0 && denominator > 0)
|| (numerator > 0 && denominator < 0))
negative = "-";
long numeratorL = Math.abs((long)(numerator));
long denominatorL = Math.abs((long)(denominator));
long inte = numeratorL / denominatorL;
long remainder = numeratorL % denominatorL;
String fraction = "";
Map<Item, Integer> map = new HashMap<Item, Integer>();
int pos = 0;
while (remainder != 0) {
remainder *= 10;
long quotient = remainder / denominatorL;
remainder = remainder % denominator;
Item item = new Item(quotient, remainder);
if (map.containsKey(item)) {
int startPos = map.get(item);
fraction = fraction.substring(0, startPos) + '('
+ fraction.substring(startPos) + ')';
break;
} else {
fraction += quotient;
map.put(item, pos);
pos++;
}
}
if ("".equals(fraction))
return negative + inte;
else
return negative + inte + "." + fraction;
}
}
【题目】Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
【解答】没什么可说的，注意有大于一个的点号。
public class Solution {
public int compareVersion(String version1, String version2) {
String[] tokens1 = version1.split("\\.");
String[] tokens2 = version2.split("\\.");
return compareVersion(tokens1, tokens2, 0);
}
private int compareVersion(String[] tokens1, String[] tokens2, int pos) {
if (tokens1.length<=pos && tokens2.length<=pos)
return 0;
int v1 = 0;
if (tokens1.length>pos)
v1 = Integer.parseInt(tokens1[pos]);
int v2 = 0;
if (tokens2.length>pos)
v2 = Integer.parseInt(tokens2[pos]);
if (v1>v2)
return 1;
else if (v1<v2)
return -1;
return compareVersion(tokens1, tokens2, pos+1);
}
}
【题目】Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
【解答】注意题目要求solve in linear time/space，因此普通的排序不能考虑，因为普通的排序复杂度都是n(log n)的，考虑到这些数都是32-bit signed integer，因此说白了就是0~2^31，我最先考虑搞一个boolean数组存放这些可能的数，下标表示实际数值-1（这里“-1”是因为考虑到数组最大只能表示2^31-1，而0用额外的另一个boolean变量表示）：
public class Solution {
public int maximumGap(int[] num) {
boolean arr[] = new boolean[Integer.MAX_VALUE]; // 0 ~ 2147483647-1
boolean zero = false;
for (int n : num) {
if (n==0)
zero = true;
else
arr[n-1] = true;
}
int gap = 0;
Integer last = null;
if (zero)
last = 0;
for (int i=0; i<arr.length; i++) {
if (arr[i]) {
if (last==null) {
last = i+1;
} else {
if (i+1-last>gap)
gap = i+1-last;
}
}
}
return gap;
}
}
不过申请那么大一个数组，不出意外地出现了java.lang.OutOfMemoryError: Java heap space。因此要调整一下思路，我原来的方法相当于先做了一个“计数排序”，这种特殊的排序方法使得线性时间复杂度成为可能，还有一些排序方法也具备接近线性时间复杂度的，比如基数排序，比如桶排序，这些思路从实质上说起来有很多类似的地方。我下面采用类似基数排序的思路，由于所有数值都不会超过十位数，因此构建一棵树，每个非叶子节点都有10个子节点（十叉树），从根节点开始，每深一层（深度从0开始算起），从根到叶子路径上位于第i层的节点就是从最高位开始数第i位数值的表示。比如123可表示为0000000123，进而表示为这样的从根到叶子节点的路径：
root – nexts[0] – nexts[0] – nexts[0] – nexts[0] – nexts[0] – nexts[0] – nexts[0] – nexts[1] – nexts[2] – value: 123
在这种方式下，空间复杂度和入参数组的长度是线性相关的，时间复杂度也是（因为树的深度只有10）。注意代码中Item节点里面的nextIndex的作用，这个指的是在求max gap的过程中，我实际做的是深度优先遍历，因此需要一个stack保存前一层节点访问的状态，而这个nextIndex表示的是该节点再出栈时应该访问第几个孩子节点了。
class Item {
Item[] nexts = new Item[10];
Integer val = null;
int nextIndex = 0;
}
public class Solution {
public int maximumGap(int[] num) {
Item head = new Item();
// build tree
for (int i = 0; i < num.length; i++) {
// 0~2147483647
Item node = head;
int n = num[i];
for (int j = 1000000000; j >= 1; j = j / 10) {
int digit = n / j;
n = n % j;
if (node.nexts[digit] == null)
node.nexts[digit] = new Item();
node = node.nexts[digit];
if (j == 1)
node.val = num[i];
}
}
Stack<Item> stack = new Stack<Item>();
stack.push(head);
Integer last = null;
int maxGap = 0;
Item node = null;
// calculate gaps, DFS
while (!stack.isEmpty()) {
if (node == null)
node = stack.pop();
if (node.val != null) {
if (last != null)
maxGap = Math.max(maxGap, node.val - last);
last = node.val;
node = null;
} else {
int index = node.nextIndex;
if (index != 9) {
node.nextIndex++;
stack.push(node);
}
node = node.nexts[index];
}
}
return maxGap;
}
}
【题目】A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
【解答】唯一要小心的地方在于Integer.MIN_VALUE上面，我转成了long型，就避开了越界的问题。
public class Solution {
public int findPeakElement(int[] num) {
for (int i=0; i<num.length; i++) {
long prev;
if (i==0)
prev = Integer.MIN_VALUE-1l;
else
prev = num[i-1];
long next;
if (i==num.length-1)
next = Integer.MIN_VALUE-1l;
else
next = num[i+1];
if (num[i]>prev && num[i]>next)
return i;
}
return -1;
}
}
Intersection of Two Linked Lists
【题目】Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
【解答】注意要求时间复杂度O(n)和空间复杂度O(1)。在草稿纸上画一下A和B的图示，可以发现在交汇以后，右侧的部分可以认为A和B是等长的，因此A和B长度的不同就只在左侧。比如A长于B，那么长就长在左侧未交汇的部分，那我让A的指针先走A.length()-B.length()，这样就可以保证之后A和B一齐前进的时候，一定能在交汇点处相遇。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA==null || headB==null)
return null;
int lenA = length(headA);
int lenB = length(headB);
if (lenA>lenB) {
int steps = lenA-lenB;
while (steps>0) {
headA = headA.next;
steps--;
}
} else if (lenB>lenA) {
int steps = lenB-lenA;
while (steps>0) {
headB = headB.next;
steps--;
}
}
ListNode nodeA = headA;
ListNode nodeB = headB;
while (nodeA!=null) {
if (nodeA==nodeB)
return nodeA;
nodeA = nodeA.next;
nodeB = nodeB.next;
}
return null;
}
private int length(ListNode head) {
int len = 1;
ListNode node = head;
while (node.next!=null) {
node = node.next;
len++;
}
return len;
}
}
【题目】Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- 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.
【解答】需要注意时间复杂度是常数阶的，前三个方法很容易做到常数阶，因此只需要额外考虑getMin方法就可以了。
class MinStack {
static class Item {
int min;
int val;
Item prev;
}
private Item tail = null;
public void push(int x) {
Item item = new Item();
item.val = x;
if (tail==null)
item.min = x;
else
item.min = Math.min(tail.min, x);
item.prev = tail;
tail = item;
}
public void pop() {
if (tail==null)
throw new RuntimeException("no data");
tail = tail.prev;
}
public int top() {
if (tail==null)
throw new RuntimeException("no data");
return tail.val;
}
public int getMin() {
if (tail==null)
throw new RuntimeException("no data");
return tail.min;
}
}
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接《四火的唠叨》
由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!
