【LeetCode刷题篇零】一些基础算法知识和前置技能（下）

数组常用技巧

使用数组代替Map

使用另一个数组来统计每个数字出现的次数，数组的下标作为key, 数组的值作为value，

将数字作为数组的下标索引，数组里的值存储该数字出现的次数，原理有点类似桶排序中使用的计数数组。

比如这里如果1出现了2次，就将索引0的位置存储为2，4出现了1次，就索引3的位置存储为1。

这个做法同样适用于字符串，可以建立一个长度26的整数数组来统计字符串中每个字符出现的次数，前提是只有a-z组成的小写字母（或只有大写字母）

如果是包含大小写字母的字符串，可以使用长度 128 的计数数组，即包含 [A-Z] 和 [a-z] 的ASII码即可。

此题可以用计数数组统计方法，但是空间复杂度不符合 O(1) 要求，如果空间复杂度没有要求的话，完全可以用计数数组。

方法1. 交换到正确的位置：

• 利用数组 [1, 2, ..., N] 特性 nums[i] = i + 1, 如果 nums[nums[i] - 1] != nums[i]，就不停交换 nums[i] - 1 和 i 位置上的数，最后扫描一遍满足 nums[i] != i + 1 的数就是重复的。

这里如果是找缺失的，保存的结果是 i + 1 就行

方法2. 置为负数：

• 不断将 index = nums[i] - 1 处的数字置为负数，如果该位置已经为负，说明重复, 如果找缺失的就判断正的才置为负数，最终还是正数的就是缺失的

方法3. +N:

• 不断将 index = nums[i] - 1 处的数字加 n (数组长度)，最终大于2n的位置的索引+1就是结果值，如果找缺失的就判断小于等于n

交换数组中的两个数

Java 交换两个数的三种方法：

1.使用一个临时变量暂存两个中的某一个的值

2. 两数相加保存和值

3.两数异或保存

二维数组转一维数组（下标转换）

matrix[i][j] --> data[ i * 列数 + j ]

一维数组转二维数组（下标转换）

data[i] --> matrix[ i / 列数 ][ i % 列数 ]

二维数组的四联通（方向数组）

访问二维数组中四个邻居元素的小技巧：directions数组

这个技巧在一些二维矩阵题目的DFS和BFS解法中经常使用到。

二维数组的八联通（方向数组）

注意防止下标访问越界问题：

Java 内置List、数组、Map等常用方法

这里只是列出一些在刷题过程中可能用到的，或者说比较有用的Java Api 方法，这些方法在平时开发中