19 October 2019

LeetCode(42) -- 937, 938, 941, 942, 944

by Jerry Zhang

P937. Reorder Data in Log Files (Easy)

有一个字符串数组，表示一些日志。每条日志都是空格分隔的单词。每一个单词是这条log的ID，后面的单词，要么都是小写字母，要么都是数字。

重新排序这些日志，使得字母日志全排在数字日志前面，并且按字母表顺序排序，数字日志顺序保持不变。

我的思路

我自己新写了一个类，实现compareTo方法。然后用Collection的sort方法排序。这个方法比较繁琐，先要转换成List，再转换回数组。

我的代码

public class E_937_ReorderDatainLogFiles {
    public String[] reorderLogFiles(String[] logs) {
        List<Log> logList = new ArrayList<>();
        for (String log : logs) {
            logList.add(new Log(log));
        }
        Collections.sort(logList);
        String[] ans = new String[logs.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = logList.get(i).getLog();
        }
        return ans;
    }

    class Log implements Comparable {
        String log;
        boolean isLetterLog;

        public Log(String log) {
            this.log = log;
            String[] s = log.split(" ");
            if (Character.isDigit(s[1].charAt(0))) {
                this.isLetterLog = false;
            } else {
                this.isLetterLog = true;
            }
        }

        @Override
        public int compareTo(Object o) {
            if (this == o) return 0;
            Log anotherLog = (Log) o;
            if (isLetterLog && !anotherLog.isLetterLog) {
                return Integer.MIN_VALUE;
            } else if (!isLetterLog && anotherLog.isLetterLog) {
                return Integer.MAX_VALUE;
            } else if (!isLetterLog) {
                return 0;
            } else {
                String thisLogContent = log.substring(log.indexOf(" ") + 1);
                String anotherLogContent = anotherLog.log.substring(anotherLog.log.indexOf(" ") + 1);
                int compare = thisLogContent.compareTo(anotherLogContent);
                if (compare == 0) {
                    return log.compareTo(anotherLog.log);
                } else {
                    return compare;
                }
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Log log1 = (Log) o;
            return log.equals(log1.log) && isLetterLog == log1.isLetterLog;
        }

        public String getLog() {
            return log;
        }

        public void setLog(String log) {
            this.log = log;
        }

        public boolean isLetterLog() {
            return isLetterLog;
        }

        public void setLetterLog(boolean letterLog) {
            isLetterLog = letterLog;
        }
    }
}

70%

最优解

class Solution {
    public String[] reorderLogFiles(String[] logs) {

    int size = logs.length;
    String[] reorderedLogs = new String[size];
    int digitNextInsertIndex = size - 1;
    int alphaLastInsertIndex = -1;
    for (int i = size - 1; i >= 0; i--) {
      String log = logs[i];
      char firstNonIdentifierChar = log.charAt(log.indexOf(' ') + 1);
      if (firstNonIdentifierChar >= '0' && firstNonIdentifierChar <= '9') {
        reorderedLogs[digitNextInsertIndex--] = log;
      } else {
        for (int j = 0; j < size; j++) {
          if (reorderedLogs[j] == null) {
            reorderedLogs[j] = log;
            alphaLastInsertIndex++;
            break;
          } else if (isBefore(log, reorderedLogs[j])) {
            for (int k = alphaLastInsertIndex; k >= j; k--) {
              reorderedLogs[k+1] = reorderedLogs[k];
            }
            reorderedLogs[j] = log;
            alphaLastInsertIndex++;
            break;
          }
        }
      }
    }

    return reorderedLogs;
  }

