**299. Bulls and Cows
思路：抽屉法，放进secrets，拿出guess，最终cows = cows - bulls
public String getHint(String secret, String guess) {
int bulls = 0;
int cows = 0;
int[] numbers = new int[10];
for(int i = 0; i < secret.length(); i++){
if(secret.charAt(i) == guess.charAt(i)) bulls++;
numbers[secret.charAt(i) - '0']++;
}
for(int i = 0; i < guess.length(); i++){
if(numbers[guess.charAt(i) - '0'] > 0) cows++;
numbers[guess.charAt(i) - '0']--;
}
cows = cows - bulls;
return bulls + "A" + cows + "B";
}
**380. Insert Delete GetRandom O(1)
思路：用空间复杂度换取时间复杂度，没有重复则用HashSet
public class RandomizedSet {
/** Initialize your data structure here. */
public RandomizedSet() {
//list是由数组实现的，因此增加删除的复杂度为O(n),需要用空间复杂度换取时间复杂度
list = new ArrayList<Integer>();
map = new HashMap<Integer,Integer>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) return false;
else{
map.put(val,list.size());
list.add(val);
}
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. 由于删除时同时要删除list和map中的元素，保证O(1)则多了一个替换操作保证删除最后一个元素*/
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
else{
int loc = map.get(val);
if(loc < list.size() - 1){
int value = list.get(list.size() - 1);
list.set(loc,value);
map.put(value,loc);
}
map.remove(val);
list.remove(list.size() - 1);
}
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Random rand = new Random();
return list.get(rand.nextInt(list.size()));
}
private ArrayList<Integer> list;
private HashMap<Integer,Integer> map;
}
**381. Insert Delete GetRandom O(1) - Duplicates allowed
思路同上
public class RandomizedCollection {
/** Initialize your data structure here. */
public RandomizedCollection() {
//ArrayList是用数组实现的，LinkedHashSet继承HashSet，是由map实现的，remove操作时间复杂度为O(1),而且能根据添加顺序遍历
list = new ArrayList<Integer>();
map = new HashMap<Integer,LinkedHashSet<Integer>>();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)){
map.get(val).add(list.size());
list.add(val);
return false;
}
else{
map.put(val,new LinkedHashSet<Integer>());
map.get(val).add(list.size());
list.add(val);
}
return true;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false;
else{
int loc = map.get(val).iterator().next();
map.get(val).remove(loc);
if(loc < list.size() - 1){
int value = list.get(list.size() - 1);
list.set(loc,value);
map.get(value).add(loc);
map.get(value).remove(list.size() - 1);
}
list.remove(list.size() - 1);
if(map.get(val).isEmpty()) map.remove(val);
}
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
Random rand = new Random();
return list.get(rand.nextInt(list.size()));
}
private ArrayList<Integer> list;
private HashMap<Integer,LinkedHashSet<Integer>> map;
}
37. Sudoku Solver
思路：回溯，每次遇到'.'则循环遍历0-9看看符不符合，符合则递归调用继续填空，若所有都符合则满足，否则回溯，注意判断符合时的算法
public void solveSudoku(char[][] board) {
if(board.length == 0 || board[0].length == 0) return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char k = '1'; k <= '9'; k++){
if(isValid(board,i,j,k)){
board[i][j] = k;
if(solve(board)) return true;
else board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board,int row,int col,char c){
for(int i = 0; i < 9; i++){
if(board[row][i] != '.' && board[row][i] == c) return false;
if(board[i][col] != '.' && board[i][col] == c) return false;
if(board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] != '.' && board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == c) return false;
}
return true;
}
149. Max Points on a Line
思路：两层循环，每次统计相同的点、斜率为无穷的点和其他斜率的点，用map存斜率和个数，每一趟算一个最大值，注意存的时候需要先将int转化成double再计算
public int maxPoints(Point[] points) {
if(points.length <= 2) return points.length;
int res = 0;
for(int i = 0; i < points.length; i++){
HashMap<Double,Integer> map = new HashMap<Double,Integer>();
int count = 0;
int samePoint = 1;
int infinite = 0;
for(int j = 0; j < points.length; j++){
if(i != j){
if(points[i].x == points[j].x && points[i].y == points[j].y) samePoint++;
else if(points[i].x == points[j].x) infinite++;
else{
double dist = ((double)points[j].y - points[i].y) / (points[j].x - points[i].x);
if(map.containsKey(dist)) map.put(dist,map.get(dist) + 1);
else map.put(dist,1);
}
}
}
map.put((double)Integer.MAX_VALUE,infinite);
for(Integer val : map.values()){
count = Math.max(count,val + samePoint);
}
res = Math.max(res,count);
}
return res;
}
**316. Remove Duplicate Letters
思路：用map存下字符和相应的位置，这样就得到了最终结果的所有字符和它们出现的最后位置，然后开始索引为0，结束索引为values中最小的索引，需要连接的字符一定在这个范围中，每趟更新开始索引、结束索引以及map
public String removeDuplicateLetters(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i = 0; i < s.length(); i++){
map.put(s.charAt(i),i);
}
StringBuffer res = new StringBuffer();
int len = map.size();
int j = 0;
int begin = 0;
int end = findMin(map);
while(j < len){
char c = 'z';
int index = end;
for(int k = begin; k <= end; k++){
if(map.containsKey(s.charAt(k)) && s.charAt(k) < c){
c = s.charAt(k);
index = k;
}
}
res = res.append(c);
j++;
if(map.containsKey(c)) map.remove(c);
begin = index + 1;
end = findMin(map);
}
return res.toString();
}
public int findMin(Map<Character,Integer> map){
if(map.isEmpty()) return -1;
int min = Integer.MAX_VALUE;
for(int val : map.values()){
min = Math.min(min,val);
}
return min;
}
总结
349. Intersection of Two Arrays：可以用两个HashSet降低时间复杂度，也可以用一个HashSet对数组进行排序以后用两个指针降低空间复杂度
350. Intersection of Two Arrays II：可以用HashMap存元素和数量，也可以排序后用双指针
36. Valid Sudoku:构造三个二维数组，分别代表行、列和块，每次遇到数字则将对应行的相应index置为1，以后再遇到则返回false,注意第i行第j列的位置对应块的block[i / 3 * 3 + j / 3][num]
290. Word Pattern：用空格分隔以后，用HashMap存两个数组的元素，注意如果key不存在要判断原来是否已经有该value，用map.containsValue()确保一一对应
136. Single Number:依次异或，最后剩下的那个数就是要求的那个数
389. Find the Difference：抽屉法，放进s，拿出t
242. Valid Anagram：可以排序依次比较，也可以用抽屉法
205. Isomorphic Strings：用HashMap存两个string的字符，同290注意如果key不存在要判断原来是否已经有该value，用map.containsValue()确保一一对应
409. Longest Palindrome：用HashMap存字符和个数，偶数直接加num，奇数则加上num - 1，用标志位判断有没有奇数，有最后结果再加一
454. 4Sum II：用HashMap存前两个数组中任意元素组合之和以及个数，然后用同样的方法遍历后两个数组，能得到相反数则加上个数
274. H-Index：排序以后从后往前遍历
187. Repeated DNA Sequences：循环截取前10个字符，存入map，注意当出现重复字符串时只有当前个数为1才能返回结果，防止将同一结果返回多次
347. Top K Frequent Elements：利用map和PriorityQueue自定义排序得到topK
训练
463. Island Perimeter：遇到1则数island个数，看island右边和下面是否相邻着island，数neighbor，最后得island * 4 - neighbor * 2(只需看右边和下面)
447. Number of Boomerangs：用HashMap存距离和相同距离的个数，每次循环完计算个数以后清空map
438. Find All Anagrams in a String：从s开头循环，每次取p长度字符，判断和p是不是相同，注意判断方法用抽屉法，排序后equals会超时
451. Sort Characters By Frequency：使用优先队列PriorityQueue自定义排序，注意Map.Entry map.entrySet的使用方式
**138. Copy List with Random Pointer：利用map依次复制，第一次遍历复制label，第二次遍历复制next和random指针
提示
数据结构：
1.遇到不重复问题就想到HashSet
2.有对应关系想到map
3.熟练使用ArrayList LinkedList PriorityQueue HashMap HashSet TreeSet LinkedHashSet以及如何利用它们实现排序，看源码