アルゴリズム(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)