由于个人精力有限，文章是从个人博客拷贝过来的，如果文章格式和链接跳转有问题，还请见谅！也可以在我的个人博客观看。另外简书上的文章会不定期更新，如果您觉得文章对你有用，欢迎关注我的个人博客。
最新内容快捷入口：图片平滑器
本文内容摘选自LeetCode-数组
所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按无序的形式组织起来的一种形式。
由简入难，我会从不同难度的数组算法题中挑选一些有代表性的进行解答。
简单
1 两数之和
<span id="q1"></span>
该题是算法题的第一道题，在之前的文章中解答过，这里不在重复解答。见LeetCode-算法题。
26 删除排序数组中的重复项
<span id="q26"></span>
该题在之前的文章中解答过，见LeetCode-算法题。该题首次提到了原地算法和双指针法，值得看一下。
118 杨辉三角
<span id="q118"></span>
作者：LeetCode
链接：地址
来源：力扣（LeetCode）
问题描述
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例：
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
我的解答
经过之前几十道算法题的洗礼，我在解答这道题时并没有花费什么功夫，思路也很简单，明白了每行的每个元素怎么求值题就解了。元素求值有两种方式：
- 每行的第一个和最后一个元素值恒为1
- 每对相邻的元素值的和是下一行对应元素的值。
Java语言实现。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> rowList = new ArrayList<>(numRows);
for (int row = 0; row < numRows; row++) {
List<Integer> colList = new ArrayList<>(row + 1);
rowList.add(colList);
for (int col = 0; col <= row; col++) {
if (col == 0 || col == row) {
colList.add(1);
} else {
List<Integer> lastRowList = rowList.get(row - 1);
colList.add(lastRowList.get(col - 1) + lastRowList.get(col));
}
}
}
return rowList;
}
}
Kotlin语言实现，思路同上面的Java实现。
/*
执行用时 : 248 ms, 在所有 Kotlin 提交中击败了 72.22% 的用户
内存消耗 : 32.1 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution {
fun generate(numRows: Int): List<List<Int>> {
val list = mutableListOf<MutableList<Int>>()
for (row in 0 until numRows) {
list.add(mutableListOf())
for (col in 0..row) {
if (col == 0 || col == row) {
list[row].add(1)
} else {
list[row].add(list[row-1][col-1] + list[row-1][col])
}
}
}
return list
}
}
官方解答
作者：LeetCode
链接：地址
来源：力扣（LeetCode）
方法：动态规划
实现思路和我的思路一致，这里不再累述，只贴出代码实现。但还是建议看下原文链接，有动态演示，很方便理解。
虽然这一算法非常简单，但用于构造杨辉三角的迭代方法可以归类为动态规划，因为我们需要基于前一行来构造每一行。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
// First base case; if user requests zero rows, they get zero rows.
if (numRows == 0) {
return triangle;
}
// Second base case; first row is always [1].
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
for (int rowNum = 1; rowNum < numRows; rowNum++) {
List<Integer> row = new ArrayList<>();
List<Integer> prevRow = triangle.get(rowNum-1);
// The first row element is always 1.
row.add(1);
// Each triangle element (other than the first and last of each row)
// is equal to the sum of the elements above-and-to-the-left and
// above-and-to-the-right.
for (int j = 1; j < rowNum; j++) {
row.add(prevRow.get(j-1) + prevRow.get(j));
}
// The last row element is always 1.
row.add(1);
triangle.add(row);
}
return triangle;
}
}
169 求众数
<span id="q169"></span>
作者：LeetCode
链接：地址
来源：力扣（LeetCode）
问题描述
给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于n/2的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
我的解答
这道题正确解答很简单，解法也有很多种，但是想解的好却不容易。短时间内我也只写出了下面两种解法，虽然想到了分治法也能求解，但是没有用代码实现。建议看看下面的官方题解，一些解法真的巧妙！
哈希表
思路很简单，用一个循环遍历数组，将元素和元素出现的次数存入到哈希表，最后迭代哈希表得到众数。
class Solution {
/*
执行用时 : 456 ms, 在所有 Kotlin 提交中击败了 48.15% 的用户
内存消耗 : 50.2 MB, 在所有 Kotlin 提交中击败了 75.00% 的用户
*/
fun majorityElement(nums: IntArray): Int {
val map = mutableMapOf<Int, Int>()
for (num in nums) {
map[num] = (map[num] ?: 0) + 1
}
val tmp = nums.size.div(2)
map.forEach { (key, value) ->
if (value > tmp) {
return key
}
}
throw Error()
}
}
暴力法
双重循环求解，外层循环控制元素，内层循环计算元素出现的次数，当出现满足众数条件时返回元素。
由于该解法使用双重循环，导致执行用时过高，远超出我预期。
class Solution {
/*
执行用时 : 2604 ms, 在所有 Kotlin 提交中击败了 7.41% 的用户
内存消耗 : 50.3 MB, 在所有 Kotlin 提交中击败了 75.00% 的用户
*/
fun majorityElement(nums: IntArray): Int {
val majorityCount = nums.size.div(2)
var count: Int
for (num in nums) {
count = 0
for (num2 in nums) {
if (num2 == num) {
count++
}
}
if (count > majorityCount) {
return num
}
}
throw Error()
}
}
官方题解
作者：LeetCode
链接：地址
来源：力扣（LeetCode）
这里过滤了一些常规解答，只列出了比较巧妙的解法，对其他解法感兴趣的同学可以点击地址看下。
排序
所有解法中代码行数最少，只有两行：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
思路：满足众数条件的元素，出现的次数超出了数组总长度的一半，那么在为数组排序后，数组最中间的元素肯定就是众数！
[3,2,3] 排序后：[2,3,3]，最中间的元素是：3
[2,2,1,1,1,2,2] 排序后：[1,1,1,2,2,2,2]，最中间的元素是：2
随机化
思路：由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它的值是否是众数，如果是就返回，否则继续随机挑选。
class Solution {
private int randRange(Random rand, int min, int max) {
return rand.nextInt(max - min) + min;
}
// 统计指定数字在数组中出现的次数
private int countOccurences(int[] nums, int num) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
public int majorityElement(int[] nums) {
Random rand = new Random();
int majorityCount = nums.length/2;
while (true) {
int candidate = nums[randRange(rand, 0, nums.length)];
if (countOccurences(nums, candidate) > majorityCount) {
return candidate;
}
}
}
}
Boyer-Moore 投票算法
该算法的思路及其巧妙，在看完时对作者竖然起敬，然后发现这不是“开心消消乐”吗？！
思路
- 如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
- 定义一个候选众数 candidate，再维护一个计数器 count。遇到和 candidate 相同的数字， count 加一，否则 count 减一。当 count 等于0时，忽略钱买额数字，将候选众数 candidate 改为下一个数字，计数器 count 重置为0。这样最后剩下的候选众数 candidate 就是要求的众数。
- 来看两个示例（竖线用来划分每次计数器归零的情况）。
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
448 找到所有数组中消失的数字
<span id="q448"></span>
作者：LeetCode
链接：地址
来源：力扣（LeetCode）
问题描述
给定一个范围在1 ≤ a[i] ≤ n（n=数组大小）的整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
我的解答
该题还是有一定的难度的，尤其是要求不使用额外空间且时间复杂度为O(n)的情况下完成这个任务。
- 思索来思索去，并没有想到优雅些的解决办法，所以使用暴力法进行求解，结果提交后没有通过。又审了几遍题，发现是我忽略了一点：n=数组大小，找出[1, n]范围之间没有出现在数组中的数字，惭愧的很。
- 修改后再次提交，顺利通过，但执行结果惨不忍睹。再来！
- 使用动态规划求解，执行结果有些超出预期，但代码实现可读性有些差。再来！
- 修改后的动态规划代码实现看起来就舒服了一些！
收工，看下官方题解。
暴力法
/**
* 解答错误
*/
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val disNums = arrayListOf<Int>()
if (nums.size <= 1) return disNums
nums.sort()
for (el in nums[0]..nums[nums.lastIndex]) {
if (!nums.contains(el)) {
disNums.add(el)
}
}
return disNums
}
}
修改后的暴力法
/**
* 执行用时 : 2232 ms, 在所有 Kotlin 提交中击败了 25.00% 的用户
* 内存消耗 : 52.4 MB, 在所有 Kotlin 提交中击败了 50.00% 的用户
*/
class Solution2 {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val disNums = arrayListOf<Int>()
for (el in 1..nums.size) {
if (!nums.contains(el)) {
disNums.add(el)
}
}
return disNums
}
}
动态规划
/**
* 执行用时 : 472 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
* 内存消耗 : 50.8 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val disNums = arrayListOf<Int>()
nums.sort()
nums.forEachIndexed { index, el ->
val tmp = if (index > 0) nums[index-1]+1 else 1
if (el > tmp) {
for (diff in tmp until el) {
disNums.add(diff)
}
}
if (index == nums.lastIndex && el < nums.size) {
for (diff in el+1..nums.size) {
disNums.add(diff)
}
}
}
return disNums
}
}
优化过的动态规划
/**
* 执行用时 : 480 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
* 内存消耗 : 51 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val disNums = arrayListOf<Int>()
if (nums.isEmpty()) return disNums
nums.sort()
fun addByDiff(from: Int, untilTo: Int) {
for (el in from until untilTo) {
disNums.add(el)
}
}
nums.forEachIndexed { index, el ->
if (index == 0) {
if (el > 1) {
addByDiff(1, el)
}
} else if (el > nums[index-1]+1) {
addByDiff(nums[index-1]+1, el)
}
}
if (nums[nums.lastIndex] < nums.size) {
for (el in nums[nums.lastIndex]+1..nums.size) {
disNums.add(el)
}
}
return disNums
}
}
精选题解
作者：haydenmiao
链接：地址
来源：力扣（LeetCode）
思路：
- 将数组元素对应为索引的位置加n
- 遍历加n后的数组，若数组元素值小于等于n，则说明数组下标值不存在，即消失的数字
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> res;
if(nums.empty()) return nums;
for(int i=0;i<nums.size();i++)
{
int index=(nums[i]-1)%nums.size();
nums[index]+=nums.size();
}
for(int i=0;i<nums.size();i++)
{
if(nums[i]<=nums.size())
res.push_back(i+1);
}
return res;
}
};
作者没有使用Java和Kotlin语言实现该解题思路，我使用Kotlin语言进行了实现。
/**
* 执行用时 : 392 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
* 内存消耗 : 49.6 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution4 {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
val disNums = arrayListOf<Int>()
if (nums.isEmpty()) return disNums
for (el in nums) {
nums[(el-1) % nums.size] += nums.size
}
nums.forEachIndexed { index, el ->
if (el <= nums.size) {
disNums.add(index+1)
}
}
return disNums
}
}
566 重塑矩阵
<span id="q566"></span>
作者：LeetCode
来源：力扣（LeetCode）
链接：地址
在MATLAB中，有一个非常有用的函数reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例 1:
输入:
nums = [[1,2],[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:
输入:
nums = [[1,2],[3,4]]
r = 2, c = 4
输出:
[[1,2],[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：
给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。
我的解答
解题思路：
- 先判断原始矩阵和转换后的新矩阵的元素个数是否相等。
- 若相等，说明可以转换；若不相等，说明不能转换。
- 使用“双指针”：rowCount和colCount代表原始矩阵的行和列，依次取出原始矩阵中的元素存放到新矩阵中即可。
/**
* 执行用时 : 328 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
* 内存消耗 : 44.9 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution {
fun matrixReshape(nums: Array<IntArray>, r: Int, c: Int): Array<IntArray> {
if (r * c != nums.size * nums[0].size) {
return nums
}
val result = mutableListOf<IntArray>()
var rowCount = 0
var colCount = 0
for (_r in 0 until r) {
val rowArray = mutableListOf<Int>()
for (_c in 0 until c) {
rowArray.add(nums[rowCount][colCount])
colCount++
if (colCount > nums[rowCount].lastIndex) {
rowCount++
colCount = 0
}
}
result.add(rowArray.toIntArray())
}
return result.toTypedArray()
}
}
官方题解
作者：LeetCode
链接：题解
来源：力扣（LeetCode）
看了官方题解后，发现我的解答法是“不用额外空间”，不过官方给出的题解思路很相似，复杂度上也都相同，该题并没有特别“巧妙”的解法。
使用队列 [通过]
最简单的方法是通过以行方式读取元素来提取给定矩阵的所有元素。在此实现中，我们使用队列来放置提取的元素。然后，我们可以取出以串行顺序形成的队列元素，并再次按行逐行排列所得到的所需矩阵中的元素。
如果原始矩阵中的元素数量不等于所得矩阵中的元素数量，则不可能形成所得矩阵。
public class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int count = 0;
Queue < Integer > queue = new LinkedList < > ();
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
queue.add(nums[i][j]);
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
res[i][j] = queue.remove();
}
}
return res;
}
}
不用额外空间 [通过]
我们不必像在暴力方法中那样不必要地使用队列，而是可以在逐行顺序迭代给定矩阵的同时，直接将数字放在结果矩阵中。在将数字放入结果数组时，我们固定一个特定的行，并继续增加列数，直到我们到达cc指示的所需列的末尾。此时，我们通过递增来更新行索引，并将列索引重置为从0开始。因此，我们可以节省队列消耗的空间，以便存储只需要复制到新数组中的数据。
public class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int rows = 0, cols = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
res[rows][cols] = nums[i][j];
cols++;
if (cols == c) {
rows++;
cols = 0;
}
}
}
return res;
}
}
除法和取模 [通过]
在上一种方法中，我们需要跟踪我们何时到达结果矩阵的列的末尾，并且需要通过每次检查当前索引来更新当前行和列号以放置提取的元素。我们可以利用数学来帮助解决，而不是在每一步都进行限制性检查。
这种方法背后的想法如下。
你知道二维数组是如何存储在主存中的（本质上是一维）吗？它仅在内部表示为一维阵列。
元素 nums[i][j]nums 数组通过使用以下形式的索引以一维数组的形式表示：是列数字。因此，我们可以节省每一步所需的额外检查。
public class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] res = new int[r][c];
if (nums.length == 0 || r * c != nums.length * nums[0].length)
return nums;
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
res[count / c][count % c] = nums[i][j];
count++;
}
}
return res;
}
}
661 图片平滑器
<span id="q661"></span>
作者：LeetCode
来源：力扣（LeetCode）
链接：地址
包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
示例 1:
输入:
[[1,1,1],
[1,0,1],
[1,1,1]]
输出:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
注意:
- 给定矩阵中的整数范围为 [0, 255]。
- 矩阵的长和宽的范围均为 [1, 150]。
我的解答
<span id="q661_my1"></span>
思路：“双重嵌套”+“补位”
- 创建一个新的矩阵，双重嵌套遍历矩阵。
- 通过“补位”使原矩阵中每个单位周围有8个单位格。
- 在双重嵌套最内部计算单位的平均值，通过单元在矩阵中的坐标判断是否是“补位”单元，来计算平均值。
/**
* 执行用时 : 392 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
* 内存消耗 : 38.3 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
*/
class Solution {
fun imageSmoother(M: Array<IntArray>): Array<IntArray> {
if (M.isEmpty() || M[0].isEmpty()) return M
fun getEl(row: Int, col: Int): Int {
return when {
row < 0 || row >= M.size -> -1
col < 0 || col >= M[0].size -> -1
else -> M[row][col]
}
}
var elCount = 0
var elSum = 0
fun handle(el: Int) {
if (el >= 0) {
elCount++
elSum += el
}
}
val resetArray = arrayOfNulls<IntArray>(M.size)
for (row in M.indices) {
resetArray[row] = IntArray(M[0].size) { col ->
elCount = 0
elSum = 0
handle(getEl(row - 1, col - 1))
handle(getEl(row - 1, col))
handle(getEl(row - 1, col + 1))
handle(getEl(row, col - 1))
handle(getEl(row, col))
handle(getEl(row, col + 1))
handle(getEl(row + 1, col - 1))
handle(getEl(row + 1, col))
handle(getEl(row + 1, col + 1))
elSum / elCount
}
}
return resetArray as Array<IntArray>
}
}
精选题解
见我的解答，得瑟一波～
我在看了部分题解后，并没有发现特别好的解题思路，有些解法思路复杂、实现繁琐，并没有我的解法简洁，所以毛（hoz）遂（yan）自（wu）荐（chi）把自己的解法贴了出来。貌似，“矩阵”类的算法题并没有特别好的解法？
再毛（chou）遂（bu）自（yao）荐（lian）一次，我把我的题解也发布到LeetCode上了，点这里查看，欢迎点赞和交流！
