검 지 offer 시리즈 (19) - 배열 에서 중복 되 는 숫자, 곱 하기 배열 구축, 정규 표현 식 일치

배열 에서 중복 되 는 숫자
제목 설명
길이 가 n 인 배열 의 모든 숫자 는 0 에서 n - 1 의 범위 안에 있다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모른다.숫자 마다 몇 번 씩 반복 되 는 지 모 르 겠 어 요.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 7 인 배열 {2, 3, 1, 0, 2, 5, 3} 을 입력 하면 해당 하 는 출력 은 첫 번 째 중복 되 는 숫자 2 입 니 다.
문제 풀이 방향:
참고:https://blog.csdn.net/u010005281/article/details/80171726?utm_source=copy
주의:
1. 배열 의 첫 번 째 중복 값 을 되 돌려 줍 니 다. 즉, 원래 배열 의 순 서 를 파괴 할 수 없습니다.
2. 이것 은 특히 주의해 야 합 니 다. 임의로 중복 되 는 값 을 찾 아 Duplication [0] 에 할당 합 니 다.
3 함수 가 True 또는 False 로 되 돌아 갑 니 다.
법 1:
hash 시 계 를 만 드 는 것 은 자바 의 hashmap 에 해당 합 니 다.
법 2:
'배열 안의 숫자 범 위 는 0 ~ n - 1 사이' 이기 때문에 기 존의 배열 로 고 를 설정 할 수 있 습 니 다. 한 숫자 가 방문 한 후에 해당 하 는 비트 의 수 + n 을 설정 할 수 있 습 니 다. 그 다음 에 같은 수 를 만 났 을 때 해당 하 는 비트 의 수가 n 보다 많 음 을 발견 할 수 있 습 니 다. 그러면 이 수 를 직접 되 돌려 주면 됩 니 다.
코드:
법 1:

# -*- coding:utf-8 -*-
class Solution:
    #        ~              duplication[0]
    #     True/False
    def duplicate(self, numbers, duplication):
        # write code here
        dict = {}
        for num in numbers:
            if num not in dict:
                dict[num]=0
            else:
                duplication[0]=num
                return True
        return False

# -*- coding:utf-8 -*-
class Solution:
    def duplicate(self, numbers, duplication):
        # write code here
        if not numbers:
            return False
        num = []
        
        for i in numbers:
            if i in num:
                duplication[0]=i
                return True
            else:
                num.append(i)
        return False

법 2:

# -*- coding:utf-8 -*-
class Solution:
    #        ~              duplication[0]
    #     True/False
    def duplicate(self, numbers, duplication):
        # write code here
        long = len(numbers)
        for i in range(long):
            index = numbers[i]%long if numbers[i]>=long else numbers[i]
            if numbers[index]>long:
                duplication[0] = index
                return True
            numbers[index] += long
        return False
        

곱셈 배열 구축
제목 설명
배열 A [0, 1,..., n - 1] 을 지정 하고 배열 B [0, 1,..., n - 1] 을 구축 하 십시오. 그 중에서 B 중의 요소 B [i] = A [0] * A [1] *... * A [i - 1] * A [i + 1] *... * A [n - 1].나눗셈 을 사용 할 수 없습니다.
문제 풀이 방향:
첫 번 째 로 문제 의 뜻 을 잘못 이해 한 B [i] 는 A [i] 를 위해 몇 번 째 항목 으로 연 승 했 습 니 다.실제로 A [0] 에서 A [n] 까지 의 연승 을 뜻 하 는데 승 이 부족 한 것 은 B [i] 이다. 다음 과 같다.        B[0] = A[1] * A[2] * A[3] * A[4] *....*A[n-1] ;(A [0] 없 음)        B[1 ]= A[0] * A[2] * A[3] * A[4] *....*A[n-1] ;(A [1] 없 음)        B[2] = A[0] * A[1] * A[3] * A[4] *....*A[n-1] ;(A 없 음 [2])
방법 1:
코드:

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if not A or len(A)<0:
            return 0
        length = len(A)
        B=[1]*length
        #    B[0]=1  1  
        for i in range(1, length):
            B[i] = B[i-1]*A[i-1]
        #    ，      ，      （num-1）   for   
        temp =1
        for i in range(length-2, -1, -1):
            temp *= A[i+1]
            B[i] *= temp
        return B

