由于個(gè)人精力有限，文章是從個(gè)人博客拷貝過(guò)來(lái)的劲赠，如果文章格式和鏈接跳轉(zhuǎn)有問(wèn)題，還請(qǐng)見(jiàn)諒只磷！也可以在我的個(gè)人博客觀看经磅。另外簡(jiǎn)書(shū)上的文章會(huì)不定期更新，如果您覺(jué)得文章對(duì)你有用钮追，歡迎關(guān)注我的個(gè)人博客预厌。
最新內(nèi)容快捷入口：圖片平滑器
本文內(nèi)容摘選自LeetCode-數(shù)組
所謂數(shù)組，是有序的元素序列元媚。若將有限個(gè)類(lèi)型相同的變量的集合命名轧叽，那么這個(gè)名稱(chēng)為數(shù)組名。組成數(shù)組的各個(gè)變量稱(chēng)為數(shù)組的分量刊棕，也稱(chēng)為數(shù)組的元素炭晒，有時(shí)也稱(chēng)為下標(biāo)變量。用于區(qū)分?jǐn)?shù)組的各個(gè)元素的數(shù)字編號(hào)稱(chēng)為下標(biāo)甥角。數(shù)組是在程序設(shè)計(jì)中网严，為了處理方便，把具有相同類(lèi)型的若干元素按無(wú)序的形式組織起來(lái)的一種形式嗤无。
由簡(jiǎn)入難震束，我會(huì)從不同難度的數(shù)組算法題中挑選一些有代表性的進(jìn)行解答怜庸。
簡(jiǎn)單
1 兩數(shù)之和
<span id="q1"></span>
該題是算法題的第一道題，在之前的文章中解答過(guò)垢村，這里不在重復(fù)解答割疾。見(jiàn)LeetCode-算法題。
26 刪除排序數(shù)組中的重復(fù)項(xiàng)
<span id="q26"></span>
該題在之前的文章中解答過(guò)嘉栓，見(jiàn)LeetCode-算法題宏榕。該題首次提到了原地算法和雙指針?lè)ǎ档每匆幌隆?/p>
118 楊輝三角
<span id="q118"></span>
作者：LeetCode
鏈接：地址
來(lái)源：力扣（LeetCode）
問(wèn)題描述
給定一個(gè)非負(fù)整數(shù) numRows侵佃，生成楊輝三角的前 numRows 行麻昼。
在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和趣钱。
示例：
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
我的解答
經(jīng)過(guò)之前幾十道算法題的洗禮涌献，我在解答這道題時(shí)并沒(méi)有花費(fèi)什么功夫，思路也很簡(jiǎn)單首有，明白了每行的每個(gè)元素怎么求值題就解了。元素求值有兩種方式：
- 每行的第一個(gè)和最后一個(gè)元素值恒為1
- 每對(duì)相鄰的元素值的和是下一行對(duì)應(yīng)元素的值枢劝。
Java語(yǔ)言實(shí)現(xiàn)井联。
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語(yǔ)言實(shí)現(xiàn)，思路同上面的Java實(shí)現(xiàn)您旁。
/*
執(zhí)行用時(shí) : 248 ms, 在所有 Kotlin 提交中擊敗了 72.22% 的用戶
內(nèi)存消耗 : 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
鏈接：地址
來(lái)源：力扣（LeetCode）
方法：動(dòng)態(tài)規(guī)劃
實(shí)現(xiàn)思路和我的思路一致烙常，這里不再累述，只貼出代碼實(shí)現(xiàn)鹤盒。但還是建議看下原文鏈接蚕脏，有動(dòng)態(tài)演示，很方便理解侦锯。
雖然這一算法非常簡(jiǎn)單驼鞭，但用于構(gòu)造楊輝三角的迭代方法可以歸類(lèi)為動(dòng)態(tài)規(guī)劃，因?yàn)槲覀冃枰谇耙恍衼?lái)構(gòu)造每一行尺碰。
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 求眾數(shù)
<span id="q169"></span>
作者：LeetCode
鏈接：地址
來(lái)源：力扣（LeetCode）
問(wèn)題描述
給定一個(gè)大小為n的數(shù)組挣棕，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于n/2的元素亲桥。
你可以假設(shè)數(shù)組是非空的洛心，并且給定的數(shù)組總是存在眾數(shù)。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
我的解答
這道題正確解答很簡(jiǎn)單，解法也有很多種，但是想解的好卻不容易。短時(shí)間內(nèi)我也只寫(xiě)出了下面兩種解法，雖然想到了分治法也能求解，但是沒(méi)有用代碼實(shí)現(xiàn)。建議看看下面的官方題解，一些解法真的巧妙！
哈希表
思路很簡(jiǎn)單棉浸，用一個(gè)循環(huán)遍歷數(shù)組，將元素和元素出現(xiàn)的次數(shù)存入到哈希表就漾，最后迭代哈希表得到眾數(shù)朗徊。
class Solution {
/*
執(zhí)行用時(shí) : 456 ms, 在所有 Kotlin 提交中擊敗了 48.15% 的用戶
內(nèi)存消耗 : 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()
}
}
暴力法
雙重循環(huán)求解，外層循環(huán)控制元素，內(nèi)層循環(huán)計(jì)算元素出現(xiàn)的次數(shù)，當(dāng)出現(xiàn)滿足眾數(shù)條件時(shí)返回元素魄幕。
由于該解法使用雙重循環(huán)翼抠，導(dǎo)致執(zhí)行用時(shí)過(guò)高量愧，遠(yuǎn)超出我預(yù)期累颂。
class Solution {
/*
執(zhí)行用時(shí) : 2604 ms, 在所有 Kotlin 提交中擊敗了 7.41% 的用戶
內(nèi)存消耗 : 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
鏈接：地址
來(lái)源：力扣（LeetCode）
這里過(guò)濾了一些常規(guī)解答赫编，只列出了比較巧妙的解法团甲，對(duì)其他解法感興趣的同學(xué)可以點(diǎn)擊地址看下身腻。
排序
所有解法中代碼行數(shù)最少，只有兩行：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
思路：滿足眾數(shù)條件的元素匹厘，出現(xiàn)的次數(shù)超出了數(shù)組總長(zhǎng)度的一半嘀趟，那么在為數(shù)組排序后，數(shù)組最中間的元素肯定就是眾數(shù)愈诚！
[3,2,3] 排序后：[2,3,3]她按，最中間的元素是：3
[2,2,1,1,1,2,2] 排序后：[1,1,1,2,2,2,2]，最中間的元素是：2
隨機(jī)化
思路：由于一個(gè)給定的下標(biāo)對(duì)應(yīng)的數(shù)字很有可能是眾數(shù)炕柔，我們隨機(jī)挑選一個(gè)下標(biāo)酌泰，檢查它的值是否是眾數(shù)，如果是就返回匕累，否則繼續(xù)隨機(jī)挑選陵刹。
class Solution {
private int randRange(Random rand, int min, int max) {
return rand.nextInt(max - min) + min;
}
// 統(tǒng)計(jì)指定數(shù)字在數(shù)組中出現(xiàn)的次數(shù)
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 投票算法
該算法的思路及其巧妙，在看完時(shí)對(duì)作者豎然起敬欢嘿，然后發(fā)現(xiàn)這不是“開(kāi)心消消樂(lè)”嗎衰琐？！
思路
- 如果我們把眾數(shù)記為 +1炼蹦，把其他數(shù)記為 -1羡宙，將它們?nèi)考悠饋?lái)，顯然和大于 0框弛，從結(jié)果本身我們可以看出眾數(shù)比其他數(shù)多辛辨。
- 定義一個(gè)候選眾數(shù) candidate，再維護(hù)一個(gè)計(jì)數(shù)器 count。遇到和 candidate 相同的數(shù)字斗搞， count 加一指攒，否則 count 減一。當(dāng) count 等于0時(shí)僻焚，忽略錢(qián)買(mǎi)額數(shù)字允悦，將候選眾數(shù) candidate 改為下一個(gè)數(shù)字，計(jì)數(shù)器 count 重置為0虑啤。這樣最后剩下的候選眾數(shù) candidate 就是要求的眾數(shù)隙弛。
- 來(lái)看兩個(gè)示例（豎線用來(lái)劃分每次計(jì)數(shù)器歸零的情況）。
[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 找到所有數(shù)組中消失的數(shù)字
<span id="q448"></span>
作者：LeetCode
鏈接：地址
來(lái)源：力扣（LeetCode）
問(wèn)題描述
給定一個(gè)范圍在1 ≤ a[i] ≤ n（n=數(shù)組大心健）的整型數(shù)組全闷，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次萍启。
找到所有在 [1, n] 范圍之間沒(méi)有出現(xiàn)在數(shù)組中的數(shù)字总珠。
您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
我的解答
該題還是有一定的難度的，尤其是要求不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)勘纯。
- 思索來(lái)思索去局服，并沒(méi)有想到優(yōu)雅些的解決辦法，所以使用暴力法進(jìn)行求解驳遵，結(jié)果提交后沒(méi)有通過(guò)淫奔。又審了幾遍題，發(fā)現(xiàn)是我忽略了一點(diǎn)：n=數(shù)組大小堤结，找出[1, n]范圍之間沒(méi)有出現(xiàn)在數(shù)組中的數(shù)字唆迁，慚愧的很。
- 修改后再次提交竞穷，順利通過(guò)媒惕，但執(zhí)行結(jié)果慘不忍睹。再來(lái)！
- 使用動(dòng)態(tài)規(guī)劃求解，執(zhí)行結(jié)果有些超出預(yù)期蘸劈，但代碼實(shí)現(xiàn)可讀性有些差胧后。再來(lái)！
- 修改后的動(dòng)態(tài)規(guī)劃代碼實(shí)現(xiàn)看起來(lái)就舒服了一些科盛！
收工帽衙，看下官方題解。
暴力法
/**
* 解答錯(cuò)誤
*/
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
}
}
修改后的暴力法
/**
* 執(zhí)行用時(shí) : 2232 ms, 在所有 Kotlin 提交中擊敗了 25.00% 的用戶
* 內(nèi)存消耗 : 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
}
}
動(dòng)態(tài)規(guī)劃
/**
* 執(zhí)行用時(shí) : 472 ms, 在所有 Kotlin 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗 : 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
}
}
優(yōu)化過(guò)的動(dòng)態(tài)規(guī)劃
/**
* 執(zhí)行用時(shí) : 480 ms, 在所有 Kotlin 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗 : 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
鏈接：地址
來(lái)源：力扣（LeetCode）
思路：
- 將數(shù)組元素對(duì)應(yīng)為索引的位置加n
- 遍歷加n后的數(shù)組贞绵，若數(shù)組元素值小于等于n厉萝，則說(shuō)明數(shù)組下標(biāo)值不存在，即消失的數(shù)字
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;
}
};
作者沒(méi)有使用Java和Kotlin語(yǔ)言實(shí)現(xiàn)該解題思路，我使用Kotlin語(yǔ)言進(jìn)行了實(shí)現(xiàn)谴垫。
/**
* 執(zhí)行用時(shí) : 392 ms, 在所有 Kotlin 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗 : 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
來(lái)源：力扣（LeetCode）
鏈接：地址
在MATLAB中章母，有一個(gè)非常有用的函數(shù)reshape，它可以將一個(gè)矩陣重塑為另一個(gè)大小不同的新矩陣翩剪，但保留其原始數(shù)據(jù)乳怎。
給出一個(gè)由二維數(shù)組表示的矩陣，以及兩個(gè)正整數(shù)r和c前弯，分別表示想要的重構(gòu)的矩陣的行數(shù)和列數(shù)蚪缀。
重構(gòu)后的矩陣需要將原始矩陣的所有元素以相同的行遍歷順序填充。
如果具有給定參數(shù)的reshape操作是可行且合理的恕出，則輸出新的重塑矩陣询枚；否則，輸出原始矩陣浙巫。
示例 1:
輸入:
nums = [[1,2],[3,4]]
r = 1, c = 4
輸出:
[[1,2,3,4]]
解釋:
行遍歷nums的結(jié)果是 [1,2,3,4]金蜀。新的矩陣是 1 * 4 矩陣, 用之前的元素值一行一行填充新矩陣。
示例 2:
輸入:
nums = [[1,2],[3,4]]
r = 2, c = 4
輸出:
[[1,2],[3,4]]
解釋:
沒(méi)有辦法將 2 * 2 矩陣轉(zhuǎn)化為 2 * 4 矩陣狈醉。 所以輸出原矩陣廉油。
注意：
給定矩陣的寬和高范圍在 [1, 100]。
給定的 r 和 c 都是正數(shù)苗傅。
我的解答
解題思路：
- 先判斷原始矩陣和轉(zhuǎn)換后的新矩陣的元素個(gè)數(shù)是否相等抒线。
- 若相等，說(shuō)明可以轉(zhuǎn)換渣慕；若不相等嘶炭，說(shuō)明不能轉(zhuǎn)換。
- 使用“雙指針”：rowCount和colCount代表原始矩陣的行和列逊桦，依次取出原始矩陣中的元素存放到新矩陣中即可眨猎。
/**
* 執(zhí)行用時(shí) : 328 ms, 在所有 Kotlin 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗 : 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
鏈接：題解
來(lái)源：力扣（LeetCode）
看了官方題解后，發(fā)現(xiàn)我的解答法是“不用額外空間”强经，不過(guò)官方給出的題解思路很相似睡陪，復(fù)雜度上也都相同，該題并沒(méi)有特別“巧妙”的解法匿情。
使用隊(duì)列 [通過(guò)]
最簡(jiǎn)單的方法是通過(guò)以行方式讀取元素來(lái)提取給定矩陣的所有元素兰迫。在此實(shí)現(xiàn)中，我們使用隊(duì)列來(lái)放置提取的元素炬称。然后汁果，我們可以取出以串行順序形成的隊(duì)列元素，并再次按行逐行排列所得到的所需矩陣中的元素玲躯。
如果原始矩陣中的元素?cái)?shù)量不等于所得矩陣中的元素?cái)?shù)量据德，則不可能形成所得矩陣鳄乏。
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;
}
}
不用額外空間 [通過(guò)]
我們不必像在暴力方法中那樣不必要地使用隊(duì)列，而是可以在逐行順序迭代給定矩陣的同時(shí)棘利，直接將數(shù)字放在結(jié)果矩陣中橱野。在將數(shù)字放入結(jié)果數(shù)組時(shí)，我們固定一個(gè)特定的行赡译，并繼續(xù)增加列數(shù)仲吏，直到我們到達(dá)cc指示的所需列的末尾。此時(shí)蝌焚，我們通過(guò)遞增來(lái)更新行索引裹唆，并將列索引重置為從0開(kāi)始。因此只洒，我們可以節(jié)省隊(duì)列消耗的空間许帐，以便存儲(chǔ)只需要復(fù)制到新數(shù)組中的數(shù)據(jù)。
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;
}
}
除法和取模 [通過(guò)]
在上一種方法中毕谴，我們需要跟蹤我們何時(shí)到達(dá)結(jié)果矩陣的列的末尾成畦，并且需要通過(guò)每次檢查當(dāng)前索引來(lái)更新當(dāng)前行和列號(hào)以放置提取的元素。我們可以利用數(shù)學(xué)來(lái)幫助解決涝开，而不是在每一步都進(jìn)行限制性檢查循帐。
這種方法背后的想法如下。
你知道二維數(shù)組是如何存儲(chǔ)在主存中的（本質(zhì)上是一維）嗎舀武？它僅在內(nèi)部表示為一維陣列拄养。
元素 nums[i][j]nums 數(shù)組通過(guò)使用以下形式的索引以一維數(shù)組的形式表示：是列數(shù)字轰绵。因此家乘，我們可以節(jié)省每一步所需的額外檢查。
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
來(lái)源：力扣（LeetCode）
鏈接：地址
包含整數(shù)的二維矩陣 M 表示一個(gè)圖片的灰度藏澳。你需要設(shè)計(jì)一個(gè)平滑器來(lái)讓每一個(gè)單元的灰度成為平均灰度 (向下舍入) ，平均灰度的計(jì)算是周?chē)?個(gè)單元和它本身的值求平均耀找，如果周?chē)膯卧癫蛔惆藗€(gè)翔悠，則盡可能多的利用它們业崖。
示例 1:
輸入:
[[1,1,1],
[1,0,1],
[1,1,1]]
輸出:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
解釋:
對(duì)于點(diǎn) (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
對(duì)于點(diǎn) (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
對(duì)于點(diǎn) (1,1): 平均(8/9) = 平均(0.88888889) = 0
注意:
- 給定矩陣中的整數(shù)范圍為 [0, 255]。
- 矩陣的長(zhǎng)和寬的范圍均為 [1, 150]蓄愁。
我的解答
<span id="q661_my1"></span>
思路：“雙重嵌套”+“補(bǔ)位”
- 創(chuàng)建一個(gè)新的矩陣双炕，雙重嵌套遍歷矩陣。
- 通過(guò)“補(bǔ)位”使原矩陣中每個(gè)單位周?chē)?個(gè)單位格撮抓。
- 在雙重嵌套最內(nèi)部計(jì)算單位的平均值妇斤，通過(guò)單元在矩陣中的坐標(biāo)判斷是否是“補(bǔ)位”單元，來(lái)計(jì)算平均值丹拯。
/**
* 執(zhí)行用時(shí) : 392 ms, 在所有 Kotlin 提交中擊敗了 100.00% 的用戶
* 內(nèi)存消耗 : 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>
}
}
精選題解
見(jiàn)我的解答站超，得瑟一波～
我在看了部分題解后，并沒(méi)有發(fā)現(xiàn)特別好的解題思路乖酬，有些解法思路復(fù)雜死相、實(shí)現(xiàn)繁瑣，并沒(méi)有我的解法簡(jiǎn)潔咬像，所以毛（hoz）遂（yan）自（wu）薦（chi）把自己的解法貼了出來(lái)算撮。貌似，“矩陣”類(lèi)的算法題并沒(méi)有特別好的解法县昂？
再毛（chou）遂（bu）自（yao）薦（lian）一次肮柜，我把我的題解也發(fā)布到LeetCode上了，點(diǎn)這里查看倒彰，歡迎點(diǎn)贊和交流审洞！
