手撕算法（定制整理版2）

最长无重复子字符串

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        max_len = 0
        tp = []
        for a in s:
            while a in tp:
                del tp[0]
            tp.append(a)
            if len(tp) > max_len:
                max_len = len(tp)
        return max_len

# ACM模式输入输出处理
if __name__ == "__main__":
    import sys
    for line in sys.stdin:
        s = line.strip()
        sol = Solution()
        print(sol.lengthOfLongestSubstring(s))

把数组排成最小数，最大数，数组中的数组合出最大的数字

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        def compare(x, y):
            xy = str(x) + str(y)
            yx = str(y) + str(x)
            return (xy > yx) - (xy < yx)  # 返回 -1, 0, 1
        
        nums.sort(cmp=compare)
        if not nums or nums[0] == 0:
            return "0"
        return ''.join(map(str, nums))

对称的二叉树

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        if not root:
            return True
        def dfs(left, right):
            if not (left or right):
                return True
            if not (left and right):
                return False
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)

回文数

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        ans = 0
        prior = x
        while x > 0:
            temp = x % 10
            ans = ans * 10 + temp
            x //= 10
        return ans == prior

# ACM模式输入输出处理
if __name__ == "__main__":
    import sys
    for line in sys.stdin:
        # 处理输入：假设每行一个整数
        x = int(line.strip())
        sol = Solution()
        print(sol.isPalindrome(x))

最长回文子串

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
            
        res = ""
        for i in range(len(s)):
            # 奇数长度回文
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(res):
                    res = s[l:r+1]
                l -= 1
                r += 1
            
            # 偶数长度回文
            l, r = i, i+1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(res):
                    res = s[l:r+1]
                l -= 1
                r += 1
                
        return res

# ACM模式输入输出处理
if __name__ == "__main__":
    import sys
    for line in sys.stdin:
        s = line.strip()
        sol = Solution()
        print(sol.longestPalindrome(s))

子字符串在原字符串中出现的次数

def count_substring(string, sub_string):
    """
    :type string: str
    :type sub_string: str
    :rtype: int
    """
    count = 0
    len_sub = len(sub_string)
    len_str = len(string)
    
    for i in xrange(len_str - len_sub + 1):
        if string[i:i+len_sub] == sub_string:
            count += 1
    return count

合并区间

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key=lambda x: x[0])

        merged= []

        for interval in intervals:
            if not merged or merged[-1][1] <interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1],interval[1])
        
        return merged

合并两个有序链表

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next

反转链表

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        pre = None
        while cur is not None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

数组找出乘积为n的两个数

写个函数来校验两个二叉树是否相同，要结构和值都相同

数组中出现最多的数字

def find_most_frequent(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return None
    
    count_dict = {}
    max_count = 0
    result = nums[0]
    
    for num in nums:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1
            
        if count_dict[num] > max_count:
            max_count = count_dict[num]
            result = num
        elif count_dict[num] == max_count:
            # 如果出现次数相同，返回数值较小的
            result = min(result, num)
            
    return result

滑动窗口

抖音电商测开