5130-等價多米諾骨牌對的數量

chaos_G 發布于2019-08-16 18:40 / 897人閱讀

摘要：如果其中某一張多米諾骨牌可以通過旋轉度或度得到另一張多米諾骨牌，我們就認為這兩張牌是等價的。等價多米諾骨牌對的數量暴力破解法有效解答等價多米諾骨牌對的數量由于，所以最大值不會超過以形式表示骨牌對，這個是翻轉度即本身翻轉度后，只要累加一次即可

前言

Weekly Contest 146的等價多米諾骨牌對的數量：

給你一個由一些多米諾骨牌組成的列表 dominoes。
如果其中某一張多米諾骨牌可以通過旋轉 0 度或 180 度得到另一張多米諾骨牌，我們就認為這兩張牌是等價的。
形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等價的前提是 a==c 且 b==d，或是 a==d 且 b==c。
在 0 <= i < j < dominoes.length 的前提下，找出滿足 dominoes[i] 和 dominoes[j] 等價的骨牌對 (i, j) 的數量。
示例：
輸入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出：1
提示：

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

解題思路

一開始我是試了一下暴力破解這個方法，可惜運行超時，只好另想它法了。

后續參考了Java中的HashMap的位桶的設計，思路如下：

數字result表示等價的骨牌對個數，數組arr表示多米諾骨牌出現的次數，其中數組下標i（假設骨牌dominoe=[a,b]，則i=a*10+b）表示對應的多米諾骨牌，arr[i]表示該骨牌出現的次數

遍歷多米諾骨牌列表dominoes，對于每個骨牌dominoe，假設dominoe=[a,b]，然后按照以下邏輯處理

使用a*10+b計算出旋轉0度時在arr的下標index1；使用b*10+a計算出旋轉180度是在arr的下標index2

如果index1等于index2，即表示dominoe的a等于b，此時result增加arr[index1]，同時arr[index1]的值自增（避免多累加一次）即可

如果index1不等于index2，即表示dominoe的a不等于b，此時result增加arr[index1]，同時arr[index1]和arr[index2]都自增。

實現代碼 暴力破解

暴力破解的方法會出現運行超時的情況，這個是一個錯誤的示例，列出來給大家參考一下。

    /**
     * 5130. 等價多米諾骨牌對的數量
     * 暴力破解法
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        for (int i = 0; i < dominoes.length; i++) {
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            for (int j = i+1; j < dominoes.length; j++) {
                int c = dominoes[j][0];
                int d = dominoes[j][1];
                if((a==c && b==d) || (a==d && b==c)){
                    ++result;
                }
            }
        }
        return result;
    }

有效解答

    /**
     * 5130. 等價多米諾骨牌對的數量
     *
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        // 由于1 <= dominoes[i][j] <= 9，所以最大值不會超過99
        int[] arr = new int[100];
        for (int i = 0; i < dominoes.length; i++) {
            // 以ij形式表示骨牌對(i,j)，這個是翻轉0度（即本身）
            int index1=dominoes[i][0]*10+dominoes[i][1];
            // 翻轉180度后
            int index2=dominoes[i][1]*10+dominoes[i][0];
            if(index1 == index2){ // i==j，只要累加一次即可
                result+=arr[index1];
                arr[index1]++;
            }else{
                result+=arr[index1];
                arr[index1]++;
                arr[index2]++;
            }
        }
        return result;
    }

GPU云服務器云服務器戴爾5130cdn 多米諾骨牌 python對的處理等價

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75530.html

第3章：抽象數據類型（ADT）和面向對象編程（OOP） 3.2設計規約

摘要：程序失敗時，很難確定錯誤的位置。它保護客戶免受單位工作細節的影響。將前提條件放在中，并將后置條件放入和。涉及可變對象的契約現在取決于每個引用可變對象的每個人的良好行為。設計規約按規約分類比較規約它是如何確定性的。大綱 1.編程語言中的功能/方法2.規約：便于交流的編程，為什么需要規約行為等同規約結構：前提條件和后條件測試和驗證規約3.設計規約分類規約圖表規約質量規約4.總結編程...

mozillazg 2019-08-16 12:34 評論0 收藏0
【EASYDOM系列教程】之獲取內聯樣式

摘要：回顧什么是內聯樣式所謂內聯樣式，就是通過頁面元素的屬性為當前元素定義樣式。對象提供的屬性和方法可以幫助我們獲取樣式的具體內容。遍歷對象由于對象具有屬性，返回該對象的屬性的數量。方法通過獲取的樣式屬性名，這種方式也可以通過方式進行替換。回顧什么是內聯樣式所謂內聯樣式，就是通過 HTML 頁面元素的 style 屬性為當前元素定義 CSS 樣式。以下代碼示例，就是通過 style 屬...

xiaodao 2019-08-22 11:05 評論0 收藏0
關于javascript函數式編程中compose的實現

摘要：結論這次主要介紹了函數式編程中的函數的原理和實現方法，由于篇幅原因，我把打算分析的源碼實現放到下一篇來介紹，可以說實現的更加函數式，需要單獨好好分析。上一篇文章介紹了javascript函數式編程中curry（柯里化）的實現，當然那個柯里化是有限參數的柯里化，等有機會在補上無限參數的那一種柯里化，這次主要說的是javascript函數式編程中另外一個很重要的函數compose，com...

jonh_felix 2019-08-20 14:21 評論0 收藏0
《javascript高級程序設計》筆記：Function類型

摘要：這么長時間沒有寫博客，就是因為函數這部分比較麻煩，自己一直想抽出大把的時間來研究這個，可是結果卻是一拖再拖，這樣不好。這么長時間沒有寫博客，就是因為函數這部分比較麻煩，自己一直想抽出大把的時間來研究這個，可是結果卻是一拖再拖，這樣不好。有時間就寫才是王道啊，不然這計劃得一直卡在這里了.. 1. 幾個概念函數：將代碼進行封裝, 復用的邏輯單元（代碼）對象：無序鍵值對的集合數組：有序鍵...

habren 2019-08-21 12:05 評論0 收藏0
Codepen 每周精選：22個頁面特效（2018-5-2）

摘要：按下右側的點擊預覽按鈕可以在當前頁面預覽，點擊鏈接可以打開原始頁面。按下右側的點擊預覽按鈕可以在當前頁面預覽，點擊鏈接可以打開原始頁面。 1. 觀影打分特效https://codepen.io/PointC/pen... 2. 純 css 寫的騎自行車的動畫https://codepen.io/dmaristem/... 3. 移動端菜單特效https://codepen.io/mi...

ddongjian0000 2019-08-29 15:15 評論0 收藏0