LeetCode 1-10

Chong Wang Lv6
  2016-09-21 10:15:24 2016-09-21 10:15:24 Created   2026-10-09 14:29:51 2026-10-09 14:29:51 Updated

September is almost over. It is time to work through LeetCode. I have long said that I would finish it, but never kept the momentum; with October approaching, I hope that three problems a day will get me through the set by year-end. While writing my diary yesterday, I realized that another notebook was nearly full. That reminded me of the many notebooks I have kept since I was seven—perhaps nearly twenty by now. Somehow, the next one feels like the second volume of my life, and I hope it will be a good one. Some competitive programmers look down on LeetCode as too easy; I disagree. Passing a problem may not be difficult, but interviews often require the best time and space complexity, which makes problems involving linked lists and STL design surprisingly demanding. I referred to many discussion threads and CSDN posts while writing these solutions.

I will not document every problem—only the details worth noting. This is a notebook, and I hope to add new insights later.

LeetCode1 Two Sum

Given an array and a target, find two values at different indices whose sum is the target, and return their indices.

If the array were sorted, scan once from both ends. Since it is unsorted, a brute-force solution is $O(n^2)$. Improve it with a map of values already seen, looking up target - current value; return when it is found.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
    	int sz=nums.size();
    	if(sz <= 1)return {-1,-1};
    	unordered_map<int,int>hax;
    	for(int i=0;i<sz;i++)
    	{
    		if(hax.find(target-nums[i])!=hax.end())
    		{
    			return {hax[target-nums[i]],i};
    		}
    		hax[nums[i]]=i;
    	}
    	return {-1,-1};
    }
};

LeetCode2 Add Two Numbers

Given two linked lists, each representing a number, compute their sum and return it as a linked list.

I once had a pointer go wildly wrong in a program, and the bug took ages to find. Ever since, pointers have made me a little nervous.

Fortunately, the digits are stored in reverse order, so no backward calculation is needed.

Keep going while either pointer or the carry is nonzero, create one node per step, and return the original head node.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {	
    	ListNode *pre = new ListNode(0);
    	ListNode *res = pre;
    	int ex = 0;
    	while(l1||l2||ex)
    	{
    		int sum = (l1?l1->val:0) + (l2?l2->val:0) + ex;
    		ListNode *a = new ListNode(sum%10);
    		ex=sum/10;
    		pre->next = a;
    		pre = a;
    		l1 = l1?l1->next:0;
    		l2 = l2?l2->next:0;
    	}   
    	return res->next;
    }
};

LeetCode3 Longest Substring Without Repeating Characters

Given a string, find its longest substring without repeating characters.

Track the most recent previous position of each character. The distance gives the length of the non-repeating substring ending at the current position; take the maximum.

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 lengthOfLongestSubstring(string s) 
    {
    	int len = s.length();
    	if(len==0)return 0;
    	vector<int>dic(256,-1);

    	int res=0,begin=-1;
    	for(int i=0;i<len;i++)
    	{
    		if(dic[s[i]]>begin)
    		{
    			begin=dic[s[i]];
    		}
    		dic[s[i]]=i;
    		res=max(res,i-begin);
    	}
    	return res;
    }
};

LeetCode4 Median of Two Sorted Arrays

Given two sorted arrays, return the median of their merged sequence.

The interesting part is repeatedly binary-searching a cut in the shorter array. A median divides the elements into two halves, so the cut position determines the cut in the other array. This gives four boundary values—L1, L2, R1, and R2. Check whether those boundaries are valid, then continue the binary search. A great problem.

The odd/even cases can be handled by multiplying by 2.

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
class Solution 
{
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int n1 = nums1.size();
		int n2 = nums2.size();

		if (n1 > n2)
		{
			return findMedianSortedArrays(nums2, nums1);
		}
		if (n2 == 0)
		{
			return (nums1[(n1 - 1) / 2] + nums1[n1 / 2]) / 2.0;
		}
		int le = 0, ri = 2 * n1;
		while (le <= ri)
		{
			int mid1 = (le + ri) >> 1;
			int mid2 = n1 + n2 - mid1;

			int L1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2];
			int R1 = mid1 == 2 * n1 ? INT_MAX : nums1[mid1 / 2];

			int L2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2];
			int R2 = mid2 == 2 * n2 ? INT_MAX : nums2[mid2 / 2];

			if (L1 > R2)
			{
				ri = mid1 - 1;
			}
			else if (L2 > R1)
			{
				le = mid1 + 1;
			}
			else
			{
				return (max(L1, L2) + min(R1, R2)) / 2.0;
			}
		}
		return -1;
	}
};

LeetCode5 Longest Palindromic Substring

Find the longest palindromic substring.

$O(n^2)$ brute force; $O(n)$ Manacher’s algorithm. Leaving this for tonight.

