アルゴリズム(Python)


文字列タイプ


特定の長さを重複配列で塗りつぶす


私の接近

p = [1,2,3,4,5]
length = 9

m = length//len(p[s])
n = length%len(p[s])

if m > 0:
    lst = p[s]
    for _ in range(m-1):
        lst += p[s]

    # last_lst = [0 for _ in range(n)]
    # for i in range(n):
    #     last_lst[i] = p[s][i]

    last_lst = p[s][:n]

    all_lst = lst + last_lst
    # print(all_lst)
else:
    all_lst = [0 for _ in range(length)]
    for i in range(length):
        all_lst[i] = p[s][i]
シェア=塗りつぶしが必要な長さ//パターンの長さ
残り=充填長%アレイ長
繰り返しパターンプラス記号+残りの長さでパターンを切り取る
->最終リストの完了

私の解決

m = length // len(p[s])
n = length % len(p[s])

if m > 0:
    all_lst = p[s] * m + p[s][:n]
else:
    all_lst = p[s][:length]

他の人を解決する

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

  • 1%5=1部=0、残り=1

  • 答えの索引%パターン長->答えの索引に一致するパターンの索引
  • 複数の特定の値がある場合のインデックス値の決定

    result = []
    for idx, val in enumerate(lst):
    	if val==max(lst):
        	result.append(idx)

    dfs、bfsタイプ


    二重リストを使用してgridにアクセスまたは作成する場合
    visited = [[False]*3]*3 
  • 上記のように、3 x 3メッシュへのアクセスアレイを作成してはならない.
  • [1,2,3]* 3リスト内要素を3回繰り返し、リストに数字が含まれていなければ1つのリストを変更し、他のリストも変更します.リストの浅いコピーと深いコピーの違いのためかもしれません.
  • そのため、以下のリストがコピーされないようにする.
  • visited = [[False]*3 for _ in range(3)]
    
    visited = [[False for _ in range(3)] for _ in range(3)]

    dfs

    # dfs 문제 구현
    
    # N, M을 공백을 기준으로 구분하여 입력 받기
    n, m = map(int, input().split())
    
    # 2차원 리스트의 맵 정보 입력 받기
    grid = []
    for i in range(n):
        grid.append(list(map(int, input())))
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    
    def dfs(x, y):
        if grid[x][y] == 0:
            grid[x][y] = 1
    
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
    
                if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                    continue
                elif grid[nx][ny] == 1:
                    continue
    
                else:
                    dfs(nx, ny)
            return True
    
        else:
            return False
    
    cnt = 0
    for i in range(n):
        for j in range(m):
            if dfs(i, j) == True:
                print(i, j)
                cnt += 1
    print(cnt)
  • 最初に入れた座標から、すべてのループが終了したとき(すべての再帰関数を実行した後)にTrueを返すのがコアです.
  • 座標から離れる範囲の設定に注意
  • 再帰関数の関数の戻り値にかかわらず、最後の再帰関数の戻り値を考慮すればよい.
  • else return falseしなくても大丈夫.
  • bfs

    # 최단거리 미로
    
    from collections import deque
    
    # N, M을 공백을 기준으로 구분하여 입력 받기
    n, m = map(int, input().split())
    
    # 2차원 리스트의 맵 정보 입력 받기
    grid = []
    for i in range(n):
        grid.append(list(map(int, input())))
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    visited = [[False for _ in range(m)] for _ in range(n)]
    def bfs(x, y):
        queue = deque([(x, y)])
        visited[x][y] = True
        while queue:
            x, y = queue.popleft()
            if (x, y) == (n-1, m-1):
                break
            print((x,y))
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
    
                if nx<0 or nx>(n-1) or ny<0 or ny>(m-1):
                    continue
                elif grid[nx][ny] == 0:
                    continue
                else:
                    if visited[nx][ny] == True:
                        print('a')
                        if grid[x][y]+1 < grid[nx][ny]:
                            grid[nx][ny] = grid[x][y]+1
    
                    else:
                        print('b')
                        grid[nx][ny] = grid[x][y]+1
                    queue.append((nx, ny))
                    visited[nx][ny] = True
    bfs(0,0)
    print(grid)
    print(grid[n-1][m-1])
  • ダライストラスが無理に解けたので、ちょっと難しかったです.
    複数の書き込みが必要なため、このノードに初めてアクセスする場合は、再アクセス時に分けて処理する必要があります.
  • bfs自体は、先頭ノードから一歩一歩ノードに近い順に巡回しているため、初回アクセス時には最短経路となる.
  • 従って、下図のように、初回アクセス時の経路長のみを反映した形で、より容易になる.
  • from collections import deque
    
    # N, M을 공백을 기준으로 구분하여 입력 받기
    n, m = map(int, input().split())
    # 2차원 리스트의 맵 정보 입력 받기
    graph = []
    for i in range(n):
        graph.append(list(map(int, input())))
    
    # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # BFS 소스코드 구현
    def bfs(x, y):
        # 큐(Queue) 구현을 위해 deque 라이브러리 사용
        queue = deque()
        queue.append((x, y))
        # 큐가 빌 때까지 반복하기
        while queue:
            x, y = queue.popleft()
            # 현재 위치에서 4가지 방향으로의 위치 확인
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 미로 찾기 공간을 벗어난 경우 무시
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                # 벽인 경우 무시
                if graph[nx][ny] == 0:
                    continue
                # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
        # 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1]
    
    # BFS를 수행한 결과 출력
    print(bfs(0, 0))

    実装タイプ


    イコールのゲーム問題
    ひょうじゅんもんだい

    このコセットの本を読むときのコード


    この可愛いアイデアをちょっと見て書いたコード
    n, m = map(int,input().split())
    x, y, p = map(int, input().split())
    
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))
    
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[x][y] = True
    def move(x, y, p):
        mcnt = 0
        while True:
            fcnt = 0
            for i in range(4):
                print('x,y', (x, y))
                print('i', i)
                if p == 0:
                    np = 3
                else:
                    np = p - 1
    
                nx = x + dx[np]
                ny = y + dy[np]
    			
                # 맵은 어차피 벽으로 사면이 둘러쌓여 있어서 a는 사실 불필요
                a = (nx<0 or nx>(n-1) or ny<0 or ny>(m-1))
                # 방문한 격자라면
                b = (visited[nx][ny] == True)
                # 벽이라면
                c = (grid[nx][ny]==1)
    
                if a or b or c:
                    p = np # 방향만 바꾸고
                    fcnt += 1 
                else:
                    x = nx
                    y = ny # 위치 바꾸고
                    p = np # 방향 바꾸고
                    visited[x][y] = True
                    mcnt += 1
                    break # 옮겨갔으니까 break
            if fcnt==4:
                if grid[x-dx[p]][y-dy[p]] == 1:
                    print(visited)
                    return mcnt
                x -= dx[p]
                y -= dy[p]
    
    print(move(x, y, p))

  • この方向に向かって進んだ時x + dx[i]後ろへx - dx[i]

  • 問題の実施は問題の理解にとって極めて重要である.

  • 私たちは頭の中ですべての状況をシミュレートしなければなりません.

  • 白俊を置いてもう一度見ると、このテストボックスだけが合格した.

  • ノードへの最初のアクセスを忘れないでください

  • flag処理が不要なのは,上のコードで方向変化の回数(fcnt)のみを計算したためである.
  • 記憶がリセットされて白俊問題を解くコード。

    n, m = map(int, input().split())
    x, y, pos = map(int, input().split())
    
    grid = []
    for _ in range(n):
        grid.append(list(map(int,input().split())))
    visited = [[False for _ in range(m)] for _ in range(n)]
    cnt = 1
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    visited[x][y] = True
    
    while True:
        for i in range(4):
            flag = False
            if pos == 0:
                pos = 3
            else:
                pos -= 1
    
            nx = x + dx[pos]
            ny = y + dy[pos]
    		
            # 움직일 수 있는 조건이라면
            if grid[nx][ny] != 1 and visited[nx][ny]!=True:
                visited[nx][ny] = True
                x = nx
                y = ny
                cnt += 1
                flag = True # 4번 돌았지만 위치를 옮긴 상황을 기록
                break
        if i == 3:
            if flag==True:
                continue
            elif grid[x-dx[pos]][y-dy[pos]] == 1:
                break
            else:
                x -= dx[pos]
                y -= dy[pos]
    print(cnt)
  • forゲートは4回カーブしていますが、最終方向に移動する可能性があるのでflagで考えてもいいです
  • 最初のノードアクセス処理&最初のノードを考慮してcnt 1から注意
  • カタツムリ問題

  • 実施問題
  • 座標移動のみを操作する概念
  • 三角形ではなくnxnアレイと考えるとインデックスの方が簡単
  • 特定の方向に1回回転するごとにその段階の個数が1つ減る
  • リファレンス
  • n = 5
    grid = [[-1 for _ in range(n)]  for _ in range(n)]
    x = -1
    y = n
    num = 0
    for i in range(n):
        for j in range(n-i):
            if i%3==0:
                x += 1
                y -= 1
            elif i%3==1:
                x -= 1
            elif i %3 == 2:
                y += 1
            num += 1
            grid[x][y] = num
    
    # print(grid)
    for i in grid:
        print(i)