代碼隨想錄刷題60天
【數(shù)組】Day1
目錄
代碼隨想錄刷題60天
引例一：
排序算法
直接插入（直接排序）
冒泡排序
雙指針?lè)?/p>
快速排序（遞歸法）
引例二
?編輯
滑動(dòng)窗口
引例三
總結(jié)與心得
引例一：
該題為leetcode上一道簡(jiǎn)單難度的題，該題需要解決的問(wèn)題是對(duì)已有數(shù)組中的數(shù)據(jù)進(jìn)行平方處理后排序。其中數(shù)據(jù)的平方處理并非本體的重點(diǎn)所在，而重點(diǎn)在于對(duì)數(shù)組進(jìn)行排序。因此對(duì)數(shù)據(jù)進(jìn)行怎樣排序才是本題的關(guān)鍵所在，筆者也將在下面介紹幾種排序算法。
排序算法
直接插入（直接排序）
class Solution
{
public:
vector<int> sortedSquares(vector<int>& nums)
{
int temp,i,j;
nums[0] = nums[0] * nums[0];
for (i = 1; i < nums.size(); i++)
{
nums[i] = nums[i] * nums[i];
if (nums[i] < nums[i - 1])
{
temp = nums[i];
for (j = i - 1; j >= 0 && temp < nums[j]; j--)
//這里必須先判斷j是否是負(fù)數(shù)，否則會(huì)造成數(shù)組角標(biāo)錯(cuò)誤
nums[j + 1] = nums[j];
nums[j + 1] = temp;//j超出了for循環(huán)的作用域，因此必須在開頭聲明。
}
}
return nums;
}
};冒泡排序
class Solution
{
public:
vector<int> sortedSquares(vector<int>& nums)
{
int temp,i,j;
nums[0] = nums[0] * nums[0];
for (i = 1; i < nums.size(); i++)
{
for (int j = 1; j < nums.size(); j++)
{
if (i == 1)
nums[j] = nums[j] * nums[j];
if (nums[j] < nums[j - 1])
{
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}
};以上兩種排序是最基本的兩種排序算法，也初學(xué)者最容易理解并寫出的兩種排序算法，但由于兩種算法都使用兩層for循環(huán)嵌套，所以時(shí)間復(fù)雜度都是n的平方，時(shí)間復(fù)雜度較高，所以從效率方面考慮，這兩種算法是不夠理想的。而接下來(lái)的兩種方法通過(guò)借助一些手段從而將算法的復(fù)雜度降低。
雙指針?lè)?/h4>
class Solution
{
public:
vector<int> sortedSquares(vector<int>& nums)
{
vector<int> res(nums.size());
int i = 0, j = nums.size()-1;
int k = j;
while (i <= j)
{
if ((nums[i] * nums[i]) < (nums[j] * nums[j]))
res[k--] = (nums[j] * nums[j--]);
else
res[k--] = (nums[i] * nums[i++]);
}
return res;
}
};
class Solution
{
public:
vector<int> sortedSquares(vector<int>& nums)
{
vector<int> res(nums.size());
int i = 0, j = nums.size()-1;
int k = j;
while (i <= j)
{
if ((nums[i] * nums[i]) < (nums[j] * nums[j]))
res[k--] = (nums[j] * nums[j--]);
else
res[k--] = (nums[i] * nums[i++]);
}
return res;
}
};該方法利用了“原本數(shù)組元素中，成員都是有序排列”的這一條件來(lái)進(jìn)行思考，我們可以發(fā)現(xiàn)當(dāng)所有成員取平方時(shí)，其最大值一定會(huì)出現(xiàn)在數(shù)組的左界或右界，利用這一特點(diǎn)，每次將最大元素從左右端取出，用一個(gè)數(shù)組進(jìn)行存儲(chǔ)，便得到我們需要的結(jié)果。這種利用已有條件設(shè)計(jì)的排序方法在本題中是最優(yōu)解。
快速排序（遞歸法）
int Paritition(int arr[],int low,int high){
int pivotLoc = arr[low];//將數(shù)組的第一個(gè)元素作為基準(zhǔn)值
int temp;
while (low < high) {
while (low < high && arr[high] >= pivotLoc)
--high;//從右界開始，將第一個(gè)比基準(zhǔn)值小的元素交換到左界（基準(zhǔn)值于左界）
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;//交換操作
while (low < high && arr[low] <= pivotLoc)
++low;//從
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;//從左界開始，將第一個(gè)比基準(zhǔn)值大的元素與基準(zhǔn)值交換位置
}
return low;//返回此時(shí)的基準(zhǔn)值角標(biāo)
}
void QSort(int arr[], int n, int low, int hight) {
int pivotloc;
if (low < hight) {
pivotloc = Paritition(arr, low, hight);
QSort(arr, n, low, pivotloc - 1);
QSort(arr, n, pivotloc + 1, hight);
}
}快速排序算法定義了兩個(gè)指針一個(gè)指向數(shù)組頭m一個(gè)指向數(shù)組尾n,然后以頭指針為基準(zhǔn)值先從尾指針開始向后找比基準(zhǔn)值小的元素，找的之后交換m，n所指向的值，此時(shí)n所指向的值就是基準(zhǔn)值，m開始向后找，找到比基準(zhǔn)值大的交換。
在數(shù)組元素本身無(wú)序的情況下，這種排序算法往往有著較高的效率。
引例二
這道題有些類似于在字符串中尋找最長(zhǎng)的連續(xù)相似字符。這道題我們當(dāng)然可以使用暴力匹配進(jìn)行處理，但這樣處理在面對(duì)一些比較復(fù)雜的字符串時(shí)，往往效率不容樂(lè)觀，因此我們可以借助一些巧妙方法來(lái)優(yōu)化復(fù)雜度。?
滑動(dòng)窗口
class Solution
{
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int i=0, j;
int sum = 0;
int len = 0;
for (j = 0; j < nums.size(); j++)
{
sum += nums[j];
while (sum >= target)
{
if (len == 0)len = (j - i + 1);
len = len > (j - i + 1) ? (j - i + 1): len;
sum -= nums[i++];
}
}
return len;
}
};通過(guò)不斷調(diào)整子數(shù)組的起始位置和終止位置，從而得到我們想要的結(jié)果。這種方法可以理解為雙指針的一種。
引例三
?該題不涉及算法，是一道典型的模擬題，我們需要通過(guò)模擬螺旋順序打印其過(guò)程。本題也重點(diǎn)考察做題者對(duì)矩陣邊界的理解程度。
具體實(shí)例代碼如下
class Solution
{
public:
vector<vector<int>> generateMatrix(int n)
{
vector<vector<int>> res(n, vector<int>(n, 0));
int loop = (n - 1) / 2 + 1;
int startX=0, startY=0;
int count = 1;
int offset = 0;
while (loop > 0)
{
int i, j;
for (i = startX; i < n - 1 - offset; i++)
res[startY][i] += count++;
for (j = startY; j < n - 1 - offset; j++)
res[j][i] += count++;
for (; i > 0 + offset; i--)
res[j][i] += count++;
for (; j > 0 + offset; j--)
res[j][i] += count++;
startX++;
startY++;
offset++;
loop--;
}
if (n / 2 == (n - 1) / 2)
res[n / 2][n / 2] = n * n;
//旋轉(zhuǎn)矩陣最內(nèi)層邊長(zhǎng)為1的矩陣由于“右開邊界”而無(wú)法被賦值。
return res;
}
};總結(jié)與心得
· 在數(shù)組的各種問(wèn)題中，對(duì)于數(shù)組邊界開閉的理解會(huì)很大程度影響解決問(wèn)題的思路。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-576910.html
· 在做題過(guò)程中，我們可以通過(guò)一些我們已知的方法與技巧來(lái)優(yōu)化本題的思考邏輯，與此同時(shí)也需要根據(jù)題目已知信息來(lái)簡(jiǎn)化本題的思考邏輯。因此，我們需要在不斷積累各種方法的同時(shí)也要學(xué)會(huì)就題解題。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-576910.html
到了這里，關(guān)于【從零開始寫博客】數(shù)組運(yùn)用：數(shù)組排序,字符串搜索和矩陣模擬（day2）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
