June

1051. 高度检查器 // 6-13

public static int heightChecker(int[] heights) {
int [] resArr = heights;
Arrays.sort(heights);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (heights[i]!=resArr[i]){
count++;
}
}
return count;
}
结果：测试用例为0
原因：Arrays.sort方法会将数组改为有序的 resAr和heights 指向为同一数组。
解决：那就复制一份数组
public static int heightChecker(int[] heights) {
int [] resArr = Arrays.copyOf(heights,heights.length);
Arrays.sort(heights);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (heights[i]!=resArr[i]){
count++;
}
}
return count;
}

计算排序：去题解偷学
public static int heightChecker(int[] heights) {
// int max = arrMax(heights);
int[] arr = new int[101];
for (int i = 0; i < heights.length; i++) {
arr[heights[i]]++;
}
// System.out.println(Arrays.toString(arr));
int count = 0;
for (int i = 0, j =0; i < arr.length; i++) {
while (arr[i]— != 0){
if (i != heights[j++] ) count++;
}
}
return count;
}
吧所有的从低到高收集到各个桶中,类似桶排序，在遍历时对比。

498. 对角线遍历 //6-14

public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] res = new int[m * n];
int pos = 0;
for (int i = 0; i < m + n - 1; i++) {
if (i % 2 == 0) { //向上走
int x = i < m ? i : m-1;
int y = i < m ? 0 : i-m+1; //加1是因为m是长度 从1开始的
while (x>=0&&y res[pos] = mat[x][y];
pos++;
x—;
y++;
}

    } else {<br />            int x = i<n? 0: i - n +1;<br />            int y = i<n? i: n-1;<br />            while (x<m&&y>=0){<br />                res[pos] = mat[x][y];<br />                pos++;<br />                y--;<br />                x++;<br />            }<br />        }<br />    }<br />    return res;<br />}

719. 找出第 K 小的数对距离 //6-15

public static int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int l = 0, r = nums[nums.length-1]-nums[0];
while (l < r) {
int mid = l + r >> 1;
if (check(nums, mid) >= k) r =mid;
else l=mid+1;
}
return l;
}
public static int check(int[] nums, int num) {
int length = nums.length,ans = 0;
for (int i = 0, j = 1; i while(j ans += j-i-1;
}
return ans;
}
对于俩层遍历超内存，o(n2)超时,o(n)不现实。那就需要考虑o（nlogn）

532. 数组中的 k-diff 数对 //6-16

public static int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int count = 0;
for (int i = 0; i < n - 1; i++) {
if (i>=1){
if (nums[i] == nums[i - 1]) continue;}
int j = i + 1;
while (j<=n-1&&nums[j] - nums[i] <= k) {
if (nums[j] - nums[i] == k) {
count++;
break;
}
j++;
}
}
return count;
}
俩层遍历，对每个数字遍历时，找到一个就可以继续下一个数的遍历寻找了，还需判断和前一个数字是否一样？就跳过该次循环：正常遍历寻找。

1089. 复写零 //6-17

public static void duplicateZeros(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
if (arr[i] == 0){
for (int j = n-2; j >=i ; j—) {
arr[j+1] = arr[j];
if (j==i){
i++;
}
}
}
}
}
遍历到0的时候把从0到最后的元素移动一格，顺便也复制了一个0。

剑指 Offer II 029. 排序的循环链表 //6-18

public Node insert(Node head, int insertVal) {
Node node = new Node(insertVal);
if (head == null) {
node.next = node;
return node;
}
if (head.next==head){
head.next=node;
node.next=head;
return head;
}
Node cur = head;
Node curNext =head.next;
do {
if (cur.val<=insertVal && curNext.val>=insertVal){
cur.next =node;
node.next=curNext;
break;
}
if (cur.val>curNext.val &&(insertVal>cur.val || insertVal cur.next = node;
node.next =curNext;
break;
}
cur =cur.next;
curNext = curNext.next;
}while (cur !=head);
cur.next =node;
node.next = curNext;
return head;
}
对各种情况进行模拟，1个或0个，遍历全局一次，简单的在顺序中插入，在最大值和最小值的边界上，如果插入的值大于最大值或者小于最小值，都将值插入到该位置上。如果遍历完发现没找到，那就是所有值都都是一样的，那就随便插入即可。

508. 出现次数最多的子树元素和 //6-19

class Solution {
HashMap map = new HashMap<>();
Integer maxCount =0;
public int[] findFrequentTreeSum(TreeNode root) {
dfs(root);
ArrayList list = new ArrayList<>();
for (Map.Entry entry:map.entrySet()) {
if (entry.getValue() == maxCount) list.add(entry.getKey());
}
int size=list.size();
int[] arr= new int[size];
for (int i = 0; i < size; i++) {
arr[i] = list.get(i);
}
return arr;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int sum = node.val+dfs(node.left)+dfs(node.right);
map.put(sum, map.getOrDefault(sum, 0) + 1);
maxCount= Math.max(map.get(sum),maxCount);
return sum;
}
}
体会：dfs算法得多加熟悉一下，数组的size和遍历的关系，因为小于关系不需要-1。

715. Range 模块

skip。。。。。。。