473. 火柴拼正方形

題目

(https://leetcode-cn.com/problems/matchsticks-to-square/)
還記得童話《賣火柴的小女孩》嗎制恍?現(xiàn)在进萄,你知道小女孩有多少根火柴吆你,請找出一種能使用所有火柴拼成一個正方形的方法肆汹。不能折斷火柴终吼,可以把火柴連接起來酪惭,并且每根火柴都要用到。

輸入為小女孩擁有火柴的數(shù)目掂碱,每根火柴用其長度表示怜姿。輸出即為是否能用所有的火柴拼成正方形。

示例 1:

輸入: [1,1,2,2,2]
輸出: true

解釋: 能拼成一個邊長為2的正方形疼燥,每邊兩根火柴沧卢。
示例 2:

輸入: [3,3,3,3,4]
輸出: false

解釋: 不能用所有火柴拼成一個正方形。
注意:

給定的火柴長度和在 0 到 10^9之間醉者。
火柴數(shù)組的長度不超過15但狭。

分析

首先判斷什么情況下不能形成正方形。什么情況可以撬即。
如果邊數(shù)少于4跟邊數(shù)不是4的倍數(shù)立磁。肯定不能形成正方形

首先我們一邊一邊放火材剥槐。如果超過邊長的話唱歧,就回溯。一直到每個邊都剛好擺成正方形
就無腦遍歷粒竖。

代碼

class Solution {
    public boolean makesquare(int[] nums) {
        //如果邊少于4不能形成正方形
         if (null == nums || nums.length<4){
                return false;
            }
            int account = 0 ;
            for (int temp:nums) {
                account += temp;
            }
        //變數(shù)總和不是4的倍數(shù)不能成為正方形
            if (account%4!=0){
                return false;
            }
            //冒泡排序 降序
            for (int k = 0; k < nums.length - 1; k++) {
                for (int j = k + 1; j < nums.length; j++) {
                    if (nums[k] < nums[j]) {
                        int temp = nums[k];
                        nums[k] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
            int sideLength = account/4;
            for (int i:nums) {
                //如果有一邊大于邊長颅崩。不能形成正方形
                if (i>sideLength){
                    return false;
                }
            }
        //四邊
            int [] sides = new int[4];

            boolean search = search(0, sides, nums, sideLength);

            return search;
    }
    private static boolean search(int pos,int[] sides,int[] nums,int sideLength) {
            //遍歷完成后判斷每一邊是否都相等
            if(pos >= nums.length){
                return  sides[0] == sideLength && sides[1] == sideLength
                        && sides[2] == sideLength && sides[3] == sideLength;
            }

            for (int i = 0; i < sides.length; i++) {
                if (sides[i]+nums[pos]>sideLength){
                    continue;
                }
                sides[i] += nums[pos];

            
                if (search(pos+1,sides,nums,sideLength)){
                    return true;
                };
                //回溯
                sides[i] = sides[i]-nums[pos];
            }



            return false;
        }
}

結(jié)果

image.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市蕊苗,隨后出現(xiàn)的幾起案子沿后,更是在濱河造成了極大的恐慌,老刑警劉巖岁歉,帶你破解...
    沈念sama閱讀 211,743評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件得运,死亡現(xiàn)場離奇詭異膝蜈,居然都是意外死亡,警方通過查閱死者的電腦和手機熔掺,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評論 3 385
  • 文/潘曉璐 我一進店門饱搏,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人置逻,你說我怎么就攤上這事推沸。” “怎么了券坞?”我有些...
    開封第一講書人閱讀 157,285評論 0 348
  • 文/不壞的土叔 我叫張陵鬓催,是天一觀的道長。 經(jīng)常有香客問我恨锚,道長宇驾,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,485評論 1 283
  • 正文 為了忘掉前任猴伶,我火速辦了婚禮课舍,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘他挎。我一直安慰自己筝尾,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 65,581評論 6 386
  • 文/花漫 我一把揭開白布办桨。 她就那樣靜靜地躺著筹淫,像睡著了一般。 火紅的嫁衣襯著肌膚如雪呢撞。 梳的紋絲不亂的頭發(fā)上损姜,一...
    開封第一講書人閱讀 49,821評論 1 290
  • 那天,我揣著相機與錄音殊霞,去河邊找鬼薛匪。 笑死,一個胖子當(dāng)著我的面吹牛脓鹃,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播古沥,決...
    沈念sama閱讀 38,960評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼瘸右,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了岩齿?” 一聲冷哼從身側(cè)響起太颤,我...
    開封第一講書人閱讀 37,719評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎盹沈,沒想到半個月后吃谣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體岗憋,經(jīng)...
    沈念sama閱讀 44,186評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡监徘,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,516評論 2 327
  • 正文 我和宋清朗相戀三年倦春,在試婚紗的時候發(fā)現(xiàn)自己被綠了溅漾。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,650評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡锐借,死狀恐怖钞翔,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情汰扭,我是刑警寧澤,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布,位于F島的核電站歉胶,受9級特大地震影響验毡,放射性物質(zhì)發(fā)生泄漏璃氢。R本人自食惡果不足惜一也,卻給世界環(huán)境...
    茶點故事閱讀 39,936評論 3 313
  • 文/蒙蒙 一喉脖、第九天 我趴在偏房一處隱蔽的房頂上張望椰苟。 院中可真熱鬧,春花似錦树叽、人聲如沸舆蝴。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽洁仗。三九已至,卻和暖如春性锭,著一層夾襖步出監(jiān)牢的瞬間赠潦,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評論 1 266
  • 我被黑心中介騙來泰國打工草冈, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留她奥,地道東北人。 一個月前我還...
    沈念sama閱讀 46,370評論 2 360
  • 正文 我出身青樓怎棱,卻偏偏與公主長得像方淤,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子蹄殃,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,527評論 2 349

推薦閱讀更多精彩內(nèi)容

  • 更多干貨就在我的個人博客 BlackBlog.tech 歡迎關(guān)注!也可以關(guān)注我的csdn博客:黑哥的博客謝謝大家你踩!...
    BlackBlog__閱讀 1,338評論 0 5
  • 長方形與正方形 教學(xué)目標: 1诅岩、 結(jié)合觀察讳苦、操作活動,能夠用自然的語言描述長方形和正方形的特征吩谦。 2鸳谜、 了解折、畫...
    密芬閱讀 1,406評論 0 1
  • 作者:yooongchun個人網(wǎng)站:www.yooongchun.com轉(zhuǎn)載申明:文章內(nèi)容原創(chuàng)式廷,轉(zhuǎn)載請注明出處咐扭! ...
    yooongchun閱讀 2,044評論 0 1
  • 這幾日,許多交大的同事朋友都在曬校園里的櫻花滑废。突然產(chǎn)生了回去賞櫻花的想法蝗肪。 西交大每年的櫻花季是最迷人的。這時侯蠕趁,...
    卡斯特羅梁閱讀 376評論 0 0
  • 兒子送走了薛闪,行李鋪蓋順豐快遞。 在義烏售票窗口折騰半個小時俺陋,反復(fù)彈出的“驗證碼錯誤”把我搞蒙了豁延。好言好語對待售票小...
    石默默閱讀 203評論 0 0