Leetcode刷题笔记 1

1. Two Sum

Q: 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.

第一反应自然是暴力

cpp
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

但这样做显然不够好，我们可以使用键值对来存储<<value, index>>对，一边遍历一边查找键值对内是否有匹配的值。具体的数据结构可以选择哈希表，因为哈希表的插入/查找都是o(1)操作，因此我们可以将总体的复杂度降至o(n)

cpp
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    unordered_map<int, int> indices;
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        if (indices.find(target - *it) != indices.end()) {
            res.push_back(indices[target - *it]);
            res.push_back(it - nums.begin());
            break;
        }
        indices[*it] = it - nums.begin();
    }
    return res;
}

2. Add Two Numbers

Q: 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.

这个题不算难，就是写起来有点别扭，我自己写的非常丑，贴一个别人写的吧。

cpp
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode dummy(0), *p = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        carry = sum / 10;
        p->next = new ListNode(sum % 10);
        p = p->next;
        l1 = l1 ? l1->next : l1;
        l2 = l2 ? l2->next : l2;
    }
    return dummy.next;
}

3. Longest Substring without Repeating Characters

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

简单的思路自然还是o(n^2)的，写起来也很简单

cpp
int lengthOfLongestSubstring(string s) {
    int ans = 0;
    for (int first = 0, last = 0; last < s.length(); last++) {
        for (int i = last - 1; i >= first; i--) {
            if (s[i] == s[last]) {
                first = i + 1;
                break;
            }
        }
        ans = max(res, last - first + 1);
    }
    return ans;
}

但是效率堪忧，容易想到保存字母最后出现的位置，在遍历的同时即可判断当前范围内是否有重复字符，因而只需要遍历一次即可解决，时间复杂度为o(n)，本题只有字母，因而使用数组就可以保存下标，如果碰到数字等范围较大的数据，则可以考虑哈希表，下面的代码是别人的实现，index数组里实际存储的不是最后出现的位置，而是最后出现的位置+1，每次遇到重复字符时，将first设置为该重复字符最后出现的位置+1，即可使范围内不再存在重复字符。只能说这个实现实在是非常精炼。

cpp
int lengthOfLongestSubstring(string s) {
    int ans = 0, index[256] = {0};
    for (int first = 0, last = 0; last < s.length(); last++) {
        first = max(index[s[last]], first);
        ans = max(ans, last - first + 1);
        index[s[last]] = last + 1; //index + 1, because index[] is init'd to all 0.
    }
    return ans;
}

5. Longest Palindrome Substring

Q: Given a string s, return the longest palindromic substring in s.

给一个字符串s，返回该字符串的最长回文子字符串。同样可以笨办法解决，思路也很简单，遍历所有可能的情况。对于每一个位置，都考虑奇数/偶数长度回文字符串向两个方向搜索，直到碰到不匹配的字符或者到达字符串边缘。

cpp
string longestPalindrome(string s) {
    int len = s.length(), max_len = 0, first = 0;
    for (int i = 0; i < len; i++) {
        //odd length
        for (int j = i, k = i; j < len && k >= 0 && s[j] == s[k]; j++, k--) {
            if (j - k + 1 > max_len) {
                max_len = j - k + 1;
                first = k;
            }
        }
        //even length
        for (int j = i + 1, k = i; j < len && k >= 0 && s[j] == s[k]; j++, k--) {
            if (j - k + 1 > max_len) {
                max_len = j - k + 1;
                first = k;
            }
        }
    }
    return s.substr(first, max_len);
}

这个问题有个o(n)的算法Manacher’s Algorithm，不过比较复杂，我就不献丑了。

6. ZigZag Conversion

Q: The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

cpp
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

这题要求实现一个字符串转换的函数，也是写起来比较烦的类型。总之我就不献丑了，抄了一个别人的代码。

cpp
string convert(string s, int numRows) {
    if (numRows == 1) return s;
    vector<string> rows(numRows);
    int curRow = 0, delta = -1;
    for (char c : s) {
        rows[curRow] += c;
        (curRow == 0 || curRow == numRows - 1) && (delta = -delta);
        curRow += delta;
    }
    string ret;
    for (string row : rows) {
        ret += row;
    }
    return ret;
}

7. Reverse Integer

Q: 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 $[-2^{31}, 2^{31} - 1]$, then return 0.

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

这是个有点意思也有点烦的题目，要求在不支持64位int的条件下实现翻转int的十进制位，如果可以使用64位整数，这个题目其实非常基础。

cpp
int reverse(int x) {
    long long res = x < 0 ? -1 : 1;
    long long sum = 0, tmp = labs(x);
    if (x == 0) return 0;
    while (tmp) {
        sum *= 10;
        sum += tmp % 10;
        tmp /= 10;
    }
    if (INT_MIN <= res * sum && res * sum <= INT_MAX)
        return res * sum;
    return 0;
}

如果限制64位数据，则需要仔细考虑溢出的问题，举个例子，一个8bit整数127翻转会变为721，原本不会溢出翻转之后就溢出了。本身这个题目就比较烦，主要考察的是底层的int范围，这里贴一个当时抄的代码。

cpp
int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        int pop = x % 10;
        x /= 10;
        if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
        if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
        rev = rev * 10 + pop;
    }
    return rev;
}

8. String to Integer (atoi)

Q: Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

  1. Read in and ignore any leading whitespace.
  2. Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
  3. Read in next the characters until the next non-digit charcter or the end of the input is reached. The rest of the string is ignored.
  4. Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
  5. If the integer is out of the 32-bit signed integer range $[-2^{31}, 2^{31} - 1]$, then clamp the integer so that it remains in the range. Specifically, integers less than $-2^{31}$ should be clamped to $-2^{31}$, and integers greater than $2^{31} - 1$ should be clamped to $2^{31} - 1$.
  6. Return the integer as the final result.

Note:

  • Only the space character ‘ ‘ is considered a whitespace character.
  • Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

这题要求实现自己的atoi函数，比较麻烦，所以也不多说了，直接贴代码吧。

cpp
int myAtoi(string str) {
    int idx = 0, sign = 1, res = 0, tmp;
    while (str[idx] == ' ') { idx++; }
    if (str[idx] == '-' || str[idx] == '+') {
        if (str[idx] == '-') {
            sign = -1;
        }
        idx++;
    }
    if (!isdigit(str[idx])) { return 0; }
    while (isdigit(str[idx])) {
        tmp = str[idx] - '0';
        if (res > INT_MAX / 10) {
            return sign == 1 ? INT_MAX : INT_MIN;
        }
        if (res == INT_MAX / 10) {
            if (sign == 1 && tmp > 6) return INT_MAX;
            if (sign == -1 && tmp > 7) return INT_MIN;
        }
        res = res * 10 + tmp;
        idx++;
    }
    return sign * res;
}