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,

更新於: 2022年4月7日

215 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告