註：本文部分內容及所有題目源自於Leetcode網站[1]，僅供本人自己學習與作為練習筆記使用。（所有引用都已標註原網址，見文章或附錄。若存在版權侵犯，請聯繫本人刪除侵權內容。）
日期Oct.28 - Nov.03 2020（每日一題）Ps:本周我們接著上一周繼續刷數組，難度依舊是簡單，題目不再按順序，而是隨機挑選，下周開始會加深難度。隨著學校的開課，我會將平時上課的內容和筆記也整理成MK的格式上傳。這學期課程主要有圖形學（Computer Graphics）等等的專業課，具體的請看話題列表，每門課我將會開設一個專門的話題。內容會跟隨課程，逐步上傳，包括自學的一些額外筆記。
數組是目前Leetcode上題量最多的一個模塊了。刷題前我們來了解一下什麼是數組：數組是在程序設計中，為了處理方便， 把具有相同類型的若干元素按有序的形式組織起來的一種形式。首先，數組會利用 索引 來記錄每個元素在數組中的位置，且在大多數程式語言中，索引是從 0 算起的。我們可以根據數組中的索引，快速訪問數組中的元素。事實上，這裡的索引其實就是內存地址。其次，作為線性表的實現方式之一，數組中的元素在內存中是 連續 存儲的，且每個元素佔用相同大小的內存。例如對於一個數組 ['oranges', 'apples', 'bananas', 'pears', 'tomatoes']，為了方便起見，我們假設每個元素只佔用一個字節，它的索引與內存地址的關係如下圖所示。在具體的程式語言中，數組的實現方式具有一定差別。比如 C++ 和 Java 中，數組中的元素類型必須保持一致，而 Python 中則可以不同。相比之下，Python 中的數組（稱為 list）具有更多的高級功能。以上文字描述均來自 LeetCode數組模塊[2]
1. 題目1539. 第 k 個缺失的正整數（難度：簡單）Oct.28刷題請點擊或見附錄：1539. 第 k 個缺失的正整數[3]
題目要求：給你一個 嚴格升序排列 的正整數數組 arr 和一個整數 k 。
示例 1：
輸入：arr = [2,3,4,7,11], k = 5
輸出：9
解釋：缺失的正整數包括 [1,5,6,8,9,10,12,13,...] 。第 5 個缺失的正整數為 9 。
示例 2：
輸入：arr = [1,2,3,4], k = 2
輸出：6
解釋：缺失的正整數包括 [5,6,7,...] 。第 2 個缺失的正整數為 6 。
1.1 解題思路我們通過示例發現，數組的下標 i 與 arr[i] 的差值 distance 就是缺失的正整數個數。因此我們可以通過判斷 distance 和 k 的大小，來知道我們要找的數所在的區間。我們同樣也可以通過 distance 計算出，我們需要的值。1.2 代碼class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
for i in range(len(arr)):
dis = arr[i] - i
if k < dis:
return arr[i] - (dis-k) #找到區間，通過dis-k計算該值與相鄰較大值得距離
return arr[-1]-dis+k+1 #若循環完了輸入數組還沒找到，則從數組的最後一個元素開始繼續加class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
int res=0,dis=0;
for(int i=0 ; i<arr.size();i++){
dis = arr[i]-i;
if(k<dis){
res=arr[i]-(dis-k);
return res;
}
}
res=arr[arr.size()-1]-dis+k+1;
return res;
}
};
2. 題目747. 至少是其他數字兩倍的最大數（難度：簡單）Oct.29刷題請點擊或見附錄：747. 至少是其他數字兩倍的最大數[4]
題目要求：在一個給定的數組nums中，總是存在一個最大元素 。
查找數組中的最大元素是否至少是數組中每個其他數字的兩倍。
示例 1：
輸入: nums = [3, 6, 1, 0]
輸出: 1
解釋: 6是最大的整數, 對於數組中的其他整數,6大於數組中其他元素的兩倍。6的索引是1, 所以我們返回1.
示例 2：
輸入: nums = [1, 2, 3, 4]
輸出: -1
解釋: 4沒有超過3的兩倍大, 所以我們返回 -1.
2.1 解題思路此題目其實只是在尋找最大值輸出其下標（索引），這個問題上多了一個輸出判斷。這個判斷是最大值是否大於等於其它的值的兩倍。這裡C++可以通過冒泡排序先找到最大值及其對應的下標（索引）。而python則可以很方便的啊使用方法 max 與 index 分別取得最大值與下標。2.2 代碼class Solution(object):
def dominantIndex(self, nums):
maxNum = max(nums) #取最大值
if all(maxNum >= 2*num for num in nums if num != maxNum ): #判斷除自身外，是否大於等於其它值的2倍
return nums.index(maxNum) #若大於等於 返回最大值索引
return -1 #否則返回-1class Solution {
public:
int dominantIndex(vector<int>& nums) {
int maxNum=0,index=0;
for(int i = 0;i < nums.size();i++) // 冒泡排序尋最大值，並且記錄下標
if(nums[i] > maxNum){
maxNum = nums[i];
index = i;
}
for(int i = 0;i < nums.size();i++)//判斷非自身的情況下，是否大於等於別的數的2倍
if( nums[i]*2 > maxNum &&i != index && nums[i]!=0){ //這裡需要注意別忘了0這個特殊的值
return -1;
}
return index;
}
};
3. 題目88. 合併兩個有序數組（難度：簡單）Oct.30刷題請點擊或見附錄：88. 合併兩個有序數組[5]
題目要求：給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合併到 nums1 中，使 nums1 成為一個有序數組。
初始化 nums1 和 nums2 的元素數量分別為 m 和 n 。你可以假設 nums1 有足夠的空間（空間大小大於或等於 m + n）來保存 nums2 中的元素。示例 1：
輸入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
3.1 解題思路C++中我們可以使用雙指針，兩個指針 pos1 和 pos2 分別從數組 num1 與 num2 的末端開始往前走。比較2個指針值大小，將較大值存入數組 num1 的末端，同時存儲指針 save 往前挪一位，較大的數組指針也往前挪一位。註：指針要注意邊界問題！！
python的思路，我們使用循環直接在 num1 的 m 位開始，把 num2 拼接上去。然後做個快速排序即可。
Ps：C++中也可以使用python的方法，我會把對應的代碼也附上。
3.2 代碼class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range (0,n):#從0開始所以不需要m+i-1！！！！
nums1[m+i]=nums2[i] #拼接數組
nums1.sort() #快速排序//使用雙指針的思路
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int pos1 = m - 1, pos2 = n - 1, save = m + n - 1;
while(save >= 0){
if(pos1 < 0){
nums1[save] = nums2[pos2];
pos2--;
}
else if(pos2 < 0){
nums1[save] = nums1[pos1];
pos1--;
}//以上兩步處理指針邊界問題
else if(nums1[pos1] <= nums2[pos2]){
nums1[save] = nums2[pos2];
pos2--;
}
else{
nums1[save] = nums1[pos1];
pos1--;
}//判斷指針大小，插入save，並且前移
save--;//存儲指針前移
}
}
};
-
//使用python相同的思路解題
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i=0 ;i<n;i++){
nums1[m+i]=nums2[i];
}
sort(nums1.begin(),nums1.end());
}
};
4. 題目509. 斐波那契數（難度：簡單）Oct.31題目要求：斐波那契數，通常用 F(n) 表示，形成的序列稱為斐波那契數列。該數列由 0 和 1 開始，後面的每一項數字都是前面兩項數字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N，計算 F(N)。
示例 1：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
輸入：3
輸出：2
解釋：F(3) = F(2)) + F(1)) = 1 + 1 = 2.
示例 3：
輸入：4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3.
4.1 解題思路圖中是一個F(5)計算的遞歸樹（圖片來自leetcode官方[7]）。從底層開始往上計算 F(N)=F(N-1)+F(N-2)4.2 代碼#注釋看C++
class Solution:
def fib(self, N: int) -> int:
sumF=0
f1=1
f0=0
if N==0:
sumF=f0
if N==1:
sumF=f1
while N>=2:
sumF=f1+f0
f0=f1
f1=sumF
N=N-1
return sumFclass Solution {
public:
int fib(int N) {
int sum = 0, f1 = 1, f0 = 0;//初始化f0 f1的值
if(N == 0){
sum=f0;
}
if(N == 1){
sum=f1;
}
while(N >= 2)//當N>2時開始從下往上計算，每計算一次N--
{
sum = f1 + f0;
f0 = f1;
f1 = sum;
N --;
}
return sum;
}
};
5. 題目118. 楊輝三角（難度：簡單）Nov.01題目要求：給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。在楊輝三角中，每個數是它左上方和右上方的數的和。
註：有圖片解釋題意 leetcode官網[9]
示例 1：
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]
5.1 解題思路這題的解法比斐波那契稍微複雜一點，要用到二維數組來計算和存儲這個數字三角。主要是用到了這個動態方程 res[i][j]=res[i-1][j-1]+res[i-1][j] 來計算。初始化斐波那契數列的時候，我們初始化了前2個數為0和1，然後從第三個數開始計算。在這裡我們需要在初始化的時候讓第一二兩行值都為1，從第三行開始計算。5.2 代碼#注釋看C++
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[1]*i for i in range(1,numRows+1)]
for i in range(2,numRows) :
for j in range(1,i) :
res[i][j] = res[i-1][j-1]+res[i-1][j]
return resclass Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int> > res;
for(int i=1; i<=numRows; ++i)
// 初始化楊輝三角形，值均為1
res.push_back(vector<int> (i, 1));
for(int i=2; i<numRows; ++i)
{//從第3行開始計算
for(int j=1; j<i; ++j)
{//每行從第二個元素開始到倒數第二個元素為止，因為第一個元素和最後一個元素我們已經初始化為1了
res[i][j] = res[i-1][j-1] + res[i-1][j];
}
}
return res;
}
};
6. 題目1331. 數組序號轉換（難度：簡單）Nov.02刷題請點擊或見附錄：1331. 數組序號轉換[10]
題目要求：給你一個整數數組 arr ，請你將數組中的每個元素替換為它們排序後的序號。
一個元素越大，那麼序號越大。如果兩個元素相等，那麼它們的序號相同。示例 1：
輸入：arr = [40,10,20,30]
輸出：[4,1,2,3]
解釋：40 是最大的元素。10 是最小的元素。20 是第二小的數字。30 是第三小的數字。
示例 2：
輸入：arr = [100,100,100]
輸出：[1,1,1]
解釋：所有元素有相同的序號。
示例 3：
輸入：arr = [37,12,28,9,100,56,80,5,12]
輸出：[5,3,4,2,8,6,7,1,3]
6.1 解題思路第三步 拿原來的數組 arr 與去重後的數組做一個匹配。輸出匹配結果。這裡需要2個空間，所以我們要重新定義一個容器，內容與 arr 數組相同。6.2 代碼class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
dic={}#創建空字典
L=sorted(list(set(arr)))#set去重，然後對list排序
for i,element in enumerate(L):
dic[element]=i+1 #元素對應序號
return [dic[i] for i in arr]#對arr元素做匹配class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> res = arr;//在定義一個數組
sort(arr.begin(), arr.end());//對原數組排序
int len = unique(arr.begin(), arr.end()) - arr.begin();//獲取去重後數組的長度 unique返回的是去重排序後 最後一位的地址
for(int& index : res) //做匹配 類似於 python的字典
index = lower_bound(arr.begin(), arr.begin() + len, index) - arr.begin() + 1;//函數lower_bound()在first和last中的前閉後開區間進行二分查找，返回大於或等於val的第一個元素位置。如果所有元素都小於val，則返回last的位置.
return res;
}
};
7. 題目53. 最大子序和（難度：簡單）Nov.03 題目要求：給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。示例 1：
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
7.1 解題思路使用動態規劃的辦法，若前一位大於0，則累加到當前位。然後對動態規劃後的新數組排序，取出最大值。7.2 代碼class Solution:
def maxSubArray(self, nums: List[int]) -> int:
size=len(nums) #獲取數組長度
for i in range (1,size): #從第二個數開始做判斷，若前一位大於0，則累加到當前位
if nums[i-1]>=0:
nums[i] += nums[i-1]
return max(nums)#取出新數組的最大值//注釋看python
class Solution {
public:
int maxSubArray(vector<int>& nums) {
for(int i=1;i<nums.size();i++){
if (nums[i-1]>=0){
nums[i] += nums[i-1];
}
}
sort(nums.begin(),nums.end());
return nums[nums.size()-1];
}
};Ps：後面難度上去可能會變成2天一題，最近開學了，開始忙了。要整理的文檔也開始多起來了！加油吧！
參考資料[1]Leetcode網站: https://leetcode-cn.com/
[2]以上文字描述均來自 LeetCode數組模塊: https://leetcode-cn.com/tag/array/
[3]刷題請點擊或見附錄：1539. 第 k 個缺失的正整數: https://leetcode-cn.com/problems/kth-missing-positive-number/
[4]刷題請點擊或見附錄：747. 至少是其他數字兩倍的最大數: https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/
[5]刷題請點擊或見附錄：88. 合併兩個有序數組: https://leetcode-cn.com/problems/merge-sorted-array/
[6]刷題請點擊或見附錄：509. 斐波那契數: https://leetcode-cn.com/problems/fibonacci-number/
[7]leetcode官方: https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode/
[8]刷題請點擊或見附錄：118. 楊輝三角: https://leetcode-cn.com/problems/pascals-triangle/
[9]leetcode官網: https://leetcode-cn.com/problems/pascals-triangle/
[10]刷題請點擊或見附錄：1331. 數組序號轉換: https://leetcode-cn.com/problems/rank-transform-of-an-array/
[11]刷題請點擊或見附錄：53. 最大子序和: https://leetcode-cn.com/problems/maximum-subarray/
- END -