【JAVA】【刷題子】473. 火柴拼正方形

語言: CN / TW / HK

theme: smartblue highlight: monokai


持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第9天,點擊查看活動詳情

一、題目與題目分析

題目

你將得到一個整數數組 matchsticks ,其中 matchsticks[i] 是第 i 個火柴棒的長度。你要用 所有的火柴棍 拼成一個正方形。你 不能折斷 任何一根火柴棒,但你可以把它們連在一起,而且每根火柴棒必須 使用一次 。
  如果你能使這個正方形,則返回 true ,否則返回 false 。
(題目來源:力扣:473. 火柴拼正方形
image.png

題目分析

就是給一些固定長度的線段,判斷這些線段是否能組成正方形。
  問題簡單化,先把干擾的排除掉。
  首先,要清楚的是,形成正方形的條件:4條長度一樣的邊。
  因此,就演變成兩個條件:① 邊長4條. ② 每條邊長都相等。

二、整體邏輯與主要代碼

題目分析已經比較清楚了,接下來我們進入代碼設計。

整體邏輯

首先,整體邏輯先把干擾的排除掉。① 把達不到4條線段的排除。 ② 把所有的線段長加起來,加起來的和不能被4整除的(也就是和對4求餘不等於0的)也排除。 ③ 檢查組成的正方形,前提是否基於在限制固定長度下的線段。

主要代碼

整體邏輯也清晰了,也有較清楚的註釋。直接來看代碼吧! (如有不懂的或者更好的建議,歡迎評論區分享友友的看法哈~) ```java class Solution { public boolean makesquare(int[] matchsticks) { int len = matchsticks.length; // 達不到4條線段的排除 if (len < 4) { return false; } int sum = 0; for (int m : matchsticks) { sum += m; } // 所有的線段長加起來,加起來的和不能被4整除的排除 if (sum % 4 != 0) { return false; } // 檢查組成的正方形,前提是否基於在限制固定長度下的線段 int avg = sum / 4; // 平均值 // 排序(升序) Arrays.sort(matchsticks); // 迭代的方法會從排序後的數,最後一個開始回溯(形成倒序,也就是會從最大的開始判斷) int[] newNums = new int[4]; // 定義對應的四條邊 int back = len - 1; // 從最後一個開始回溯 return checkSquare(matchsticks, back, newNums, avg); }

// 迭代進行判斷
public boolean checkSquare(int[] nums, int back, int[] newNums, int avg) {
    if (back == -1) { // 最底層出口
        // 已經到底部了,判斷前三條邊是否等於平均值;(一共四條邊,前三條等於平均值,第四條也等於平均值了。)
        return newNums[0] == avg && newNums[1] == avg && newNums[2] == avg;
    }
    for (int i = 0; i < 4; i++) { // 計算四條邊
        if (newNums[i] + nums[back] > avg) { // 組合的邊是否超出平均值
            continue;
        }
        // 組合邊長
        newNums[i] += nums[back];
        // 迭代追溯到最低
        if (checkSquare(nums, back - 1, newNums, avg)) {
            return true;
        }
        // 不符合的不要
        newNums[i] -= nums[back];
    }
    return false;
}

} ```

三、結果展示

image.png

四、總結

問題很難,解決問題可能更難;別怕,大不了難上加難!

題目數據庫

Gitee:傳送門

文章小尾巴

文章寫作、模板、文章小尾巴可參考:《寫作“小心思”》
  感謝你看到最後,最後再説兩點~
  ①如果你持有不同的看法,歡迎你在文章下方進行留言、評論。
  ②如果對你有幫助,或者你認可的話,歡迎給個小點贊,支持一下~
  我是南方者,一個熱愛計算機更熱愛祖國的南方人。

  (文章內容僅供學習參考,如有侵權,非常抱歉,請立即聯繫作者刪除。)