<jupyter_start><jupyter_text>leetcode [815] 公交路线<jupyter_code>from collections import defaultdict
routes = [[1,2,7],[3,6,7]]
source = 1
target = 6<jupyter_output><empty_output><jupyter_text>单向BFS<jupyter_code>def numBusesToDestination(routes, source, target):
    if source == target:
        return 0 
    stations = defaultdict(set)
    for i,stops in enumerate(routes):
        for stop in stops:
            stations[stop].add(i)
    
    routes = [set(x) for x in routes]


    q = [(source,0)]
    buses = set()
    stops = {source}

    while q:
        curstop,cost = q.pop(0)

        if curstop == target:
            return cost 

        for bus in stations[curstop] - buses:
            for stop in routes[bus] - stops:
                buses.add(bus)
                stops.add(stop)
                q.append((stop,cost+1))
        
    return -1 


numBusesToDestination(routes,source,target)<jupyter_output><empty_output><jupyter_text>双向BFS<jupyter_code>def numBusesToDestination2(routes, source, target):
    if source == target:
        return 0 
    
    routes = [set(x) for x in routes]

    stations = defaultdict(set)

    for i,stops in enumerate(routes):
        for stop in stops:
            stations[stop].add(i)

    buses = set()
    stops = {source}
    cost = 0 

    front = {source}
    back = {target}


    while front and back:
        nexstops = set() 

        for curstop in front:
            for curbus in stations[curstop] - buses:
                for targetstop in back:
                    if curbus in stations[targetstop]:
                        return cost + 1 
                buses.add(curbus)
                for nexstop in routes[curbus] - stops:
                    
                    stops.add(nexstop)
                    nexstops.add(nexstop)
            
        cost += 1 
        front = back 
        back = nexstops 
    return -1 
numBusesToDestination2(routes,source,target)<jupyter_output><empty_output><jupyter_text>leetcode [767] 重构字符串<jupyter_code>from collections import Counter 
import heapq
def reorganizeString(s):
    if not s:
        return True 
    n = len(s)
    count = Counter(s)

    maxcount = max(count.items(),key=lambda x:x[1])[1]

    if maxcount > (n+1)//2:
        return ''

    q = [(-x[1],x[0]) for x in count.items()]
    heapq.heapify(q)
    ans = []

    while len(q) > 1:
        letter1 = heapq.heappop(q)[1]
        letter2 = heapq.heappop(q)[1]
        ans.extend([letter1,letter2])
        count[letter1] -= 1 
        count[letter2] -= 1
        if count[letter1] > 0:
            heapq.heappush(q,(-count[letter1],letter1))
        if count[letter2]> 0:
            heapq.heappush(q,(-count[letter2],letter2))
    if q:
        ans.append(q[0][1])

    return "".join(ans)

s = "aaaaaabbbbbbcccccc"
reorganizeString(s)<jupyter_output><empty_output><jupyter_text>字节面经data = [  {    "id": "1",    "sub": [      {        "id": "2",        "sub": [          {            "id": "3",            "sub": null          },          {            "id": "4",            "sub": [              {                "id": "6",                "sub": null              }            ]          },          {            "id": "5",            "sub": null          }        ]      }    ]  },  {    "id": "7",    "sub": [      {        "id": "8",        "sub": [          {            "id": "9",            "sub": null          }        ]      }    ]  },  {    "id": "10",    "sub": null  }]现在给定一个id，要求实现一个函数 findPath(data, id) { }返回给定id在 data 里的路径示例: id = "1" => ["1"]id = "9" => ["7", "8", "9"]id = "100"=> []PS: id 全局唯一，无序链接：https://www.nowcoder.com/discuss/676425?type=2&channel=-1&source_id=discuss_terminal_discuss_hot_nctrack<jupyter_code>data = [ { "id": "1", "sub": [ { "id": "2", "sub": [ { "id": "3", "sub": None }, { "id": "4", "sub": { "id": "6", "sub": None } }, { "id": "5", "sub": None } ] } ] }, { "id": "7", "sub": [ { "id": "8", "sub": { "id": "9", "sub":None } } ] }, { "id": "10", "sub": None } ]
data
def findPath(data,id,path):

    if not data:
        return 
    print(f'data:{data}')
    if type(data) == dict:
        path += data['id']
        print(f"data是dict,find id:{id}, path:{path}")
        if data['id'] == id:
            res = path[:]
            return res
    else:
        for i in range(len(data)):
            path += data[i]['id']
            if data[i]['id'] == id:
                print(f"data是list, find id:{id}, path:{path}")
                return path 
        
            print(f'path:{path}')
            # if not data[i]['sub']:
            #     return 
            

            
            findPath(data[i]['sub'],id,path)
            path = path[:-1]
        return path<jupyter_output>data:[{'id': '1', 'sub': [{'id': '2', 'sub': [{'id': '3', 'sub': None}, {'id': '4', 'sub': {'id': '6', 'sub': None}}, {'id': '5', 'sub': None}]}]}, {'id': '7', 'sub': [{'id': '8', 'sub': {'id': '9', 'sub': None}}]}, {'id': '10', 'sub': None}]
path:1
data:[{'id': '2', 'sub': [{'id': '3', 'sub': None}, {'id': '4', 'sub': {'id': '6', 'sub': None}}, {'id': '5', 'sub': None}]}]
path:12
data:[{'id': '3', 'sub': None}, {'id': '4', 'sub': {'id': '6', 'sub': None}}, {'id': '5', 'sub': None}]
path:123
path:124
data:{'id': '6', 'sub': None}
data是dict,find id:100, path:1246
path:125
path:7
data:[{'id': '8', 'sub': {'id': '9', 'sub': None}}]
path:78
data:{'id': '9', 'sub': None}
data是dict,find id:100, path:789
path:10<jupyter_text>剑指 Offer 38. 字符串的排列<jupyter_code>def permutation(s) :
    if not s:
        return s 
    n = len(s)
    res = []
    path = ''
    visited = [0]*n 
    s = sorted(s)
    def backtrack(s,path):
        if len(path)== len(s):
            path = path[:]
            res.append(path)
        
        for i in range(n):
            if visited[i] or (i > 0 and not visited[i-1] and s[i] == s[i-1]):
                continue 
            path += s[i]
            visited[i] = True 
            backtrack(s,path)
            path = path[:-1]
            visited[i] = False 
    
    
    backtrack(s,path)
    return res 
permutation('abc')
def permutation(s):
    if len(s) <= 1:
        return [s] 
    n = len(s)
    res = []
    for i in range(n):
        cur = s[i]
        nex = permutation(s[:i]+s[i+1:])
        for item in nex:
            res.append(cur+item)

    return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18562214881233285, 'fraction_numerical': 0.024539877300613498, 'mean_word_length': 1.9125057260650482, 'pattern_counts': {'":': 40, '<': 25, '<?xml version=': 0, '>': 32, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '267864', 'license': 'MIT', 'n_tokens_mistral': 2392, 'n_tokens_neox': 2299, 'n_words': 517, 'path': '每日刷题/2021/06/20210629.ipynb', 'repo_name': 'ZhengyangXu/Algorithm-Daily-Practice', 'size': '6357'}