常见高频题

• 找出字符串 出现次数最多的字符且有几次(功夫小团子)

def collect(string1):
    dic = {}
    for i in set(string1):
        dic[i] = string1.count(i)
    for k, v in dic.items():
        if v == max(dic.values()):
            print(k,v)
 
if "__name__" == "__name__":
    string1 = "aaaabbbbbbccccccdd"
    collect(string1)

优化

def collect(string1):
    dic = {}
    max_number = -1
    for i in set(string1):
        dic[i] = string1.count(i)
        if max_number < string1.count(i):
            max_number = string1.count(i)
    for key , value in dic.items():
        if max(dic.value) == value:
            print(key, value)

• 括号匹配（宇宙）

  def check(string1):
      left = "{(["
      right = "})]"
      dic = dict(zip(left,right))
      list1 = []
      for i in string1:
          if i in left:
              list1.append(i)
          elif i in right:
              # 匹配  / 不匹配
              if list1 and dic[list1[-1]] == i:
                  list1.pop()
              else:
                  return False
      return len(list1) == 0
  string1 = "{}{}{}[]"
  print(check(string1))
  

二分查找

def binary_search_1(alist,item):
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last) // 2
        if alist[mid] == item:
            return True
        elif alist[mid] < item:
            first = mid + 1
        else:
            last = mid - 1
    return False

• 最大回文数

class Solution:
    def longestPalindrome(self, s):
        if (len(s) < 2):
            return s
        start = 0  #记录最长回文子串开始的位置
        maxLen = 0 #记录最长回文子串的长度
        for i in range(len(s) - 1):
            for j in range(i,len(s)):#j从i开始，不从i+1开始，s=‘ac’就能选第一个‘a’
                # 法一：截取所有子串，然后在逐个判断是否是回文的
                # 法二（优化）：截取所有子串，如果截取的子串小于等于之前遍历过的最大回文串，直接跳过。
                          # 因为截取的子串即使是回文串也不可能是最大的，所以不需要判断
                if (j - i < maxLen):
                    continue
                if self.isPalindrome(s, i, j) and  (maxLen < j - i + 1):
                # maxLen为最大长度时，后面maxLen<j-i+1 就为False,能保证截取最长回文字符串
                    start = i
                    maxLen = j - i + 1
        return s[start:start + maxLen]
 
    # 判断是否是回文串
    def isPalindrome(self,s,start,end):
        while (start < end) :
            if s[start] != s[end]:
                 return False
            start += 1
            end -= 1
        return True
 
s =   "ac"
S = Solution()
result = S.longestPalindrome(s)
print(result)