LeetCode

First Post:

Last Update:

Word Count:
2.4k

Read Time:
14 min

My leetcode: https://leetcode.com/i0gan

1. Two Sum

Intro

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int> ret;
        for(int i = 0; i < size; i++) {
            for(int j = i + 1; j < size; j++) {
                if(nums[i] + nums[j] == target) {
                    ret.push_back(i);
                    ret.push_back(j);
                }
            }
        }
        return ret;
    }
};

Runtime: 40 ms

Memory Usage: 8.9 MB

2. Add Two Numbers

Intro

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

img 
1
2
3
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

1
2
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

1
2
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Solution

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *l1p = l1;
        ListNode *l2p = l2;
        ListNode *out = new ListNode;
        ListNode *outp = out;
        outp->next = nullptr;
        
        int over = 0; //溢出位
        do {
            int l1v = 0, l2v = 0;
            bool is_continue = false;
            if(l1p) {
                l1v = l1p->val;
                l1p = l1p->next;
            }else {
                l1v = 0;
            }
            
            if(l2p) {
                l2v = l2p->val;
                l2p = l2p->next;
            }else {
                l2v = 0;
            }
            
            outp->val = (l1v + l2v + over) % 10; //加法运算
            over = (l1v + l2v + over) / 10; // 获取进位
            
            is_continue = l1p || l2p; // 是否循环
            
            if(is_continue) {
                outp->next = new ListNode;
                outp = outp->next;
                outp->next = nullptr;
                
            }else {
                if(over) { //进位不为0,则加入如进位到最高位。
                    outp->next = new ListNode;
                    outp = outp->next;
                    outp->val = over;
                    outp->next = nullptr;
                }
                break;
            }
        }while(true);
        
        return out;
    }
};

Runtime: 52 ms

Memory Usage: 71.4 MB

3. Longest Substring Without Repeating Characters

Intro

  • Given a string s, find the length of the longest substring without repeating characters.

    Example 1:

    1
    2
    3
    Input: s = "abcabcbb"
    Output: 3
    Explanation: The answer is "abc", with the length of 3.

    Example 2:

    1
    2
    3
    Input: s = "bbbbb"
    Output: 1
    Explanation: The answer is "b", with the length of 1.

    Example 3:

    1
    2
    3
    4
    Input: s = "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3.
    Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

    Example 4:

    1
    2
    Input: s = ""
    Output: 0

    Constraints:

    • 0 <= s.length <= 5 * 104
    • s consists of English letters, digits, symbols and spaces.

Solution

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ch_map[127] = {0};
        int out = 0;
        int sum = 0;
        int length = s.length(); 
        for(int i = 0; i < length; i++) {
            
            for(int j = i; j < length; j++) {
                if(ch_map[s[j]] == 1) { // 重复.
                    // 该子字符串长度sum
                    if(sum > out) out = sum; 
                    // 对ch_map清0
                    memset(ch_map, 0, sizeof(ch_map));
                    sum = 0;
                    break;
                } else {
                    ch_map[s[j]] = 1;
                    sum += 1;
                }
            }
        }
        
        if(sum > out) out = sum;
        
        return out;
    }
};

Runtime: 20 ms

Memory Usage: 6.9 MB

7. Reverse Integer

Intro

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

1
2
Input: x = 123
Output: 321

Example 2:

1
2
Input: x = -123
Output: -321

Example 3:

1
2
Input: x = 120
Output: 21

Constraints:

  • -231 <= x <= 231 - 1

Solution

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:
	int reverse(int x) {
		int _x = 0;
		bool if_minus = false;
		if(x == 0x80000000) return 0;

		if(x == 0) return 0;

		if(x < 0) {
			if_minus = true;
			_x = (0 - x);
		}else _x = x;

		int times = 0;	
		unsigned int num = _x;	
		long long result = 0;
		unsigned long long uresult = 0;

		do {
		times = num % 10;
		result *= 10;
		result += times;

		}while(num /= 10);
		uresult = (unsigned long long)result;

		if(uresult > 0xFFFFFFFF) {
			return 0;
		}else if(0 - result > 0xFFFFFFFF) {
			return 0;
		}


		if(if_minus) {
			if(if_minus == ((int)(0 - result) > 0)) return 0;
		 	else return (int)(0 - result);
		}else {
			if(if_minus == ((int)(result) > 0)) return 0;
		 	else return (int)result;
		}
	}
	
};

Runtime: 3 ms

Memory Usage: 6 MB

9. Palindrome Number

Intro

easy

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

  • For example, 121 is a palindrome while 123 is not.

Example 1:

1
2
3
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

1
2
3
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

  • -231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isPalindrome(int x) {
	int num_arr[16] = {0};	
	int len = 0;
	int num = x;
	if(x < 0) return false;

	do {
		num_arr[len] = num % 10;
		++ len;
	}while(num /= 10);
	

	for(int j = 0; j < len; j++){
		if(num_arr[j] != num_arr[len - j -1])
			return false;
	}	
	return true;
    }
};

