จำนวนคู่ที่เทียบเท่ากับโซลูชัน Leetcode ของ Domino


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน
แถว

คำชี้แจงปัญหา

ในปัญหา "จำนวนคู่โดมิโนที่เท่ากัน" เราจะได้รับรายการของโดมิโนที่แต่ละโดมิโนประกอบด้วยสองค่าเช่นโดมิโน [i] = [a, b] สองโดมิโนโดมิโน [i] = [a, b] และโดมิโน [j] = [c, d] เทียบเท่ากันถ้า (a == c และ b == d) หรือ (a == d และ c == d) .

จำนวนคู่ที่เทียบเท่ากับโซลูชัน Leetcode ของ Domino

งานของเราคือหาจำนวนคู่ทั้งหมด (i, j) โดยที่ i! = j และแต้ม [i] คือ เท่ากัน ถึงโดมิโน [j] ค่าของ a และ b อยู่ในช่วง [1,9]

ตัวอย่าง

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

คำอธิบาย: ในตัวอย่างนี้โดมิโน [0] เทียบเท่ากับโดมิโน [1] เนื่องจากเป็นไปตามเงื่อนไข (a == d และ c == d) เนื่องจากนี่เป็นคู่เดียวที่ตรงตามเกณฑ์โดมิโนที่เทียบเท่ากันดังนั้นคำตอบจึงเป็นหนึ่งเดียว

แนวทางสำหรับจำนวนโซลูชัน Leetcode ของ Domino Pairs ที่เท่ากัน

เราสามารถแก้ปัญหานี้ได้โดยเลือกโดมิโนจากนั้นตรวจสอบโดมิโนอื่น ๆ ที่เหลือทั้งหมดว่าเทียบเท่ากับโดมิโนที่เลือกหรือไม่ เราจะทำสิ่งนี้สำหรับโดมิโนทั้งหมดจากนั้นหารจำนวนแต้มทั้งหมดของโดมิโนที่เท่ากันด้วย 2 จะให้คำตอบ แต่ความซับซ้อนของเวลาสำหรับแนวทางนี้จะเป็น O (n * n) เราสามารถแก้ปัญหานี้ได้ในเวลา O (n) โดยทำตามขั้นตอนด้านล่าง:

  1. เราจะแปลงตัวเลขสองตัว (a, b) ให้เป็นเลขตัวเดียวซึ่งจะทำให้การตรวจสอบความเท่าเทียมเป็นเรื่องง่าย
  2. ฟังก์ชันแฮชนี้จะแปลงตัวเลขสองตัวเป็นหนึ่งหมายเลข c = min (a, b) * 10 + max (a, b)
  3. ตอนนี้เราจะสร้างตารางแฮชเพื่อนับความถี่ของแต่ละหมายเลข
  4. เราจะสำรวจอาร์เรย์โดมิโนและจะเก็บความถี่ของ c ไว้ในตารางแฮช
  5. หลังจากคำนวณความถี่ของค่า c แล้วเราสามารถคำนวณจำนวนโดมิโนที่เท่ากันได้ สมมติว่าตัวเลข x มีความถี่ f ในตารางแฮชจำนวนคู่ที่เท่ากันสำหรับค่า x จะเป็น fC2 นั่นคือ (f * (f-1)) / 2
  6. เราจะสำรวจตารางแฮชและจะคำนวณจำนวนโดมิโนที่เทียบเท่าทั้งหมดโดยการสรุปจำนวนโดมิโนที่เท่ากันของแต่ละรายการในตารางแฮช

การดำเนินงาน

รหัส C ++ สำหรับจำนวนคู่โดมิโนที่เทียบเท่า

#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

รหัส Java สำหรับจำนวนคู่ Domino ที่เทียบเท่า

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

การวิเคราะห์ความซับซ้อนของจำนวนเท่าของโซลูชัน Leetcode คู่ Domino Pairs

ความซับซ้อนของเวลา

ความซับซ้อนของเวลาของรหัสข้างต้นคือ O (n) เพราะเราข้ามผ่านอาร์เรย์โดมิโนเพียงครั้งเดียว นี่คือความยาวของอาร์เรย์โดมิโน

ความซับซ้อนของพื้นที่

ความซับซ้อนของช่องว่างของรหัสข้างต้นคือ O (n) เพราะเรากำลังสร้างตารางแฮช

อ้างอิง