C++程式:查詢不同行程中我們所乘坐的有軌電車線路
假設我們有一個包含n個子列表L的巢狀列表。有軌電車軌道上有幾個站點。其中我們只看到了n個站點。L[i]包含另一個列表,L[i]列表的大小決定了該站點上的有軌電車線路數量。L[i]列表的值是線路編號,並且它們可以以任意順序排列。我們必須找到我們可能乘坐的有軌電車的線路有哪些?
問題類別
程式設計中的各種問題可以透過不同的技術來解決。為了解決一個問題,我們首先必須設計一個演算法,為此我們必須詳細研究特定問題。如果同一個問題反覆出現,則可以使用遞迴方法;或者,我們也可以使用迭代結構。if-else和switch case等控制語句可用於控制程式中的邏輯流程。有效地使用變數和資料結構可以提供更簡單的解決方案以及輕量級、低記憶體需求的程式。我們必須檢視現有的程式設計技術,例如分治法、貪心演算法、動態規劃,並找出它們是否可以。
因此,如果我們問題的輸入類似於L = [[1, 4, 6], [1, 4], [10, 5, 6, 4, 1]],則輸出將為[1, 4]
步驟
為了解決這個問題,我們將遵循以下步驟 -
Define an array cnt of size: 101 and fill with 0 n := size of L for initialize i := 1, when i <= n, update (increase i by 1), do: r := size of L[i - 1] for initialize j := 1, when j <= r, update (increase j by 1), do: x := L[i - 1, j - 1] (increase cnt[x] by 1) for initialize i := 0, when i < 100, update (increase i by 1), do: if cnt[i] is same as n, then: print i
示例
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h> using namespace std; void solve(vector<vector<int>> L){ int n, x, r, cnt[101] = { 0 }; n = L.size(); for (int i = 1; i <= n; i++){ r = L[i - 1].size(); for (int j = 1; j <= r; j++){ x = L[i - 1][j - 1]; cnt[x]++; } } for (int i = 0; i < 100; i++){ if (cnt[i] == n){ cout << i << ", "; } } } int main(){ vector<vector<int>> L = { { 1, 4, 6 }, { 1, 4 }, { 10, 5, 6, 4, 1 } }; solve(L); }
輸入
{ { 1, 4, 6 }, { 1, 4 }, { 10, 5, 6, 4, 1 } }
輸出
1, 4,
廣告