这是一道hard的题目，在此之前，先看与之类似的easy的题目：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:1
2Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
合并两个已排序的链表，非常简单，分别从头开始遍历，并对比，将小的数添加到前面即可。如下：
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:1
2
3
411110
11010
11000
00000
Answer: 1
Example 2:1
2
3
411000
11000
00100
00011
Answer: 3
这道题比较简单，很容易就能想到遍历到grid(x, y) = 1的上下左右各数，如果为1则与grid(x, y)在同一个“岛屿”。深度优先搜索正好可以应用在这种场景下。
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
题目的意思是合并交集。假设有集合组[1,3],[2,6],[8,10],[15,18]，如下图：
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 11
2Input: [3,0,1]
Output: 2
Example 21
2Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Examples:1
2
3
4
5s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
通过之前的练习LeetCode#242，很容易就能想到使用数组来记录字母出现的次数，然后找到字符串中，第一个出现次数为1的字符。如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14int unique(s) // s is the target string
if (s = null)
return -1
count = new int[26]
chars = s.toCharArray()
for (c in chars)
count[c - 'a']++
for (i = 0; i < chars.length; i++)
if (count[chars[i] - 'a']-- = 0)
return i
return -1
上述答案还可以通过消除减法来降低耗时。因为题目规定字符串中只包含小写字母，因此可以不考虑扩展ASCII码，也就是创建一个长度为128的数组，从而避免减法。
Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
Note:
You may assume the string contains only lowercase alphabets.
既然只有小写字母，那就可以通过一个长度为26的数组记录第一个字符串中的字符出现的次数，再通过遍历第二个字符串并做减法，如果某个字符对应的次数小于0，则说明两个字符串不是变位词。1
2
3
4
5
6
7
8
9
10
11
12boolean isAnagram(s1, s2)
count = new int[26]
chars1 = s1.toCharArray()
for (c in chars1)
count[c - 'a']++
chars2 = s2.toCharArray()
for (c in chars2)
if (count[c - 'a']-- == 0)
return false
return true
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.
这道题很简单，可以先排序，中间的数就是答案。1
2
3int majority(nums) // nums is a integer array
sort(nums)
return nums[nums.length / 2]
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given _a_ = 1 and _b_ = 2, return 3.
按照题目的要求，不能使用+和-，那只能使用位运算了。这样的话，很容易就能想到使用&来进行计算，通过计算两个数每一位的与，以及下一位与的结果，就可以知道当前位的值。但是由于不能用+，所以即使计算出了结果的每一位，也没办法计算出最后的值。
既然&可以计算出进位，那么是否有其他的位运算可以计算出当前位的值？那就是^了。通过异或计算出的值是不含进位的，因此在异或之后需要和进位结果再异或一次，以得出新的值。但是这次计算又可能产生新的进位，因此需要循环直到不再含有进位。代码如下：1
2
3
4
5int getSum(a, b)
while (b != 0)
carry = a & b // 计算出需要进位的位
a = a ^ b
b = carry << 1 // 左移一位即可得出进位结果
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
这是一道典型的二叉树遍历题目，可以查看之前对于“树的遍历”的介绍。可以选择深度优先搜索递归法解决：1
2
3
4
5
6
7
8
9int depth(node)
return depth(node, 0)
int depth(node, depth)
if (node = null)
return depth
depth++
return max(depth(node.left, depth), depth(node.right, depth))
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?