İkili simli alternativ etmək üçün silinəcək minimum simvollar

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Coursera Fourkites Piyada çox yol qət eləmək MAQ o9 həlləri Cib daşları Taksi4Sure
SimBaxılıb 278

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

İkili verilmişdir sim, bu sətirdən silinə biləcək minimum simvol sayını tapacaq bir proqram yazın ki, alternativ olsun. A binar ardıcıl 0 və ya 1 yoxsa simli alternativ olduğu deyilir

Giriş Formatı

"S" simli olan ilk sətir.

Çıxış formatı

Birinci sətirdə ikili simli alternativ etmək üçün silinəcək simvolların sayını əks etdirən bir tam dəyər var.

Məhdudiyyətlər

  • 1 <= | s | <= 10 ^ 6
  • s [i] ya 0, ya da 1-dir

misal

0011
2

Explanation: Verilən “0011” sətrində bir-birini əvəz etmək üçün bir sıfır və birini 1 çıxarmaq lazımdır.

Alqoritm

1. Verilən simli s soldan sağa keçin.

2. Mövcud char növbəti char-dan fərqlidirsə, sadəcə növbəti indeksə keçin.

3. Başqa bir simvol silməyimiz lazımdır.

Həyata keçirilməsi

İkili simli alternativ etmək üçün silinəcək minimum simvollar üçün C ++ proqramı

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

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int ans=0;
   for(int i=0;i<n-1;i++)
   {
       if(s[i]==s[i+1])
       {
           ans++;
       }
   }
   cout<<ans<<endl;
   return 0;
}

İkili bir simli alternativ etmək üçün silinəcək minimum simvollar üçün Java proqramı

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                int ans=0;
                for(int i=0;i<n-1;i++)
                {
                    if(a[i]==a[i+1])
                    {
                        ans++;
                    }
                }
                System.out.println(ans);
  } 
} 
00011101
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilən sətrin ölçüsüdür "S". Burada sadəcə simli keçib cari char-un növbəti char-a bərabər olub olmadığını yoxlayırıq. Əgər bərabərdirsə, ans-ı artırın, əks halda növbəti indeksə keçin.

Kosmik Mürəkkəblik

Burada heç bir köməkçi məkan istifadə etmirik, ona görə də kosmik mürəkkəblikdir O (1). Sadəcə burada ikili simli alternativ etmək üçün silinəcək simvol sayını saxlayan bir tam dəyişən elan edirik.

Crack Sistemi Dizayn Müsahibələri
Translate »