LeetCode 21-30

Chong Wang Lv6
  2016-10-07 22:27:24 2016-10-07 22:27:24 Created   2026-10-09 09:05:52 2026-10-09 09:05:52 Updated

These ten problems are difficult—there is a lot to remember.

21 Merge Two Sorted Lists

Merge two linked lists; handle empty lists carefully.

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
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution 
{
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
	{
		ListNode node(INT_MIN);
		ListNode *head = &node;

		while (l1&&l2)
		{
			if (l1->val < l2->val)
			{
				head->next = l1;
				l1 = l1->next;
			}
			else
			{
				head->next = l2;
				l2 = l2->next;
			}
			head = head->next;
		}
		head->next = l1 ? l1 : l2;
		return node.next;
	}
};

22 Generate Parentheses

Generate valid parentheses strings of length $2 * n$.

Recursion makes this problem easy to understand, but it can also be written iteratively; here is a dynamic-programming solution. Let $dp[x]$ represent every valid string with $x$ pairs of parentheses; derive $x+1$ by combining earlier strings whose pair counts add up to $x$.

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
void gen(vector<string>&res, int le, int ri, string cur)
{
	if (le == 0 && ri == 0)
	{
		res.push_back(cur);
		return;
	}
	if (le > 0)
	{
		gen(res, le - 1, ri, cur + '(');
	}
	if (ri > le)
	{
		gen(res, le, ri - 1, cur + ')');
	}
}

class Solution 
{
public:
	vector<string> generateParenthesis(int n)
	{
		vector<string>res;
		gen(res, n, n, "");
		return res;
	}
};

23 Merge k Sorted Lists

Merge $k$ linked lists.

Use the merge-sort idea.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
	ListNode node(INT_MIN);
	ListNode *head = &node;

	while (l1&&l2)
	{
		if (l1->val < l2->val)
		{
			head->next = l1;
			l1 = l1->next;
		}
		else
		{
			head->next = l2;
			l2 = l2->next;
		}
		head = head->next;
	}
	head->next = l1 ? l1 : l2;
	return node.next;
}

class Solution 
{
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) 
	{
		int sz = lists.size();
		if (sz == 0)
		{
			return NULL;
		}
		else if (sz == 1)
		{
			return lists[0];
		}
		vector<ListNode*>left(lists.begin(), lists.begin() + sz / 2);
		vector<ListNode*>right(lists.begin() + sz / 2, lists.end());
		return mergeTwoLists(mergeKLists(left), mergeKLists(right));
	}
};

24 Swap Nodes in Pairs

Swap adjacent nodes in a linked list.

This is a simpler version of reversing each following group of $k$ nodes. (There can never be too many linked-list problems.)

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
    	ListNode no = ListNode(0);
    	no.next = head;
    	ListNode *pre=&no;

    	while(head&&head->next)
    	{
    		ListNode *tmp=head->next->next;

    		pre->next=head->next;
    		head->next->next=head;
    		head->next=tmp;

    		pre = head;
    		head = tmp;
    	}

    	return no.next;   
    }
};

********25 Reverse Nodes in k-Group

Rotate each adjacent group of $k$ nodes in a linked list.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* reverseKGroup(ListNode* head, int k)
	{
		if (head == NULL || k == 1)return head;
		ListNode *res = new ListNode(-1);
		res->next = head;
		ListNode *pre = res;
		ListNode *cur = res;
		ListNode *nxt = res;

		int num = 0;
		while (cur->next)
		{
			cur = cur->next;
			num++;
		}
		while (num >= k)
		{
			cur = pre->next;
			nxt = cur->next;

			for (int i = 1; i < k; i++)
			{
				cur->next = nxt->next;
				nxt->next = pre->next;
				pre->next = nxt;
				nxt = cur->next;
			}
			num -= k;
			pre = cur;
		}
		return res->next;
	}
};

27 Remove Element

Remove elements equal to val from an array without allocating extra space.

