leetcode演算法之數組
明年就是找工作了，又要開始刷題了，把之前做過的題目再梳理整理一遍，但願明年不要那麼拉跨，祈禱明年能找到工作，千萬不能畢業就失業。
分類別解析leetcode上的一些相關的例題路，程式碼採用C++與python實現。
所有的題目均來自leetcode官網.
數組
涉及的一些leetcode問題：
- 283 Move Zeroes (Easy)
- 566 Reshape the Matrix (Easy)
- 485 Max Consecutive Ones (Easy)
- 240 Search a 2D Matrix II (Medium)
- 378 Kth Smallest Element in a Sorted Matrix ((Medium))
- 645 Set Mismatch (Easy)
- 287 Find the Duplicate Number (Medium)
- 697 Degree of an Array (Easy)
- 766 Toeplitz Matrix (Easy)
- 565 Array Nesting (Medium)
283 Move Zeroes (Easy)
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
說明:
必須在原數組上操作，不能拷貝額外的數組。 盡量減少操作次數。
- 第一個直觀的想法:
使用額外的數組,直接遍歷一遍原始數組,然後將非零的複製到前半部分,在後邊按照數組補零即可.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 新建一個vector,保存移動後的vector
vector<int> res(nums.size(), 0);
int j = 0;
// 遍歷原始數組,修改res中的元素
for (int i=0; i < nums.size(); i++){
if (nums[i]!=0){
res[j] = nums[i];
j++;
}
}
// 將res再賦值給原始數組
nums.assign(res.begin(), res.end());
}
};
- 題目要求不能使用額外的數組.
就只能使用雙指針在原始數組上操作,左指針指向交換完成的元素,右指針向後掃描查找交換元素
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 雙指針
int l=0, r=0;
while (r < nums.size()){
if (nums[r] != 0){
swap(nums[r], nums[l]);
l++;
}
r++;
}
}
};
566 Reshape the Matrix (Easy)
題目較簡單,直接附上程式碼,遍歷即可
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
// 直接遍歷即可
int m=nums.size(), n=nums[0].size();
if (m*n != r*c) return nums;
vector<vector<int>> res(r, vector<int>(c, 0)); //保存最終的結果
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
int index = i*n + j;
res[index/c][index%c] = nums[i][j];
}
}
return res;
}
};
485 Max Consecutive Ones (Easy)
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
//直接遍歷
int res = 0;
int i = 0;
while (i < nums.size()){
int count = 0;
while (i < nums.size() && nums[i] == 1){
count++;
i++;
}
res = max(res, count);
i++;
}
return res;
}
};
240 Search a 2D Matrix II (Medium)
編寫一個高效的演算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
-
最直觀的想法, 直接遍歷二維數組進行對比,這就變成了一道簡單題,沒有用到題目當中的條件
-
從右上角開始遍歷,因為這樣遍歷,比target小的在左邊,比target大的在下邊
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 從右上角開始遍歷
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n-1;
while (i >= 0 && i < m && j >= 0 && j < n){
if (matrix[i][j] == target)
return true;
else if (matrix[i][j] > target)
j--;
else
i++;
}
return false;
}
};
378 Kth Smallest Element in a Sorted Matrix ((Medium))
給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
- 第一個思路: 直接將其變為一維數組,然後直接進行排序,找到第k小的元素.
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<int> res(m*n, 0);
int index = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
res[index] = matrix[i][j];
index++;
}
}
sort(res.begin(), res.end());
return res[k-1];
}
};
- 第二個思路,利用優先順序隊列.
將所有的元素全部插入優先順序隊列中,然後找到第k個
class point{
public:
int val, x, y;
point()=default;
point(int val, int x, int y): val(val), x(x), y(y) {}
bool operator > (const point& a) const {
return this->val > a.val;
}
};
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
//按行進行歸併排序
//定義優先順序隊列,這個隊列採用vector實現
priority_queue<point, vector<point>, greater<point>> q;
int n = matrix.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
q.emplace(point(matrix[i][j], i, j));
}
point res;
for (int i = 0; i < k - 1; i++) {
res = q.top();
q.pop();
}
return q.top().val;
}
};
插入的時候不需要將所有的元素均插入,按照其升序的特點,只需要按行插入右側元素即可,找到最小的k個
class point{
public:
int val, x, y;
point()=default;
point(int val, int x, int y): val(val), x(x), y(y) {}
bool operator > (const point& a) const {
return this->val > a.val;
}
};
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
//按行進行歸併排序
//定義優先順序隊列,這個隊列採用vector實現
priority_queue<point, vector<point>, greater<point>> q;
int n = matrix.size();
for (int i = 0; i < n; i++) {
q.emplace(point(matrix[i][0], i, 0));
}
for (int i = 0; i < k - 1; i++) {
point now = q.top();
q.pop();
if (now.y != n - 1) {
q.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
}
}
return q.top().val;
}
};
645 Set Mismatch (Easy)
集合 S 包含從1到 n的整數。不幸的是，因為數據錯誤，導致集合裡面某一個元素複製了成了集合裡面的另外一個元素的值，導致集合丟失了一個整數並且有一個元素重複。
給定一個數組 nums 代表了集合 S 發生錯誤後的結果。你的任務是首先尋找到重複出現的整數，再找到丟失的整數，將它們以數組的形式返回。
非常簡單的題目, 直接使用哈希表即可,找出哪一個數字已經出現過,然後查找那個數字沒有出現過,共遍歷兩次.
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> res;
unordered_set<int> hashset;
for (auto c : nums){
if (hashset.find(c) == hashset.end())
hashset.insert(c);
else
res.push_back(c);
}
for (int i=1; i <= nums.size(); i++){
if (hashset.find(i) == hashset.end())
res.push_back(i);
}
return res;
}
};
287 Find the Duplicate Number (Medium)
給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和n），
可知至少存在一個重複的整數。假設只有一個重複的整數，找出這個重複的數。
直觀的幾種想法:
- 直接遍歷,兩重循環,每次查找元素nums[i]是否在nums[i+1:]的範圍內出現,時間複雜度n2,不滿足題意
- hash表存儲訪問過的元素,空間複雜度o(n),不滿足題意
- 先排序,然後遍歷相鄰的相同元素即為重複元素,不滿足”不能更改原數組”的要求.
這道題的限制條件,直接堵死了常用的幾種直觀的思路.
這裡採用二分查找來解決這個問題.
題解:
- 這道題的數字的範圍均在1~n之間,且只有一個重複的數.舉個例子就知道
例如 [1,3,4,2,2], n=4,因此設置mid = (1+4) / 2=2, 那麼小於等於2的數字有3個大於選定的mid,因此重複的數字就肯定小於等於mid,否則重複的數字大於mid
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size()-1;
int l= 0, r = n;
// 二分法查找區間
while (l < r){
int mid = l + (r - l) / 2;
int cnt = 0;
// 統計小於等於mid的數字的數目
for (auto num :nums){
if (num <= mid)
cnt++;
}
// 如果統計的數字大於mid,那麼最終重複的數字位於左側
if (cnt > mid)
r = mid;
else
l = mid+1;
}
return l;
}
};
697 Degree of an Array (Easy)
給定一個非空且只包含非負數的整數數組 nums, 數組的度的定義是指數組裡任一元素出現頻數的最大值。
你的任務是找到與 nums 擁有相同大小的度的最短連續子數組，返回其長度。
簡單的題目,但是注意頻數最大的數組元素不一定只有一個
#include <algorithm>
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
// 使用無序映射表來存儲每個元素在數組中出現的索引列表
unordered_map<int, vector<int>> res;
for (auto e : nums){
res.insert(make_pair(e, vector<int>()));
}
for (int i=0; i <nums.size(); i++){
res[nums[i]].push_back(i);
}
int min_dis = nums.size();
int max_ferq = 0;
// 查找出現最多的索引出現的次數
for (auto e=res.cbegin(); e != res.end(); e++){
vector<int> index = e->second;
int dis = index.size();
max_ferq = max(max_ferq, dis);
}
//統計最小的連續子數組
for (auto e=res.cbegin(); e != res.end(); e++){
vector<int> index = e->second;
if (index.size() == max_ferq){
min_dis = min(min_dis, index[index.size()-1] - index[0] + 1);
}
}
return min_dis;
}
};
766 Toeplitz Matrix (Easy)
如果矩陣上每一條由左上到右下的對角線上的元素都相同，那麼這個矩陣是 托普利茨矩陣 。
給定一個 M x N 的矩陣，當且僅當它是托普利茨矩陣時返回 True。
簡單的題目, 僅僅需要發現同一條對角線上的橫縱坐標差值為常數(在做八皇后問題也會遇到)就可以了,然後藉助map可以輕鬆求解.
class Solution {
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
// 利用哈希表來,鍵為行列坐標的差值, 值為對應的數字
unordered_map<int, int> indexdiff_value;
for (int i = 0; i < matrix.size(); i++){
for (int j = 0; j < matrix[0].size(); j++){
if (indexdiff_value.find(i - j) == indexdiff_value.end())
indexdiff_value.insert(make_pair(i-j, matrix[i][j]));
else{
if (matrix[i][j] != indexdiff_value[i-j])
return false;
}
}
}
return true;
}
};
565 Array Nesting (Medium)
索引從0開始長度為N的數組A，包含0到N – 1的所有整數。找到最大的集合S並返回其大小，其中 S[i] = {A[i], A[A[i]],
A[A[A[i]]], … }且遵守以下的規則。假設選擇索引為i的元素A[i]為S的第一個元素，S的下一個元素應該是A[A[i]]，之後是A[A[A[i]]]…
以此類推，不斷添加直到S出現重複的元素。
看似複雜,其實只需要將所有的 這種嵌套的子列全部查找出來,並找到最長的滿足條件的最長的長度即可.
例如,對於[5,4,0,3,1,6,2]這個序列,其滿足條件的S分別為: [5, 6, 0, 2], [4,1]與[3]這三個從中找到最短的即可.
基本辦法就是遍歷+ hash表去重
class Solution {
public:
int arrayNesting(vector<int>& nums) {
//利用哈希表記錄訪問過的元素,避免重複訪問.
unordered_set<int> visited;
int res = 0; // 最終的結果,最長的S
// 遍歷,找到所有的字串
for (int i = 0; i < nums.size(); i++){
if( visited.find(nums[i]) != visited.end() ) continue;
int length = 1; // S的長度
// 開始查找一個滿足條件的S.
int index = i;
while (nums[index] != i){
visited.insert(nums[index]);
index = nums[index];
length++;
}
visited.insert(nums[i]);
res = max(res, length);
}
return res;
}
};
更多筆記資料
-
GitHub地址： //github.com/lxztju/leetcode-algorithm
-
csdn部落格： 小哲AI
-
知乎專欄： 小哲AI
-
微信公眾號： 小哲AI
-
AI研習社專欄：小哲AI
