Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 781 Reading time ≈ 1 mins.

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverse(self, x: int) -> int:
        res, MAX = 0, (1 << 31) - 1
        sign = -1 if x < 0 else 1
        x = abs(x)
        while x > 0:
            res = res * 10 + x % 10
            x //= 10
            if res > MAX: return 0
        return res * sign

这道题不需要保存负号，直接转即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int reverse(int x) {
        long res = 0;
        while (x) {
            res = res * 10 + x % 10;
            x /= 10;
            if (res < INT_MIN || res > INT_MAX) return 0; // 只要invalid就返回
        }
        return res;
    }
};

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int reverse(int x) {
        if (x == INT_MIN || x == 0) return 0;
        int sign = x < 0 ? -1 : 1;
        x = abs(x);
        string s = to_string(x);
        while (!s.empty() && s.back() == '0') s.pop_back();
        long res = 0;
        for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
            res = res * 10 + *rit - '0';
            if (res > INT_MAX) return 0;
        }
        return sign * res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 721 Reading time ≈ 1 mins.

O(n) time O(n) space
用辅助字符串组来保存每一行的字符串，通过调整step来决定是从上往下放字符还是从下往上放字符，当指针指向第一行则从上往下，当指针指向最后一行则从下往上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows <= 1 or numRows >= len(s): return s
        v = [''] * numRows
        # v = ['' for i in range(numRows)]
        i, step = 0, -1
        for c in s:
            if i == numRows - 1:
                step = -1
            elif i == 0:
                step = 1
            v[i] += c
            i += step
        return ''.join(v)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> v(numRows);
        int i = 0, step = -1;
        for (char c : s) {
            if (i == numRows - 1) {
                step = -1;
            } else if (i == 0) {
                step = 1;
            }
            v[i] += c;
            i += step;
        }
        string res;
        for (const auto &str : v) {
            res += str;
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.2k Reading time ≈ 3 mins.

manacher’s algorithm可以O(n)但是不会
O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def find(l, r):
            while 0 <= l and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1
        ll, rr = 0, 0
        for i in range(len(s)):
            l, r = find(i, i)
            if r - l > rr - ll: ll, rr = l, r
            l, r = find(i, i + 1)
            if r - l > rr - ll: ll, rr = l, r
        return s[ll:rr + 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindrome(self, s: str) -> str:
        ll, rr = 0, 0
        for i in range(len(s)):
            l, r = self.find(s, i, i)
            if r - l > rr - ll: ll, rr = l, r
            l, r = self.find(s, i, i + 1)
            if r - l > rr - ll: ll, rr = l, r
        return s[ll:rr + 1]

    def find(self, s, l, r):
        while 0 <= l and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPalindrome(string s) {
        int ll = 0, rr = 0;
        auto search = [&s, &ll, &rr](int l, int r) {
            while (0 <= r && r < size(s) && s[l] == s[r]) {
                --l;
                ++r;
            }
            if (r - l > rr - ll) {
                ll = l;
                rr = r;
            }
        };
        for (int i = 0; i < size(s); ++i) {
            search(i, i);
            search(i, i + 1);
        }
        return s.substr(ll + 1, rr - ll - 1);
    }
};

因为回文串是对称的，所以枚举所有可能的对称轴
对称轴可能是某个字符，也可能是两个字符中间，填充#符号来避免奇偶问题
枚举每个可能的对称轴，从对称轴开始向左右两边比较字符直到找到不一样的或者越界，然后左右指针均回退一个（回退以后一定都是指向#符号），更新全局左右指针
最后重建原字符串里的最长回文子字符串
O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '#' + '#'.join(list(s)) + '#'
        n = len(s)
        ll, rr = n, n
        for i in range(1, n):
            l, r = i - 1, i + 1
            while 0 <= l and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l > rr - ll: ll, rr = l + 1, r - 1
        return s[ll + 1 : rr : 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
class Solution {
public:
    string longestPalindrome(string s) {
        string str = "#";
        for (char c : s) {
            str += c;
            str += '#';
        }
        int n = str.length(), ll = 0, rr = 0;
        for (int i = 1; i < n - 1; ++i) {
            int l = i - 1, r = i + 1;
            while (0 <= l && r < n && str[l] == str[r]) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (r - l > rr - ll) {
                ll = l;
                rr = r;
            }
        }
        string res;
        for (int i = ll + 1; i <= rr; i += 2) {
            res += str[i];
        }
        return res;
    }
};
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:
    string longestPalindrome(string s) {
        string str = split(s);
        int n = str.length();
        int left = 0, right = 0;
        for (int i = 1; i < n - 1; ++i) {
            int l = i, r = i;
            while (str[l] == str[r] && l >= 0 && r < n) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (r - l > right - left) {
                left = l;
                right = r;
            }
        }
        return reconstruct(str, left, right);
    }

    string split(string &s) {
        string str = "#";
        for (const auto &c : s) {
            str += c;
            str += '#';
        }
        return str;
    }

    string reconstruct(string &s, int l, int r) {
        string str;
        for (int i = l + 1; i < r; i += 2) {
            str += s[i];
        }
        return str;
    }
};

memo+recursive
f(l, r)表示s[l:r]中最长的回文串的长度

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:
    string longestPalindrome(string s) {
        int n = s.length(), b = 0;
        m.resize(n, vector<int>(n, -1));
        int mx = f(s, 0, n - 1);
        for (int l = 0, r = l + mx - 1; 0 <= r && r < n; ++l, ++r) {
            if (m[l][r] == mx) return s.substr(l, mx);
        }
        return "";
    }

    int f(const string &s, int l, int r) {
        if (l > r) return 0;
        if (m[l][r] > 0) return m[l][r];
        if (l == r) return m[l][r] = 1;
        m[l][r] = max(f(s, l, r - 1), f(s, l + 1, r));
        if (s[l] == s[r]) {
            int t = f(s, l + 1, r - 1);
            if (l + t + 1 == r) {
                m[l][r] = max(m[l][r], r + 1 - l);
            }
        }
        return m[l][r];
    }

    vector<vector<int>> m;
};

