சமமான டோமினோ சோடிகள் லீட்கோட் தீர்வின் எண்ணிக்கை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான்
அணி

சிக்கல் அறிக்கை

”சமமான டோமினோ சோடிகளின் எண்ணிக்கை” என்ற சிக்கலில், ஒவ்வொரு டோமினோவும் டோமினோக்கள் [i] = [a, b] போன்ற இரண்டு மதிப்புகளைக் கொண்ட டோமினோக்களின் பட்டியல் எங்களுக்கு வழங்கப்படுகிறது. (A == c மற்றும் b == d) அல்லது (a == d மற்றும் c == d) என்றால் இரண்டு டோமினோக்கள், டோமினோக்கள் [i] = [a, b] மற்றும் டோமினோக்கள் [j] = [c, d] சமம். .

சமமான டோமினோ சோடிகள் லீட்கோட் தீர்வின் எண்ணிக்கை

நான்! = J மற்றும் டோமினோக்கள் [i] இருக்கும் ஜோடியின் மொத்த எண்ணிக்கையை (i, j) கண்டுபிடிப்பதே எங்கள் பணி இணையான டோமினோக்களுக்கு [j]. A மற்றும் b இன் மதிப்புகள் [1,9] வரம்பில் உள்ளன.

உதாரணமாக

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

விளக்கம்: இந்த எடுத்துக்காட்டில் டோமினோக்கள் [0] டோமினோக்களுக்கு சமம் [1] ஏனெனில் இது நிலைமையை திருப்திப்படுத்துகிறது (a == d மற்றும் c == d). சமமான டோமினோ அளவுகோல்களை திருப்திப்படுத்தும் ஒரே ஜோடி இது என்பதால், பதில் ஒன்று.

சமமான டோமினோ சோடிகள் லீட்கோட் தீர்வின் எண்ணிக்கைக்கான அணுகுமுறை

ஒரு டோமினோவைத் தேர்ந்தெடுத்து, மீதமுள்ள டோமினோக்கள் தேர்ந்தெடுக்கப்பட்ட டோமினோவுக்கு சமமானதா இல்லையா என்பதைச் சரிபார்த்து இந்த சிக்கலை நாம் தீர்க்க முடியும். எல்லா டோமினோக்களுக்கும் இதைச் செய்வோம், பின்னர் சமமான டோமினோக்களின் மொத்த எண்ணிக்கையை 2 ஆல் வகுப்போம். ஆனால் இந்த அணுகுமுறையின் நேர சிக்கலானது O (n * n) ஆக இருக்கும். பின்வரும் படிகளைப் பின்பற்றுவதன் மூலம் O (n) நேரத்தில் இந்த சிக்கலை தீர்க்க முடியும்:

  1. நாங்கள் இரண்டு எண்களை (a, b) ஒற்றை எண்ணாக மாற்றுவோம், இது சமநிலையை சரிபார்க்க எளிதாக்கும்.
  2. இந்த ஹாஷ் செயல்பாடு இரண்டு எண்களை ஒரு எண்ணாக மாற்றும் c = min (a, b) * 10 + அதிகபட்சம் (a, b).
  3. இப்போது ஒவ்வொரு எண்ணின் அதிர்வெண்ணையும் கணக்கிட ஒரு ஹாஷ் அட்டவணையை உருவாக்குவோம்.
  4. நாங்கள் டோமினோக்களின் வரிசையை கடந்து, ஹாஷ் அட்டவணையில் c இன் அதிர்வெண்ணை சேமிப்போம்.
  5. சி மதிப்புகளின் அதிர்வெண்ணைக் கணக்கிட்ட பிறகு, சமமான டோமினோக்களின் எண்ணிக்கையை நாம் கணக்கிடலாம். ஒரு எண் x க்கு ஹாஷ் அட்டவணையில் f அதிர்வெண் இருப்பதாக வைத்துக்கொள்வோம், பின்னர் மதிப்பு 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) ஏனென்றால் நாங்கள் டோமினோக்களின் வரிசையை ஒரு முறை மட்டுமே கடந்து செல்கிறோம். இங்கே n என்பது டோமினோஸ் வரிசையின் நீளம்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (n) ஏனெனில் நாங்கள் ஒரு ஹாஷ் அட்டவணையை உருவாக்குகிறோம்.

குறிப்புகள்