头像

CE自动机


访客:3361

离线:1天前



class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)


活动打卡代码 LeetCode 9. 回文数

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;

        int renum = 0;
        while (x > renum) 
        {
            renum = renum * 10 + x % 10;
            x /= 10;
        }

        return x == renum || x == renum / 10;
    }
};



class Solution(object):
    def myAtoi(self, str):
        return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)


活动打卡代码 LeetCode 7. 整数反转

class Solution {
public:
    int reverse(int x) {
    int  res = 0;     

    while(x != 0)          
    {
        if(res > INT_MAX / 10) 
            return 0;        
        if(res < INT_MIN / 10) 
            return 0;                  
        res = 10 * res + x % 10;   
        x /= 10;         
    }
    return res;
    }
};



class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int N1 = nums1.size(), N2 = nums2.size();
        if (N1 < N2) return findMedianSortedArrays(nums2, nums1);

        int lo = 0, hi = N2 * 2;
        while (lo <= hi) 
        {
            int mid2 = (lo + hi) / 2;
            int mid1 = N1 + N2 - mid2;

            double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];
            double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
            double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
            double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];

            if (L1 > R2) lo = mid2 + 1;
            else if (L2 > R1) hi = mid2 - 1;
            else return (max(L1,L2) + min(R1, R2)) / 2;
        }
        return -1;
    }
};


活动打卡代码 LeetCode 6. Z 字形变换

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if (numRows == 1) return s;
        for (int j = 0; j < numRows; ++j)
        {
            if (j == 0 || j == numRows - 1)
                for (int i = j; i < s.size(); i += (numRows-1) * 2) res += s[i];
            else
            {
                for (int k = j, i = numRows * 2 - 1 - j - 1;
                        i < s.size() || k < s.size();
                        i += (numRows - 1) * 2, k += (numRows - 1) * 2)
                {
                    if (k < s.size()) res += s[k];
                    if (i < s.size()) res += s[i];
                }
            }
        }
        return res;    
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int res = 0;
        string str;
        for (int i = 0; i < s.size(); ++i)
        {
            for (int j = 0; i - j >= 0 && i + j < s.size(); ++j)
                if (s[i - j] == s[i + j])
                {
                    if (j * 2 + 1 > res)
                    {
                        res = 2 * j + 1;
                        str = s.substr(i - j, j * 2 + 1);
                    }
                }
                else break;

            for (int j = i, k = i + 1; j >= 0 && k < s.size(); --j, ++k)
                if (s[j] == s[k])
                {
                    if (k - j + 1 > res) 
                    {
                        res = k - j + 1;
                        str = s.substr(j, k - j + 1);
                    }
                }
                else break;
        }
        return str;
    }
};



class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int res = 0;
        for (int i = 0, j = 0; j < s.size(); ++j) {
            ++mp[s[j]];
            while (mp[s[j]] > 1) mp[s[i++]]--;
            res = max(res, j - i + 1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 2. 两数相加

/**
 * 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) {
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        int carry = 0;
        while (l1 || l2)
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1); 
        return dummy->next;
    }
};


活动打卡代码 LeetCode 1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        int len = nums.size();
        for (int i = 0; i < len; ++i)
        {
            int t = target - nums[i];
            if (hash.count(t))
                return vector<int>({hash[t], i});
            hash[nums[i]] = i;
        }
        return vector<int>();
    }
};