跨步問題

跳躍游戲||

問題描述

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。

每個元素 nums[i] 表示從索引 i 向后跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

• 0 <= j <= nums[i]
• i + j < n

返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

原題鏈接

思路分析

設nums[0]=x從起點0處出發走1步能到達[0,x]內的所有點，不必糾結具體要到那個點，反正到不了x+1及以后的點，遍歷[0,x]區間內的每個點i，用nums[i]+i來更新走第2步能到達的最遠點next，等遍歷到x點，第二步所能到達的點的范圍就是[x+1,next]，以此類推，直到遍歷到終點。

具體實現上，定義cur表示走ans步所能到達的最遠點，next表示下一階段所能到達的最遠點，從左到右依次遍歷，等遍歷到cur時，表示到達ans步所能到達的最遠點，若還沒到達終點，則ans++，cur更新為next，最后的ans就是答案。

以{2,4,3,12,0,5,1}為例：

代碼

int jump(vector<int>& nums) {int n = nums.size(), ans = 0, cur = 0, next = 0;  //cur為走ans步能到達的最遠處.for (int i = 0; i < n - 1; i++) {  //注意i截止到n-2.next = max(next, i + nums[i]);  //next為走ans+1步能到達的最遠處.if (i == cur) cur = next, ans++; //到達ans步所能到達的最遠處cur，后面還有節點，ans需要再+1，cur更新為next}return ans;}

總結：不用關系每一步走到哪的細節，到達ans所能到達的最遠點后，貪心地選取下一階段能到達的最遠點next為階段終點，步步為營。

達到數組末尾的最大得分

問題描述

給你一個長度為 n 的整數數組 nums 。

你的目標是從下標 0 出發，到達下標 n - 1 處。每次你只能移動到 更大 的下標處。

從下標 i 跳到下標 j 的得分為 (j - i) * nums[i] 。

請你返回你到達最后一個下標處能得到的 最大總得分 。

原題鏈接

思路分析

首先來分析一個子問題，1.從0下標處直接跳到n-1下標處，2.從0跳到中間某個下標i處再跳到n-1下標處，方案2的總得分比方案1大嗎？

1. nums[i]>nums[0] 則nums[0] * i + nums[i] * (n-1-i) > nums[0] * i+nums[0] (n-1-i)

   即 nums[0] * i + nums[i] * (n-1-i) > nums[0] * （n-1） 方案2總得分大

2. nums[i]<=nums[0] 則nums[0] * i + nums[i] * (n-1-i) <= nums[0] * i+nums[0] (n-1-i)

   即 nums[0] * i + nums[i] * (n-1-i) >= nums[0] * （n-1） 方案2總得分沒有更大

綜上說明當中間有某個下標對應數組值大于nums[0]時，方案2的總得分才更大。

這也說明最佳方案是否要中轉到i處，判斷nums[i]是否大于上一階段起點對應的nums值。

定義tar，初始時為nums[0]*(n-1)，表示從0下標直接跳到n-1下標處的總得分

運用貪心思想，從下標1開始從左往右遍歷，每次遍歷到nums[i]，判斷nums[i]是否大于上一階段的起點數組值，是說明中轉到 i 處的方案獲得的總得分比直接到終點獲得的總得分要大；

此時便更新 上一階段獲得最大得分值，目標歷史最大值，上一階段起點數組值，上一階段起點下標值

直到遍歷完n-2,此時的目標歷史最大值即為目標最大分數

代碼

long long findMaximumScore(vector<int>& nums) {long long n=nums.size();long long tar=(long long)nums[0]*(n-1);long long maxn=nums[0];  //上一階段起點數組值long long mt=0;  //上一階段起點下標值long long tr=0;  //上一階段獲得最大得分值for(int i=1;i<n-1;i++){if(nums[i]>maxn){tr+=(i-mt)*maxn;tar=tr+nums[i]*(n-i-1);maxn=nums[i];mt=i;}}return tar;}

區間交集問題

用最少數量的箭引爆氣球

問題描述

有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數數組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標。

一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 start，end， 且滿足 start ≤ x ≤ end，則該氣球會被 引爆 。可以射出的弓箭的數量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。

給你一個數組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數 。

原題鏈接

思路分析

首先對數組升序排序，定義一個變量pos，表示當前箭射在的位置，第一箭射在第一個氣球的右邊界，定義一個變量ans表示最少箭數，數組不為空時初始為1；

往右遍歷每個氣球，每當有新的氣球的左邊界小于等于pos，說明該氣球可和前面氣球有重疊部分可以一箭射穿，否則說明沒有重疊部分，重置pos為其右邊界，箭數+1；

代碼

int findMinArrowShots(vector<vector<int>>& points) {if (points.empty()) {return 0;}sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {return u[1] < v[1];  //以右邊界為標準升序排序});int pos = points[0][1];int ans = 1;for (auto balloon: points) {if (balloon[0] > pos) {pos = balloon[1];++ans;}}return ans;}

無重疊區間

問題描述

給定一個區間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區間的最小數量，使剩余區間互不重疊 。

注意 只在一點上接觸的區間是 不重疊的。例如 [1, 2] 和 [2, 3] 是不重疊的。

思路分析

求移除區間的最少數目，相當于求保留區間的最多數目，參照上一題用最少數量的箭引爆氣球，k個兩兩相交的區間只能保留一個，為使后續保留的互不重疊的區間最多，應保留右邊界最小的那個，將數組按右區間大小升序排序，定義一個變量right，代表當前兩兩相交區間集合的右邊界，從左往右遍歷每個區間，每當有區間左邊界小于right，則該區間可以舍棄，否則更新右邊界為當前區間的右邊界，并將保留區間統計量m+1。最后intervals.size() - m就是答案。

將區間數組按右區間大小升序排序，再從左往右遍歷，保證了枚舉的區間右邊界逐漸增大，使每個獨立的兩兩相交區間集合的右邊界盡量小，讓后面能容納更多的獨立區間，最后統計的m就是保留區間數量的最大值。

代碼

int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {return a[1] < b[1];});int m = 1;int right = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= right) {m++;right = intervals[i][1];}}return intervals.size() - m;}