This was a review of Manacher’s algorithm. I found this explanation especially clear. When computing each Len[j], the earlier Len[i] values are known; compare rightmost - i with the length at the position symmetric to rightmost, and take the smaller as the initial Len[j].

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
74
75
76
77
78
79
80
string change(string x)
{
	string res="@";
	int len=x.length();

	for(int i=0;i<len;i++)
	{
		res = res + '#';
		res = res + x[i];
	}
	res = res + '#';
	res = res + '$';
	return res;
}

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
    	int len=s.length();
    	if(len==0)return "";
    	s=change(s);
    	len=s.length();
        vector<int> Len(len+1,0);
        int mx=0,ans=0,po=0,resp=0;
        for(int i=1;i<=len;i++)
        {
        	if(mx>i)
        	{
        		Len[i] = min(mx-i,Len[2*po-i]);
        	}
        	else
        	{
        		Len[i] = 1;
        	}
        	while(s[i-Len[i]]==s[i+Len[i]])
        	{
        		Len[i]++;
        	}
        	if(Len[i]+i>mx)
        	{
        		mx=Len[i]+i;
        		po=i;
        	}
        	if(Len[i]>ans)
        	{
        		ans=Len[i];
        		resp = i;
        	}
        }
        string r;
    	for(int i=resp; i<=resp+ans-1 ;i++)
    	{
    		r=r+s[i];
    	}
    	string pre=r;
    	reverse(r.begin(),r.end());
    	string all = r+pre;
    	string ret="";
    	if(s[resp]=='#')
    	{
    		for(int i=0;i<all.length();i++)
    		{
    			if(all[i]=='#')continue;
    			ret=ret+all[i];
    		}
    	}
    	else
    	{
			for(int i=0;i<all.length();i++)
    		{
    			if(i>=1&&all[i]==all[i-1])continue;
    			if(all[i]=='#')continue;
    			ret=ret+all[i];
    		}
    	}
    	return ret;
    }
};

LeetCode7 Reverse Integer

Given an integer, reverse its digits.

Pay close attention to trailing zeroes such as 100, negative values, and overflow. I encountered this kind of edge case in a Baidu interview, where it was expected to 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
    int reverse(int x)
    {
    	if(x==0)return 0;
    	int f=0;
    	if(x<0)
    	{
    		f=1;
    		x=-x;
    	}
        int dig[20];
        int cnt=0;
        while(x)
        {
        	cnt++;
        	dig[cnt]=x%10;
        	x/=10;
        }
        long long res=0;
        for(int i=1;i<=cnt;i++)
        {
        	res=res*10+dig[i];
        }
        if(f)
        {
        	res=-res;
        }
        if(res>2147483647||res<-2147483648)
        {
        	return 0;
        }
        else
        {
        	return res;
		}
    }
};

LeetCode8 String to Integer (atoi)

Convert a string to an integer.

Watch the sign.

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 Solution 
{
public:
    int myAtoi(string str)
    {  
        int i=0;
        int sign=1;
        while(str[i]==' ')i++;
        if(str[i]=='-'||str[i]=='+')
        {
            sign = 1-2*(str[i]=='-');
            i++;
        }
        int base=0;
        int len=str.length();

        while(i<len&&str[i]<='9'&&str[i]>='0')
        {
            if(base>INT_MAX/10||(base==INT_MAX/10&&str[i]>='7'))
            {

                if(sign==1)
                {
                    return INT_MAX;
                }
                else
                {
                    if(base>INT_MAX/10||(base==INT_MAX/10&&str[i]>='8'))
                    {
                        return INT_MIN;
                    }
                }
            }

            base=base*10+str[i]-'0';
            i++;
        }

        if(sign==-1)
        {
            base=-base;
        }
        return base;
    }
};

LeetCode10 Regular Expression Matching

Given a matching rule where . matches any character and * means the preceding character may occur zero or more times.

This problem was painful. I spent a long time untangling the statement: .* can match every character, whereas I initially thought the preceding . had already been fixed.

After that, DP is the natural approach. dp[i][j] represents whether the first $i$ characters can match the first $j$ characters.

The rest is straightforward; the key is *, which requires considering zero, one, or multiple occurrences of its preceding character.

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 m = s.length();
		int n = p.length();
		vector<vector<int>>dp(n + 1, vector<int>(m + 1, 0));

		dp[0][0] = 1;
		for (int i = 1; i <= n; i++)
		{
			if (p[i - 1] == '*'&&dp[i - 2][0])
			{
				dp[i][0] = 1;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (p[i - 1] == '*')
				{
					dp[i][j] |= dp[i - 2][j];//0
					dp[i][j] |= dp[i - 2][j - 1] && (p[i - 2] == '.' || p[i - 2] == s[j - 1]);//1
					if (j >= 2)
					{
						dp[i][j] |= dp[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.');//multi
					}
				}
				else
				{
					dp[i][j] = dp[i - 1][j - 1] && (p[i - 1] == '.' || p[i - 1] == s[j - 1]);
				}
			}
		}
		return dp[n][m];
	}
}t;
On this page
LeetCode 1-10
  1. LeetCode1 Two Sum
  2. LeetCode2 Add Two Numbers
  3. LeetCode3 Longest Substring Without Repeating Characters
  4. LeetCode4 Median of Two Sorted Arrays
  5. LeetCode5 Longest Palindromic Substring
  6. LeetCode7 Reverse Integer
  7. LeetCode8 String to Integer (atoi)
  8. LeetCode10 Regular Expression Matching