LeetCode 41-50

Chong Wang Lv6
  2016-12-12 20:43:11 2016-12-12 20:43:11 Created   2026-10-09 09:06:43 2026-10-09 09:06:43 Updated  

If I do not write another post, this blog will gather dust. Recently I have been working on program static analysis: extracting relevant features and using IDA Python to obtain opcodes and immediate values. I have some interview notices, so I decided to return to LeetCode and catch up. I have now solved a little over 200 LeetCode problems and will write more summaries later. I still have more than ten Level 4 51nod problems left; after finishing them, I will organise my thoughts properly. (I have almost forgotten how to write a blog.)

41 First Missing Positive

Given an array, find the smallest missing positive integer in $O(n)$ time and constant space.

Make the value at index $i$ equal to $i+1$ by repeatedly swapping at each position, then scan for the first value that is not $i+1$.

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:
	int firstMissingPositive(vector<int>& nums) 
	{
		int sz = nums.size();
		if (sz == 0)return 1;
		for (int i = 0; i < sz; )
		{
			if (nums[i] != i + 1 && nums[i] <= sz&&nums[i] >= 1&&nums[i]!=nums[nums[i]-1])
			{
				swap(nums[i], nums[nums[i] - 1]);
			}
			else
			{
				i++;
			}
		}
		for (int i = 0; i < sz; i++)
		{
			if (nums[i] != i + 1)
			{
				return i + 1;
			}
		}
		return sz + 1;
	}
};

42 Trapping Rain Water

Given heights at every position, find the total amount of trapped water.

At every position, the trapped water is the smaller of the two side maxima minus the position’s height.

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
class Solution
{
public:
	int trap(vector<int>& height)
	{
		if (height.size() < 3)return 0;
		int i, j, k;
		int sz = height.size();
		vector<int>le(sz, 0);
		vector<int>ri(sz, 0);

		le[0] = height[0], ri[sz - 1] = height[sz - 1];
		for (i = 1; i <= sz - 2;i++)
		{
			le[i] = max(le[i - 1], height[i]);
		}
		for (i = sz - 2; i >= 1; i--)
		{
			ri[i] = max(ri[i + 1], height[i]);
		}
		int res = 0;
		for (i = 1; i <= sz - 2; i++)
		{
			int val = min(le[i - 1], ri[i + 1]);
			if (height[i] >= val)continue;
			res += (val - height[i]);
		}
		return res;
	}
};

43 Multiply Strings

Multiply two large integers.

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
class Solution
{
public:
	string multiply(string num1, string num2)
	{
		int len1 = num1.length();
		int len2 = num2.length();
		string res(len1 + len2, '\0');

		for (int i = len1 - 1; i >= 0; i--)
		{
			int c = 0;
			for (int j = len2 - 1; j >= 0; j--)
			{
				int k = i + j + 1;
				int v1 = num1[i] - '0';
				int v2 = num2[j] - '0';
				res[k] = res[k] + v1*v2 + c;
				c = res[k] / 10;
				res[k] = res[k] % 10;
			}
			res[i] += c;
		}

		size_t pos = res.find_first_not_of('\0');
		if (string::npos != pos)
		{
			for (int i = pos; i < res.length(); i++)
			{
				res[i] = res[i] + '0';
			}
			return res.substr(pos);
		}
		return "0";
	}
};

44 Wildcard Matching

? matches any character and * matches any character sequence; determine whether the latter pattern matches the former string.

Dynamic programming: use a two-dimensional array.

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
class Solution
{
public:
	bool isMatch(string s, string p)
	{
		int len1 = s.length();
		int len2 = p.length();
		vector<vector<bool>>dp(len2 + 1, vector<bool>(len1 + 1, 0));
		s = ' ' + s;
		p = ' ' + p;
		dp[0][0] = 1;
		for (int i = 1; i <= len2; i++)
		{
			if (dp[i - 1][0])
			{
				if (p[i] == '*')
				{
					dp[i][0] = 1;
				}
			}
		}
		for (int i = 1; i <= len2; i++)
		{
			for (int j = 1; j <= len1; j++)
			{
				if (p[i] == '?')
				{
					if (dp[i - 1][j - 1])
					{
						dp[i][j] = 1;
					}
				}
				else if (p[i] == '*')
				{
					if (dp[i - 1][j - 1])
					{
						dp[i][j] = 1;
					}
					if (dp[i - 1][j])dp[i][j] = 1;
					if (dp[i][j - 1])dp[i][j] = 1;
				}
				else
				{
					if (p[i] == s[j])
					{
						if (dp[i - 1][j - 1])
						{
							dp[i][j] = 1;
						}
					}
				}
			}
		}
		return dp[len2][len1];
	}
};

