如何解決編碼挑戰的時間限制

我正在做一個編碼測驗（練習），它是這樣的：

輸入是帶有 | 和 * 的字串。
例如**|*|*|**|***

實作功能：
List<int> countItems(string line, List<int> startLocations, List<int> endLocations)

計算*開始和結束字符對之間的|字符數。

其中 2 個位置是包含字串line的開始和結束位置（索引）的陣列。

例如，如果 line = *|*|*and startLocations = [1] and endLocations = [3] 這意味著我需要檢查 substring *|*。
由于只有 1 個管道，因此結果為零。
由于某種原因，位置值似乎是基于 1 而不是基于 0。

例如，如果范圍是 1 和 5，則結果將為 1，因為管道之間只有 1 *。

我想出的代碼確實解決了大約一半的測驗用例，如下所示：

List<int> countItems(string line, List<int> startLocations, List<int> endLocations)
{
    var results = new List<int>();
    
    if (String.IsNullOrWhiteSpace(line) || startLocations.Count == 0)
    {
        return results;
    }

    for (var i = 0; i < startLocations.Count; i  )
    {
        var startIndex = startLocations[i] - 1;
        var endIndex = endLocations[i] - 1;

        var start = false;
        var total = 0;
        var tempTotal = 0;

        for (var j = startIndex; j < endIndex; j  )
        {
            if (!start && line[j] == '|')
            {
                start = true;
                tempTotal = 0;
            }
            else if (start && line[j] == '*')
            {
                tempTotal  ;
            }
            else if (line[j] == '|')
            {
                total  = tempTotal;
                tempTotal = 0;
            }
        }

        if (line[endIndex] == '|')
        {
            total  = tempTotal;
        }

        results.Add(total);
    }

    return results;
}

所有的測驗用例要么通過，要么失敗，因為時間用完了。

錯誤說它超過了 3 秒的時間。

現在我看不到實際資料被傳遞到測驗中，所以我無法對其進行更多測驗。

但我懷疑解決方案是某種臨時串列或字典，以便只迭代字串 1 次，而不是像我的代碼中那樣多次。

我想了解在這種情況下使用哪種解決方案，但不確定這是否是解決方案具有某種名稱或通用概念的常見問題型別。

我將不勝感激任何解決此類問題的明顯指標，甚至可以鏈接到我可以練習更多的類似編程挑戰。

uj5u.com熱心網友回復：

在這種情況下，我認為最好的選擇是使用堆疊理論。它是括號平衡問題的一種變體。你可以在這里找到更多關于它的 文章括號平衡問題

uj5u.com熱心網友回復：

我設法重做測驗，并找到了答案和問題型別。

這是一個“蠟燭之間的盤子”型別的問題。

我試圖自己解決它，但幾乎沒時間了，最??終只是復制/粘貼了我找到的答案。
這是一次練習，而不是實際的測驗或應用程式。

這是有效的解決方案...我將對其進行研究以更好地理解它...

List<int> numberOfItems(string s, List<int> startIndices, List<int> endIndices)
{
    int q = startIndices.Count;
    int l = s.Length;

    for (var i = 0; i < startIndices.Count; i  )
    {
        startIndices[i]--;
        endIndices[i]--;
    }

    var ans = new List<int>();
    var prev = new int[l];
    var next = new int[l];
    var preSum = new int[l];

    int p = -1, nxt = -1;

    // calculating prev candle up to this index.
    for (int i = 0; i < l; i  )
    {

        if (s[i] == '|')
        {
            p = i;
        }
        prev[i] = p;
    }
    //Calculating next candle from this index.

    for (int i = l - 1; i >= 0; i--)
    {

        if (s[i] == '|')
        {
            nxt = i;
        }
        next[i] = nxt;
    }

    int c = 0;

    // calculating the number of stars between these indices.
    for (int i = 0; i < l; i  )
    {

        if (s[i] == '*')
        {
            c  ;
        }
        preSum[i] = c;
    }

    // calculating ans.
    for (int k = 0; k < q; k  )
    {

        int i = startIndices[k];
        int j = endIndices[k];

        int right = prev[j];// position of left candle.
        int left = next[i];// position of right candle.
                           //cout<<right<<left;

        if (left == -1 || right == -1 || left > right)
        {
            ans.Add(0);
        }
        else
        {
            ans.Add(preSum[right] - preSum[left]);
        }
    }
    return ans;
}

標籤：C＃ 。网 测试 谜

上一篇：在Jest/Testing-library中的textarea上模擬鍵入更改后不顯示任何文本

下一篇：立即捕捉到頁面頂部？