在C 中使用堆疊洗掉相等的數字-有解無憂

我對這個任務有疑問

假設給定一個整數序列。如果該序列中存在三個或更多連續相等的數字，則從該序列中洗掉第一組這樣的相等數字。用獲得的序列重復這樣的操作，直到沒有東西可以洗掉。計算將被移除的專案的數量。使用 STL 堆疊復雜度必須為 O(n)。

示例 1. 在序列 {2, 3, 3, 3, 1} 中，第一組相等的數字是 {3, 3, 3}。組洗掉后，序列為{2, 1}，沒有可洗掉的內容。

示例 2. 在序列 {3, 2, 2, 2, 3, 3, 3} 中，要洗掉的第一組數字是 {2, 2, 2}。那么序列將是{3, 3, 3, 3}，因此可以洗掉整個序列。

我嘗試像這樣制作 smth，如果 group lenth 只有 3，它可以作業，但它非常慢，并且測驗會拋出 TIME OUT

#include <cstdio>
#include <stack>
int main()
{
    int x, res = 0;
    std::stack<int> st, tmp_st;
    scanf_s("%d", &x);
    while (x != -1) {
        st.push(x);
        tmp_st = st;
        while ((!tmp_st.empty()) && st.top() == tmp_st.top()) {
            tmp_st.pop();
        }
        if (st.size() - tmp_st.size() == 3) {
            res  = 3;
            st.swap(tmp_st);
        }
        scanf_s("%d", &x);
    }
    printf("%d", res);
    return 0;
}

UPD：此處不需要“靜態”

關于我的決定：每次添加一個專案時，我都會保存原始堆疊的副本，??并查看添加的專案之前連續出現了多少次，如果這個數字等于 3（更多，我需要改善條件）然后專案也從原始堆疊中洗掉，以及我在標準輸出流中最后輸出的洗掉專案的數量，同樣在輸入中的條件只能是從0到9的數字

UPD2：我讓它作業，但它的鋼鐵慢

#include <cstdio>
#include <stack>
int main()
{
    int x = 0, res = 0, n = 1;
    std::stack<int> st, tmp_st;
    
    while (x != -1) {

        scanf_s("%d", &x);
        
        if (!st.empty()&&x != st.top()) {
            if (n < 3) 
            {
                st.push(x);
                tmp_st.push(n);
                n = 1;
                continue;
            }
            
                 res  = n;
                 while (n != 0) 
                 {
                    --n;
                    st.pop();
                 }
                 if (!tmp_st.empty()&&x != st.top()) 
                 {
                     n = 1;
                 }
                 else
                 {
                     if (x == -1) break;
                     n = tmp_st.top() 1;
                     tmp_st.pop();
                     
                 }
                 st.push(x);
                 continue;
                 
            
        }

        if (!st.empty() && x == st.top())
        {
              n;
            st.push(x);
        }

        if (st.empty()) 
        {
            st.push(x);
            n = 1;
        }
        
        
    }
    printf("%d", res);
    return 0;
}

uj5u.com熱心網友回復：

我會只使用一個堆疊并計算最后一個符號的重復，直到出現另一個符號。如果重復次數超過 3，您只需彈出 3 次。在最壞的情況下這將是 O(2n) 所以你有 O(n)

uj5u.com熱心網友回復：

假設

我將假設任務中存在“不對稱”，特別是反轉輸入通常不會產生相反的結果：

{ 3 2 2 2 3 3 3 }→ { 3 3 3 3 }→{ }
{ 3 3 3 2 2 2 3 }→ { 2 2 2 3 }→{ 3 }

換句話說，你不需要回溯一個“最優的”（通過移除專案的最高數量）移除順序，而是可以采取一種“貪婪”的方法：移除第一個“可移除”（足夠長的）序列和重復。

這個↑↑↑假設非常重要，因為它區分了 O( n ) 問題和 O( n2 ) 問題。

演算法

一種可能的方法是回圈

讀取下一個數字item，
與item的頂部相比stack，并且
- 如果相等，則添加item到stack,
- 如果不相等，
  - 如果上一組相等item的 sstack足夠大，
    - 從堆疊中彈出組，將其大小添加到removed items 的數量，然后
  - 將新添加item到stack.

該實作有一些分散注意力的技術細節，例如使用計數器 ( ) 進行“預折疊” top_count。但很容易看出，外回圈運行 O( n ) 次，而內回圈并沒有增加復雜度，因為 (1) 它不能彈出比從輸入讀取stack的 s 次數更多的次數和 (2) 所有item不彈出的代碼路徑stack導致內部回圈退出。（這個論點與為什么Aho-Corasick是線性的非常相似，只是在這種情況下更簡單。）

代碼

為簡潔起見，此示例缺少輸入錯誤檢查。

