스냅 연습 - 두 수의 합 (python 언어)

문제 설명

사고방식과 제시

개인적인 사고방식

공식 알림

코드 및 설명

코드

작성 과정(여기는 학습 과정)

요약

코드 최적화

참조 코드

에서 배운 문장

1.enumerate 함수

2.permutations 함수

3.combinations 함수

공책에 적는 것보다 필기를 인터넷에 기록하는 것이 더 편리하다는 것을 문득 발견하고 작은 시도를 한 번 기록했다.

문제 설명

정수 그룹nums와 목표 값 target을 지정합니다. 이 그룹에서 목표 값과 두 개의 정수를 찾아내고 그 그룹의 하표를 되돌려 주십시오.
너는 모든 입력이 단지 하나의 답안에만 대응할 것이라고 가정할 수 있다.그러나 이 수조에서 같은 원소를 반복해서 이용할 수는 없다.
예:
주어진nums=[2,7,11,15], target=9은nums[0]+nums[1]=2+7=9이므로 [0,1]
출처: 리코더 링크:https://leetcode-cn.com/problems/two-sum

사고의 방향과 제시

개인적 사고방식

주어진 목록에서 순서대로 놓지 않은 숫자를 꺼내고, 이 숫자를 새 목록 (mirror) 에 저장하고, target에서 이 숫자를 빼서, 차액이 주어진 목록에 있는지 확인하십시오.만약에mirror에 차치도 저장하고 이 두 값이 주어진 목록에 있는 위치를 찾아 출력한다.만약 없으면mirror의 숫자를 팝업하고 다음 숫자를 계속합니다.두루 돌아다니는 방법에 해당한다.

정부측 제시

1.A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
2.So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x, where value is the input parameter. Can we change our array somehow so that this search becomes faster?
3.The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
총괄: 앞의 두 가지는 해결 방법으로 아마도 나 개인의 사고방식과 일치할 것이다.세 번째 해시맵은 아직 무슨 뜻인지...

코드 및 설명

코드

class Solution(object):
    def twoSum(self, nums, target):
        twopos=[]
        mirror=nums[:]
        for i in nums:
            mirror.remove(i)
            twopos.append(i)
            x=target-i
            if x in mirror :
                twopos.append(x)
                if len(set(nums)) != len(nums):
                    one=nums.index(twopos[0])
                    nums[nums.index(twopos[0])]=''
                    two=nums.index(twopos[1])
                    return [one,two]
                else:
                    return[nums.index(twopos[0]), nums.index(twopos[1]) ]
            else:
                twopos.pop(0)

작성 과정(여기는 학습 과정)

문제를 보자마자 느낌이 비교적 간단해서 코드를 빨리 썼는데 그 방법은 몇 번을 반복해서 수정한 후에야 비로소 일이 그렇게 간단하지 않다는 것을 알게 되었다. 두 가지 비교적 전형적인 문제를 열거했다.
처음 발생한 문제:

mirror=nums
'''     mirror nums         '''

mirror와nums가 하나의 목록을 공유하는 것과 같기 때문에mirror의 조작은nums에도 같은 영향을 미칩니다. 마지막return에서nums에서 수치를 찾을 수 없습니다.
두 번째 문제: 한 번의 판단이 없어지면nums=[3,3],target=6시 [0,1]을 출력해야 하기 때문에 한 번의 판단을 더해야 한다.

if len(set(nums)) != len(nums):
                    one=nums.index(twopos[0])
                    nums[nums.index(twopos[0])]=''
                    two=nums.index(twopos[1])
                    return [one,two]
'''             ，              （´▽`） '''

수정된 후에 코드는 마침내 성공적으로 운행할 수 있게 되었다
결과:
실행 시: 560ms, 모든python 제출에서 49.83%의 사용자 메모리 소모를 격파: 13.1MB, 모든python 제출에서 15.65%의 사용자를 격파했다
자신이 사용한 것이 바로 폭력 해독법이다. 시간의 복잡도는 O(n2)일 것이다. 그러나 누군가가 폭력 해독법으로 1636ms를 소모하는 것을 보니 확실하지 않아 의문이다.알고리즘의 복잡도: 알고리즘의 시간 복잡도와 공간 복잡도 - 총결
1636ms 코드:

def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(lens):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
            #  num2=num1, nums       ，     num1  。
                continue
            else:
                j = nums.index(target - nums[i],i+1) 
                #index(x,i+1)  num1      num2                
                break
    if j>0:
        return [i,j]
    else:
        return []

#  ：lao-la-rou-yue-jiao-yue-xiang
#  ：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-#jie-fa-by-lao-la-rou-yue-j/
#  ：  （LeetCode）
#        。             ，          。

총결산

이를 통해 알 수 있듯이 사용하는 것은 모두 간단한 문장(아무리 어려워도 자신이 알아볼 수 없다)이다. 변수의 명칭과 문장은 매우 거칠고 쓰기도 느리며 경험이 너무 적다.

코드 최적화

1. 변수를 명명할 때 경험이 부족합니다. 예를 들어 두 수의 합의 두 수는num1,num2로 표시할 수 있습니다.2. 동일한 두 수가 존재하면 최종 판정 시간에 주어진 목록의 값을 직접 수정하는 것은 좋지 않다.

참조 코드

간결하고 자신이 이해할 수 있는 코드를 찾았다. 힌트 3의hashmap을 사용했다.

class Solution(object):
    def twoSum(self, nums, target):
        hashmap = {}
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None

#  ：lao-la-rou-yue-jiao-yue-xiang
#  ：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-#jie-fa-by-lao-la-rou-yue-j/
#  ：  （LeetCode）
#        。             ，          。

결과:
실행 시: 40ms, 모든python 제출에서 87.30%의 사용자 메모리 소모를 격파: 13.1MB, 모든python 제출에서 15.26%의 사용자를 격파했다
시간의 복잡도는 O(n)이다.

배운 문장

1. enumerate 함수

python의 enumerate 명령문:
enumerate범람할 수 있는 데이터 대상을 색인 서열로 조합할 수 있으며, 데이터와 데이터 하표를 열거할 수 있으며, 일반적으로 for 순환에 사용됩니다.
예:

 >>> product = [ "Mac pro","iPhone","iWatch"]
 >>> for index,item in enumerate(product):
          print(index,item)

 '''      ：'''
 0    Mac pro
 1    iPhone
 2    iWatch

Python의 enumerate 함수 소개 참조

2. permutations 함수

이 함수는python의 라이브러리 itertools에서 가져옵니다.

>>> import itertools
>>> s = [1, 2, 3]
>>> print(itertools.permutations(s,2))
<itertools.permutations object at 0x000002C49B0283A8>
>>> n=itertools.permutations(s,2)
>>> for i in n:
	print(i)

'''      ：'''	
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

3. combinations 함수

이 함수는python의 라이브러리 itertools에서도 가져올 수 있습니다.

>>> import itertools
>>> s = [1, 2, 3]
>>> t=list(itertools.combinations(s, 2))
>>> print(t)
[(1, 2), (1, 3), (2, 3)]

>>> t=list(itertools.combinations(s, 3))
>>> print(t)
[(1, 2, 3)]

즉:permutations와combinations는 모두 교체기를 얻는다.combinations 방법은 조합에 중점을 두고permutations 방법은 배열에 중점을 둔다.