정사각형 2차 배열의 소용돌이 모양 획득 방법!
11620 단어 알고리즘과 데이터 구조Python
1. 시작
안녕하세요, 처음 뵙겠습니다!
저는 지금 대학에서 소프트웨어 공학을 전공하고 있는 모나방입니다.
읽기에 앞서 코드보다는 독자들이 사고방식을 참고로 읽기를 바란다.
갑작스럽지만 배열의 흐름에 곤혹스러우신가요?
그건 알아!이렇게 토할 수도 있으니 조금만 더 읽어주세요.
그렇다면 바늘로 정사각형의 배열을 소용돌이 모양으로 움직이는 방법을 아십니까?
자세히 설명해 주세요.
메시지
그럼 바로 본론으로 들어가겠습니다.
정사각형의 2차 배열이 존재한다고 가정하다.
예제
array_traversal.py
array = [
[1, 2, 3, 4]
[12, 13, 14, 5]
[11, 16, 15, 6]
[10, 9, 8, 7]
]
이 세로 x 가로의 2차 배열을 소용돌이 모양으로 하여 하나하나의 요소를 통해 1차 배열을 얻으십시오.(시간 계산은 O(n))
출력 예[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
생각
일단 생각부터.
1. 시선을 조금 바꿔보자
첫 번째 그림:
첫 번째 이미지 보시면 이해하기 쉬울 거예요.
소용돌이 모양으로 얻었지만 거기서 시각을 조금 바꿔서 문제를 처리하면
바깥쪽의 사각과 안쪽의 사각으로 나눌 수 있다.
그렇게 보면 조금 덜 복잡해요.맞죠?
다음에 이 네 귀퉁이를 돌면서 두 개의 바늘(촛불과 열에 사용)을 고려해 보세요.
이곳의 지침은 간단하게 말하면 지시 처리를 위한 것이다컴퓨터에 전달되는 것으로 이해해 주세요.
이 두 바늘을 소용돌이 모양으로 만들기 위한 고려점이 있다.
그것은 이중 계산의 제어다.
보충:
여기서 밀랍은 횡열을 가리키고 열은 종열을 가리킨다.
반복 계산(double counting)은 간단하게 말하면 처리할 때 같은 요소에 덮어씌운다.
2. 이중 추출 제어
아래 그림을 보십시오.
두 번째:
이렇게 하면 쌍방이 모두 경계선을 그을 수 있을 뿐만 아니라 중복 계산도 방지할 수 있기 때문에 나는 이것이 일종의 효율적인 해법이라고 생각한다
*SC, EC, SR, ER란??
SC 열이 시작되고 EC 열이 끝납니다.
SR 시작은 라, ER 끝은 라.
그렇습니다.
3. 일련의 처리 프로세스(외부)
그럼 마지막으로 준비된 곳에서 절차를 설명하겠습니다.
3.1 열의 포인터를 통해 최상위 수준 가져오기([1,2,3,4])
이곳은 평소에 사용하던 forloop 방법으로 할 수 있다.
샘플 코드: for col in range(sc, ec + 1):
result.append(array[sr][col])
3.2 촛불의 바늘로 EC가 가리키는 열을 ER로 가져온다.(이곳은 [5,6,7]이지.)
샘플 코드: for row in range(sr + 1, er + 1):
result.append(array[row][ec])
3.3 열의 바늘을 통해 밑에 있는 촛불을 반대로 가져온다([10,9,8]).
여기에는 Reverse라는 built-in function을 사용하여 역방향 for loop을 실현합니다.
샘플 코드: for col in reversed(range(sc, ec)):
result.append(array[er][col])
3.4 마지막으로 두 번째 줄의 [12]와 세 번째 줄의 [11]를 얻으려고 하기 때문에 SR+1~ER 구간에서 마우스 포인터로 역방향으로 얻는다.
여기도 Reverse를 사용합니다.
샘플 코드: for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
이렇게 해서 마침내 바깥쪽의 사각형 요소를 모두 소용돌이 모양으로 만들었다.
4. 일련의 처리 프로세스(내부)
다음은 안쪽의 사각형.
하지만 이렇게 처리하면 하드 코드가 되겠죠?
따라서 SR과 SC를 합쳐 안쪽으로 접근한다.또 EC와 ER를 합쳐 안쪽에 접근함으로써 1∼5로 만든 제품을 재활용할 수 있다!에코죠~ 웃어요#内側の正方形の処理
sr += 1
er -= 1
sc += 1
ec -= 1
다음은 이미지와 코드에 대한 설명을 생략합니다.
array = [
[1, 2, 3, 4]
[12, 13, 14, 5]
[11, 16, 15, 6]
[10, 9, 8, 7]
]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
for col in range(sc, ec + 1):
result.append(array[sr][col])
for row in range(sr + 1, er + 1):
result.append(array[row][ec])
for col in reversed(range(sc, ec)):
result.append(array[er][col])
for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
#内側の正方形の処理
sr += 1
er -= 1
sc += 1
ec -= 1
이것도 마찬가지로 평소에 사용되는 forloop 방법으로 할 수 있다.
여기에는 Reverse라는 built-in function을 사용하여 역방향 for loop을 실현합니다.
완료 코드
array_traversal.py
def spiralTraverse(array):
result = []
sr, er = 0, len(array) - 1
sc, ec = 0, len(array[0]) - 1
while sr <= er and sc <= ec:
for col in range(sc, ec + 1):
result.append(array[sr][col])
for row in range(sr + 1, er + 1):
result.append(array[row][ec])
for col in reversed(range(sc, ec)):
result.append(array[er][col])
for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
sr += 1
er -= 1
sc += 1
ec -= 1
return result
끝맺다
결국, 이것은 단지 하나의 생각일 뿐, 다른 많은 해답 방법이 있다.예를 들어 회귀법의 처리 등을 사용한다.
주의점으로 여기는 가장자리 상황을 고려하지 않았기 때문에 문제에 협조하여 처리해 주십시오.
길어졌지만 이게 다야!수고하셨습니다!
잘 부탁드립니다!
Reference
이 문제에 관하여(정사각형 2차 배열의 소용돌이 모양 획득 방법!), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/daikidev111/items/eb376ce10891e62fa0c9
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def spiralTraverse(array):
result = []
sr, er = 0, len(array) - 1
sc, ec = 0, len(array[0]) - 1
while sr <= er and sc <= ec:
for col in range(sc, ec + 1):
result.append(array[sr][col])
for row in range(sr + 1, er + 1):
result.append(array[row][ec])
for col in reversed(range(sc, ec)):
result.append(array[er][col])
for row in reversed(range(sr + 1, er)):
result.append(array[row][sr])
sr += 1
er -= 1
sc += 1
ec -= 1
return result
Reference
이 문제에 관하여(정사각형 2차 배열의 소용돌이 모양 획득 방법!), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/daikidev111/items/eb376ce10891e62fa0c9텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)