  private boolean isBefore(String s1, String s2) {
    int s1fs = s1.indexOf(' ');
    int s2fs = s2.indexOf(' ');
    String s1_content = s1.substring(s1fs + 1);
    String s2_content = s2.substring(s2fs + 1);
    int comp = s1_content.compareTo(s2_content);
    if (comp != 0) {
      return comp < 0;
    }

    String s1Ident = s1.substring(0, s1fs);
    String s2Ident = s2.substring(0, s2fs);

    return s1Ident.compareTo(s2Ident) < 0;
  }
}

答案

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs, (log1, log2) -> {
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);
            boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
            boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
            if (!isDigit1 && !isDigit2) {
                int cmp = split1[1].compareTo(split2[1]);
                if (cmp != 0) return cmp;
                return split1[0].compareTo(split2[0]);
            }
            return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
        });
        return logs;
    }
}

用lamda expression写了一个定制化的sort方法。Arrays.sort这个方法值得学习。第二点是split后面加个2,就是把字符串分成两部分，这个也值得学习。但是这个性能很差，只有15%

次优解

class Solution {
    public String[] reorderLogFiles(String[] logs) {

        Comparator<String> myComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1si = s1.indexOf(' ');
                int s2si = s2.indexOf(' ');
                char s1fc = s1.charAt(s1si+1);
                char s2fc = s2.charAt(s2si+1);

                if (s1fc <= '9') {
                    if (s2fc <= '9') return 0;
                    else return 1;
                }
                if (s2fc <= '9') return -1;

                int preCompute = s1.substring(s1si+1).compareTo(s2.substring(s2si+1));
                if (preCompute == 0) return s1.substring(0,s1si).compareTo(s2.substring(0,s2si));
                return preCompute;
            }
        };

        Arrays.sort(logs, myComp);
        return logs;
    }
    }

我觉得这个最好

P938. Range Sum of BST (Easy)

在一个BST中，找出所有在给定范围内的数的sum

我的思路

遍历BST，符合条件就累加起来。后来优化了一下，因为只有当当前值大于范围的下限时，才需要去看左子树；只有当当前节点的值小于范围上限时，才需要去看右子树。如果当前值都已经小于最小值了，左子树只会比它更小，不用看了。

我的代码

public class E_938_RangeSumofBST {

    int sum;

    public int rangeSumBST(TreeNode root, int L, int R) {
        inOrder(root, L, R);
        return sum;
    }

    private void inOrder(TreeNode node, int L, int R) {
        if (node == null) {
            return;
        }
        if (node.val >= L) {
            inOrder(node.left, L, R);
        }
        if (node.val >= L && node.val <= R) {
            sum += node.val;
        }
        if (node.val <= R) {
            inOrder(node.right, L, R);
        }
    }
}

52% -> 100%

最优解

class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        }
        if (root.val > R) {
            return rangeSumBST(root.left, L, R);
        }
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }
}

其实不需要辅助方法。这个方法最简洁。值得学习。

P941. Valid Mountain Array (Easy)

判断一个数组是否是山峰形数组。先增长后减少。

我的思路

两个while循环，然后判断是否走到最后了。还要判断是否两个循环都进去过，也就是说曾经有过增加，也有过减少。

我的代码

public class E_941_ValidMountainArray {
    public boolean validMountainArray(int[] A) {
        if (A.length < 3) {
            return false;
        }
        int i = 1;
        boolean increase = false, decrease = false;
        while (i < A.length && A[i] > A[i - 1]) {
            increase = true;
            i++;
        }
        while (i < A.length && A[i] < A[i - 1]) {
            decrease = true;
            i++;
        }
        return i == A.length && increase && decrease;
    }

    public static void main(String[] args) {
        int[] test = {0,3,2,1};
        boolean b = new E_941_ValidMountainArray().validMountainArray(test);
        System.out.println("b = " + b);

    }
}

100%

最优解

class Solution {
    public boolean validMountainArray(int[] A) {

        int length = A.length;
        int i = 0;

        while (i+1 < length && A[i+1] > A[i])
            i++;

        if (i == 0 || i == length-1) return false;

        while(i+1 < length && A[i+1] < A[i])
            i++;

        return (i == length-1);

    }
}