정규 표현 식 일치
제목 설명
'' 와 '*' 를 포함 한 정규 표현 식 과 일치 하 는 함 수 를 구현 하 십시오.모드 의 문자 '' 는 임의의 문 자 를 표시 하고 '*' 는 앞의 문자 가 임의의 번 (0 번 포함) 이 나타 날 수 있 음 을 나타 낸다.이 문제 에서 일치 하 는 것 은 문자열 의 모든 문자 가 전체 패턴 과 일치 하 는 것 을 말 합 니 다.예 를 들 어 문자열 'aa' 는 모드 'a. a' 와 'ab * ac * a' 와 일치 하지만 'aa. a' 와 'ab * a' 는 일치 하지 않 습 니 다.
문제 풀이 방향:
 . 임의의 문자 일 수 있 음 을 표시 합 니 다.  ,
eg:     aa  a.a  ab * ac * a (b 가 0 번 나타 나 고 c 가 0 번 나타 나 면 aa 입 니 다)
다음 과 같은 상황 으로 나 뉜 다.
1 s 가 pattern 과 일치 하면 True
2 pattern 이 '' 라면 s 와 pattern 이 같 지 않 기 때문에 false
3. s 가 ', pattern 이' 라면 True 로 돌아 갑 니 다.  s 가 '' 일 때 pattern 길이 가 1 이 고 '' 가 아니 거나 pattern 두 번 째 문자 가 * 가 아니라면 pattern 이 비어 있 을 수 없습니다. False 로 돌아 갑 니 다.  pattern 길이 가 1 이 아니 고 두 번 째 문자 가 * 이면 pattern 이 비어 있 을 수 있 습 니 다. 세 번 째 문자 부터 교체 합 니 다.
4 pattern 길이 가 2 보다 작 지 않 고 pattern 의 두 번 째 문자 가 * 가 아 닌 경우   pattern [0] 이 s [0] 과 같 지 않 고 그렇지 않 을 때 s 와 pattern 은 반드시 같 지 않다.   그렇지 않 으 면 s 와 pattern 은 모두 오른쪽으로 한 자 리 를 옮 겨 계속 비교 합 니 다.
5 pattern 길이 가 2 보다 작 지 않 고 pattern 두 번 째 문자 가 * 인 경우  만약 s [0] 가 pattern [0] 과 같 지 않 고 pattern [0] 이 그렇지 않다 면 첫 번 째 가 성공 하지 못 할 것 입 니 다. pattern 은 두 분 을 뒤로 이동 해서 뒤에 s 첫 번 째 와 일치 할 수 있 는 지 계속 비교 해 야 합 니 다.  s [0] 가 pattern [0] 이나 pattern [0] 이... 1 위 와 일치 하면        1. aa 와 a * a 의 경우 별표 가 여러 개의 a 를 대표 하기 때문에 s 는 계속 오른쪽으로 이동 하여 계속 비교 해 야 합 니 다.        2. a 와 a * a 중 이 경우 별표 가 0 개의 a 를 대표 하기 때문에 s 는 오른쪽으로 이동 할 필요 가 없고 pattern 은 오른쪽으로 두 자 리 를 이동 해 야 합 니 다.        3. abc 와 a * bc 의 경우 별 번 호 는 1 개의 a, s 오른쪽으로 한 자 리 를 옮 기 고 pattern 오른쪽으로 두 자 리 를 계속 비교 합 니 다.
 상기 pattern 이 2 보다 작 지 않 은 경 우 를 제외 하고 pattern 이 1 인 경우 만 남 았 기 때문에 pattern 이 "..." 이면  그리고 s 길 이 는 1 이 고 True 로 돌아 갑 니 다.
코드:
방법 1:

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern     
    def match(self, s, pattern):
        # write code here
        if s == pattern:
            return True
        elif pattern == '':
            return False
        elif s == '':
            if pattern == '.':
                return False
            elif len(pattern)==1 or pattern[1]!='*':
                return False
            else:
                return self.match(s, pattern[2:])
            
        if len(pattern) >=2 and pattern[1] != '*':
            if s[0] != pattern[0] and pattern[0]!='.':
                return False
            else:
                return self.match(s[1:], pattern[1:])
        elif len(pattern) >=2 and pattern[1] =='*':
            if s[0] != pattern[0] and pattern[0] !='.':
                return self.match(s, pattern[2:])
            else:
                return self.match(s[1:], pattern) or self.match(s, pattern[2:] or self.match(s[1:],pattern[2:]))
        elif pattern == '.' and len(s)==1:
            return True
        return False
            

방법 2:

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern     
    def match(self, s, pattern):
        # write code here
        if s == pattern: 
            return True 
        if len(pattern)>1 and pattern[1] == '*': 
            if s and (s[0]==pattern[0] or pattern[0] == '.'):
                return self.match(s,pattern[2:]) or self.match(s[1:],pattern) 
            else:
                return self.match(s,pattern[2:]) 
        elif s and pattern and (s[0] == pattern[0] or pattern[0]=='.'): 
            return self.match(s[1:],pattern[1:]) 
        return False