資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++青蛙跳躍
假設有一隻青蛙正在過河。河被分成x個單位，每個單位可能有一塊石頭。青蛙可以跳到石頭上，但不能跳到水裡。這裡我們有一個按升序排列的石頭位置列表，我們必須檢查青蛙是否能夠透過落在最後一塊石頭上來過河。
當青蛙當前跳躍了k個單位時，它下一步跳躍必須是k-1、k或k+1個單位。青蛙只能向前跳。
因此，如果給定的陣列是[0,1,3,4,5,7,9,10,12]，則答案將為true，因為青蛙可以跳躍1個單位到第二塊石頭，2個單位到第三塊石頭，然後再次跳躍2個單位到第四塊石頭，然後跳躍3個單位到第六塊石頭，4個單位到第七塊石頭，最後跳躍5個單位到第八塊石頭。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個名為visited的對映
- 定義一個函式canCross()，它將接收一個數組stones，pos初始化為0，k初始化為0，
- key := pos 或 (k左移11位)
- 如果visited中存在key，則：
- 返回visited[key]
- 對於初始化i := pos + 1，當i < stones的大小，更新（i增加1），執行：
- gap := stones[i] - stones[pos]
- 如果gap < k - 1，則：
- 忽略以下部分，跳到下一次迭代
- 如果gap > k + 1，則：
- visited[key] := false
- 返回false
- 如果呼叫函式canCross(stones, i, gap)的結果非零，則：
- visited[key] = true
- 返回true
- 如果(pos等於stones的大小 - 1)則visited[key] = true，否則為false
- 返回visited[key]
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
unordered_map < lli, int > visited;
bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
lli key = pos | k << 11;
if(visited.find(key) != visited.end())return visited[key];
for(int i = pos + 1; i < stones.size(); i++){
int gap = stones[i] - stones[pos];
if(gap < k - 1)continue;
if(gap > k + 1){
return visited[key] = false;
}
if(canCross(stones, i, gap))return visited[key] = true;
}
return visited[key] = (pos == stones.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {0,1,3,5,6,8,12,17};
cout << (ob.canCross(v));
}輸入
0,1,3,5,6,8,12,17
輸出
1
更新於：2020年6月1日
1K+ 瀏覽量
廣告