211. Add and Search Word - Data structure design
建立一棵字典树，特别注意.的情况。
public class WordDictionary {
public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
}
private TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}
public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}
private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return !node.item.equals("");
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
} else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
}
213. House Robber II
分两种情况遍历两遍数组即可，第一遍是可以偷第一个，不能偷最后一个，第二遍时可以偷最后一个，不能偷第一个。
class Solution {
public int rob(int[] nums) {
int res = 0;
if(nums == null || nums.length==0)
return res;
if(nums.length==1)
return nums[0];
if(nums.length==2)
return Math.max(nums[0],nums[1]);
int[] temp = new int[nums.length-1];
temp[0] = nums[0];
temp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length-1;i++){
temp[i] = Math.max(nums[i] + temp[i-2],temp[i-1]);
}
res = temp[nums.length-2];
temp[0] = nums[1];
temp[1] = Math.max(nums[1],nums[2]);
for(int i=3;i<nums.length;i++){
temp[i-1] = Math.max(nums[i] + temp[i-3],temp[i-2]);
}
res = Math.max(res,temp[nums.length-2]);
return res;
}
}
215. Kth Largest Element in an Array
如果求第K大的元素，那么要构建的是小顶堆。求第K小的元素，那么要构建大顶堆！先构建k个元素的堆，另外i-k个元素逐个跟堆顶元素比较，如果比堆顶元素小，那么就将该元素纳入堆中，并保持堆的性质。
当然这里只是为了复习一下堆排序所以用了这个方法，还有很多方法比如快速排序等都可以使用。
class Solution {
public int findKthLargest(int[] nums, int k) {
heapSort(nums,k);
return nums[0];
}
public static void heapSort(int[] nums,int k){
for(int i=k/2;i>=0;i--){
perceDown(nums,i,k);
}
System.out.println(nums[0]);
for(int i=k;i<nums.length;i++){
if (nums[i] <= nums[0])
continue;
else{
nums[0] = nums[I];
perceDown(nums,0,k);
}
}
}
public static void perceDown(int[] nums,int index,int k){
int temp = nums[index];
int child = 2 * index + 1;
while(child < k){
if(child + 1 < k && nums[child+1] < nums[child])
child = child + 1;
if(temp >nums[child]){
nums[index] = nums[child];
index= child;
child = 2 * index + 1;
}
else
break;
}
nums[index] = temp;
}
}
216. Combination Sum III
回溯法的使用，这里犯了一个小错误，Arraylist remove删除的是对应索引位置的元素，而不是删除指定值的元素。
class Solution {
public List<List<Integer>> res;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<List<Integer>>();
backpop(1,k,n,new ArrayList<Integer>());
return res;
}
public void backpop(int start,int k,int n,List<Integer> single){
if(n==0 && k==0){
res.add(new ArrayList<Integer>(single));
return;
}
if(n < start)
return;
for(int i=start;i<=9;i++){
single.add(i);
backpop(i+1,k-1,n-i,single);
single.remove(single.size()-1);
}
}
}
217. Contains Duplicate
使用一个Hashset即可，可以节省空间
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for(int num:nums){
if(!set.contains(num))
set.add(num);
else
return true;
}
return false;
}
}
219. Contains Duplicate II
由于涉及到位置信息，所以这次用Map保存。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(!map.containsKey(nums[I]))
map.put(nums[i],i);
else{
if ((i - map.get(nums[i])) <= k)
return true;
map.put(nums[i],i);
}
}
return false;
}
}
220. Contains Duplicate III
这道题使用到了java中的TreeSet，有关TreeSet，我们后面会详细介绍，这里贴一个链接已备查：https://blog.csdn.net/thinking2013/article/details/46336373
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> ts = new TreeSet<Long>();
for(int i=0;i<nums.length;i++){
if(i-k-1>=0)
ts.remove((long)nums[i-k-1]);
//返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
Long tmp = ts.ceiling((long)nums[I]);
if(tmp != null && t>=Math.abs(tmp-nums[i])) return true;
//返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。
tmp = ts.floor((long)nums[I]);
if(tmp!=null && t>= Math.abs(nums[i] - tmp)) return true;
ts.add((long)nums[i]);
}
return false;
}
}
