9/2練習

a224: 明明愛明明

題目:輸入字串，無視英文字母(大小寫視為同一)和數字以外的字元，若能改寫成為回文則輸出yes否則輸出no。

思路:先轉成小寫，再來運用ASCII碼檢查非字母、數字的元素(沒寫得很好，若ASCII剛好在57~97之間有BUG)。
          然後進入判斷式，若奇數的值>1則無法構成回文，如ab就不是回文，最後輸出。

        while True:
          try:
              a=input().lower()
              a=''.join(sorted(a))
              while ord(a[0])<97:
                  if ord(a[0])>=48 and ord(a[0])<=57:
                      break
                  else:
                      a=a.replace(a[0],'')
                      if len(a) == 0:
                          print("no...")
              count = 0  # 紀錄奇數有沒有超過2
              while len(a)>0:
                  if a.count(a[0])%2==0:
                      a=a.replace(a[0],'')
                  else:
                      count+=1
                      a = a.replace(a[0], '')
              if count>1:
                  print("no...")
              else:print('yes !')
          except:
              break

a225: 明明愛排列

題目:輸入以空白分開數列，要求輸出先以個位數由小到大排序，其中同個位數分別由大到小排序。

思路:直接spilit後先以個位數大小作排列，再來建立暫存區和答案區，如果後一位數字個位數一樣大就一起放入暫存區，直到不滿足時排列暫存區。
          排列完暫存區之後將暫存區加入答案區並清空，最後輸出答案區。(後來發現不用這麼麻煩，先排列大小一次在排列個位數就好，但還是把第一次思考過程放上來參考。)

        while True:
          try:
              k=input() #沒用
              a=input().split()
              b=sorted(a, key=lambda x:x[-1])
              temptlist=[]
              finallist=[]
              for i in range(len(b)):
                  if i==0 or b[i][-1]==b[i-1][-1]:
                      temptlist.append(b[i])
                  else:
                      finallist.append(sorted(temptlist,key=lambda x:int(x),reverse=True))
                      temptlist=[]
                      temptlist.append(b[i])
              finallist.append(sorted(temptlist,key=lambda x:int(x),reverse=True))
              for ans in finallist:
                  if len(ans)>1:
                      for anschild in ans:
                          print(anschild,end=' ')
                  else:print(ans[0],end=' ')
              print()
          except:
              break

a229: 括號匹配問題

題目:經典問題...吧?詳見此

思路:原本自己的寫法是窮舉括號(利用二進制輸出0、1)然後消去不滿足規則的括號後輸出，但速度超慢。
          優化過兩到三次仍遠遠不足，最後沒辦法轉而搜尋演算法，才發現這題完全適合用dfs解。假設有n個括號，令left代表左括號//right代表右括號。
          n==left==right，path則記錄每一次分支的路徑，res輸出答案。第一個函式呼叫答案，再來第二個函式慢慢深入:
          若左括號>0就在path寫入左括號->左括號仍大於0再寫入、同時左括號小於右括號，則path寫入右括號。如此反覆就能保證每個括號都符合規則。
          最後依輸出規則進行排序，十分的快速。

      class Solution:
          def Parent(self, n):
              res = []
              self.dfs(res, n, n, '')
              return res
          def dfs(self, res, left, right, path):
              if left==right==0:
                  res.append(path)
                  return
              if left>0:
                  self.dfs(res,left-1,right,path+'(')
              if left<right:
                  self.dfs(res,left,right-1,path+')')
      while True:
          try:
              x=Solution()
              anslist=x.Parent(n=int(input()))
              for ans in anslist:
                  print(ans)
          except:
              break

arrow_circle_left home arrow_circle_right