검 지 offer (제2판) python 실현

19877 단어 알고리즘 지식
검지 offer 제2판
  • 제2 장 면접 에 필요 한 기본 지식
  • 2.2 프로 그래 밍 언어
  • 면접 문제 2: 단일 디자인 모델 실현
  • 2.3 데이터 구조
  • 면접 문제 3: 배열 에서 중복 되 는 숫자
  • 면접 문제 4: 2 차원 배열 에서 찾기
  • 면접 문제 5: 스페이스 바 꾸 기
  • 면접 문제 6: 끝 에서 끝까지 링크 인쇄
  • 면접 문제 7: 이 진 트 리 재건
  • 제2 장 면접 에 필요 한 기본 지식
    2.2 프로 그래 밍 언어
    면접 문제 2: 단일 디자인 모델 구현
    제목: 하나의 클래스 를 설계 합 니 다. 우 리 는 이 클래스 의 인 스 턴 스 만 생 성 할 수 있 습 니 다.
    LeetCode: 이 문 제 는 LeetCode 에 없습니다.
    문제 풀이 방향:
    개인 플래그 를 정의 하고 None 로 초기 화 합 니 다. 인 스 턴 스 를 만 들 면 이 플래그 를 인 스 턴 스 로 설정 합 니 다.
    구현 코드:
    class Earth(object):
        __instance = None
    
        def __new__(cls):
            if cls.__instance is not None:
                #   __instance             
                #      __new__(cls)    
                cls.__instance = object.__new__(cls)
                return cls.__instance
            else:
                #           
                return cls.__instance
    
    

    2.3 데이터 구조
    면접 문제 3: 배열 에서 중복 되 는 숫자
    제목: 하나의 정수 배열 a 를 지정 하 였 으 며, 그 중 1 ≤ a [i] ≤ n (n 은 배열 길이), 그 중 일부 요 소 는 두 번 나타 나 고, 기타 요 소 는 한 번 나타 납 니 다.두 번 나타 나 는 모든 원 소 를 찾 습 니 다.
    제목 요구: 당신 은 어떠한 추가 공간 도 가지 않 고 O (n) 시간 복잡 도 에서 이 문 제 를 해결 할 수 있 습 니까?
    LeetCode: LeetCode 442: 배열 에서 중복 되 는 데이터
    문제 풀이 방향:
  • 우선 이 배열 의 중간 에 있 는 모든 숫자 가 이 배열 의 길 이 를 초과 하지 않 기 때문에 우 리 는 이 배열 아래 표 시 된 값 으로 해당 위치의 값 이 존재 하 는 지 를 저장 할 수 있다.
  • 이 위치의 값 이 0 보다 크 면 이 배열 에 대응 하 는 배열 의 이 숫자 가 아래 표 시 된 값 을 마이너스 로 설정 하고 이 마이너스 에 다시 접근 하면 중복 요 소 를 되 돌려 줍 니 다.

  • 구현 코드:
    def findDuplicates(nums):
        m_list = []
        for i in nums:
            #          ,                   
            #      ,            ,     ,              
            if nums[abs(i)-1] > 0:
                nums[abs(i)-1] *= -1
            else:
                m_list.append(abs(i))
    
        print(m_list)
    
    
    if __name__ == '__main__':
        list = [4, 3, 2, 7, 8, 2, 3, 1]
        findDuplicates(list)
    
    

    면접 문제 4: 2 차원 배열 에서 의 찾기
    제목: m x n 매트릭스 matrix 의 목표 값 target 을 검색 하기 위해 효율 적 인 알고리즘 을 만 듭 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다. 각 줄 의 요 소 는 왼쪽 에서 오른쪽으로 오름차 순 으로 배열 된다.각 열의 요 소 는 위 에서 아래로 오름차 순 으로 배열 된다.
    제목: 없 음
    LeetCode: LeetCode 240: 2 차원 매트릭스 검색 II
    문제 풀이 방향:
  • 행렬 보다 좋 은 것 은 질서 가 있 기 때문에 우 리 는 첫 줄 의 가장 큰 요소 부터 판단 할 수 있다.
  • 이 값 이 목표치 보다 작 으 면 이 줄 은 목표치 보다 큰 수가 존재 하지 않 고 다음 줄 을 판단 한다.
  • 이 값 이 목표치 보다 크 면 열 을 버 립 니 다. 이 열 은 목표치 보다 큰 수가 존재 하지 않 기 때문에 나머지 행렬 에 이 목표치 가 있 는 지 판단 합 니 다.

  • 구현 코드:
    def searchMatrix(matrix, target):
        found = False
        #      
        rows = len(matrix)
        #        
        columns = len(matrix[0])
        if matrix is not None and rows > 0 and columns > 0:
            #         
            row = 0
            #         
            column = columns - 1
            #          ,               
            #          0
            while row < rows and column >= 0:
                if matrix[row][column] == target:
                    found = True
                    return found
                elif matrix[row][column] > target:
                    column -= 1
                else:
                    row += 1
            return found
    
    
    if __name__ == '__main__':
        mli = [
            [1,   4,  7, 11, 15],
            [2,   5,  8, 12, 19],
            [3,   6,  9, 16, 22],
            [10, 13, 14, 17, 24],
            [18, 21, 23, 26, 30]
        ]
        found = searchMatrix(mli, 20)
        print(found)
    
    

    면접 문제 5: 스페이스 바 꾸 기
    제목: 한 문자열 의 빈 칸 을 '% 20' 으로 바 꾸 는 함 수 를 구현 하 십시오.예 를 들 어: We Are Happy 가 바 뀐 문자열 은: We% 20are% 20Happy 입 니 다.
    제목: 없 음
    LeetCode: 우 객 망
    문제 풀이 방향:
    python 에 내 장 된 문자열 로 함수 replace 를 바 꾸 고 빈 칸 을% 20 으로 바 꿉 니 다.
    구현 코드:
    def replaceSpace(s):
        return s.replace(' ', '%20')
    
    
    if __name__ == '__main__':
        s = 'We are happy'
        print(replaceSpace(s))
    
    

    면접 문제 6: 끝 에서 끝까지 링크 인쇄
    제목: 단일 체인 시트 반전.예제: 입력: 1 - > 2 - > 3 - > 4 - > 5 - > NULL 출력: 5 - > 4 - > 3 - > 2 - > 1 - > NULL
    제목: 없 음
    LeetCode: LeetCode 206: 반전 링크
    문제 풀이 방향:
    각 노드 를 이 노드 의 앞 자 리 를 가리 키 며 역 순 서 를 완성 합 니 다.
    구현 코드:
    class Solution(object):
    	def reverseList(self, head):
    		"""
    		:type head: ListNode
    		:rtype: ListNode
    		"""
    		#       ,pre  cur,pre  None
    		pre = None
    		cur = head
    		#     ,while               
    		#       ,           
    		while cur:
    			#             
    			tmp = cur.next
    			#          pre
    			cur.next = pre
    			# pre cur       
    			pre = cur
    			cur = tmp
    		return pre	
    
      :user7439t
      :https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
      :  (LeetCode)
            。             ,          。
    
    

    면접 문제 7: 이 진 트 리 재건
    제목: 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순 서 를 입력 하 십시오. {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순 서 를 입력 하 십시오. {4, 7, 2, 1, 5, 3, 8, 6} 은 이 진 트 리 를 재 구축 하고 돌아 갑 니 다.
    제목: 없 음
    LeetCode: LeetCode 206: 반전 링크
    문제 풀이 방향:
    각 노드 를 이 노드 의 앞 자 리 를 가리 키 며 역 순 서 를 완성 합 니 다.
    구현 코드:
    class Solution(object):
    	def reverseList(self, head):
    		"""
    		:type head: ListNode
    		:rtype: ListNode
    		"""
    		#       ,pre  cur,pre  None
    		pre = None
    		cur = head
    		#     ,while               
    		#       ,           
    		while cur:
    			#             
    			tmp = cur.next
    			#          pre
    			cur.next = pre
    			# pre cur       
    			pre = cur
    			cur = tmp
    		return pre	
    
      :user7439t
      :https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
      :  (LeetCode)
            。             ,          。
    
    

    좋은 웹페이지 즐겨찾기