LC28 Implement strStr()

Problem

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Think

KMP，参见KMP

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
25
26
27
28
29
30
31
int strStr(string haystack, string needle) {
    vector<int> next = getNext(needle);
    int m = haystack.size(), n = needle.size();
    int i = 0, j = 0;
    while(i < m && j < n){
        if(j == -1 || haystack[i] == needle[j]){
            i++;
            j++;
        }
        else{
            j = next[j];
        }
    }
    return j == n ? i - j: -1;
}
vector<int> getNext(string needle){
    int n = needle.size();
    vector<int> next(n, -1);
    int k = -1, j = 0;
    while(j < n - 1){
        if(k == -1 || needle[k] == needle[j]){
            j++;
            k++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
    return next;
}

LC61 Rotate List

Problem

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Think

首先确定长度，然后截取第n - k和第n - k - 1个元素，进行置换即可。注意要先判断一下k是否为0，如果为0则直接返回head即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* rotateRight(ListNode* head, int k) {
    if(!head) return NULL;
    
    int len = 0;
    ListNode* node = head;
    while(node){
        len++;
        node = node->next;
    }
    k = k % len;
    if(k == 0) return head;
    node = head;
    for(int i = 0; i < len - k - 1; i++){
        node = node->next;
    }
    ListNode* res = node->next;
    node->next = NULL;
    ListNode* tail = res;
    while(tail->next) tail = tail->next;
    tail->next = head;
    return res;
}

LC75 Sort Colors

Problem

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?
Think

设两个指针left和right，所有小于left的下标的数值都是0，大于right的下标的数值都是2.设cur = 0，则当cur <= right的时候：

如果cur对应的数值为0，则交换cur和left对应的值，然后cur和left均右移一位；

如果cur对应的数值为2，则交换cur和right对应的值，然后right左移一位；

否则cur右移一位。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
void sortColors(vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = n - 1, cur = 0;
    while(cur <= right){
        if(nums[cur] == 0){
            swap(nums[cur++], nums[left++]);
        }
        else if(nums[cur] == 2){
            swap(nums[cur], nums[right--]);
        }
        else cur++;
    }
}

LC80 Remove Duplicates from Sorted Array II

Problem

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Think

双指针，分别表示前一个和前两个的值，注意要从第三个数字开始计算。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
    if(nums.size() < 2) return nums.size();
    int i = 2;
    int p1 = nums[0], p2 = nums[1];
    for(int j = 2; j < nums.size(); j++){
        int num = nums[j];
        if(num == p1 && num == p2){
            continue;
        }
        else{
            nums[i++] = num;
        }
        p1 = p2;
        p2 = num;
    }
    return i;
}

LC86 Partition List

Problem

Given a linked list and a value x, partition it such that all nodes less than xcome before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Think

定义两个变量。分别指向小于部分的首节点和大于等于部分的首节点

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* partition(ListNode* head, int x) {
    ListNode *head1 = new ListNode(0), *head2 = new ListNode(0);
    ListNode *res1 = head1, *res2 = head2;
    while(head){
        ListNode *node = new ListNode(head->val);
        if(head->val < x){
            head1->next = node;
            head1 = head1->next;
        }
        else{
            head2->next = node;
            head2 = head2->next;
        }
        head = head->next;
    }
    head1->next = res2->next;
    return res1->next;
}

LC88 Merge Sorted Array

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
Think

双指针，从最后一位开始遍历。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1;
    int k = m + n - 1;
    while(i >= 0 && j >= 0){
        if(nums1[i] > nums2[j]){
            nums1[k--] = nums1[i--];
        }
        else{
            nums1[k--] = nums2[j--];
        }
    }
    while(i >= 0) nums1[k--] = nums1[i--];
    while(j >= 0) nums1[k--] = nums2[j--];
}

LC141 Linked List Cycle

Problem

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

img

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Think

快慢指针找环

Code 
1
2
3
4
5
6
7
8
9
bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while(slow != NULL && fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow) return true;
    }
    return false;
}

LC142 Linked List Cycle II

Problem

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

img