構造連續值問題

構造的連續值的最大數目

問題描述

給你一個長度為 n 的整數數組 coins ，它代表你擁有的 n 個硬幣。第 i 個硬幣的值為 coins[i] 。如果你從這些硬幣中選出一部分硬幣，它們的和為 x ，那么稱，你可以 構造 出 x 。

請返回，你最多能 構造 出多少個從 0 開始（包括 0 ）的連續整數。

你可能有多個相同值的硬幣。

思路分析

設我們現在能構造出[0,x]區間的整數，現在我們新增一個整數 y，那么我們可以構造出的區間為[0,x]和 [y,x+y]，那么如果 y≤x+1，則加入整數 y 后我們能構造出 [0,x+y] 區間的整數，否則我們還是只能構造出連續的 [0,x] 區間的數字。

具體實現上，我們每次從數組中找到未選擇數字中的最小值來作為 y，因為如果此時的最小值 y 都不能更新區間 [0,x]，那么剩下的其他更大元素肯定不能更新區間 [0,x]。那么我們初始從 x=0 開始，按照升序來遍歷數組 nums 的元素來作為 y，如果 y≤x+1 那么我們擴充區間為 [0,x+y]，否則我們無論選任何未選的數字都不能使答案區間變大，此時直接退出即可。

代碼

int getMaximumConsecutive(vector<int>& coins) {int res = 1;sort(coins.begin(), coins.end());for (auto& i : coins) {if (i > res) {break;}res += i;}return res;}
作者：靈茶山艾府

最少砝碼

問題描述

你有架天平。現在你要設計一套砝碼，使得利用這些砝碼可以稱出任意小于等于N的正整數重量。

那么這套砝碼最少需要多少個砝碼？

注意天平的兩邊都可以放砝碼。

思路分析

本題與上一題相似，略有不同之處在于，本題用數字構造連續區間可以用減法（放在天平另一側）。思路大體相同。

設我們現在能構造出[1,x]區間的所有整數，現在新增一個y，那能構造出的區間為[1,x],[y-x,y],[y,x+y]。

如果y-x<=x+1即y<=2x+1則加入整數 y 后我們能構造出 [1,x+y] 區間的所有整數，最優方案的y是2x+1。

• 1個砝碼時，使用最優方案，用重量為1的砝碼，能稱出的最大的從1開始連續的最大重量是sum(1)=1
• 2個砝碼時，使用最優方案，添加一個重量為sum(1)*2+1=3的砝碼，能稱出最大的從1開始連續的最大重量是sum(2)=sum(1)+3
• 依次類推，n個砝碼，能稱出符合要求的最大上界是sum(n-1)*2+1+sum(n-1)即3*sum(n-1)+1。

具體實現上，sum記錄所能稱出符合要求的最大上界，cnt記錄砝碼個數。每次添加一個砝碼，并更新sum值，當sum>=n時的cnt就是答案。

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;int sum = 1, cnt = 1; //sum存儲可以表示區間的最大值while(sum<n){sum+=sum*2+1;  //也可寫成sum=3*sum+1cnt++;}cout << cnt ;return 0;
}