成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

5130-等價(jià)多米諾骨牌對(duì)的數(shù)量

chaos_G / 902人閱讀

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

前言

Weekly Contest 146的 等價(jià)多米諾骨牌對(duì)的數(shù)量：

給你一個(gè)由一些多米諾骨牌組成的列表 dominoes。


如果其中某一張多米諾骨牌可以通過(guò)旋轉(zhuǎn) 0 度或 180 度得到另一張多米諾骨牌，我們就認(rèn)為這兩張牌是等價(jià)的。


形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等價(jià)的前提是 a==c 且 b==d，或是 a==d 且 b==c。


在 0 <= i < j < dominoes.length 的前提下，找出滿足 dominoes[i] 和 dominoes[j] 等價(jià)的骨牌對(duì) (i, j) 的數(shù)量。


示例：


輸入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出：1


提示：



1 <= dominoes.length <= 40000


1 <= dominoes[i][j] <= 9
解題思路

一開始我是試了一下暴力破解這個(gè)方法，可惜運(yùn)行超時(shí)，只好另想它法了。

后續(xù)參考了Java中的HashMap的位桶的設(shè)計(jì)，思路如下：

數(shù)字result表示等價(jià)的骨牌對(duì)個(gè)數(shù)，數(shù)組arr表示多米諾骨牌出現(xiàn)的次數(shù)，其中數(shù)組下標(biāo)i（假設(shè)骨牌dominoe=[a,b]，則i=a*10+b）表示對(duì)應(yīng)的多米諾骨牌，arr[i]表示該骨牌出現(xiàn)的次數(shù)

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

使用a*10+b計(jì)算出旋轉(zhuǎn)0度時(shí)在arr的下標(biāo)index1；使用b*10+a計(jì)算出旋轉(zhuǎn)180度是在arr的下標(biāo)index2

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

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

實(shí)現(xiàn)代碼 暴力破解

暴力破解的方法會(huì)出現(xiàn)運(yùn)行超時(shí)的情況，這個(gè)是一個(gè)錯(cuò)誤的示例，列出來(lái)給大家參考一下。

    /**
     * 5130. 等價(jià)多米諾骨牌對(duì)的數(shù)量
     * 暴力破解法
     * @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. 等價(jià)多米諾骨牌對(duì)的數(shù)量
     *
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        // 由于1 <= dominoes[i][j] <= 9，所以最大值不會(huì)超過(guò)99
        int[] arr = new int[100];
        for (int i = 0; i < dominoes.length; i++) {
            // 以ij形式表示骨牌對(duì)(i,j)，這個(gè)是翻轉(zhuǎn)0度（即本身）
            int index1=dominoes[i][0]*10+dominoes[i][1];
            // 翻轉(zhuǎn)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;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75530.html

相關(guān)文章

  • 第3章：抽象數(shù)據(jù)類型（ADT）和面向?qū)ο缶幊蹋∣OP） 3.2設(shè)計(jì)規(guī)約

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

    mozillazg 評(píng)論0 收藏0

  • 【EASYDOM系列教程】之獲取內(nèi)聯(lián)樣式

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

    xiaodao 評(píng)論0 收藏0

  • 關(guān)于javascript函數(shù)式編程中compose的實(shí)現(xiàn)

    摘要：結(jié)論這次主要介紹了函數(shù)式編程中的函數(shù)的原理和實(shí)現(xiàn)方法，由于篇幅原因，我把打算分析的源碼實(shí)現(xiàn)放到下一篇來(lái)介紹，可以說(shuō)實(shí)現(xiàn)的更加函數(shù)式，需要單獨(dú)好好分析。 上一篇文章介紹了javascript函數(shù)式編程中curry（柯里化）的實(shí)現(xiàn)，當(dāng)然那個(gè)柯里化是有限參數(shù)的柯里化，等有機(jī)會(huì)在補(bǔ)上無(wú)限參數(shù)的那一種柯里化，這次主要說(shuō)的是javascript函數(shù)式編程中另外一個(gè)很重要的函數(shù)compose，com...

    jonh_felix 評(píng)論0 收藏0

  • 《javascript高級(jí)程序設(shè)計(jì)》筆記：Function類型

    摘要：這么長(zhǎng)時(shí)間沒(méi)有寫博客，就是因?yàn)楹瘮?shù)這部分比較麻煩，自己一直想抽出大把的時(shí)間來(lái)研究這個(gè)，可是結(jié)果卻是一拖再拖，這樣不好。 這么長(zhǎng)時(shí)間沒(méi)有寫博客，就是因?yàn)楹瘮?shù)這部分比較麻煩，自己一直想抽出大把的時(shí)間來(lái)研究這個(gè)，可是結(jié)果卻是一拖再拖，這樣不好。有時(shí)間就寫才是王道啊，不然這計(jì)劃得一直卡在這里了.. 1. 幾個(gè)概念 函數(shù)：將代碼進(jìn)行封裝, 復(fù)用的邏輯單元（代碼）對(duì)象：無(wú)序鍵值對(duì)的集合數(shù)組：有序鍵...

    habren 評(píng)論0 收藏0

  • Codepen 每周精選：22個(gè)頁(yè)面特效（2018-5-2）

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

    ddongjian0000 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<