LeetCode(37) -- 840, 844, 849, 852, 859

P840. Magic Squares In Grid (Easy)

一个二维数组，判断其中神奇九宫格（横竖斜加起来都相等）的个数。

我的思路

九宫格中点必然是5。只有当它是5时，再进去检查1：是否包含了1到9所有数，2：加起来是否都相等。

我的代码

public class E_840_MagicSquaresInGrid {
    public int numMagicSquaresInside(int[][] grid) {
        int count = 0;
        for (int i = 1; i < grid.length - 1; i++) {
            for (int j = 1; j < grid[i].length - 1; j++) {
                if (grid[i][j] == 5) {
                    boolean hasDistinctNumbers = true;
                    boolean[] numbers = new boolean[16];
                    numbers[grid[i-1][j-1]] = true;
                    numbers[grid[i-1][j]] = true;
                    numbers[grid[i-1][j+1]] = true;
                    numbers[grid[i][j-1]] = true;
                    numbers[grid[i][j]] = true;
                    numbers[grid[i][j+1]] = true;
                    numbers[grid[i+1][j-1]] = true;
                    numbers[grid[i+1][j]] = true;
                    numbers[grid[i+1][j+1]] = true;
                    for (int k = 1; k < 10; k++) {
                        if (!numbers[k]) {
                            hasDistinctNumbers = false;
                            break;
                        }
                    }

                    int sum1 = grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1];
                    int sum2 = grid[i][j-1] + grid[i][j] + grid[i][j+1];
                    int sum3 = grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1];
                    int sum4 = grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1];
                    int sum5 = grid[i-1][j] + grid[i][j] + grid[i+1][j];
                    int sum6 = grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1];
                    int sum7 = grid[i-1][j-1] + grid[i][j] + grid[i+1][j+1];
                    int sum8 = grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1];
                    if (hasDistinctNumbers && sum1 == sum2 && sum2 == sum3 && sum3 == sum4 &&
                            sum4 == sum5 && sum5 == sum6 && sum6 == sum7 && sum7 == sum8) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

100% 代码极为难看。。。纯暴力求解。。。

最优解

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        int ans = 0;
        for (int r = 0; r < R-2; ++r)
            for (int c = 0; c < C-2; ++c) {
                if (grid[r+1][c+1] != 5) continue;  // optional skip
                if (magic(grid[r][c], grid[r][c+1], grid[r][c+2],
                          grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],
                          grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]))
                    ans++;
            }

        return ans;
    }

    public boolean magic(int... vals) {
        int[] count = new int[16];
        for (int v: vals) count[v]++;
        for (int v = 1; v <= 9; ++v)
            if (count[v] != 1)
                return false;

        return (vals[0] + vals[1] + vals[2] == 15 &&
                vals[3] + vals[4] + vals[5] == 15 &&
                vals[6] + vals[7] + vals[8] == 15 &&
                vals[0] + vals[3] + vals[6] == 15 &&
                vals[1] + vals[4] + vals[7] == 15 &&
                vals[2] + vals[5] + vals[8] == 15 &&
                vals[0] + vals[4] + vals[8] == 15 &&
                vals[2] + vals[4] + vals[6] == 15);
    }
}

思路跟我是差不多的，但是因为用了一个辅助方法，把9个数传进去验证，代码看起来好看一些。

P844. Backspace String Compare (Easy)

两个字符串，其中用#代表退格键，问编辑后的两个字符串是否相同。

我的思路

最直接的办法是把两个字符串处理后，再比较。

我的代码

public class E_844_BackspaceStringCompare {
    public boolean backspaceCompare(String S, String T) {
        String s = processString(S);
        String t = processString(T);
        return s.equals(t);
    }

    private String processString(String s) {
        char[] chars = s.toCharArray();
        int j = 0;
        for (int i = 0; i < chars.length; i++, j++) {
            chars[j] = chars[i];
            if (chars[i] == '#') {
                j = j - 2;
                if (j < -1) {
                    j = -1;
                }
            }
        }
        return String.valueOf(chars, 0, j);
    }

    public static void main(String[] args) {
        boolean b = new E_844_BackspaceStringCompare().backspaceCompare("a#c", "b");
        System.out.println("b = " + b);
    }
}

100%

最优解

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int sLen = S.length() - 1;
        int tLen = T.length() - 1;
        int sSkip = 0;
        int tSkip = 0;
        while(sLen >= 0 || tLen >= 0) {
            while(sLen >= 0) {
                if (S.charAt(sLen) == '#') {
                    sSkip++;
                    sLen--;
                } else if (sSkip > 0) {
                    sSkip--;
                    sLen--;
                } else {
                    break;
                }
            }
            while(tLen >= 0) {
                if (T.charAt(tLen) == '#') {
                    tSkip++;
                    tLen--;
                } else if (tSkip > 0) {
                    tSkip--;
                    tLen--;
                } else {
                    break;
                }
            }
            if (sLen >= 0 && tLen >=0) {
                if (S.charAt(sLen) != T.charAt(tLen)) {
                    return false;
                }
            }
            sLen--;
            tLen--;
        }

        return sLen == tLen;
    }
}

