검지 Offer프로 그래 밍 문제 (문자열 을 정수 / 배열 에서 중복 되 는 숫자 로 변환 / 곱 하기 배열 / 정규 표현 식 일치 구축)

검지 Offer프로 그래 밍 문제
49. 문자열 을 정수 로 변환
시간 제한: 1 초 공간 제한: 32768 K 열도 지수: 223789
이 문제 지식 점: 문자열 진법 전환
제목 설명: 하나의 문자열 을 정수 로 변환 합 니 다 (Integer. valueOf (string) 기능 을 구현 하지만, string 이 숫자 요구 에 부합 되 지 않 을 때 0 으로 되 돌려 줍 니 다). 문자열 로 정수 라 이브 러 리 함 수 를 변환 할 수 없 도록 합 니 다.수치 가 0 이거 나 문자열 이 합 법 적 인 수치 가 아니면 0 을 되 돌려 줍 니 다.
입력 설명: 숫자 알파벳 기 호 를 포함 한 문자열 을 입력 하 십시오. 비어 있 을 수 있 습 니 다.
출력 설명: 합 법 적 인 수치 표현 이 라면 이 숫자 를 되 돌려 줍 니 다. 그렇지 않 으 면 0 을 되 돌려 줍 니 다.
사고: 정수, 판단 하기 쉬 워 요. 첫 번 째 를 처리 한 후에 뒤의 숫자 인지 아 닌 지 판단 하기 만 하면 돼 요.

class Solution {
public:
    int StrToInt(string str) {
        if(str=="0"||str=="") return 0;
        int flag=0,len=str.size();//  
        int fu=0,cnt=0;
        long long val=0;
        if(str[cnt]=='-') fu=1,cnt++;
        else if(str[cnt]=='+') fu=2,cnt++;
        while(cnt='0'){
                val=val*10+str[cnt]-'0';
            }
            else{
                flag=1;
                break;
            }
            cnt++;
        }
        if(flag) return 0;
        else{
            if(fu==1) val=-val;
            return val;
        }
    }
};

50. 배열 에서 중복 되 는 숫자
시간 제한: 1 초 공간 제한: 32768 K 열도 지수: 284260
주제 지식 포인트: 배열
제목 설명: n 길이 의 배열 에 있 는 모든 숫자 는 0 에서 n - 1 범위 안에 있 습 니 다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모른다.숫자 마다 몇 번 씩 반복 되 는 지 모 르 겠 어 요.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 7 인 배열 {2, 3, 1, 0, 2, 5, 3} 을 입력 하면 해당 하 는 출력 은 첫 번 째 중복 되 는 숫자 2 입 니 다.
사고: 200 개의 배열 (ASCII 수 는 128) 을 열 고 기 수 를 옮 겨 다 니 며 판단 합 니 다.

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        int cnt[200];
        memset(cnt,0,sizeof(cnt));
        bool flag=false;
        for(int i=0;i1){
                *duplication=numbers[i];
                flag=true;
                break;
            }
        }
        return flag;
    }
};

51. 곱 하기 배열 구축
시간 제한: 1 초 공간 제한: 32768 K 열도 지수: 139906
주제 지식 포인트: 배열
제목 설명: 배열 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].나눗셈 을 사용 할 수 없습니다.
사고: 상 삼각형 과 하 삼각형 으로 나 누 어 처리 합 니 다.

class Solution {
public:
    vector multiply(const vector& A) {
        int len=A.size();
        vector B(len);
        B[0]=1;
        for(int i=1;i=0;i--){
            temp*=A[i+1];
            B[i]*=temp;
        }
        return B;
    }
};

 
52. 정규 표현 식 일치
시간 제한: 1 초 공간 제한: 32768 K 열도 지수: 224879
주제 지식 포인트: 문자열
제목 설명: '' 와 '*' 를 포함 한 정규 표현 식 과 일치 하 는 함 수 를 구현 하 십시오.모드 의 문자 '' 는 임의의 문 자 를 표시 하고 '*' 는 앞의 문자 가 임의의 번 (0 번 포함) 이 나타 날 수 있 음 을 나타 낸다.이 문제 에서 일치 하 는 것 은 문자열 의 모든 문자 가 전체 패턴 과 일치 하 는 것 을 말 합 니 다.예 를 들 어 문자열 'aa' 는 모드 'a. a' 와 'ab * ac * a' 와 일치 하지만 'aa. a' 와 'ab * a' 는 일치 하지 않 습 니 다.
사고: 이 문 제 는 처음에 이 묘 사 를 읽 지 못 했 습 니 다. 원래 \ # 앞의 그 문 자 는 0 - n 번 나 올 수 있 기 때문에 aa 는 ab * ac * a 와 일치 합 니 다. 그 중에서 b, c 는 0 번 나 옵 니 다.aa 와 aa. a 는 일치 하지 않 습 니 다. aa. a 의 수가 많 기 때 문 입 니 다.일치 란 두 글자 가 완전히 일치 하면 똑 같 을 수 있다 는 것 을 말한다.그리고 char * 처리 하기 어렵 고 캡 처 하기 어려워 서 string 처리 로 바 뀌 었 고 뒤에 있 는 문자열 문제 도 이렇게 했 습 니 다.재 귀적 으로 찾기 시작 하 다.상황 을 나 누 어야 할 것 은 1. 뒤에 \ # 가 없 으 면 바로 일치 합 니 다. 2. 뒤에 \ # 는 생략 할 수도 있 고 여러 번 할 수도 있 습 니 다.

class Solution {
public:
    bool mymatch(string str,string pattern){
        int lens=str.size();
        int lenp=pattern.size();
        if(lens==0&&lenp==0) return true;
        if(lenp==0&&lens!=0) return false;
        if(pattern[0]=='*') return false;
        if(lenp>1&&pattern[1]=='*'){//*        0，1，2
            if(lens>0&&(str[0]==pattern[0]||pattern[0]=='.'))
                return mymatch(str.substr(1),pattern)||mymatch(str,pattern.substr(2));
            else
                return mymatch(str,pattern.substr(2));
        }
        else if(lens>0&&(str[0]==pattern[0]||pattern[0]=='.')){
            return mymatch(str.substr(1),pattern.substr(1));//     
        }
        else return false;
    }
    bool match(char* str, char* pattern)
    {//          。。。
        string s="";
        string p="";
        int lens=strlen(str);
        int lenp=strlen(pattern);
        for(int i=0;i