13 October 2019

LeetCode(36) -- 821, 824, 830, 832, 836

by Jerry Zhang

P821. Shortest Distance to a Character (Easy)

给一个字符串和一个字母，找出这个字符串每个字母，距离这个字母最短的距离。

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

我的思路

肯定要把这个字符串中所有这个字母的坐标找出来，否则我走着走着并不知道前方还有一个，距离肯定算不对。然后就控制一下索引，使距离不要超过中点。

我的代码

public class E_821_Shortest_Distance_to_a_Character {
    public int[] shortestToChar(String S, char C) {
        LinkedList indexes = new LinkedList();
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == C) {
                indexes.addAtTail(i);
            }
        }
        int[] ans = new int[chars.length];
        int first = indexes.getFirst();
        int i = 0;
        while (i < first) {
            ans[i] = first - i;
            i++;
        }

        while (indexes.getSecond() != -1) {
            first = indexes.getFirst();
            int second = indexes.getSecond();
            int mid = first + (second - first) / 2;
            while (i <= mid) {
                ans[i] = i - first;
                i++;
            }
            while (i < second) {
                ans[i] = second - i;
                i++;
            }
            indexes.removeFirst();
        }
        first = indexes.getFirst();
        while (i < chars.length) {
            ans[i] = i - first;
            i++;
        }
        return ans;
    }

    static class LinkedListNode {
        int index;
        LinkedListNode next;

        public LinkedListNode() {
        }

        LinkedListNode(int index, LinkedListNode next) {
            this.index = index;
            this.next = next;
        }
    }

    static class LinkedList {
        LinkedListNode head;
        LinkedListNode tail;
        int size;

        void addAtHead(int index) {
            head = new LinkedListNode(index, head);
            if (size == 0) {
                tail = head;
            }
            size++;
        }

        void removeFirst() {
            if (head != null) {
                head = head.next;
                size--;
            }
        }

        void addAtTail(int index) {
            if (size == 0) {
                addAtHead(index);
            } else {
                tail.next = new LinkedListNode(index, null);
                tail = tail.next;
                size++;
            }
        }

        int getFirst() {
           if (size == 0) {
               return -1;
           }
           return head.index;
        }

        int getSecond() {
            if (size < 2) {
                return -1;
            }
            return head.next.index;
        }

        int getLast() {
            if (size == 0) {
                return -1;
            }
            return tail.index;
        }

        public int size() {
            return size;
        }
    }
}

98% 自己写了一个LinkedList，所以代码长得有点吓人…

最优解

class Solution {
    public int[] shortestToChar(String s, char c) {
        char[] arr = s.toCharArray();
        int n = arr.length;

        int[] ans = new int[n];
        int i=0, dist = 0;
        while(arr[i] != c) ans[i++] = Integer.MAX_VALUE;

        for(; i<n; ++i) {
            if(arr[i] == c) {
                ans[i] = 0;
                dist = 1;
                int j = i-1;
                while(j >= 0 && ans[j] > dist) ans[j--] = dist++;
                dist = 1;
            } else ans[i] = dist++;
        }

        return ans;
    }
}

这个算法太巧妙了！不知道后一个目标值在哪里没关系，距离先暂时累加着，直到遇到下一个目标值，再回头，把距离改回来。第一轮的时候，因为没有初始值，所以先把所有的数都设置成最大整数，这样前面的所有数肯定是大于distance的，也就是说要回头一直走到数组的初始。

P824. Goat Latin (Easy)

给一个字符串写着一句话，每个单词只有大小写字母。如果这个单词以元音字母开头，则在单词结尾加上“ma”，如果以辅音字母开头，则把每一个字母挪到最后，再加上”ma”。同时该单词在句子中，是第几个单词就加几个“a”。

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

我的思路

并不难，根据规则实现即可。

我的代码

public class E_824_GoatLatin {
    public String toGoatLatin(String S) {
        String[] words = S.split(" ");
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            char first = words[i].charAt(0);
            if (first == 'a' || first == 'e' || first == 'i' || first == 'o' || first == 'u' ||
                first == 'A' || first == 'E' || first == 'I' || first == 'O' || first == 'U') {
                ans.append(words[i]);
            } else {
                ans.append(words[i].substring(1)).append(words[i].charAt(0));
            }
            ans.append("ma");
            for (int j = 0; j < i + 1; j++) {
                ans.append('a');
            }
            ans.append(" ");
        }
        return ans.toString().trim();
    }
}

94%

最优解

