难度中等

图论的好多东西都忘记了，看了题解才想起来二分图的定义和处理。

主要思路是染色法，对每一个节点进行染色。对未染色的节点优先染成红色，之后对它的邻接节点染成绿色，再对邻接节点进行同样的操作。如果发现邻接节点的颜色与要染的颜色相反（红绿相对）就能判定该图不能形成二分图。

class Solution {private static final int UNCOLORED = 0;private static final int RED = 1;private static final int GREEN = 2;private int[] color;private boolean valid;public boolean isBipartite(int[][] graph) {int n = graph.length;valid = true;color = new int[n];// Arrays.fill(color, UNCOLORED);for (int i = 0; i < n && valid; ++i) {if (color[i] == UNCOLORED) {dfs(i, RED, graph);}}return valid;}public void dfs(int node, int c, int[][] graph) {color[node] = c;int cNei = c == RED ? GREEN : RED;for (int neighbor : graph[node]) {if (color[neighbor] == UNCOLORED) {dfs(neighbor, cNei, graph);if (!valid) {return;}} else if (color[neighbor] != cNei) {valid = false;return;}}}
}

难度中等

双百哦，自己写出来的。

class Solution {public int search(int[] arr, int target) {return search(arr, target, 0, arr.length - 1);}public int searchByOrder(int[] arr, int target, int begin, int end){for(int i = begin;i <= end;i++){if(arr[i] == target){return i;}}return -1;}public int search(int[] arr, int target, int begin, int end){while(begin <= end){int mid = begin + (end - begin) / 2;//特殊情况，三个位置的值都相同，就顺序遍历if(arr[begin] == arr[mid] && arr[mid] == arr[end]){return searchByOrder(arr, target, begin, end);}//找到目标值if(arr[mid] == target){//找到最小的索引while(mid >= 0 && arr[mid] == target){mid--;}return mid + 1;}else if(arr[begin] < arr[mid]){//前面的序列是有序的if(arr[mid] > target){end = mid - 1;}else{begin = mid + 1;}}else{//前面的序列是无序，就需要对前后数组都进行搜索int l = search(arr, target, begin, mid - 1);int r = search(arr, target, mid + 1, end);if(l == -1 || r == -1){return Math.max(l, r);}return Math.min(l, r);}}return -1;}
}

难度简单

因为是排序好的数组，所以可以用二分查找来解决。不过因为存在空字符串，所以这部分不可避免要顺序查找到非空字符串。

class Solution {public int findString(String[] words, String s) {return findString(words, s, 0, words.length - 1);}public int findString(String[] words, String s, int begin, int end){int mid;while(begin <= end){mid = begin + (end - begin) / 2;int index = mid;while(mid <= end && words[mid].equals("")){mid++;}if(mid == end + 1){end = index - 1;continue;}if(words[mid].equals(s)){return mid;}else if(words[mid].compareTo(s) > 0){end = index - 1;}else{begin = index + 1;}}return -1;}
}

难度中等

观察矩阵我们可以发现，从矩阵的左下方出发，向右是增大，向上是减小。所以我们可以根据这个特性来找到解决方法。类似于走路时选择路口，当遇到对应的条件时就选择对应的路口。如果走到了边界还没有找到目标值，那么就不包含该元素。（参照了题解）

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = matrix.length - 1, j = 0;while(i > -1 && j < matrix[0].length){if(matrix[i][j] == target){return true;}else if(matrix[i][j] < target){j++;}else{i--;}}return false;}
}

难度中等

因为峰和谷的位置是确定的，（第一位为0）偶数为峰，奇数为谷。所以只要判断每一个位置的元素是否满足要求。如果不满足要求就交换位置。

class Solution {public void wiggleSort(int[] nums) {for(int i = 1;i < nums.length; i++){if((i % 2 == 0 && nums[i] < nums[i - 1]) || (i % 2 != 0 && nums[i] > nums[i - 1])){int temp = nums[i];nums[i] = nums[i - 1];nums[i - 1] = temp;}}}
}

难度中等

将两个数加在一起，利用数学的特性就行了。

class Solution {public int[] swapNumbers(int[] numbers) {numbers[0] = numbers[0] + numbers[1];numbers[1] = numbers[0] - numbers[1];numbers[0] = numbers[0] - numbers[1];return numbers;}
}

难度中等

一个哈希表解决？感觉是不是有点简单。

class WordsFrequency {Map<String, Integer> map = new HashMap<>();public WordsFrequency(String[] book) {for(String s : book){if(map.containsKey(s)){map.put(s, map.get(s) + 1);}else{map.put(s, 1);}}}public int get(String word) {if(!map.containsKey(word)){return 0;}return map.get(word);}
}/*** Your WordsFrequency object will be instantiated and called as such:* WordsFrequency obj = new WordsFrequency(book);* int param_1 = obj.get(word);*/

难度中等

为了方便处理，先将这个String数组转变成char的二维数组。之后对遍历到的每个位置去判断行列是否满足要求，特殊处理是最左上角和最右上角存在对角线的可能性，需要进行额外的处理。

当然可以进行优化，只有当i0和j0时才会对对应的对应的行和列进行遍历匹配。

class Solution {public String tictactoe(String[] board) {boolean pending = false;int n = board.length;char[][] arr = new char[n][n];for(int i = 0;i < board.length;i++){arr[i] = board[i].toCharArray();}for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){char c = arr[i][j];if(c == ' '){pending = true;continue;}else if(c == 'O'){//判断if(win(arr, c, i, j)){return "O";}}else if(c == 'X'){if(win(arr, c, i, j)){return "X";}}}}if(pending){return "Pending";}else{return "Draw";}}//行public boolean winRow(char[][] arr, char c, int row){for(int i = 0;i < arr.length;i++){if(arr[row][i] != c){return false;}}return true;}//列public boolean winColumn(char[][] arr, char c, int column){for(int i = 0;i < arr.length;i++){if(arr[i][column] != c){return false;}}return true;}//左对角线public boolean winLeftUpLine(char[][] arr, char c, int index){while(index < arr.length){if(arr[index][index] != c){return false;}index++;}return true;}//右对角线public boolean winRightDownLine(char[][] arr, char c, int index){int n = arr.length;while(index >= 0){if(arr[n - index - 1][index] != c){return false;}index--;}return true;}public boolean win(char[][] arr, char c, int i, int j){boolean winRow = winRow(arr, c, i);boolean winColumn = winColumn(arr, c, j);if(i == 0 && j == 0){return winRow || winColumn || winLeftUpLine(arr, c, i);}if(i == 0 && j == arr.length - 1){return winRow || winColumn || winRightDownLine(arr, c, j);}return winColumn || winRow;}
}

难度中等

自己写的时候发现溢出情况有点难解决。参照了题解，为了解决溢出问题，我们先将差用负值的形式表现出来。最后再把它转变成正数。

class Solution {public static int smallestDifference(int[] a, int[] b) {if (a == null || b == null || a.length == 0 || b.length == 0) return -1;int minDiff = Integer.MIN_VALUE , aIdx = 0 , bIdx = 0;//为了使用二分，所以要先进行排序Arrays.sort(a);Arrays.sort(b);while (aIdx < a.length && bIdx < b.length) {//关键，解决溢出 ， 负数域 大于 正数域。minDiff = Math.max(minDiff, -Math.abs(a[aIdx] - b[bIdx]));if (a[aIdx] < b[bIdx]) {aIdx++;}else {bIdx++;}}//反置return Math.abs(minDiff);}
}

难度简单

数学问题，参照了题解

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CxtpEMeA-1594980833091)(C:\Users\ASUS\AppData\Roaming\Typora\typora-user-images\image-20200717133948078.png)]

class Solution {public int maximum(int a, int b) {long c = a;long d = b;int res = (int) ((Math.abs(c-d) + c + d)/2);return res;}
}

难度中等

没什么思路。看了题解说这是一个套路题，用一个前缀和数组表示之前存活的人数。这个数组中的最大值就是存活的最大人数。

class Solution {public int maxAliveYear(int[] birth, int[] death) {int[] live = new int[102];for(int birthYear : birth){live[birthYear - 1900]++;}for(int deadYear : death){live[deadYear - 1900 + 1]--;}int[] preSum = new int[102];//用一个前缀和表示之前存活的人数int year = 1900;int maxNum = -1;preSum[0] = live[0];for(int i = 1;i < live.length;i++){preSum[i] = live[i] + preSum[i - 1];if(preSum[i] > maxNum){year = i + 1900;maxNum = preSum[i];}}return year;}
}

难度简单

一个简单的数学问题。

class Solution {public int[] divingBoard(int shorter, int longer, int k) {if (k == 0) {return new int[0];}if (shorter == longer) {return new int[]{shorter * k};}int[] lengths = new int[k + 1];for (int i = 0; i <= k; i++) {lengths[i] = shorter * (k - i) + longer * i;}return lengths;}
}

难度中等

我太蠢了，怎么都没思路。一看题解，我怎么那么笨。因为碰撞会掉头，当碰撞时我们可以想象成两只蚂蚁穿透而过，这个题就变成了求蚂蚁离边缘的最大距离。

class Solution {public int getLastMoment(int n, int[] left, int[] right) {int ans = 0;for(int i = 0;i < left.length;i++){ans = Math.max(ans, left[i]);}for(int i = 0;i < right.length;i++){ans = Math.max(ans,n -  right[i]);}return ans;}
}