目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:

S 只包含小写字母并且长度在[1, 500]区间内。

二、解题思路

1.对S中的字母构建数组哈希表，统计各个字符出现的次数；

2.将出现次数最多的字符，添加至res结果字符串，并且次数减一；

3.每次循环都去找当前出现次数最多，并且和上一个添加进res中不同的字符，插入到结果字符串后；

4.如果找不到这样的字符，就返回“”空字符串

注：若想得到相邻这样的关系，只有字母出现次数多的相邻，否则只能一个挨着一个都是一样的字母了。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def reorganizeString(self, S: str) -> str:
     
    
   

    

     

    
    

     

       record = [0 for _ in range(26)]
     
    
   

    

     

    
    

     
 for i in range(len(S)):
     
    
   

    

     

    
    

     

       record[ord(S[i]) - ord('a')] += 1
     
    
   

    

     

    
    

     

       max_record = max(record)
     
    
   

    

     

    
    

     

       max_record_index = record.index(max_record)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     

       res.append(chr(ord('a') + max_record_index))
     
    
   

    

     

    
    

     

       record[max_record_index] -= 1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while len(res) < len(S):
     
    
   

    

     

    
    

     

       next_max_record_index = -1
     
    
   

    

     

    
    

     

       max_record = 0
     
    
   

    

     

    
    

     
 for i in range(26):
     
    
   

    

     

    
    

     
 if record[i] > max_record and i != max_record_index:
     
    
   

    

     

    
    

     

       max_record = record[i]
     
    
   

    

     

    
    

     

       next_max_record_index = i
     
    
   

    

     

    
    

     
 if next_max_record_index != -1:
     
    
   

    

     

    
    

     

       res.append(chr(ord('a') + next_max_record_index))
     
    
   

    

     

    
    

     

       record[next_max_record_index] -= 1
     
    
   

    

     

    
    

     

       max_record_index = next_max_record_index
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     
 return ""
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return "".join(res)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       a = "aaab"
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.reorganizeString(a)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110384725