128. Longest Consecutive Sequence
Posted Updated LeetCode / Medium / 复习2 minutes read (About 306 words)

128. Longest Consecutive Sequence

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}
1647. Make Character Frequencies Unique
Posted Updated LeetCode / Medium2 minutes read (About 227 words)

1647. Make Character Frequencies Unique

Question

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return* the minimum number of characters you need to delete to make s good.*

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组，如果哈希表中已经记录，则将数组统计减少，直到归零。
每减少一次则为count加一。
如果哈希表中未记录，则将当前数字添加到哈希表中。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDeletions(String s) {
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] bin = new int[26];
        for(char c : s.toCharArray()){
            bin[c - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            while(bin[i] !=0 && set.contains(bin[i])){
                bin[i]--;
                count++;
            }
            set.add(bin[i]);
        }
        return count;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 353 words)

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

计算两个链表的长度。将长的链表向下移动两者长度的差，对齐两个链表的长度。
同时向下移动两个链表，如果两个节点的内存地址相同，则返回节点。否则返回null。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0, sizeB = 0;
        ListNode l1 = headA, l2 = headB;
            
        while(l1 != null){
            l1 = l1.next;
            sizeA++;
        }
        while(l2 != null){
            l2 = l2.next;
            sizeB++;
        }
        if(sizeA > sizeB){
            int size = sizeA - sizeB;
            while(size != 0){
                headA = headA.next;
                size--;
            }
        }
        else{
            int size = sizeB - sizeA;
            while(size != 0){
                headB = headB.next;
                size--;
            }
        }
        while(headA != null){
            if(headA == headB) return headA;
                headA = headA.next;
                headB = headB.next;
        }
        return null;
    }
}

遍历移动一个链表，将其加入哈希集合。
然后移动另一个链表，如果哈希集合中有重复节点，则返回该节点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 411 words)

142. Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

快慢指针。快指针的移动速度是慢指针的两倍。
设环外长度为a，b是快指针和慢指针相遇的位置，c是环中剩余位置。
可以由此得到公式a + (n + 1)b + nc = 2(a + b)，也就是a = c + (n - 1)(b + c)
由于（b + c）是环的长度。因此，当两个指针相遇时，在头部设置一个新节点。慢指针和新指针将在循环入口处相遇，此时返回节点。

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if( head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)) break;
        }
        
        if(fast == null || fast.next == null){
            return null;
        }
        
        ListNode root = head;
        while(!root.equals(slow)){
            slow = slow.next;
            root = root.next;
        }
        return root;
    }
}

哈希表，递归并将节点加入哈希集合，如果重复则返回节点，反之返回null。

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    HashSet<ListNode> set;
    public ListNode detectCycle(ListNode head) {
        set = new HashSet<>();
        return findCycle(head, 0);
    }
    
    private ListNode findCycle(ListNode root, int count){
        if(root == null){
            return null;
        }
        if(set.contains(root)){
            return root;
        }
        set.add(root);
        count++;
        return findCycle(root.next, count);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 252 words)

535. Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the Solution class:

  • Solution() Initializes the object of the system.
  • String encode(String longUrl) Returns a tiny URL for the given longUrl.
  • String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

计算传入连接的哈希值。将其作为key放入map中。
解码时将url转换为key，取出map中的value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Codec {
    HashMap<Integer, String> map = new HashMap<>();
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        int key = longUrl.hashCode();
        map.put(key, longUrl);
        return Integer.toString(key);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl));
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
Posted Updated LeetCode / Easya minute read (About 181 words)

705. Design HashSet

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

Implement MyHashSet class:

  • void add(key) Inserts the value key into the HashSet.
  • bool contains(key) Returns whether the value key exists in the HashSet or not.
  • void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

计算哈希值，使用数组实现Hash Set。

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
class MyHashSet {
    int PRIME = 1009;
    List<Integer>[] data;
    
    public MyHashSet() {
        data = new List[PRIME];
        for(int i = 0; i < PRIME; i++){
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        if(!contains(key)){
            int h = getHash(key);
            data[h].add(key);
        }
    }
    
    public void remove(int key) {
        int h = getHash(key);
        data[h].remove(new Integer(key));
    }
    
    public boolean contains(int key) {
        int h = getHash(key);
        for( int num : data[h] ){
            if( num == key ){
                return true;
            }
        }
        return false;
    }
    
    private int getHash(int o){
        return o % PRIME;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */
Follow

Recents

Archives

Links

×