554. 磚牆

你的面前有一堵矩形的、由 n 行磚塊組成的磚牆。這些磚塊高度相同（也就是一個機關高）但是寬度不同。每一行磚塊的寬度之和應該相等。

你現在要畫一條自頂向下的、穿過最少磚塊的垂線。如果你畫的線隻是從磚塊的邊緣經過，就不算穿過這塊磚。你不能沿着牆的兩個垂直邊緣之一畫線，這樣顯然是沒有穿過一塊磚的。

給你一個二維數組 wall ，該數組包含這堵牆的相關資訊。其中，wall[i] 是一個代表從左至右每塊磚的寬度的數組。你需要找出怎樣畫才能使這條線穿過的磚塊數量最少，并且傳回穿過的磚塊數量。

示例 1：

LeetCode 刷題記錄(每日一題)350. 兩個數組的交集 II

輸入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

輸出：2

示例 2：

輸入：wall = [[1],[1],[1]]

輸出：3

提示：

n == wall.length

1 <= n <= 104

1 <= wall[i].length <= 104

1 <= sum(wall[i].length) <= 2 * 104

對于每一行 i ，sum(wall[i]) 應當是相同的

1 <= wall[i][j] <= 231 - 1

自己想法:

就是周遊總長-1次，這樣每個狹縫都會周遊，就是假設所有的都當成1，周遊這麼多次，當值不為1時就是說狹縫被堵，sum++。找出每條縫的磚數，然後找出最小。

寫代碼一小時，調試一小時。

一直有這個錯誤

錯誤原因是:我使用list.get(n)，中目前list隻有2個值，你n卻大于等于2.超出了list大小。

public static int leastBricks(List<List<Integer>> wall) {
        Iterator it = wall.get(0).iterator();
        int hc = 0;
        while (it.hasNext()) {
            hc += (int) it.next();
        }
        int min = wall.size();
        Map map = new HashMap();
        for (int bll = 0; bll < hc - 1; bll++) {
            int sum = 0;
            int dq = 0;
            int dqbll = bll;
            for (int blh = 0; blh < wall.size(); blh++) {
                bll = dqbll;
                if (map.get(blh) != null) {
                    bll = (int) map.get(blh);
                }
                if (wall.get(blh).size() <= bll) {
                    bll = wall.get(blh).size() - 1;
                }
                dq = wall.get(blh).get(bll);
                if (dq == 1) {
                    if (map.get(blh) != null)
                        map.remove(blh);
                }
                if (dq > 1) {
                    sum++;
                    dq--;
                    wall.get(blh).set(bll, dq);
                    map.put(blh, bll);

                }
                bll = dqbll;
            }
            if (sum < min) {
                min = sum;
            }
        }

        return min;

    }

官方簡答

public static int leastBricks1(List<List<Integer>> wall) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (List<Integer> widths : wall) {
            int n = widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                sum += widths.get(i);
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            }
        }
        int maxCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            maxCnt = Math.max(maxCnt, entry.getValue());
        }
        return wall.size() - maxCnt;
    }

檢視了題解，就是看完了一遍答案後自己又重新寫了

public static int a(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        for (List<Integer> xwall : wall) {
            int sum = 0;
            int n = xwall.size();
            for (int i = 0; i < n - 1; i++) {
                sum += xwall.get(i);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        int fmax = 0;
        for (Integer value : map.values()) {
            fmax = Math.max(fmax, value);
        }

        return wall.size() - fmax;
       
    }

map下的getOrDefault(1，2)第一次見到，功能是尋找map裡面有則是1，無則是預設值2

map的周遊，

for (Integer value : map.values()) { } //隻需要值
for (Integer value : map.keySet()) { }//隻鍵
for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) { }//值鍵都有

看完人家代碼發現，還是得多練習，要不然真想不到。雖然現在感覺就反向想一下。。。

每日一題

2021/5/2 16:19

350. 兩個數組的交集 II

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]

輸出：[2,2]

示例 2:

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

輸出：[4,9]

說明：

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現次數的最小值一緻。

我們可以不考慮輸出結果的順序。

代碼還有問題，不想改了，改不出來問題應該是雙重for循環。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        
        int min = Math.min(nums1.length,nums2.length);
        Map<Integer,Integer> map = new HashMap();
        for(int nums : nums1){
            int sum = map.getOrDefault(nums,0)+1;
            map.put(nums,sum);
        }

        int[] res = new int[min];
        int f=0;
      for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                int count = map.getOrDefault(nums2[j],0);
                if(count>0){
                    res[f++] = nums2[j];
                    count--;
                    if(count>0){
                        map.put(nums2[j],count);
                    }else{
                        map.remove(nums2[j]);
                    }
                }
            }
        }
        return Arrays.copyOfRange(res, 0, f);
    }
}

題解

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

Arrays.copyOfRange(intersection, 0, index); 該方法從0 開始到index截止，将原數組截取到新數組并傳回。
if (nums1.length > nums2.length) {

return intersect(nums2, nums1);

}

用于確定nums1為小的數組，居然還能這樣寫，看的時候都沒看懂。。。

2021/5/5 20:12

1720. 解碼異或後的數組

未知整數數組 arr 由 n 個非負整數組成。

經編碼後變為長度為 n - 1 的另一個整數數組 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 經編碼後得到 encoded = [1,2,3] 。

給你編碼後的數組 encoded 和原數組 arr 的第一個元素 first（arr[0]）。

請解碼傳回原數組 arr 。可以證明答案存在并且是唯一的。

示例 1：

輸入：encoded = [1,2,3], first = 1

輸出：[1,0,2,1]

解釋：若 arr = [1,0,2,1] ，那麼 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

輸入：encoded = [6,2,7,3], first = 4

輸出：[4,2,0,7,4]

class Solution {
    public int[] decode(int[] encoded, int first) {
        int[] arr = new int[encoded.length+1];
        
         arr[0] =  first; 
         int a=1;
         int b=0;
        for(int i=0;i< encoded.length;i++){
            arr[a++] = encoded[i] ^ arr[b++];  
        }

        return arr;
    }
}

今天代碼簡單。

異或就是 a^b ab相同為0，不同為1.

2021/5/6 21:59

1486. 數組異或操作

給你兩個整數，n 和 start 。

數組 nums 定義為：nums[i] = start + 2*i（下标從 0 開始）且 n == nums.length 。

請傳回 nums 中所有元素按位異或（XOR）後得到的結果。

示例 1：

輸入：n = 5, start = 0

輸出：8

解釋：數組 nums 為 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。

“^” 為按位異或 XOR 運算符。

示例 2：

輸入：n = 4, start = 3

輸出：8

解釋：數組 nums 為 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：

輸入：n = 1, start = 7

輸出：7

這題真簡單，不過還有另外一種解法

class Solution {
    public int xorOperation(int n, int start) {
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = start +2*i;
        }
        int res=nums[0];
        for(int j=1;j<n;j++){
            res = res ^ nums[j];
        }
        return res;
    }
}

2021/5/7 16:18

LeetCode 刷題記錄(每日一題)350. 兩個數組的交集 II

554. 磚牆

350. 兩個數組的交集 II

1720. 解碼異或後的數組

1486. 數組異或操作

繼續閱讀

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程式設計

leetcode809

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希