Posted Updated LeetCode / Mediuma minute read (About 219 words)

763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

将英文字母出现的首尾作为intervals看待。
根据字符创建数组并填入左右的index。
根据左侧index排序数组。

从左至右，如果intervals有交集，则合并。
否则在答案中添加当前interval的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] alphabet = new int[26][2];
        int head = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'a';
            if(head != index && alphabet[index][0] == 0) alphabet[index][0] = i;
            alphabet[index][1] = i;
        }
        
        Arrays.sort(alphabet, (a,b) -> a[0] - b[0]);
        
        List<Integer> ans = new ArrayList();
        int[] hold = alphabet[0];
        for(int i = 1; i < alphabet.length; i++){
            if(alphabet[i][0] <= hold[1]){
                hold[1] = Math.max(hold[1], alphabet[i][1]);
            }
            else{
                ans.add(hold[1]-hold[0]+1);
                hold = alphabet[i];
            }
        }
        ans.add(hold[1]-hold[0]+1);
        return ans;
        
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 353 words)

986. Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

设置两个指针，分别指向两个intervals的头部。
循环，相交的left等于两者左端的较大值。right等于两者右端的较小值。
只有在left小于right时，两个interval才相交，填入列表。
然后更新两个interval中右端较小的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> ans = new ArrayList(); 
        int i = 0;
        int j = 0;
        
        while(i < firstList.length && j < secondList.length){
            int left = Math.max( firstList[i][0], secondList[j][0] );
            int right = Math.min( firstList[i][1], secondList[j][1] );
            if(left <= right){
                ans.add(new int[]{left, right});
            }
            if(firstList[i][1] < secondList[j][1]) i++;
            else j++;

        }
        
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        ArrayList<int[]> ans = new ArrayList(); 
        int[] holdA;
        int[] holdB;

        while(i < firstList.length && j < secondList.length){
            holdA = firstList[i];
            holdB = secondList[j];
            
            int[] arr = new int[2];
            
            if(holdA[0] <= holdB[0] && holdA[1] >= holdB[1]){
                ans.add(holdB);
                j++;
            }
            else if(holdA[0] >= holdB[0] && holdA[1] <= holdB[1]){
                ans.add(holdA);
                i++;
            }
            else if(holdA[0] <= holdB[0] && holdA[1] >= holdB[0]){
                arr[0] = holdB[0];
                arr[1] = holdA[1];
                ans.add(arr);
                i++;
            }
            else if(holdA[0] >= holdB[0] && holdB[1] >= holdA[0]){
                arr[0] = holdA[0];
                arr[1] = holdB[1];
                ans.add(arr);
                j++;
            }
            else if(holdA[1] <= holdB[1]){
                i++;
            }
            else{
                j++;
            }
        }
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 183 words)

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

首先对intervals按照后一项的大小进行排序。（直接将两数字相减作为比较值比Integer.compare方法更快。）
贪心算法，将已取得的最大值max设置为最小整数值。
遍历intervals，如果当前interval的左侧小于max，则不能选择该interval，计数加一。
反之则可以选择interval，更新max的值为interval的最大值。
返回总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int[] interval : intervals){
            if(interval[0] < max){
                count++;
            }
            else{
                max = interval[1];
            }
        }
        return count;
    }
}
Posted Updated LeetCode / Easy / 复习3 minutes read (About 431 words)

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

哈希表，先设置一个素数Prime作为map的尺寸。
（这里设置成素数是为了减少可能的碰撞。）
创建一个Pair类记录key和value。

map初始化时需要生成一个LinkedList数组。

  • hash方法计算哈希值。用key % Prime并返回。
  • put方法，根据key计算其哈希值h。如果列表中有则重新设置当前Pair的value。
  • get方法，根据哈希值h搜索并查找链表中的Pair，如果找到则返回Pair，否则返回-1。
  • remove方法，根据哈希值h搜索并remove链表中的Pair。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class MyHashMap {
    final int PRIME = 1009;
    List<Pair>[] map;
    public MyHashMap() {
        map = new LinkedList[PRIME];
        for(int i = 0; i < PRIME; i++){
            map[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                p.setValue(value);
                return;
            }
        }
        Pair p = new Pair(key, value);
        map[h].add(p);
    }
    
    public int get(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                return p.value;
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                map[h].remove(p);
                return;
            }
        }
    }
    
    private int hash(int key){
        return key % PRIME;
    }
}

class Pair {
    int key;
    int value;
    public Pair(int k, int v){
        key = k;
        value = v;
    }
    
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
    public void setValue(int v){
        value = v;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */
Follow

Recents

Archives

Links

×