Follow-up:
Can you solve it without using extra space?

Think

首先用快慢指针确定环的长度len，然后快指针先走len步，之后快慢指针一起走，相遇点就是环的起始点。

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
25
ListNode *detectCycle(ListNode *head) {
    int len = 0;
    ListNode* slow = head, *fast = head;
    bool flag = false;
    while(slow != NULL && fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        len++;
        if(slow == fast){
            flag = true;
            break;
        }
    }
    if(!flag) return NULL;
    slow = head;
    fast = head;
    for(int i = 0; i < len; i++){
        fast = fast->next;
    }
    while(slow != fast){
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

LC344 Reverse String

Problem

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

1
2
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

1
2
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Think

双指针，交换即可。

Code 
1
2
3
4
5
6
7
8
9
void reverseString(vector<char>& s) {
    int n = s.size();
    int left = 0, right = n - 1;
    while(left < right){
        char tmp = s[left];
        s[left++] = s[right];
        s[right--] = tmp;
    }
}

LC345 Reverse Vowels of a String

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

1
2
Input: "hello"
Output: "holle"

Example 2:

1
2
Input: "leetcode"
Output: "leotcede"

Note:
The vowels does not include the letter “y”.

Think

双指针，判断是否为元音字母即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isVowel(char c){
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
string reverseVowels(string s) {
    int n = s.size();
    int left = 0, right = n - 1;
    while(left < right){
        if(!isVowel(s[left])){
            left++;
            continue;
        }
        if(!isVowel(s[right])){
            right--;
            continue;
        }
        char tmp = s[left];
        s[left++] = s[right];
        s[right--] = tmp;
    }
    return s;
}

LC457 Circular Array Loop

Problem

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward ksteps. Conversely, if it’s negative (-k), move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:

1
2
3
Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.

Example 2:

1
2
3
Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example 3:

1
2
3
Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:

  1. -1000 ≤ nums[i] ≤ 1000
  2. nums[i] ≠ 0
  3. 1 ≤ nums.length ≤ 5000

Follow up:

Could you solve it in O(n) time complexity and O(1) extra space complexity?

Think

快慢指针，首先确定从i节点出发找环，如果i处对应的值为0，说明该节点被访问过（即已经判断过是否在环上），则继续下一个节点，否则：

首先判断当前节点的值和fast节点以及fast的next节点是否符合同正负，当符合时，slow向后一位，fast向后两位，判断是否相等即可。

最后将这个环上所有访问过的节点置为0。

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
25
26
bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(nums[i] == 0) continue;
            int slow = i, fast = getNext(nums, i), val = nums[i];
            while(val * nums[fast] > 0 && val * nums[getNext(nums, fast)] > 0){
                if(slow == fast){
                    if(slow == getNext(nums, slow)) break;
                    return true;
                }
                slow = getNext(nums, slow);
                fast = getNext(nums, getNext(nums, fast));
            }
            slow = i;
            while(val * nums[slow] > 0){
                int next = getNext(nums, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }
    int getNext(vector<int>& nums, int i){
        int n = nums.size();
        return (((nums[i] + i) % n) + n) % n;
    }

LC524 Longest Word in Dictionary through Deleting

Problem

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

1
2
3
4
5
Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

  1. All the strings in the input will only contain lower-case letters.
  2. The size of the dictionary won’t exceed 1,000.
  3. The length of all the strings in the input won’t exceed 1,000.
Think

对于每一个word，判断是否是s的一个子序列，如果是，则判断是否需要更新即可。

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
25
26
27
string findLongestWord(string s, vector<string>& d) {
    int len = 0;
    string res = "";
    for(string word: d){
        if(canProduce(s, word)){
            if(len < word.size()){
                len = word.size();
                res = word;
            }
            else if(len == word.size()){
                res = min(res, word);
            }
        }
    }
    return res;
}
bool canProduce(string s, string word){
    int n = s.size(), m = word.size();
    int i = 0, j = 0;
    while(i < n && j < m){
        if(s[i] == word[j]){
            j++;
        }
        i++;
    }
    return j == m;
}

Review

None