My approach was still much more complicated; this solution runs in 0 ms.

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 removeElement(vector<int>& nums, int val)
	{
		int sz = nums.size();
		if (sz == 0)
		{
			return 0;
		}
		int idx = sz - 1;
		for (int i = sz - 1; i >= 0; i--)
		{
			if (nums[i] == val)
			{
				swap(nums[i], nums[idx]);
				idx--;
				sz--;
			}
		}
		nums.resize(sz);
		return sz;
	}
};

28  Implement strStr()

Return the index at which a substring occurs in the original string.

Plain KMP.

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
void getnext(string x, vector<int>&nxt)
{
	int k = -1;
	int len = x.length();
	nxt[0] = -1;
	for (int i = 0; i < len; )
	{
		if (k == -1 || x[k] == x[i])
		{
			k++;
			i++;
			nxt[i] = k;
		}
		else
		{
			k = nxt[k];
		}
	}
}

class Solution 
{
public:
	int strStr(string haystack, string needle) 
	{
		int len1 = haystack.length();
		int len2 = needle.length();
		
		vector<int>nxt(needle.length() + 1, 0);
		getnext(needle, nxt);

		int i = 0, j = 0;
		while (i < len1 && j < len2)
		{
			if (j == -1 || haystack[i] == needle[j])
			{
				i++;
				j++;
			}
			else
			{
				j = nxt[j];
			}
		}
		if (j == len2)
		{
			return i - len2;
		}
		else
		{
			return -1;
		}
	}
};

29 Divide Two Integers

Divide two integers without using multiplication, division, or modulo.

Use bit shifts and reduce the problem to binary operations.

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
long long cal(long long dividend, long long divisor)
{
	long long res = 0;
	long long d = abs(dividend);
	long long t = abs(divisor);

	while (d >= t)
	{
		long long cnt = 0;
		while ((t << cnt) <= d)
		{
			cnt++;
		}
		cnt--;
		d -= (t << cnt);
		res += (1LL << cnt);
	}
	int s1 = dividend < 0;
	int s2 = divisor < 0;
	if (s1^s2)
	{
		return -res;
	}
	else
	{
		return res;
	}
}

class Solution 
{
public:
	int divide(int dividend, int divisor) 
	{
		int s1 = dividend < 0;
		int s2 = divisor < 0;
		if (s1^s2)
		{
			if (abs(dividend) == INT_MIN&&abs(divisor) == 1)
				return INT_MIN;
		}
		else
		{
			if (abs(dividend) == INT_MIN&&abs(divisor) == 1)
				return INT_MAX;
		}
		long long res = cal(dividend, divisor);
		if (res > INT_MAX || res < INT_MIN)
		{
			return INT_MAX;
		}
		else
		{
			return res;
		}
	}
};

30 Substring with Concatenation of All Words

Given a set of strings and a source string, return every position where all set strings occur exactly once.

Keep a map of string counts, then inspect every position for missing or excessive occurrences.

This took far too long. This post uses a trie; I will improve this after reading it.

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
class Solution
{
public:
	vector<int> findSubstring(string s, vector<string>& words) 
	{
		map<string, int>num;
		int sz = words.size();
		int len = 0;
		vector<int>res;
		if (sz == 0)return res;
		int one = words[0].length();
		for (int i = 0; i < sz; i++)
		{
			num[words[i]]++;
			len += words[i].length();
		}
		int lens = s.length();
		for (int i = 0; i + len <= lens; i++)
		{
			map<string, int>tmp;
			int f = 0;
			for (int k = 0; k < sz; k++)
			{
				string t = s.substr(i + k*one, one);
				if (num.find(t) != num.end())
				{
					tmp[t]++;
					if (tmp[t] > num[t])
					{
						f = 1;
						break;
					}
				}
				else
				{
					f = 1;
					break;
				}
			}
			if (f == 0)
			{
				res.push_back(i);
			}
		}
		return res;
	}
};
On this page
LeetCode 21-30
  1. 21 Merge Two Sorted Lists
  2. 22 Generate Parentheses
  3. 23 Merge k Sorted Lists
  4. 24 Swap Nodes in Pairs
  5. ********25 Reverse Nodes in k-Group
  6. 27 Remove Element
  7. 28  Implement strStr()
  8. 29 Divide Two Integers
  9. 30 Substring with Concatenation of All Words