[면경] CVTE 의 두 필기시험 프로 그래 밍 문제

저녁 에 컨디션 이 좀 안 좋아 서 급 하 게 필기시험 을 봤 어 요.앞 에 많은 선택 문제 가 있 는데 정말 구덩이 입 니 다. 모두 다 선 입 니 다.다음은 필기시험 문제 의 두 개의 프로 그래 밍 문 제 를 말씀 드 리 겠 습 니 다.사실 제 가 할 때 도 긴 장 했 습 니 다. 주제 에 맞 게 제출 을 하고 최적화 도 하지 않 았 습 니 다. 사실 시간 이 허락 된다 면 저도 최적화 하고 싶 었 습 니 다. 하지만 이 필기시험 은 당신 이 얼마나 잘 최적화 되 었 는 지 보 는 것 이 아니 라 당신 이 잘 했 는 지 보 는 것 입 니 다.
첫 번 째 문제: 문자 배열 의 순환 오른쪽 이동 문제
제목 요구: N 글자 의 배열 을 오른쪽으로 이동 합 니 다.시간 복잡 도 O (N).현장 사고: 1. k 는 N 보다 작고 N 보다 크 며 N 과 같 을 수 있 으 며 이 몇 가지 상황 에 따라 분석 할 수 있다.우선, N = dK (d = 0, 1, 2.) 시 문자 배열 이 오른쪽으로 이동 하면 문자 배열 의 문자 위치 가 변 하지 않 는 다 는 것 을 알 아야 합 니 다.이 '돌파구' 가 있 으 면 우 리 는 K > N 을 K < = N 으로 전환 시 켜 판단 의 범 위 를 좁 힐 수 있다.2. 이제 우 리 는 K 분석 만 하면 된다.
public static void solution(int[] arr, int length, int shiftStep)
{
    if(arr==null||length==0) return;
    int count=shiftStep%length;
    if(count==0) return;
    int[] copy=new int[length];
    for(int i=0;i<length;i++){
        copy[i]=arr[i];
    }
    for(int i=0;i<length;i++){
        arr[(i+count)%length]=copy[i];
    }
}

두 번 째 문제: 문자열 의 무 거 운 문제 제거
제목 요구: 소문 자 문자열 의 중복 문 자 를 삭제 합 니 다.가능 하 다 면, 중복 문자 중 그 보다 작은 문자 앞 에 있 는 문 자 를 우선 삭제 합 니 다.예 를 들 어 입력: bbcacdw;출력: bacdw 현장 사고: 처음에 저 는 이 문제 의 최 적 화 를 생각 하고 있 었 습 니 다. '폭 파' 를 사용 하 는 것 을 제외 하고.한참 을 생각 했 더 니 너무 긴 장 했 는 지 생각 이 떠 오 르 지 않 았 다.시간 이 거의 다 되 어 어 어 쩔 수 없 이 '폭 파' 를 했다.그러나 '폭 파' 도 쉽 지 않다.
public static String solution(String s)
{
    if(s==null||"".equals(s)) return s;

    StringBuilder sb = new StringBuilder(s);
    int i = 0;
    while (i < sb.length())
    {
        char temp = sb.charAt(i);
        boolean isR = false; //          i   
        boolean isFront = true; //           ?true         :false         
        int j = i + 1;
        while (j < sb.length())
        {
            if (isFront && sb.charAt(j) < temp)
            {
                isFront = false;
            }
            if (sb.charAt(j) == temp)
            {
                if (isFront)
                {
                    sb.deleteCharAt(j);
                    continue;
                }
                else
                {
                    isR = true;
                }
            }
            j++;
        }
        if (isR)
        {
            sb.deleteCharAt(i);
        }
        else
        {
            i++;
        }
    }
    return sb.toString();
}

결론: 알고리즘 문 제 는 맞 춤 형 문 제 를 풀 고 그 중에서 해법 과 경험 을 추출 해 야 한다.

좋은 웹페이지 즐겨찾기