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

最长无重复子字符串

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""if not s:return 0max_len = 0tp = []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 sysfor 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, 1nums.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 Truedef dfs(left, right):if not (left or right):return Trueif not (left and right):return Falseif left.val != right.val:return Falsereturn 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 Falseans = 0prior = xwhile x > 0:temp = x % 10ans = ans * 10 + tempx //= 10return ans == prior# ACM模式输入输出处理
if __name__ == "__main__":import sysfor 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 sres = ""for i in range(len(s)):# 奇数长度回文l, r = i, iwhile l >= 0 and r < len(s) and s[l] == s[r]:if r - l + 1 > len(res):res = s[l:r+1]l -= 1r += 1# 偶数长度回文l, r = i, i+1while l >= 0 and r < len(s) and s[l] == s[r]:if r - l + 1 > len(res):res = s[l:r+1]l -= 1r += 1return res# ACM模式输入输出处理
if __name__ == "__main__":import sysfor 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 = 0len_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 += 1return 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 = dummywhile list1 and list2:if list1.val < list2.val:cur.next = list1list1 = list1.nextelse:cur.next = list2list2 = list2.nextcur = cur.nextcur.next = list1 if list1 else list2return dummy.next

反转链表

class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""cur = headpre = Nonewhile cur is not None:temp = cur.nextcur.next = prepre = curcur = tempreturn pre

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

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

数组中出现最多的数字

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

滑动窗口

抖音电商测开