數組類型筆試題2
-
-
- 1. 搜尋旋轉排序數組
- 2. 顔色分類
- 3. 删除排序數組中的重複項 II
- 4. 柱狀圖中最大的矩形
- 5. 買股票的最佳時機
- 6. 買賣股票的最佳時機 II
- 7. 用一個數組實作三個棧
- 8. 堆盤子
-
1. 搜尋旋轉排序數組
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回 -1
你可以假設數組中不存在重複的元素
示例1
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int end = nums.size()-1;
while (left<end){
int mid = (left + end)/2;
if (nums[mid]==target){
return mid;
}
if (nums[mid] > nums[end]){
if (nums[left]<=target && target<=nums[mid]){
end = mid;
}
else{
left = mid+1;
}
}
else{
if (nums[mid] <= target && target<= nums[end]){
left = mid+1;
}
else{
end = mid-1;
}
}
}
return nums[left]==target ?left:-1;
}
};
2. 顔色分類
給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。
此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色。
示例
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
思路：其實這就是一個排序過程，可以使用冒泡，快速，選擇，插入，歸并…但是用排序算法有點大材小用了，因為這個資料是比較簡單的，隻有三個數字，我們定義三個指針就可以了。
思路：定義三個指針，left = 0，mid = 0,right = len(num)-1
始終用 num[mid]與0,1，2這三個數字進行判斷，如果等于0，則與第一個指針交換，如果等于2則與最後一個指針交換，如果等于1不做交換，指針繼續往前走，當mid>=right 的時候，退出循環。
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0, mid = 0;
int right = nums.size()-1;
while(mid<=right){
if(nums[mid]==2){
swap(nums[mid],nums[right]);
right-=1;
}
else if(nums[mid]==0){
swap(nums[mid],nums[left])
left+=1;
mid+=1;
}
else{
mid+=1;
}
}
}
};
3. 删除排序數組中的重複項 II
給定一個排序數組，你需要在原地删除重複出現的元素，使得每個元素最多出現兩次，傳回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。
示例1
給定 nums = [1,1,1,2,2,3],
函數應傳回新長度 length = 5, 并且原數組的前五個元素被修改為 1, 1, 2, 2, 3 。
你不需要考慮數組中超出新長度後面的元素。
示例2
給定 nums = [0,0,1,1,1,1,2,3,3],
函數應傳回新長度 length = 7, 并且原數組的前五個元素被修改為 0, 0, 1, 1, 2, 3, 3 。
你不需要考慮數組中超出新長度後面的元素。
思路：定義兩個指針，隻要保證第 i +2 個數不等于 i 位置的數就可以了
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int index = 0;
for(int i = 0;i<nums.size();++i){
if(index<2 || nums[i] > nums[index-2]){
nums[index] = nums[i];
index += 1;
}
}
return index;
}
};
4. 柱狀圖中最大的矩形
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]。
數組類型筆試題2 
數組類型筆試題2 圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個機關。
示例
輸入: [2,1,5,6,2,3]
輸出: 10
思路：單調棧
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> s;
int maxArea = 0;
for(int i = 0;i<heights.size();i++){
while(!s.empty() && heights[i]<heights[s.top()]){
int top= s.top();
s.pop();
// 計算出寬度
int weith = s.empty()?i:(i-s.top()-1);
maxArea = max(maxArea,heights[top]*weith);
}
s.push(i);
}
return maxArea;
}
};
5. 買股票的最佳時機
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。
注意你不能在買入股票前賣出股票。
示例1
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例2
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
暴力法簡單，但是時間太長
在周遊的過程我們要做兩件事，第一件事就是記錄到目前為止最小的值，第二件事是要 記錄目前值減去最小值的大小。并且更新這兩個值…
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
minprice = prices[0]
max_price = 0
for i in range(1,len(prices)):
if prices[i]<minprice:
minprice = prices[i]
if prices[i]-minprice>max_price:
max_price = prices[i]-minprice
return max_price
6. 買賣股票的最佳時機 II
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個算法來計算你所能擷取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
示例1
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例2
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再将它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例3
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
思路：看起來好像很複雜的樣子，其實都是花架子
就比如執行個體2:[1,2,3,4,5] 第一天買進來，第五天買出去，完全可以認為第一天買，第二天賣了，第二天再買，第三天再賣了，第三天再買回來，第四天再賣了，第四天再買一次，到第五天賣了，這樣一來也就相當于第一天買，第五天賣，他們的利潤是一樣的。
是以我們在周遊的時候，隻要發現後一項比前一項大，就跌加起來。
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
total = 0
for i in range(1,len(prices)):
if prices[i]>prices[i-1]:
total +=prices[i]-prices[i-1]
return total
7. 用一個數組實作三個棧
三個棧互相是沒有關系的，如果每個棧滿了，則不進行插入，如果沒有元素，彈出的時候會傳回-1
class TripleInOne {
private:
vector<int> s;
int stackSize;
int spointer[3];
public:
TripleInOne(int stackSize) {
s = vector<int>(stackSize*3, 0);
this->stackSize = stackSize;
spointer[0] = 0;
spointer[1] = stackSize;
spointer[2] = stackSize*2;
}
//然後将元素push進去的話我們首先看有沒有溢出的
void push(int stackNum, int value) {
if(spointer[stackNum] < (stackNum+1)*stackSize){
s[spointer[stackNum]++] = value;
}
}
//這裡的pop的話就看是否有元素讓你pop出來，沒有的話就傳回-1
int pop(int stackNum) {
int res = -1;
if(spointer[stackNum] > (stackNum)*stackSize){
res = s[--spointer[stackNum]];
}
return res;
}
// peek的操作和上面的pop操作類似，
// 不同的點就是我們不需要把指針往後退一步
int peek(int stackNum) {
int res = -1;
if(spointer[stackNum] > (stackNum)*stackSize){
res = s[spointer[stackNum]-1];
}
return res;
}
//看看是不是空的話我們就看每個棧的指針是不是在原來的初始位置上
bool isEmpty(int stackNum) {
return spointer[stackNum] == stackNum*stackSize;
}
};
8. 堆盤子
堆盤子。設想有一堆盤子，堆太高可能會倒下來。是以，在現實生活中，盤子堆到一定高度時，我們就會另外堆一堆盤子
請實作資料結構SetOfStacks，由多個棧組成，并且在前一個棧填滿時建立一個棧。此外，SetOfStacks.push()和SetOfStacks.pop()應該與普通棧的操作方法相同（也就是說，pop()傳回的值，應該跟隻有一個棧時的情況一樣）。 進階：實作一個popAt(int index)方法，根據指定的子棧，執行pop操作
當某個棧為空時，應當删除該棧。當棧中沒有元素或不存在該棧時，pop，popAt 應傳回 -1.
class StackOfPlates {
public:
StackOfPlates(int cap) {
this->capacity = cap;
}
void push(int val) {
if(capacity <=0){
return;
}
//需要擴容啦
if(list.empty() || list.back().size()==capacity){
list.push_back(stack<int>());
}
list.back().push(val);
}
int pop() {
if(capacity <=0 || list.empty()){
return -1;
}
int res = list.back().top();
list.back().pop();
if(list.back().empty()){
list.pop_back();
}
return res;
}
int popAt(int index) {
// 越界了
if(capacity <=0 || index >=list.size()){
return -1;
}
// 為什麼要用疊代器呢？因為是随機删除，裡面有庫可以使用
auto iter = list.begin();
while(index--){
++iter;
}
int res = (*iter).top();
(*iter).pop();
if((*iter).empty()){
iter = list.erase(iter);
}
return res;
}
private:
list<stack<int>>list;
int capacity;
};