LeetCode(16) -- 876, 883, 884, 888, 892

P876. Middle of the Linked List (Easy)

非空，单向链表，返回中间的节点。

我的思路

快慢指针。

我的代码

public class E_876_MiddleoftheLinkedList {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

100%, 有点过于简单了。。。

最优解

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next !=null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

P883. Projection Area of 3D Shapes (Easy)

在一个三维空间时摆放111 的小立方体。用一个二维数组来表示每个格子摆放几个立方体。grid[i][j]代表摆放的个数。当分别从三个角度看这个三维物体时，求它们的面积和。

我的思路

俯视图是最容易的，就是这个数组一共有多少个元素。然后再找每个小数组里最大是几，累加起来。最后再找所有小数组中同一个位置最大是几。

我的代码

public class E_883_ProjectionAreaof3DShapes {
    public int projectionArea(int[][] grid) {
        int xSum = 0, ySum = 0, zSum = 0;
        int[] yMax = new int[grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            int xMax = 0;
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] > 0) {
                    zSum++;
                }
                xMax = Math.max(xMax, grid[i][j]);
                yMax[j] = Math.max(yMax[j], grid[i][j]);
            }
            xSum += xMax;
        }
        for (int max : yMax) {
            ySum += max;
        }
        return xSum + ySum + zSum;
    }
}

40%

最优解

class Solution {
    public int projectionArea(int[][] grid) {

        int length = grid.length;
        int width = grid[0].length;
        int[] left = new int[length];
        int area = 0;

        for (int i = 0 ; i < length ; i++) {
            int right = 0;
            for (int j = 0 ; j < length ; j++) {
                if (grid[i][j] != 0) {
                    area += 1;
                }

                if (grid[i][j] > right) {
                    right = grid[i][j];
                }

                if (grid[i][j] > left[j]) {
                    left[j] = grid[i][j];
                }
            }
            area += right;
        }

        for (int v: left) {
            area += v;
        }
        return area;
    }
}

看算法跟我的也差不多啊，不知道为什么我的只有40%.

答案

class Solution {
    public int projectionArea(int[][] grid) {
        int N = grid.length;
        int ans = 0;

        for (int i = 0; i < N;  ++i) {
            int bestRow = 0;  // largest of grid[i][j]
            int bestCol = 0;  // largest of grid[j][i]
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] > 0) ans++;  // top shadow
                bestRow = Math.max(bestRow, grid[i][j]);
                bestCol = Math.max(bestCol, grid[j][i]);
            }
            ans += bestRow + bestCol;
        }

        return ans;
    }
}

P884. Uncommon Words from Two Sentences (Easy)

两个字符串代表两个句子。只有小写字母。如果一个单词只在一个句子中出现了恰好一次，且没在另一个句子中出现，则称为uncommon. 输出所有这样的单词。

我的思路

把两组单词放到一起，没重复的就是要的结果。用HashMap 计数

我的代码

public class E_884_UncommonWordsfromTwoSentences {
    public String[] uncommonFromSentences(String A, String B) {
        String[] a = A.split(" ");
        String[] b = B.split(" ");
        HashMap<String, Integer> map = new HashMap<>();
        for (String s : a) {
            map.put(s, map.getOrDefault(s,0) + 1);
        }
        for (String s : b) {
            map.put(s, map.getOrDefault(s,0) + 1);
        }
        ArrayList<String> ans = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                ans.add(entry.getKey());
            }
        }
        return ans.toArray(new String[0]);
    }
}

59%

最优解

class Solution {
    public String[] uncommonFromSentences(String A, String B) {

        Set<String> abSet = new HashSet<>();
        Set<String> duplicateSet = new HashSet<>();

        for(String str : A.split(" ")){
            if(!abSet.add(str))
                duplicateSet.add(str);
        }

        for(String str : B.split(" ")){
            if(!abSet.add(str))
                duplicateSet.add(str);
        }

        for(String str:duplicateSet)
            abSet.remove(str);
        abSet.remove("");

        return abSet.toArray(new String[abSet.size()]);
    }
}

HashSet的add方法有如下特性，如果已经存在，返回false；如果不存在，返回true。