P849. Maximize Distance to Closest Person (Easy)

一个数组中，0代表空的座位，1代表有人。找出离其他人最远的距离。

我的思路

两个1距离的一半，就是能坐的最远的距离。首尾的特殊情况需要处理一下。

我的代码

class Solution {
    public int maxDistToClosest(int[] seats) {
        int i = 0;
        int length = seats.length;
        while (i < length && seats[i] != 1) {
            i++;
        }
        int max = i, prev = i;
        for (int j = i + 1; j < seats.length; j++) {
            if (seats[j] == 1) {
                max = Math.max(max, (j - prev) / 2);
                prev = j;
            }
        }
        return Math.max(max, length - prev - 1);
    }
}

89%

最优解

class Solution {
    public int maxDistToClosest(int[] seats) {
        int i = 0, res = 0;
        while (i < seats.length) {
            // track 1s from beginning
            while (i < seats.length && seats[i] == 1) i++;

            // j is the start of 0
            int j = i;

            // track continuous 0s from j
            while (i < seats.length && seats[i] == 0) i++;

            if (j == 0 || i == seats.length) res = Math.max(res, i - j);
            // the (i - j + 1) here is derived from i - (j - 1)
            else res = Math.max(res, (i - j + 1) / 2);

        }
        return res;
    }
}

用两层循环解决的。其他差不多。

P852. Peak Index in a Mountain Array (Easy)

一个数组，先从小到大再从大到小。找到中间那个最大值。

我的思路

我直接遍历了一次。其实应该可以用binary search。

我的代码

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        for (int i = 1; i < A.length - 1; i++) {
            if (A[i] > A[i-1] && A[i] > A[i+1]) {
                return i;
            }
        }
        return -1;
    }
}

100%

最优解

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int start = 0;
        int end = A.length - 1;
        int mid = (start + end)/2;
        while (start < end) {
            mid = (start + end);
            if(A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
                return mid;
            }

            if(A[mid] < A[mid - 1]) {
                end = mid - 1;
                continue;
            }

            if(A[mid] < A[mid + 1]) {
                start = mid + 1;
                continue;
            }
        }
        return mid;
    }
}

P859. Buddy Strings (Easy)

给两个数组，如果调换A中的两个字母后能变成B，就返回true.

我的思路

如果两个字符串完全一样，那其中必须要有重复的字母。如果两个字符串不一样，则必须长度相等，且恰好有两个不一样，且调换后要一样。

我的代码

class Solution {
    public boolean buddyStrings(String A, String B) {
        if (A.equals(B)) {
            char[] chars = A.toCharArray();
            boolean[] exist = new boolean[26];
            for (char c : chars) {
                int index = c - 'a';
                if (exist[index]) return true;
                exist[index] = true;
            }
        } else if (A.length() == B.length()) {
            int[] diff = new int[2];
            diff[0] = diff[1] = -1;
            char[] a = A.toCharArray();
            char[] b = B.toCharArray();
            for (int i = 0; i < A.length(); i++) {
                if (a[i] != b[i]) {
                    if (diff[0] == -1) {
                        diff[0] = i;
                    } else if (diff[1] == -1) {
                        diff[1] = i;
                    } else {
                        return false;
                    }
                }
            }
            return a[diff[0]] == b[diff[1]] && a[diff[1]] == b[diff[0]];
        }

        return false;
    }
}

100%

最优解

class Solution {
    public boolean buddyStrings(String A, String B) {
        if (A == null || B == null) return false;
        if (A.length() != B.length()) return false;
        if (A.length() < 2) return false;

        char[] charA = A.toCharArray();
        int[] flag = new int[26];
        if (A.equals(B)) {
            for (char c : charA) {
                flag[c - 'a']++;
                if (flag[c - 'a'] == 2) return true;
            }

            return false;
        }

        char[] charB = B.toCharArray();
        int[] diff = new int[2];
        int sum = 0;
        for (int i = 0; i < A.length(); i++) {
            if (charA[i] != charB[i]) {
                sum++;
                if (sum > 2) return false;
                diff[sum - 1] = i;
            }
        }

        return charA[diff[0]] == charB[diff[1]] && charA[diff[1]] == charB[diff[0]];
    }
}

跟我思路基本差不多，细节上有点小差异。