Runtime: 22 ms

Memory Usage: 6 MB

13. Roman to Integer

Intro

easy

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

1
2
3
Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

1
2
3
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

1
2
3
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15
  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solution

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
class Solution {
public:
    int romanToInt(string s) {
        map<char, int> table = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        int ans = 0;
        int len = s.size();
        for(int i = 0; i < len-1; i++){
            if(table[s[i]] >= table[s[i+1]]){
                ans += table[s[i]];
            }else{
                ans += -table[s[i]];
            }
        }
        ans += table[s[len-1]];
        return ans;
    }
};

Runtime: 10 ms

Memory Usage: 8.3 MB

14

Intro

easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

Solution

部分还出错。

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
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
	string result("");
	vector<int> str_len_arr;
	int i = 0;
	int str_n = strs.size();
	if (str_n == 0) return result;

	for(i = 0; i < str_n; i++) {
		str_len_arr.push_back(strs[i].length());
	}

	for(i = 0; i < str_n - 1; i++) {
		if(str_len_arr[i] > str_len_arr[i + 1]) {
			str_len_arr[i] += str_len_arr[i + 1];
			str_len_arr[i + 1] = str_len_arr[i] - str_len_arr[i + 1];
			str_len_arr[i] = str_len_arr[i] - str_len_arr[i + 1];
		}
	}
	int min = str_len_arr[0];
	i = 0;
	while(true) {
		for(int j = 1; j < str_n; j++) {
			if(strs[j][i] != strs[0][i]) {
				goto NO;
			}
		}
//		cout << "debug" << i << endl;
		result += strs[0][i];
		i++;
		if(i >= min) break;
	}
	NO:	
	return result;
    }
};

20. Valid Parentheses

Solution

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
81
82
83
84
85
86
87
88
89
class Solution {
public:
    bool isValid(string s) {
        int len = s.length();
	int j = 0;
	char ch = 0;

	for(int i = 0; i < len; ) {
		switch(s[i]) {
		case '{': {
			if(i + 1 >= len){
				return false;
			}
			for(j = i + 1; j < len; ) {
				if(s[j] == ' ' ){
					j++;
				} else if (s[j] == '}') {
					s[i] = ' ';
					s[j] = ' ';
					while(i > 0) {
						if(s[i] == '{' || s[i] == '[' || s[i] == '(') break;
						else i --;
					}
					break;
				}else {
					i ++;
					break;
				}
				if(j >= len) return false;
			}
		} break;
		case '[': {
			if(i + 1 >= len){
				return false;
			}
			for(j = i + 1; j < len; ) {
				if(s[j] == ' ' ){
					j++;
				} else if (s[j] == ']') {
					s[i] = ' ';
					s[j] = ' ';
					while(i > 0) {
						if(s[i] == '{' || s[i] == '[' || s[i] == '(') break;
						else i --;
					}
					break;
				}else {
					i ++;
					break;
				}
				if(j >= len) return false;
			}
		} break;
		case '(': {
			if(i + 1 >= len){
				return false;
			}
			for(j = i + 1; j < len; ) {
				if(s[j] == ' ' ){
					j++;
				} else if (s[j] == ')') {
					s[i] = ' ';
					s[j] = ' ';
					while(i > 0) {
						if(s[i] == '{' || s[i] == '[' || s[i] == '(') break;
						else i --;
					}
					break;
				}else {
					i ++;
					break;
				}
				if(j >= len) return false;
			}
		} break;

		default : {
			i++;
		}
		}
	}

	for(int k = 0; k < len; k++) {
		if(s[k] != ' ') return false;
	}
	return true;	
    }

};

Runtime: 15 ms

Memory Usage: 6.2 MB

21. Merge Two Sorted Lists

Intro

easy

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

img 
1
2
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

1
2
Input: list1 = [], list2 = []
Output: []

Example 3:

1
2
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Solution

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:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

	if(l1 == NULL && l2 == NULL) return NULL;
	if(!l1) return l2;
	if(!l2) return l1;
	

	ListNode *ret = l1;
	do {
	if(l1 -> next != NULL) {
		l1 = l1 -> next;
	}	

	}while(l1 -> next);
	l1 -> next = l2; // merge

	for(l1 = ret;l1 -> next; l1 = l1 -> next) {
		for(l2 = ret; l2 -> next; l2 = l2 -> next) {
			if(l2 -> val > l2 -> next -> val) {
				l2 -> val += l2 -> next -> val;
				l2 -> next -> val = l2 -> val - l2 -> next -> val;
				l2 -> val = l2 -> val - l2 -> next -> val;
			}
		}
	}
	return ret;	
    } 
};
打赏点小钱
支付宝 | Alipay
微信 | WeChat