검 지 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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.