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

theme: smartblue highlight: monokai

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

一、題目與題目分析

題目

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

題目分析

就是給一些固定長度的線段，判斷這些線段是否能組成正方形。
　　問題簡單化，先把干擾的排除掉。
　　首先，要清楚的是，形成正方形的條件：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;
}

} ```

三、結果展示

四、總結

問題很難，解決問題可能更難；別怕，大不了難上加難！

題目數據庫

Gitee：傳送門

文章小尾巴

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

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