Posted on Edited on In Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

二分法O(log(m+n))
题解
把原题转换成给定两个排好序的数组，找出其中第k小的数（k是1-based）
复杂度计算：少1/4，少1/8，少1/16，直到逼近中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n = len(nums1) + len(nums2) + 1
        return (self.findKth(nums1, 0, nums2, 0, n // 2) + self.findKth(nums1, 0, nums2, 0, (n + 1) // 2)) / 2 #必须要用self，跟MATLAB一样

    def findKth(self, A: List[int], b1: int, B: List[int], b2: int, k) -> float:
        m, n = len(A) - b1, len(B) - b2
        if m > n: return self.findKth(B, b2, A, b1, k)
        if m == 0: return B[b2 + k - 1]
        if k == 1: return min(A[b1], B[b2])
        i, j = min(k // 2, m), min(k // 2, n)
        if A[b1 + i - 1] < B[b2 + j - 1]: return self.findKth(A, b1 + i, B, b2, k - i)
        return self.findKth(A, b1, B, b2 + j, k - j)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def findKth(A, b1, B, b2, k):
            m, n = len(A) - b1, len(B) - b2
            if m > n: return findKth(B, b2, A, b1, k)
            if m == 0: return B[b2 + k - 1]
            if k == 1: return min(A[b1], B[b2])
            i, j = min(k // 2, m), min(k // 2, n)
            if A[b1 + i - 1] < B[b2 + j - 1]: return findKth(A, b1 + i, B, b2, k - i)
            return findKth(A, b1, B, b2 + j, k - j)
        n = len(nums1) + len(nums2) + 1
        return (findKth(nums1, 0, nums2, 0, n // 2) + findKth(nums1, 0, nums2, 0, (n + 1) // 2)) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (kth(nums1, 0, nums2, 0, (m + n + 1) / 2) + kth(nums1, 0, nums2, 0, (m + n + 2) / 2)) * 0.5;
    }

    int kth(const vector<int> &nums1, int b1, const vector<int> &nums2, int b2, int k) {
        int m = int(nums1.size()) - b1, n = int(nums2.size()) - b2;
        if (m > n) return kth(nums2, b2, nums1, b1, k);
        if (m == 0) return nums2[b2 + k - 1];
        if (k == 1) return min(nums1[b1], nums2[b2]);
        int i = min(m, k / 2), j = min(n, k / 2);
        return nums1[b1 + i - 1] < nums2[b2 + j - 1] ? kth(nums1, b1 + i, nums2, b2, k - i) : kth(nums1, b1, nums2, b2 + j, k - j);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) * 0.5; // 这里因为是第k大，所以是1-based，(m + n + 1) / 2和(m + n + 2) / 2当m + n是奇数的时候相等，偶数的时候相邻
    }

    double findKth(const vector<int> &A, const vector<int> &B, int k) {
        int m = A.size(), n = B.size();
        if (m > n) return findKth(B, A, k); // 永远保持A比B少
        if (m == 0) return B[k - 1]; // 如果A是空的，直接在B里找
        if (k == 1) return min(A[0], B[0]); // 如果要找第1小的数，直接返回最小的那个
        int i = min(m, k / 2), j = min(n, k / 2); // 每次去掉较小的那k / 2个
        return A[i - 1] < B[j - 1] ? findKth(vector<int>(A.begin() + i, A.end()), B, k - i) : findKth(A, vector<int>(B.begin() + j, B.end()), k - j);
    }
};

O(log(m+n))二分法
把原题转换成找第k小的数，k=(m+n)/2
每次比较两个数组中第k/2大的数，假设nums1[k/2] < nums2[k/2]，则nums1的前k/2元素都不可能是第k大的数，因为至少有剩余的k个数以及nums2[k/2]共k+1个数比这k/2个数大，所以接下来只需要在nums1的剩余数和nums2全部数中找第k-k/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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n & 1) {
            return findKth(nums1, 0, nums2, 0, (n + 1) / 2);
        } else {
            return (findKth(nums1, 0, nums2, 0, n / 2) + findKth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
        }
    }

    double findKth(const vector<int> &nums1, int s1, const vector<int> &nums2, int s2, int k) {
        if (s1 >= nums1.size()) return nums2[s2 + k - 1];
        if (s2 >= nums2.size()) return nums1[s1 + k - 1];
        if (k == 1) return min(nums1[s1], nums2[s2]);
        int i1 = s1 + k / 2 - 1, i2 = s2 + k / 2 - 1;
        int e1 = i1 >= nums1.size() ? INT_MAX : nums1[i1];
        int e2 = i2 >= nums2.size() ? INT_MAX : nums2[i2];
        if (e1 < e2) {
            return findKth(nums1, s1 + k / 2, nums2, s2, k - k / 2);
        } else {
            return findKth(nums1, s1, nums2, s2 + k / 2, k - k / 2);
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n) 用hashmap维护下标
l表示上一个发生重复的位置

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        res, l = 0, -1
        for r, c in enumerate(s):
            l = max(l, d.get(c, -1))
            res = max(res, r - l)
            d[c] = r
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> f(256, -1);
        int n = s.length();
        int res = 0;
        for (int r = 0, l = -1; r < n; ++r) {
            l = max(l, f[s[r]]); // 更新l
            f[s[r]] = r; // 更新表
            res = max(res, r - l); // 更新res
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> hm(256, -1);
        int n = s.length();
        int start = -1;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            start = max(start, hm[s[i]]); // 一定要用max更新start，否则见反例abba
            hm[s[i]] = i;
            res = max(res, i - start);
        }
        return res;
    }
};

O(n) two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        bool hashmap[256] = {false};
        int n = s.length();
        int res = 0;
        for (int i = 0, j = i; i < n; ++i) {
            while (j < n && !hashmap[s[j]]) {
                hashmap[s[j++]] = true;
            }
            res = max(res, j - i);
            hashmap[s[i]] = false;
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

O(max(m, n)) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tail = dummy = ListNode(-1)
        c = 0
        while l1 or l2 or c:
            a = l1.val if l1 else 0
            b = l2.val if l2 else 0
            l1 = l1.next if l1 else l1
            l2 = l2.next if l2 else l2
            c, s = divmod(a + b + c, 10)
            tail.next = ListNode(s)
            tail = tail.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tail = dummy = ListNode(-1)
        c = 0
        while l1 or l2 or c != 0:
            a = l1.val if l1 else 0
            b = l2.val if l2 else 0
            l1 = l1.next if l1 else l1
            l2 = l2.next if l2 else l2
            s = a + b + c
            tail.next = ListNode(s % 10)
            tail = tail.next
            c = s // 10
        return dummy.next
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
/**
 * 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) {
        int c = 0;
        ListNode dummy_head(0), *tail = &dummy_head;
        while (l1 || l2 || c > 0) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
            int s = a + b + c;
            tail->next = new ListNode(s % 10);
            tail = tail->next;
            c = s / 10;
        }
        return dummy_head.next;
    }
};
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
/**
 * 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) {
        int a = 0, b = 0, c = 0;
        ListNode *n1 = l1, *n2 = l2, dummy_head(-1), *t = &dummy_head;
        while (n1 || n2 || c > 0) {
            a = n1 ? n1->val : 0;
            b = n2 ? n2->val : 0;
            int s = a + b + c;
            t->next = new ListNode(s % 10);
            t = t->next;
            c = s / 10;
            n1 = n1 ? n1->next : n1;
            n2 = n2 ? n2->next : n2;
        }
        return dummy_head.next;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

hashmap O(n) time O(n) space

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, num in enumerate(nums):
            x = target - num
            if x in d:
                return [d[x], i]
            d[num] = i
        return [-1, -1]
1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            x = target - nums[i]
            if x in d:
                return [d[x], i]
            d[nums[i]] = i
        return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int x = target - nums[i];
            if (m.count(x)) {
                return {m[x], i};
            }
            m[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hm;
        for (int i = 0; i < n; ++i) {
            auto it = hm.find(target - nums[i]); // 为了解决数组中有相同数的问题，在每次插新数之前先进行查找，查找无果之后再插数，这样只需要扫描一遍即可
            if (it != hm.end()) {
                return {min(it->second, i), max(it->second, i)};
            }
            hm[nums[i]] = i;
        }
        return {-1, -1};
    }
};

Posted on Edited on In , Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins. 
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
class Widget {
public:
    Widget(Widget&& rhs)
    : name(std::move(rhs.name))
    , p(std::move(rhs.p)) {}

private:
    std::string name;
    std::shared_ptr<SomeDataStructure> p;
};

class Widget {
public:
    template<typename T>
    void setName(T&& newName) {
        name = std::forward<T>(newName);
    }
};

Widget makeWidget() {
    Widget w;
    ...
    return std::move(w); // DO NOT DO THIS!
}

Widget w1;
Widget w2 = std::move(w1); // w1 is "empty"
Widget &&w3 = std::move(w2); // w3 is an rvalue reference and an lvalue, no type deduction
void f(Widget &&w) {
  // modify w
}
f(w3); // compilation error! w3 is an lvalue
f(std::move(w3)); // Okay! modifying w inside f changes w3
Read more »