中间判断了一下i是否是第一个或者最后一个，这两种情况都不行。

P942. DI String Match (Easy)

给一个字符串，只含有I或者D。I表示上升，D表示下降。N是这个字符串的长度。数组[0, 1, ..., N]，调换顺序，使得它的上升下降趋势符合字符串中的表示。

我的思路

所有上升的地方，就从前往后依次排；所有下降的地方就从后往前依次排。

我的代码

public class E_942_DIStringMatch {
    public int[] diStringMatch(String S) {
        char[] chars = S.toCharArray();
        int[] ans = new int[S.length() + 1];
        int l = 0, r = S.length();
        int i = 0;
        for ( ; i < S.length(); i++) {
            if (chars[i] == 'I') {
                ans[i] = l;
                l++;
            } else {
                ans[i] = r;
                r--;
            }
        }
        ans[i] = l;
        return ans;
    }
}

94%

最优解

class Solution {
    public int[] diStringMatch(String S) {
        int n,add,sub,num,i;
        n = (S.length());
        add = 0;
        sub = n;
        num = 0;
        char ch[]= S.toCharArray();
        int a[] = new int[n+1];
        for(i = 0 ; i< n ; i++){
            if(ch[i] == 'I'){
                a[i] = add;
                add = add+1;

            }else{
                a[i] = sub;
                sub = sub - 1;
            }

        }
       a[n]= sub;
       return a;
    }
}

答案

class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int lo = 0, hi = N;
        int[] ans = new int[N + 1];
        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == 'I')
                ans[i] = lo++;
            else
                ans[i] = hi--;
        }

        ans[N] = lo;
        return ans;
    }
}

感觉都差不多，随便用哪个都可以。

P944. Delete Columns to Make Sorted (Easy)

我的思路

每个单词都跟前一个比较，每个字符去比，如果有小于前一个的就记下来，说明这个位置需要删除掉。

我的代码

class Solution {
    public int minDeletionSize(String[] A) {
        boolean[] ans = new boolean[A[0].length()];
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < A[i].length(); j++) {
                if (ans[j]) continue;
                if (A[i].charAt(j) < A[i - 1].charAt(j)) {
                    ans[j] = true;
                }
            }
        }
        int count = 0;
        for (boolean an : ans) {
            if (an) {
                count++;
            }
        }
        return count;
    }
}

12%

最优解

class Solution {
    public int minDeletionSize(String[] a) {
        int result = 0;
        int stringLength = a[0].length();

        for (int i = 0; i < stringLength; i++) {
            if (isNotSort(a, i)) {
                result++;
            }
        }
        return result;
    }

    public static boolean isNotSort(String[] s, int num) {
        char prev = s[0].charAt(num);
        for (String value : s) {
            char curr = value.charAt(num);
            if (curr < prev)
                return true;
            prev = curr;
        }
        return false;
    }
}

98% 这是最快的。我不明白为什么拆分出来一个函数，做同样的事，就比其他方法快很多。

答案：

class Solution {
    public int minDeletionSize(String[] A) {
        int ans = 0;
        for (int c = 0; c < A[0].length(); ++c)
            for (int r = 0; r < A.length - 1; ++r)
                if (A[r].charAt(c) > A[r+1].charAt(c)) {
                    ans++;
                    break;
                }

        return ans;
    }
}

18%

tags: LeetCode

Jerry's Blog

Recording what I learned everyday

LeetCode(42) -- 937, 938, 941, 942, 944

P937. Reorder Data in Log Files (Easy)

我的思路

我的代码

最优解

答案

次优解

P938. Range Sum of BST (Easy)

我的思路

我的代码

最优解

P941. Valid Mountain Array (Easy)

我的思路

我的代码

最优解

P942. DI String Match (Easy)

我的思路

我的代码

最优解

答案

P944. Delete Columns to Make Sorted (Easy)

我的思路

我的代码

最优解

答案：