সমান ডমিনো জোড় লেটকোড সমাধানের সংখ্যা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক
বিন্যাস

সমস্যা বিবৃতি

সমান সংখ্যক ডোমিনো জোড় সংখ্যায়, "আমাদের ডোমিনোজের একটি তালিকা দেওয়া আছে যেখানে প্রতিটি ডোমিনোতে ডোমিনোজের মতো দুটি মান থাকে [i] = [ক, খ]। দুটি ডোমিনোস, ডোমিনয়েজ [i] = [ক, খ] এবং ডমিনোস [জে] = [সি, ডি] সমতুল্য হলে (এ == সি এবং বি == ডি) বা (এ == ডি এবং সি == ডি) ।

সমান ডমিনো জোড় লেটকোড সমাধানের সংখ্যা

আমাদের কাজটি হ'ল আমি! = জে এবং ডোমিনোস [i] কোথায় থাকা মোট জোড়ার সংখ্যা (i, জে) সন্ধান করা is সমতুল্য to dominoes [j]। A এবং b এর মান দেওয়া হয়েছে [1,9] এর মধ্যে।

উদাহরণ

dominoes = [[1,2],[2,1],[3,4],[5,6]]
1

ব্যাখ্যা: এই উদাহরণে ডোমিনোস [0] ডোমিনোজের সমতুল্য [1] কারণ এটি শর্তটি সন্তুষ্ট করছে (a == d এবং c == d)। যেহেতু এটি একমাত্র জুটি সন্তোষজনক ডমিনো মানদণ্ডের তাই উত্তরটি একটি।

সমান ডমিনো পেয়ারস লেটকোড সলিউশন সংখ্যার জন্য পদ্ধতির ach

আমরা ডোমিনো নির্বাচন করে এবং তারপরে বাকী সমস্ত ডোমিনয়েস নির্বাচিত ডোমিনির সমান কিনা তা পরীক্ষা করে এই সমস্যার সমাধান করতে পারি। আমরা এটি সমস্ত ডোমিনোয়ের জন্য করব এবং তারপরে সমমানের ডোমিনোজের মোট গণনা 2 দিয়ে ভাগ করে উত্তর দেব। তবে এই পদ্ধতির জন্য সময় জটিলতা হ'ল ও (এন * এন)। আমরা নীচের পদক্ষেপগুলি অনুসরণ করে ও (এন) সময়ে এই সমস্যাটি সমাধান করতে পারি:

  1. আমরা দুটি সংখ্যার (ক, খ) একক সংখ্যায় রূপান্তর করব, এটি সমতা সমীক্ষা সহজ করে তুলবে।
  2. এই হ্যাশ ফাংশনটি দুটি সংখ্যাকে একটি সংখ্যায় সি = মিনিট (ক, খ) * 10 + সর্বোচ্চ (ক, খ) রূপান্তর করবে।
  3. এখন আমরা প্রতিটি সংখ্যার ফ্রিকোয়েন্সি গণনা করার জন্য একটি হ্যাশ টেবিল তৈরি করব।
  4. আমরা ডোমিনয়েস অ্যারে অতিক্রম করব এবং সি এর ফ্রিকোয়েন্সি হ্যাশ টেবিলে সংরক্ষণ করব।
  5. সি মানগুলির ফ্রিকোয়েন্সি গণনার পরে আমরা সমতুল্য ডোমিনোজের সংখ্যা গণনা করতে পারি। ধরুন একটি হ্যাশ টেবিলের মধ্যে একটি সংখ্যার এক্স এর ফ্রিকোয়েন্সি রয়েছে তবে মান x এর সমতুল্য জোড়ার সংখ্যা হবে fC2 যা (f * (f-1)) / 2 হবে।
  6. আমরা হ্যাশ টেবিলটি অতিক্রম করব এবং হ্যাশ টেবিলের প্রতিটি প্রবেশের সমতুল্য ডোমিনোজের সংখ্যার যোগ করে মোট সমতুল্য ডোমিনয়েসের সংখ্যা গণনা করব।

বাস্তবায়ন

সমমানের ডোমিনো জোড়গুলির সংখ্যার জন্য সি ++ কোড

#include <bits/stdc++.h> 
using namespace std; 
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int, int> count;
        int res = 0;
        for (auto& d : dominoes) {
           count[min(d[0], d[1]) * 10 + max(d[0], d[1])]++;
        }
         for (auto const& pair: count)
         {
          int v= pair.second; 
          res += v * (v - 1) / 2;
         }

        return res;
    }

int main() 
{ 
    vector<vector<int>> dominoes
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
int ans=numEquivDominoPairs(dominoes); 
 cout<<ans<<endl;
 return 0;
}
1

সমান ডমিনো পেয়ার সংখ্যার জন্য জাভা কোড

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int[] d : dominoes) {
            int k = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]);
            count.put(k, count.getOrDefault(k, 0) + 1);
        }
        for (int v : count.values()) {
            res += v * (v - 1) / 2;
        }
        return res;
    }
  public static void main(String[] args) {
        int[][] dominoes=
    {
        {1,2},
        {2,1},
        {3,4},
        {5,6}
    };
        int ans=numEquivDominoPairs(dominoes); 
        System.out.println(ans);
  }
}
1

সমান ডমিনো পেয়ারস লেটকোড সলিউশন সংখ্যার জটিলতা বিশ্লেষণ

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা উপর) কারণ আমরা ডমিনোস অ্যারে কেবল একবারই পার করছি। এখানে n হল ডোমিনোস অ্যারের দৈর্ঘ্য।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা উপর) কারণ আমরা একটি হ্যাশ টেবিল তৈরি করছি।

তথ্যসূত্র