class Solution {
    public String toGoatLatin(String S) {
        StringBuffer sbf = new StringBuffer();

        if(S != null && S.length() > 0) {
            boolean start = true;
            String postFix = "";
            int wordCount = 1;
            for(int i = 0; i < S.length(); i++) {
                char ch = S.charAt(i);
                if(ch == ' ') {
                    if(!start) {
                        start = true;
                        wordCount++;
                        sbf.append(postFix);
                        sbf.append('m');
                        for(int j=0; j < wordCount; j++) {
                            sbf.append('a');
                        }
                    }
                    sbf.append(ch);
                } else {
                    if(start) {
                        char lch = Character.toLowerCase(ch);
                        if(lch == 'a' || lch == 'e' || lch == 'i' || lch == 'o' || lch == 'u') {
                            sbf.append(ch);
                            postFix = "";
                        } else {
                            postFix = Character.toString(ch);
                        }
                        start = false;
                    } else sbf.append(ch);
                }
            }
            sbf.append(postFix);
            sbf.append('m');
            for(int j=0; j<wordCount+1; j++) {
                sbf.append('a');
            }
        }
        return sbf.toString();
    }
}

没啥值得学习的。代码看着比我的乱。

P830. Positions of Large Groups (Easy)

字符串，连续的相同的字母分为一组。求长度大于3的起始坐标和终止坐标。

我的思路

按要求实现即可。

我的代码

public class E_830_PositionsOfLargeGroups {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> list = new ArrayList<>();
        char[] chars = S.toCharArray();
        int first = 0;
        char curr = chars[0];
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            while (i < chars.length && chars[i] == curr) {
                count++;
                i++;
            }
            if (count >= 3) {
                List<Integer> index = new ArrayList<>();
                index.add(first);
                index.add(i - 1);
                list.add(index);
            }
            if (i < chars.length) {
                count = 1;
                first = i;
                curr = chars[i];
            }
        }
        return list;
    }
}

100% 测试case给了一个‘a’，出了两次bug

最优解

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        if(S.length() < 3) {
            return res;
        }
        char[] chars = S.toCharArray();
        int counter = 1;

        for(int i = 1; i <= chars.length; i++) {
            if(i == chars.length) {
                if(counter >= 3){
                    temp.add(i - counter);
                    temp.add(i - 1);
                    res.add(temp);
                }
                break;
            }
            if(chars[i] == chars[i - 1])
                counter++;
            else {
                if(counter >= 3) {
                    temp.add(i - counter);
                    temp.add(i - 1);
                    res.add(temp);
                    temp = new ArrayList<>();
                }
                counter = 1;
            }
        }

        return res;
    }
}

差不多。

P832. Flipping an Image (Easy)

二维数组，每一行先反转，再把1，0互换。

我的思路

换要求实现即可。

我的代码

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for (int i = 0; i < A.length; i++) {
            int length = A[i].length;
            for (int j = 0; j < length / 2; j++) {
                int temp = A[i][j];
                A[i][j] = A[i][length - j - 1];
                A[i][length - j - 1] = temp;
            }
            for (int j = 0; j < length; j++) {
                if (A[i][j] == 0) {
                    A[i][j] = 1;
                } else {
                    A[i][j] = 0;
                }
            }
        }
        return A;
    }
}

36%

最优解

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for (int i = 0; i< A.length; i++) {
            int[] curRow = A[i];
            int len = curRow.length;
            for (int j = 0; j < (len+1)/2; j++) {
                int k = len-1-j;
                int temp = curRow[j];
                curRow[j] = curRow[k];
                curRow[k] = temp;
                curRow[j] ^= 1;
                if (j != k)
                    curRow[k] ^= 1;
            }
        }
        return A;
    }
}

跟“1”做“异或”实现反转

答案

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int C = A[0].length;
        for (int[] row: A)
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }

        return A;
    }
}

P836. Rectangle Overlap (Easy)

[x1, y1, x2, y2]表示一个长方形，x1,y1是左下角的坐标，x2,y2是右上角的坐标。给两个长方形，问是否重叠。只有边或点接触不算，必须真的有重叠的面积。

我的思路

第一个长方形的x1要小于第二个长方形的x2，并且第一个长方形的x2要大于第二个长方形的x1。纵坐标也类似。

我的代码

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        boolean horizontalOverlap = false;
        boolean verticalOverlap = false;
        if (rec1[0] < rec2[2] && rec1[2] > rec2[0]) {
            horizontalOverlap = true;
        }
        if (rec1[1] < rec2[3] && rec1[3] > rec2[1]) {
            verticalOverlap = true;
        }
        return horizontalOverlap && verticalOverlap;
    }
}

100% 关于重叠的问题，基本都是这个思路。

最优解

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return !(rec1[2] <= rec2[0] ||   // left
                 rec1[3] <= rec2[1] ||   // bottom
                 rec1[0] >= rec2[2] ||   // right
                 rec1[1] >= rec2[3]);    // top
    }
}

其实就是我上面那四个条件反着说。

tags: LeetCode

Jerry's Blog

Recording what I learned everyday

LeetCode(36) -- 821, 824, 830, 832, 836

P821. Shortest Distance to a Character (Easy)

我的思路

我的代码

最优解

P824. Goat Latin (Easy)

我的思路

我的代码

最优解

P830. Positions of Large Groups (Easy)

我的思路

我的代码

最优解

P832. Flipping an Image (Easy)

我的思路

我的代码

最优解

答案

P836. Rectangle Overlap (Easy)

我的思路

我的代码

最优解