Specify Collection

一种是写一个Comparator 还可以在自己定义的class里面加功能 implement Comparable Interface

需要Override的是compareTo而不是compare!比如下面这样实现

    public class Point implements Comparable<Point>{
        public int time;
        public int flag;
        public Point(int time,int flag){
            this.time = time;
            this.flag = flag;
        }
        @Override
        public int compareTo(Point next){
            if(this.time == next.time)return this.flag - next.flag;
            return this.time - next.time;
        }

56. Merge Intervals

首先Specific Sort所给的Range List,按照start time 从小到大排列。然后使用Last代表上一个range，如果形成了单独的range加入result list然后更新range pointer

代码写的好首先思路要易懂清晰 可以类比链表的链接 ~ 我们在链接新的链表的时候 需要和前面的node建立一种联系

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 *     Use a last pointer to point the last not yet merged range. If the current range is seperated add to
 *     The final result list and make the new last pointer the current pointer 
 * }
 */
public class Solution {
    //怎么处理边界，因为不是比较i+1就是比较i-1，这里将intervals.get(0)单独列出并且更新很巧妙
    public List<Interval> merge(List<Interval> intervals){
        List<Interval> result = new ArrayList();
        int len = intervals.size();
        if(len == 0)return result;
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval s1, Interval s2) {
                return s1.start - s2.start;
            }});
        Interval last = intervals.get(0);
        for(int i = 1;i < len;i++){
            Interval cur = intervals.get(i);
            //可以merge,更新last的end,不加
            if(cur.start <= last.end){
                last.end = Math.max(last.end,cur.end);
            }
            else{
                //先加入上一段
                result.add(last);
                last = cur;
            }
        }
        //最后一段加入
        result.add(last);
        return result;
    }
}

280. Wiggle Sort

Go by one pass and swap the element according to different index (even or odd)

public class Solution {
     public void wiggleSort(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1]
            if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){
                int tmp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i] = tmp;
            }
        }
    }
}

296. Best Meeting Point

数学 主要是思路 怎么确定两个点之间的最短值 就是横坐标之差 可以把所有点横纵坐标分开考虑 排序好之后从两边向中间计算

横纵坐标分开计算https://leetcode.com/submissions/detail/98136753/

Solution

179. Largest Number

Get to know what Comparator does for an arrays of things and how to utilized them for the problem.

要最大肯定是前面的位更大 写一collection sort整个数组 (先变成String) 然后链接起来就是最后的result

Corner Case: 第一个是0 则后面的都是0 直接返回

Time:O(NlogN) (Collection Sort)

public class Solution {
    public String largestNumber(int[] num) {
        if(num == null || num.length == 0) return "";

        //Convert int array to String array, so we can sort later on
        String[] arr = new String[num.length];
        for(int i = 0; i < num.length; i++){
            arr[i] = String.valueOf(num[i]);
        }

        //Comparator to decide which string should come first in concatenation
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return s2.compareTo(s1); 
            }};

        Arrays.sort(arr, comp);
        // An extreme edge case by lc, say you have only a bunch of 0 in your int array
              if(arr[0].charAt(0) == '0')return "0";
        StringBuilder sb = new StringBuilder();
        for(String s: arr) sb.append(s);
        return sb.toString();

    }
}

524 Longest Word in Dictionary through Deleting #google

• 双指针：判断其中一个string是另外一个string的subsequence(通过delete一些字母可以match
• 怎么override compare( ) 进行sorting . 也可以不排序通过比较记录过程中所得到的结果和之前的结果进行对比(这一周还没有写)

class Solution {
    public String findLongestWord(String s, List<String> d) {
        // sort the given dictionary - first sort then perform the rest 
        // procedure is one solution 
        Collections.sort(d,new Comparator<String>() {
            @Override
            public int compare(String a,String b) {
                // the longer words come first
                if (a.length() != b.length()) 
                    return b.length() - a.length();
                // the word with bigger value come first 
                return a.compareTo(b);
            }
        });
        // go through the dictionary and find the first matching result
        for(String candidate : d) {
            if(isSubsequence(candidate,s))return candidate;
        }
        return "";
    }
    // if string s1 is subsequence of s2 
    private boolean isSubsequence(String s1,String s2) {
        if (s1.length() > s2.length()) return false;
        int i1 = 0;
        int i2 = 0;
        int count = 0;
        while(i1 < s1.length() && i2 < s2.length()) {
            if(s1.charAt(i1) == s2.charAt(i2)) {
                count++;
                i1++;
                i2++;
            }
            else{
                i2++;
            }
        }
        return count == s1.length();
    }
}