The runtime was painful, so compress the two dimensions into one. Different cases use different values during iteration, so their for loops differ.

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
class Solution
{
public:
	bool isMatch(string s, string p)
	{
		int len1 = s.length();
		int len2 = p.length();
		vector<bool>dp(len1 + 1,0);
		s = ' ' + s;
		p = ' ' + p;
		dp[0] = 1;
		for (int i = 1; i <= len2; i++)
		{
			if (p[i] == '*')
			{
				for (int j = 1; j <= len1; j++)
				{
					dp[j] = dp[j] | dp[j - 1];
				}
			}
			else
			{
				for (int j = len1; j >= 1; j--)
				{
					if ((p[i] == '?') ||((p[i] == s[j])))
					{
						dp[j] = dp[j - 1];
					}
					else
					{
						dp[j] = false;
					}
				}
			}
			dp[0] = dp[0] & (p[i] == '*');
		}
		return dp[len1];
	}
}wc;

45 Jump Game II

Given the maximum jump distance at each position, find the minimum number of jumps from the start to the end.

Normally, record the furthest reachable position, num[i] + i, at every index. When the current reach is insufficient, jump from the earlier position with the greatest reach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution 
{
public:
	int jump(vector<int>& nums)
	{
		int res = 0;
		int curMax = 0;
		int curDis = 0;

		for (int i = 0; i < nums.size(); i++)
		{
			if (curDis < i)
			{
				res++;
				curDis = max(curDis, curMax);
			}
			curMax = max(curMax, nums[i] + i);
		}
		return res;
	}
};

47 Permutations II

Given an array with duplicate elements, return all unique permutations.

It is not very different from the previous combination problem: use i != begin && num[i] == num[i - 1] to skip duplicates.

This time, repeatedly swap elements and backtrack.

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
void perm(vector<vector<int>>& res, vector<int> nums, int k)
{
	if (k == nums.size())
	{
		res.push_back(nums);
		return;
	}
	for (int i = k; i < nums.size(); ++i)
	{
		if (i != k && nums[i] == nums[k]) continue;
		swap(nums[i], nums[k]);
		perm(res, nums, k + 1);
	}
}

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums)
	{
		vector<vector<int>>res;
		sort(nums.begin(),nums.end());
		perm(res,nums,0);
		return res;
	}
};

48 Rotate Image

Rotate an $n * n$ matrix 90 degrees clockwise.

Move from the outside in, swapping the values at four positions each time.

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
class Solution
{
public:
	void rotate(vector<vector<int>>& matrix)
	{
		int n = matrix.size();
		if (n == 0)return;

		int sz = n;
		int cur = 0;
		while (sz > 1)
		{

			for (int i = cur; i < sz - 1; i++)
			{
				int tmp = matrix[cur][i];
				matrix[cur][i] = matrix[n - 1 - i][cur];
				matrix[n - 1 - i][cur] = matrix[n - 1 - cur][n - 1 - i];
				matrix[n - 1 - cur][n - 1 - i] = matrix[i][n - 1 - cur];
				matrix[i][n - 1 - cur] = tmp;
			}
			cur++;
			sz--;
		}

	}
}wc;

50 Pow(x, n)

Compute $x$ to the power of $n$.

I am recording this mainly as a reminder that x and n can take many forms, and every case must be considered.

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
class Solution {
public:
    double myPow(double x, int n) 
    {
    	double res=1;
    	int f=0;
    	long long tmp=n;
    	if(tmp<0)
    	{
    		f=1;
    		tmp=-tmp;
    	}
    	while(tmp)
    	{
    		if(tmp&1)
    		{
    			res=res*x;
    		}
    		x=x*x;
    		tmp>>=1;
    	}  
    	if(f)res=1.0/res;  
    	return res;
    }
};
On this page
LeetCode 41-50
  1. 41 First Missing Positive
  2. 42 Trapping Rain Water
  3. 43 Multiply Strings
  4. 44 Wildcard Matching
  5. 45 Jump Game II
  6. 47 Permutations II
  7. 48 Rotate Image
  8. 50 Pow(x, n)