P888. Fair Candy Swap (Easy)

Alice 和 Bob 有一些不同尺寸的糖果棒。他们愿意交换，使得两人的总尺寸相同。题目保证有至少一个正确的结果。

我的思路

暴力求解：把他们俩的总和都算出来。然后从第一个数组挨个看，去匹配第二个数组的每一个值，如果交换后两个和相等，则为正确结果。O(n^2)

或者可以排个序，然后binary search。

或者可以建个大数组，用反射索引的办法，即可瞬间找到另一个数组中是否有需要的值。

我的代码

class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        boolean[] hash = new boolean[100001];
        int sumA = 0, sumB = 0;
        for (int i : A) {
            sumA += i;
            hash[i] = true;
        }
        for (int i : B) {
            sumB += i;
        }
        int[] ans = new int[2];
        for (int i : B) {
           int target = (sumA - sumB) / 2 + i;
            if (target >= 1 && target <= 100000 && hash[target]) {
                ans[0] = target;
                ans[1] = i;
            }
        }
        return ans;
    }
}

99%

最优解

class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int[] result = new int[2];
        int sum = 0;
        boolean[] exists = new boolean[100001];
        for (int a : A) {
            exists[a] = true;
            sum += a;
        }
        for (int b : B) {
            sum -= b;
        }
        sum /= 2;
        for (int b : B) {
            if (b + sum > 0 && b + sum < 100001 && exists[b + sum]) {
                result[0] = b + sum;
                result[1] = b;
                return result;
            }
        }
        return null;
    }
}

答案

class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sa = 0, sb = 0;  // sum of A, B respectively
        for (int x: A) sa += x;
        for (int x: B) sb += x;
        int delta = (sb - sa) / 2;
        // If Alice gives x, she expects to receive x + delta

        Set<Integer> setB = new HashSet();
        for (int x: B) setB.add(x);

        for (int x: A)
            if (setB.contains(x + delta))
                return new int[]{x, x + delta};

        throw null;
    }
}

P892. Surface Area of 3D Shapes (Easy)

跟883一样，这次求表面积。

我的思路

把883最后的结果乘以2就完了。不对，有可能有些面是看不见的，被遮挡住了。可能需要计算所有相邻的方格，再用所有方块的个数算总的表面积，减去相邻的表面积。

我的代码

class Solution {
    public int surfaceArea(int[][] grid) {
        int sum = 0, stick = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                sum += grid[i][j];
                if (grid[i][j] > 0) {
                    stick += (grid[i][j] - 1) * 2;
                }
                if (j > 0) {
                    stick += Math.min(grid[i][j], grid[i][j - 1]) * 2;
                }
                if (i > 0) {
                    stick += Math.min(grid[i][j], grid[i - 1][j]) * 2;
                }
            }
        }
        return sum * 6 - stick;
    }
}

99%

最优解

class Solution {
    public int surfaceArea(int[][] grid) {
        int area = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                area += getArea(grid, i, j);
            }
        }
        return area;
    }

    private int getArea(int[][] grid, int i, int j) {
        int area = 0;
        if (grid[i][j] != 0) {
            area += 2;
            area += compareWithUp(grid, i, j);
            area += compareWithBottom(grid, i, j);
            area += compareWithLeft(grid, i, j);
            area += compareWithRight(grid, i, j);
        }
        return area;
    }

    private int compareWithUp(int[][] grid, int i, int j) {
        return compare(grid, i, j, i - 1, j);
    }

    private int compareWithBottom(int[][] grid, int i, int j) {
        return compare(grid, i, j, i + 1, j);
    }

    private int compareWithLeft(int[][] grid, int i, int j) {
        return compare(grid, i, j, i, j - 1);
    }

    private int compareWithRight(int[][] grid, int i, int j) {
        return compare(grid, i, j, i, j + 1);
    }

    private int compare(int[][] grid, int i, int j, int k, int l) {
        if (k < 0 || l < 0
            || k > grid.length - 1
            || l > grid[k].length - 1) {
            return grid[i][j];
        }
        return grid[i][j] < grid[k][l] ? 0 : grid[i][j] - grid[k][l];
    }
}