#include <cstdint>
#include <iostream>
#include <stack>
#include <tuple>

namespace {
constexpr std::size_t LIMIT{3};

std::size_t count_removed(std::istream& input) {
  std::stack<std::tuple<int, std::size_t>> stack;
  int item;
  if (input >> item) {
    stack.emplace(item, 1);
  } else {
    return 0;
  }
  std::size_t removed{};
  while (input >> item) {
    for (;;) {
      auto& [top_item, top_count]{stack.top()};
      if (item == top_item) {
          top_count;
        break;
      } else if (top_count >= LIMIT) {
        removed  = top_count;
        stack.pop();
        if (!stack.empty()) continue;
      }
      stack.emplace(item, 1);
      break;
    }
  }
  const auto& [top_item, top_count]{stack.top()};
  if (top_count >= LIMIT) removed  = top_count;
  return removed;
}
}  // namespace

int main() { std::cout << count_removed(std::cin) << '\n'; }

示例和測驗

{ }→ 0 (/0)
{ 1 }→ 0 (/1)
{ 1 1 }→ 0 (/2)
{ 1 1 1 }→ 3 (/3)
{ }
{ 1 1 1 1 }→ 4 (/4)
{ }
{ 3 2 2 2 3 3 3 }→ 7 (/7)
{ 3 3 3 3 }
{ }
{ 3 3 3 2 2 2 3 }→ 6 (/7)
{ 2 2 2 3 }
{ 3 }
{ 1 1 2 2 2 1 1 }→ 7 (/7)
{ 1 1 1 1 }
{ }
{ 1 1 1 2 2 1 1 1 }→ 6 (/8)
{ 2 2 1 1 1 }
{ 2 2 }
{ 1 1 2 2 2 1 1 1 2 2 }→ 8 (/10)
{ 1 1 1 1 1 2 2 }
{ 2 2 }
{ 0 0 1 2 2 3 4 4 5 5 4 3 3 2 1 1 0 }→ 0 (/17)
{ 0 0 1 2 2 3 4 4 5 5 5 4 3 3 2 1 1 0 }→ 18 (/18)
{ 0 0 1 2 2 3 4 4 4 3 3 2 1 1 0 }
{ 0 0 1 2 2 3 3 3 2 1 1 0 }
{ 0 0 1 2 2 2 1 1 0 }
{ 0 0 1 1 1 0 }
{ 0 0 0 }
{ }
{ 0 1 1 2 2 2 3 3 3 3 2 2 2 1 1 4 4 4 4 }→ 18 (/19)
{ 0 1 1 3 3 3 3 2 2 2 1 1 4 4 4 4 }
{ 0 1 1 2 2 2 1 1 4 4 4 4 }
{ 0 1 1 1 1 4 4 4 4 }
{ 0 4 4 4 4 }
{ 0 }
{ 0 0 1 2 2 3 3 3 2 1 1 2 2 3 3 3 2 1 0 }→ 15 (/19)
{ 0 0 1 2 2 2 1 1 2 2 3 3 3 2 1 0 }
{ 0 0 1 1 1 2 2 3 3 3 2 1 0 }
{ 0 0 2 2 3 3 3 2 1 0 }
{ 0 0 2 2 2 1 0 }
{ 0 0 1 0 }
{ 1 1 2 2 3 3 3 4 3 3 3 2 1 }→ 6 (/13)
{ 1 1 2 2 4 3 3 3 2 1 }
{ 1 1 2 2 4 2 1 }
{ 1 1 2 2 3 3 3 2 3 3 3 2 1 }→ 9 (/13)
{ 1 1 2 2 2 3 3 3 2 1 }
{ 1 1 3 3 3 2 1 }
{ 1 1 2 1 }
{ 1 1 2 3 3 3 2 3 3 3 2 1 1 }→ 13 (/13)
{ 1 1 2 2 3 3 3 2 1 1 }
{ 1 1 2 2 2 1 1 }
{ 1 1 1 1 }
{ }

uj5u.com熱心網友回復：

tmp_st = st是性能殺手。復制堆疊不是一個恒定時間的操作，而是O(n)根據堆疊長度。這將時間復雜度降低到二次。你不需要這樣做。

您只需要將數字與堆疊頂部進行比較，也許與頂部下方的數字進行比較：

如果數字比較不等于頂部，只需推動它。
否則，試探一下pop，并將數字與新的top進行比較
- 如果它們比較不相等，則沒有三元組。按兩次號碼
- 否則，我們有一個三胞胎。不要推動任何東西，但只要您讀取相同的值，就繼續閱讀和丟棄。

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489530.html

標籤：C 算法表现堆

上一篇：了解“將所有1組合在一起的第二個最小交換”問題的特定解決方案

下一篇：這是已知的最花搜索演算法嗎？如果是，它的名字是什么？