計數具有相等數量的0s,1s和2s的子字符串  


難度級別
經常問 思傑 免費收費 高盛 OYO房間 時代互聯網 Twilio
哈希

問題“計數具有相等數量的0s,1s和2s的子字符串”指出給您一個 只能有0、1和2。 問題語句要求找出僅包含等於0、1和2的等號的子字符串的數量。

例  

計數具有相等數量的0s,1s和2s的子字符串

str= “01200”
2

解釋

(0)和(1)是兩個相等的2、012和120子字符串。

str= “10201012”
4

解釋

(0)和(1),(2)和(102)這四個相等的201、012和201012子字符串。

算法  

  1. 聲明一個 地圖.
  2. 將一對初始化為0,然後將其放入地圖中。
  3. 在你的生活中 零計數, 單數, twocount,產量 到0。
  4. 從i = 0循環到i
    1. 檢查當前子字符串的每個字符是否為0、1和2。然後相應地更新計數。
    2. 計算對的差。
    3. 檢查映射中是否不存在差異,然後將0加到輸出中。
    4. 否則,將temp的map值添加到輸出中。
    5. 將溫度添加到地圖。
  5. 返回輸出。

解釋

給我們一個僅包含0、1和2的字符串。 我們的任務是找出不等於0、1和2的子字符串的總數。為此,我們將使用 哈希。 默認情況下,以(0,0)作為鍵初始化一對,並將其值設置為1。 計算之間的差異 零計數單數零計數雙重計數。 我們將成對存儲該值,並將該對存儲到映射中。 如果映射中已經存在一對差異,那麼只需從映射中獲取/獲取當前對的值即可。 然後將其添加到輸出中。 如果差異尚未存在於地圖中。 然後將0加到輸出中。 我們還需要將差異對插入地圖中,並增加其頻率(如果地圖中已存在)。 否則,將差異對的新條目(值1)存儲到映射中。

也可以看看
查找範圍內缺少的元素

讓我們考慮一個例子:

字符串=“ 01200”

我們已經將對初始化為0,然後將對作為鍵,將1作為值插入到映射中。 我們將檢索第一個字符,如0。因此,我們將計算差異對並獲得(1,1)。 另外,這是因為我們增加了零的計數。 因此,我們將計算出差異並得出結果。 在獲取地圖的當前值並將輸出值加0後,因為這對是新的。 我們只是將這對插入地圖。 當前輸出為0。

我們將選擇下一個字符1。現在,我們將增加一個字符的數量。 然後我們將得到的差異為0,1。 由於這對也是新的,因此我們將其添加到地圖中,並且輸出仍然保持不變。

然後我們得到2作為輸入,因為所有數字的計數現在都是0,所以將對變成0,1。我們也將其存儲在地圖中,這一次更新輸出,因為已經在地圖中初始化了0,0。所以現在的輸出是1。

接下來,我們得到0,現在零計數為1,1。 我們得到2,因為它已經在地圖上了。 然後,我們將更新輸出,並將其插入到值為XNUMX的地圖中。

至此,我們找到了所有可能的子字符串,這是我們獲得等於0、1和2的任意一個的方式。

也可以看看
下一個更高的頻率元素

推薦碼  

C ++代碼對相等數目的0、1和2的子字符串進行計數

#include<bits/stdc++.h>
using namespace std;

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

int getSubString(string str)
{
    int n = str.length();
    unordered_map< pair<int, int>, int, hash_pair > MAP;
    MAP[make_pair(0, 0)] = 1;
    int zerocount = 0, onecount = 0, twocount = 0;
    int output = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '0')
            zerocount++;
        else if (str[i] == '1')
            onecount++;
        else
            twocount++;
        pair<int, int> x = make_pair(zerocount - onecount,zerocount - twocount);
        output = output + MAP[x];
        MAP[x]++;
    }
    return output;
}
int main()
{
    string str = "10201012";
    cout << getSubString(str) << endl;
    return 0;
}
4

Java代碼對相等數目的0、1和2的子字符串進行計數

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int x, int y)
    {
        this.first=x;
        this.second=y;
    }
}
class SubstringCount
{
    public static int getSubString012(String str1)
    {
        int n = str1.length();

        HashMap< String, Integer > MAP=new HashMap<>();



        MAP.put("0:0", 1);

        int zerocount = 0, onecount = 0, twocount = 0;

        int output = 0;
        for (int i = 0; i < n; ++i)
        {
            if (str1.charAt(i)=='0')
                zerocount++;
            else if (str1.charAt(i) == '1')
                onecount++;
            else
                twocount++;

            Pair pair = new Pair(zerocount - onecount, zerocount - twocount);

            String str=pair.first+":"+pair.second;

            if(!MAP.containsKey(str))
                output = output + 0;
            else
                output = output + MAP.get(str);

            if(MAP.containsKey(str))
                MAP.put(str, MAP.get(str)+1);
            else
                MAP.put(str, 1);
        }

        return output;
    }
    public static void main(String [] args)
    {
        String str = "10201012";
        System.out.println(getSubString012(str));
    }
}
4

複雜度分析  

時間複雜度

O(N)  哪裡 “ n” 是數組中元素的數量。 由於我們使用了HashMap,因此每個操作的所有插入,刪除和搜索僅需要O(1)時間。

空間複雜度

O(N)  哪裡 “ n” 是數組中元素的數量。

也可以看看
插入二叉樹