《 검 지 offer 》
1. 1. 제목
제목 설명
문자열 을 입력 하고 이 문자열 의 모든 배열 을 사전 순서에 따라 출력 하 십시오.예 를 들 어 문자열 abc 를 입력 하면 문자 a, b, c 가 배열 할 수 있 는 모든 문자열 abc, acb, bac, bca, cab 와 cba 를 출력 합 니 다.
입력 설명
길이 가 9 을 넘 지 않 는 문자열 을 입력 하 십시오. 대소 문자 만 포함 합 니 다.
1, 2. 해법 1
사고: 현재 문자열 Sn 에 따라 1 보다 큰 문자열 Sn + 1 을 계산 한 다음 에 Sn + 1 을 현재 상태 로 프로 그래 밍 하여 재 귀적 으로 실행 합 니 다.
class Solution {
public:
void sort_str(string &str) {
for(int i=1 ; i0 && str[j] &rv){
string s=rv[rv.size()-1];
int i;
for(i=s.size()-1 ; i>0 && s[i]<=s[i-1] ;--i)
;
if(i==0) return;
int j;
for(j=s.size()-1 ; s[j]<=s[i-1]; --j)
;
swap( s[i-1], s[j] );
int n=s.size()-1;
while(n>i)
swap(s[i++],s[n--]);// ！ ！ ！！！
rv.push_back(s);
f(rv);
}
vector Permutation(string str) {
vector rv;
if(str.empty()) return rv;
sort_str(str);
rv.push_back(str);
f(rv);
return rv;
}
1.3. 해법 2 (검 지 offer 참조)
주의 하 세 요. 제 가 본 것 은 기념 판 인 을 보 았 는데 이 버 전 작가 가 제시 한 코드 가 틀 렸 습 니 다.지침 이 아니 라 값 을 전달 해 야 한다.
class Solution {
public:
vector Permutation(string str) {
vector rv;
dfs(rv, str, 0);
return rv;
}
void dfs(vector &rv, string s, size_t start){
if(start==s.size()) return;
size_t starth=start;
while(starth 2. 배열 에 나타 난 횟수 가 절반 을 넘 는 숫자
2.1. 제목
제목 설명
배열 에 나타 난 숫자 가 배열 길이 의 절반 을 넘 으 니 이 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 9 인 배열 {1, 2, 3, 2, 2, 5, 4, 2} 을 입력 하 십시오.숫자 2 는 배열 에서 5 번 나타 나 배열 길이 의 절반 을 넘 기 때문에 출력 2.존재 하지 않 으 면 0 을 출력 합 니 다.
2.2. 해법 1 (검 지 offer 참조)
횟수 가 절반 이상 나 온 이상 중위 수 는 원 하 는 결과 일 것 이다.비교 하 는 방식 을 통 해 한 배열 에서 k 번 째 로 큰 수 를 구하 고 이론 적 으로 가장 좋 은 시간 복잡 도 는 O (n) 이다. 예 를 들 어 5 분 법 이지 만 코드 는 비교적 번거롭다.여기 서 사용 하 는 방법 은 최 악의 시간 복잡 도 는 O (n * n) 이지 만 평균 복잡 도 역시 O (n) 이다.빠 른 배열 의 사상 을 사용 하 는 것 과 빠 른 배열 의 차이 점 은 원래 의 배열 을 두 개의 배열 로 나 눈 후에 이 두 개의 배열 을 모두 재 귀적 으로 호출 하 는 것 이다. 여 기 는 그 중의 관심 이 있 는 배열 만 재 귀적 으로 호출 하면 된다. 그래서 평균 시간 복잡 도 는 빠 른 배열 의 O (nlogn) 로 인해 O (n) 가 되 었 다.
class Solution {
public:
int MoreThanHalfNum_Solution(vector numbers) {
if(numbers.empty()) return 0;
int mid;
if(numbers.size() < 3)
mid=numbers[0];
else{
m=numbers.size()/2;
mid=find_middle(numbers,0,numbers.size());
}
if(check(numbers,mid))
return mid;
return 0;
}
private:
int find_middle(vector &numbers, size_t l, size_t r){
if(r-l ==1) return numbers[l];
if(r-l ==2){
if(numbers[l]>numbers[l+1]) swap(numbers[l],numbers[l+1]);
return numbers[m];
}
partial(numbers,l,r);
size_t i=l;
size_t j=r-2;
int pivod=numbers[r-1];
while(true){
while(numbers[++i]pivod){}
if(ii) return find_middle(numbers,i+1,r);
return numbers[m];
}
void partial(vector &numbers,size_t l, size_t r){
size_t middle=(l+r)/2;
if(numbers[l]>numbers[middle]) swap(numbers[l], numbers[middle]);
if(numbers[l]>numbers[r-1]) swap(numbers[l],numbers[r-1]);
if(numbers[middle] &numbers,int rv){
int count=0;
for(size_t i=0 ; inumbers.size()/2) return true;
return false;
}
int m=0;
};
2.3. 해법 2 (검 지 offer 참조)
비록 우리 가 모든 다른 수 를 이 출현 빈도 가 가장 높 은 수 를 상쇄 하 더 라 도 결국 이 수 를 상쇄 할 수 없 기 때문에 다음 과 같은 알고리즘 이 있다.
class Solution {
public:
int MoreThanHalfNum_Solution(vector numbers) {
if(numbers.empty()) return 0;
int rv;
int count=0;
for(int i=0; i < numbers.size() ; ++i){
if(count==0){
rv=numbers[i];
++count;
}else if(rv==numbers[i])
++count;
else
--count;
}
if(count==0) return 0;
if(check(numbers,rv)) return rv;
return 0;
}
private:
bool check(vector &numbers,int rv){
int count=0;
for(int i=0; i < numbers.size(); ++i)
if(rv==numbers[i]) ++count;
return count>numbers.size()/2;
}
};
3. 창고 의 압축, 팝 업 시퀀스
3.1. 제목
제목 설명
두 개의 정수 서열 을 입력 하 십시오. 첫 번 째 서열 은 창고 의 압축 순 서 를 표시 합 니 다. 두 번 째 서열 이 창고 의 팝 업 순서 인지 판단 하 십시오.창고 에 쌓 인 모든 숫자 가 같 지 않다 고 가정 하 세 요.예 를 들 어 서열 1, 2, 3, 4, 5 는 특정한 스 택 의 압 입 순서 이 고 서열 4, 5, 3, 2, 1 은 이 스 택 서열 에 대응 하 는 팝 업 서열 이지 만 4, 3, 5, 1, 2 는 이 스 택 서열 의 팝 업 서열 일 수 없다.(주의: 이 두 서열 의 길 이 는 같다)
3.2 해법
보조 스 택 을 만 듭 니 다. 예 를 들 어 12345 순서 로 스 택 에 들 어가 면 스 택 의 순서 가 45321 입 니 다. 스 택 이 비어 있 으 면 1 을 보조 스 택 에 들 어간 다음 에 스 택 의 요 소 를 계속 검사 한 다음 에 두 번 째 서열 의 첫 번 째 요소 와 다르다 는 것 을 알 게 되 었 습 니 다. 그래서 2 를 스 택 에 들 어가 서 스 택 의 요소 가 4 와 같 는 지 다시 확인 합 니 다. 4 를 눌 렀 을 때 스 택 의 꼭대기 요 소 는 4 와 같 으 면 스 택 에서 나 옵 니 다.또한 스 택 후 새로운 스 택 꼭대기 요소 가 두 번 째 서열 의 다음 요소, 즉 5 와 같 는 지 비교 하면 3 과 5 가 다 르 면 첫 번 째 서열 의 5 를 스 택 에 넣 습 니 다.상술 한 과정 은 사실상 창고 에서 나 와 창고 에 들 어 가 는 과정 을 재현 하 는 것 이다.두 번 째 서열 의 증 가 를 관찰 하면 두 번 째 서열 의 성장 이 가장 느 린 것 이 분명 하 다.만약 에 두 번 째 서열 이 스 택 서열 이 아니라면 유일한 상황 은 첫 번 째 서열 이 모두 스 택 에 들 어 갔 지만 스 택 꼭대기 요 소 는 두 번 째 서열 에서 처리 해 야 할 요소 와 다르다 는 것 이다.
class Solution {
public:
bool IsPopOrder(vector pushV,vector popV) {
vector stack1;
auto ab=pushV.begin();
auto bb=popV.begin();
while(bb != popV.end()){
if( ab == pushV.end() && stack1[stack1.size()-1] != *bb ) return false;
if(stack1.empty() || stack1[stack1.size()-1] != *bb )
stack1.push_back(*ab++);
else{
stack1.pop_back();
++bb;
}
}
return true;
}
};
4. 최소 k 개수
4.1 제목
제목 설명
n 개의 정 수 를 입력 하여 그 중에서 가장 작은 K 개 수 를 찾 아 라.예 를 들 어 4, 5, 1, 6, 2, 7, 3, 8 이라는 8 개의 숫자 를 입력 하면 가장 작은 4 개의 숫자 는 1, 2, 3, 4 이다.
4.2. 해법 1
stl 의 우선 대기 열 로 쌓 는 시간 복잡 도 는 O (n) 이 고 한 번 찾 는 시간 복잡 도 는 O (logn) 이 며 k 번 은 O (klogn) 이기 때문에 전체적인 시간 복잡 도 는 O (n + klogn) 이 고 공간 복잡 도 입 니 다.O (n) 입 니 다.
class Solution {
public:
vector GetLeastNumbers_Solution(vector input, int k) {
vector return_value;
if(input.empty() || k <=0 || k>input.size())
return return_value;
priority_queue,greater > d(input.begin(),input.end());
while(k--){
return_value.push_back(d.top());
d.pop();
}
return return_value;
}
};
4.3. 해법 2
빨리 배열 하 는 사상 은 앞의 k 개 수 를 정렬 하 는 것 이 고 시간 복잡 도 는 k 에 달 려 있 을 것 이다. 최 악 은 O (n * n) 이 고 평균 이다.추측 은 O (n + klogk)
class Solution {
public:
vector GetLeastNumbers_Solution(vector input, int k) {
vector rv;
if( input.empty() || k>input.size() ) return rv;
partial_sort( input , 0 , input.size() , k );
for(int i = 0 ; i < k ; ++i)
rv.push_back( input[i] );
return rv;
}
private:
void partial_sort(vector &input, int l, int r, int k){
if(r-l < 2) return;
if(r-l == 2 ){
if( input[l] > input[l+1] )
swap( input[l] , input[l+1] );
return;
}
mid( input, l , r );
int i=l;
int j=r-2;
int pivod = input[r-1];
while( i < j ) {
while( input[++i] < pivod ) {}
while( input[--j] > pivod ) {}
if( i < j )
swap( input[i] , input[j] );
else
break;
}
swap( input[i] , input[r-1] );
partial_sort( input , l , i , k );
if( k > i+1 ) partial_sort( input , i+1 , r , k);
}
void mid(vector &input , int l , int r) {
int middle = ( l + r )/2;
if( input[l] > input[r-1] ) swap( input[l] , input[r-1] );
if( input[l] > input[middle] ) swap( input[l] , input[middle] );
if( input[r-1] > input[middle] ) swap( input[r-1] , input[middle] );
swap( input[r-2] , input[middle] );
}
};
5. 최대 하위 배열 의 합
class Solution {
public:
int FindGreatestSumOfSubArray(vector array) {
int accum=0;
int max=(1<<31);
for( int i=0 ; i < array.size() ; ++i ){
accum+=array[i];
if(accum > max ) max=accum;
if(accum < 0 ) accum=0;
}
return max;
}
};
6. 정수 중 1 이 나 오 는 횟수
먼저 규칙 찾기: 구간 [0, 9] 에서 나타 난 횟수 는 f (1) = 1 이다.구간 [0, 99] 에서 나타 난 횟수 는 f (2) = 10f (1) + 10 이다. 여기 서 10f (1) 는 개 위 는 1 의 횟수 를 나타 내 고 10 은 1 의 횟수 를 나타 낸다. 예 를 들 어 10, 11,... 19 이 10 개의 수 는 모두 1 이다. 유추 하면 f (1) = 1 을 알 수 있다.f(n)=10f(n-1)+10^(n-1), n>1; 그래서 f (n) 의 통항: f (n) = n10 ^ (n - 1) 는 g (n) 으로 0 에서 n 중 1 이 나타 나 는 횟수 를 나타 낸다. 예 를 들 어 g (612372) 는 g (612372) = 6f (5) + 100000 + g (12372), 예 를 들 어 g (112372) = 1f (5) + 12372 + g (12372) 이 높 은 위치 에서 낮은 위치 로 계산 하면 이것 은 재 귀적 인 해법 이다.물론 낮은 자리 에서 높 은 자리 로 계산 할 수도 있 고 이 럴 때 는 재 귀적 이지 않 아 도 된다.코드 도 더 쉬 워 요.
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
if(n<=0) return 0;
int count=0;
int nn=n;
if(nn%10) ++count;
nn/=10;
int pow=1;
int idx=1;
int temp;
while(nn){
temp=nn%10;
count+=temp*idx*pow;
if(temp>1) count+=pow*10;
if(temp==1) count+=n%(pow*10)+1;
++idx;
pow*=10;
nn/=10;
}
return count;
}
};
7. 배열 을 가장 작은 수로 배열 한다.
7.1. 제목
제목 설명
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
7.2. 해법 (검 지 offer 참조)
연산 a 를 정의 합 니 다. 상기 순서 에서 배열 을 작은 것 에서 큰 것 으로 정렬 한 다음 에 배열 의 요 소 를 순서대로 인쇄 합 니 다. 인쇄 결 과 는 최종 답 입 니 다.
class Solution {
public:
string PrintMinNumber(vector numbers) {
sort(numbers.begin(), numbers.end(), Solution());
string s;
s.reserve(numbers.size()*4);
for(int i=0 ; i < numbers.size() ; ++i)
s+=to_string(numbers[i]);
return s;
}
bool operator ()(const int &a, const int &b){
return less_(a,b);
}
private:
bool less_(const int &a, const int &b){
long l=((long)a*pow(bit_(b)))+b;
long r=((long)b*pow(bit_(a)))+a;
return l 8. 실수
8.1. 제목
제목 설명
인자 2, 3, 5 만 포 함 된 수 를 축 수 (Ugly Number) 라 고 한다.예 를 들 어 6, 8 은 모두 추 수 이지 만 14 는 인자 7 을 포함 하기 때문이다.습관 적 으로 우 리 는 1 을 첫 번 째 못 생 긴 숫자 로 여 긴 다.어 릴 때 부터 큰 순서 로 N 번 째 축 수 를 구하 세 요.
8.2. 해법 1 (O (nlogn) 의 복잡 도)
작은 것 부터 큰 것 까지 배열 한 어릿광대 벡터 를 유지 합 니 다. 우리 가 다음 에 더 큰 어릿광대 수 를 계산 하려 고 할 때 이 벡터 의 특정한 요 소 를 2, 3 또는 5 로 곱 하면 이 과정의 복잡 도 는 log (n) 이기 때문에 전체적인 복잡 도 는 nlog (n) 입 니 다. 주의 하 세 요. 이분법 은 반드시 경계 조건 을 잘 처리 해 야 합 니 다. 예 를 들 어 여기,r - l = = 2 일 때 계속 재 귀 하면 순환 이 된다.
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<1) return 0;
ugly.push_back(1);
while(--index > 0)
ugly.push_back(find_next());
return ugly[ugly.size()-1];
}
private:
vector ugly;
int find_next(){
int m2=find_next_factor(2, 0, ugly.size());
int m3=find_next_factor(3, 0, ugly.size());
int m5=find_next_factor(5, 0, ugly.size());
if(m2>m3) swap(m2, m3);
if(m2>m5) swap(m2, m5);
return m2;
}
int find_next_factor(int factor, size_t l, size_t r){
if(r-l==1) return factor*ugly[l];
if(r-l==2) return factor*ugly[l]>ugly[ugly.size()-1]?factor*ugly[l]:factor*ugly[l+1];
int middle=(l+r)/2;
if(factor*ugly[middle] > ugly[ugly.size()-1])
return find_next_factor(factor, l, middle+1);
return find_next_factor(factor, middle+1, r);
}
};
8.3. 해법 2: 해법 1 에 대한 최적화 (O (n) 의 복잡 도)
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index < 1 ) return 0;
ugly.push_back(1);
while(--index)
next_();
return ugly[ugly.size()-1];
}
private:
void next_(){
int temp2=ugly[next2idx]*2;
int temp3=ugly[next3idx]*3;
int temp5=ugly[next5idx]*5;
int min_temp=temp2;
if(min_temp>temp3) min_temp=temp3;
if(min_temp>temp5) min_temp=temp5;
if(min_temp == temp2) ++next2idx;
if(min_temp == temp3) ++next3idx;
if(min_temp == temp5) ++next5idx;
ugly.push_back(min_temp);
}
vector ugly;
size_t next2idx=0;
size_t next3idx=0;
size_t next5idx=0;
};
9. 첫 번 째 한 번 만 나타 나 는 문자
9.1. 제목
제목 설명
한 문자열 (1 < = 문자열 길이 < = 10000, 모두 알파벳 으로 구성) 에서 첫 번 째 로 한 번 만 나타 나 는 문 자 를 찾 아 그 위 치 를 되 돌려 줍 니 다.
9.2. 해법
hash 의 사상 을 사용 합 니 다. 그러나 요소 의 종류 가 너무 적 기 때문에 이 hashtable 은 충분 합 니 다. 충돌 을 어떻게 해결 하 는 지 전혀 고려 하지 않 아 도 됩 니 다. 만약 에 문자 가 굵 은 선 이 없 으 면 hashtable 에서 의 값 은 - 2 이 고 여러 번 나타 나 면 - 1 이 며 한 번 만 나타 나 면 나타 나 는 위치 입 니 다.마지막 으로 hashtable 을 옮 겨 다 니 며 가장 앞 에 있 는 위 치 를 얻 습 니 다.
class Solution {
public:
int FirstNotRepeatingChar(string str) {
size_t table_size='z'-'A'+1;
size_t begin_='A';
int hash_table['z'-'A'+1];
for(int i=0 ; i < table_size ; ++i)
hash_table[i]=-2;
for(int i=0 ; i < str.size() ; ++i){
int idx=str[i]-begin_;
if( hash_table[idx] == -2)
hash_table[idx]=i;
else if(hash_table[idx] >= 0)
hash_table[idx]=-1;
}
size_t min=10000;
for(int i=0 ; i < table_size ; ++i)
if(hash_table[i] >= 0 && hash_table[i] < min ) min=hash_table[i];
if( min == 10000 ) return -1;
return min;
}
};
10. 배열 의 역순 대
10.1. 제목
제목 설명
배열 에 있 는 두 개의 숫자 가 앞의 숫자 가 뒤의 숫자 보다 크 면 이 두 개의 숫자 는 하나의 역순 대 를 구성한다.배열 을 입력 하여 이 배열 의 역순 쌍 의 총 P 를 구하 십시오.그리고 P 를 1000000007 모드 로 출력 합 니 다.출력 P% 1000000007
입력 설명:
제목 은 입력 한 배열 에 같은 숫자 데이터 범위 가 없습니다.% 50 의 데이터 에 대해 size < = 10 ^ 4% 75 의 데이터 에 대해 size < = 10 ^ 5% 100 의 데이터 에 대해 size < = 2 * 10 ^ 5
10.2. 해법
데이터 양 이 105 수량 급 에 이 르 렀 기 때문에 O (n * n) 알고리즘 을 사용 할 수 없 음 이 분명 하 다. 그렇지 않 으 면 연산 횟수 가 O (1010) 에 이 르 렀 고 몇 십 초 를 소모 할 것 으로 예상 된다.병합 순 서 를 고려 하고 합병 과정 에서 역순 대 수량 도 계산한다.매번 역 서 수 를 업데이트 할 때마다 1000000007 에 대해 야 합 니 다. 그렇지 않 으 면 넘 치 는 오류 가 영문 을 모 를 수 있 습 니 다.(역순 대 데이터 형식 은 int 모델 이기 때문에 표시 할 수 있 는 최대 수 는 대략 2 배의 1000000007 보다 조금 많 고 2 * 10 ^ 5 의 최고 역순 대 수 는 int 가 표시 할 수 있 는 최대 정수 의 10 배 이다.)
class Solution {
public:
int InversePairs(vector data) {
temp=data;
return merge_sort(data, temp, 0, data.size());
}
int merge_sort(vector &data, vector &temp , size_t l , size_t r){
if(r-l<=1) return 0;
int middle=(l+r)/2;
return (
( merge_sort(data, temp , l , middle)
+ merge_sort(data, temp , middle , r) )%1000000007
+ merge(data, temp , l , r))%1000000007;
}
int merge(vector &data, vector &temp , size_t l , size_t r){
int middle=(l+r)/2;
int i=l;
int j=middle;
int k=l;
int rv=0;
while( i < middle && j temp;
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
