2. 12295. 19 검 지 BAT, 자바 백 엔 드 연구 개발 면접 문제 해석, 문제 풀이 방향 까지 알려 줄 게.

12362 단어
BAT 는 중국 3 대 인터넷 회사 로 서 모든 프로그래머 들 이 꿈 꾸 는 근무 환경 이다. 마치 고등 학생 들 이 수 능 을 보 는 목적 이 칭 화 베 이 징 대 복 단 과 같 기 때문에 모든 젊 은 프로그래머 들 이 BAT 에 들 어가 일 을 시도 해 야 한다.
첫 번 째 문제: 두 행렬 검색
m x n 매트릭스 matrix 의 목표 값 target 을 검색 하기 위해 효율 적 인 알고리즘 을 만 듭 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다.
  • 각 줄 의 요 소 는 왼쪽 에서 오른쪽으로 오름차 순 으로 배열 된다.
  • 각 열의 요 소 는 위 에서 아래로 오름차 순 으로 배열 된다.

  • 예시:
    현재 매트릭스 매트릭스 행렬 은 다음 과 같 습 니 다.
    [
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]
    
  • 주어진 target = 5, true 로 돌아 갑 니 다.
  • 주어진 target = 20, false 로 돌아 갑 니 다.

  • 문제 풀이 의 사고 방향.
    2 차원 배열 은 규칙 적 이다. 오른쪽 상단 의 숫자 는 한 열 에서 가장 작고 한 줄 에서 가장 크다. 이 숫자 와 target 을 비교 하면 한 줄 또는 한 열 을 후보 구역 으로 배출 할 수 있다. 그러면 target 이 존재 할 수 있 는 범 위 를 좁 혀 결 과 를 얻 을 수 있다.
    public Boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        for (int i = 0, j = matrix[0].length - 1; i < matrix.length && j >= 0; ) {
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
    

    두 번 째 문제: 스페이스 바 꾸 기
    한 문자열 의 빈 칸 을 '% 20' 으로 바 꾸 는 함 수 를 구현 하 십시오.예 를 들 어, 문자열 이 We Are Happy 일 때, 교 체 된 문자열 은 We% 20Are% 20Happy 입 니 다.
    문제 풀이 의 사고 방향.
  • 문자열 의 빈 칸 개 수 를 통 해 새 문자열 의 길 이 를 계산 합 니 다
  • 두 바늘 로 문자열 을 복사 합 니 다. '' 를 만 났 을 때% 20
  • 으로 바 꿉 니 다.
    public String replaceSpace(StringBuffer str) {
        char[] chars = str.toString().toCharArray();
        StringBuilder res = new StringBuilder();
        for (char c : chars) {
            if (c == ' ') res.append("%20"); else res.append(c);
        }
        return res.toString();
    }
    

    세 번 째 문제: 처음부터 끝까지 링크 인쇄
    링크 를 입력 하고 링크 값 이 끝 에서 끝까지 의 순서에 따라 Array List 를 되 돌려 줍 니 다.
    문제 풀이 의 사고 방향.
  • 창고
  • public ArrayList printListFromTailToHead(ListNode listNode) {
        LinkedList stack = new LinkedList<>();
        while (listNode != null) {
            stack.addLast(listNode.val);
            listNode = listNode.next;
        }
        ArrayList res = new ArrayList<>();
        while (!stack.isEmpty()) {
            res.add(stack.pollLast());
        }
        return res;
    }
    
  • 재 귀: 링크 가 너무 길 면 스 택 이 넘 칠 수 있 습 니 다
  • public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList res = new ArrayList<>();
        print(res,listNode);
        return res;
    }
    private void print(ArrayList res, ListNode listNode) {
        if (listNode == null) return;
        print(res, listNode.next);
        res.add(listNode.val);
    }
    

    네 번 째 문제: 이 진 트 리 재건
    이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 다시 만 들 고 돌아 갑 니 다.
    문제 풀이 의 사고 방향.
  • 앞 순 서 를 통 해 루트 노드 를 찾 습 니 다
  • 그러면 중간 순서 에서 루트 노드 의 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무
  • 입 니 다.
  • 순서대로 유추 하여 노드 를 생 성 하 는 왼쪽 나무 와 오른쪽 나무
  • 구축 과정 이 아래 에서 위로
  • public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        Map preIndex = new HashMap<>();
        for (int i = 0; i < pre.length; i++) {
            preIndex.put(pre[i], i);
        }
        return buildTree(preIndex, in, 0, in.length - 1);
    }
    private TreeNode buildTree(Map preIndex, int[] in, int start, int end) {
        if (start == end) {
            return new TreeNode(in[start]);
        }
        int indexOfRoot = start;
        for (int i = start; i <= end; i++) {
            if (preIndex.get(in[i]) < preIndex.get(in[indexOfRoot])) {
                indexOfRoot = i;
            }
        }
        TreeNode root = new TreeNode(in[indexOfRoot]);
        if (start <= indexOfRoot - 1) root.left = buildTree(preIndex, in, start, indexOfRoot - 1);
        if (indexOfRoot + 1 <= end) root.right = buildTree(preIndex, in, indexOfRoot + 1, end);
        return root;
    }
    

    다섯 번 째 문제: 두 개의 창고 로 하나의 대열 을 실현 한다.
    두 개의 스 택 으로 하나의 대기 열 을 실현 하고 대기 열의 Push 와 Pop 작업 을 완성 합 니 다.대기 열 에 있 는 요 소 는 int 형식 입 니 다.
    문제 풀이 의 사고 방향.
  • stack 1 을 push 대기 열 로 하여 요소 push 를 stack 1
  • 로 합 니 다.
  • stack 2 를 pop 대기 열 로 하고 stack 2 가 비어 있 을 때 stack 1 의 데 이 터 를 stack 2 로 push 합 니 다. 그렇지 않 으 면 직접 pop stack 2
  • 두 개의 stack 을 연결 하 는 것 과 같 습 니 다: - > stack 1 <: > stack 2 - >
    Stack pushStack = new Stack<>();
    Stack popStack = new Stack<>();
    public void push(int node) {
        pushStack.push(node);
    }
    public int pop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        if (popStack.isEmpty()) return -1; else return popStack.pop();
    }
    

    여섯 번 째 문제: 회전 배열 의 최소 숫자
    한 배열 의 맨 처음 몇 개의 요 소 를 배열 의 끝 에 옮 기 는 것 을 우 리 는 배열 의 회전 이 라 고 부른다.정렬 되 지 않 은 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.NOTE: 제 시 된 모든 요 소 는 0 보다 큽 니 다. 배열 크기 가 0 이면 0 을 되 돌려 주 십시오.
    문제 풀이 의 사고 방향.
  • 회전 한 후의 배열 은 두 개의 상승 서열 이 존재 하고 최소 요 소 는 두 개의 상승 서열 의 중간
  • 에 있다.
  • 두 개의 포인터 로 두 배열 에서 최대 와 최소 의 값 을 찾 으 면 end 가 가리 키 는 수 는 최소
  • 이다.
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int start = 0, end = array.length - 1;
        while (end - start != 1) {
            int mid = (start + end) / 2;
            if (array[mid] >= array[start]) {
                start = mid;
            }
            if (array[mid] <= array[end]) {
                end = mid;
            }
        }
        return array[end];
    }
    

    일곱 번 째 문제: 피 보 나 체 수열
    모두 가 피 보 나치 수열 을 알 고 있 습 니 다. 지금 은 정수 n 을 입력 하 라 고 요구 하고 있 습 니 다. 피 보 나치 수열 의 n 번 째 항목 (0 부터 0 번 째 항목 은 0) 을 출력 하 십시오.n<=39
    문제 풀이 의 사고 방향.
  • 재 귀 계산 이 느 리 고 가장 간단 한 알고리즘
  • 이다.
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int l = 1, ll = 0;
        for (int i = 2; i <= n; i++) {
            int t = ll + l;
            ll = l;
            l = t;
        }
        return l;
    }
    

    여덟 번 째 문제: 2 진법 중 1 의 개수
    정 수 를 입력 하고 이 바 이 너 리 는 1 의 개 수 를 출력 합 니 다.그 중 음 수 는 부호 로 표시 한다.
    문제 풀이 의 사고 방향.
  • 음 수 는 패 치 표시
  • >>> 은 부호 가 없 는 오른쪽으로 이동 하고 >> 은 기호 가 있 는 오른쪽으로 이동 하 며 n 이 마이너스 일 때 남 은 1
  • 이 증가한다.
    public int NumberOf1(int n) {
        int mask = 0x01;
        int res = 0;
        int t = n;
        while (t != 0) {
            if ((t & mask) == 1) {
                res++;
            }
            t = t >>> 1;
        }
        return res;
    }
    

    9 번: 수치의 정수 제곱
    double 형식의 부동 소수점 base 와 int 형식의 정수 exponent 를 지정 합 니 다.base 의 exponent 제곱 을 구하 다.
    문제 풀이 의 사고 방향.
  • n 이 짝수 일 때 $$a^n = a^{n/2} * a^{n/2}$$
  • n 이 홀수 일 때 $$a^n = a^{n/2} * a^{n/2} * a$$
  • 피 보 나 체 와 유사 한 방식 으로 재 귀 를 이용 하여 구 해 낼 수 있다
  • public double Power(double base, int exponent) {
        if (base == 0) {
            return 0;
        }
        if (base == 1) {
            return 1;
        }
        int t_exponent = Math.abs(exponent);
        double t = PositivePower(base, t_exponent);
        return exponent > 0 ? t : 1 / t;
    }
    private double PositivePower(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double t = PositivePower(base, exponent >> 1);
        t *= t;
        if ((exponent & 0x01) == 1) {
            t *= base;
        }
        return t;
    }
    

    10 번: 최대 n 자리 인쇄
    n 을 입력 하고 1 에서 최대 n 자리 10 진 수 를 출력 하 십시오.예 를 들 어 3 을 입력 하면 1, 2, 3 에서 최대 3 자리 999 까지 출력 한다.
    문제 풀이 의 사고 방향.
  • n 이 커서 출력 된 숫자 가 int 또는 long
  • 을 초과 할 수 있 습 니 다.
    public void PrintN(int n) {
        if (n <= 0) {
            return;
        }
        String res = "0";
        while (true) {
            Boolean all9 = true;
            res = Plus(res, 1);
            System.out.println(res);
            for (int i = 0; i < res.length(); i++) {
                if (res.charAt(i) != '9') {
                    all9 = false;
                    break;
                }
            }
            if (all9 && res.length() == n) {
                break;
            }
        }
    }
    private String Plus(String t, int i) {
        char[] chars = t.toCharArray();
        StringBuilder res = new StringBuilder();
        chars[chars.length - 1] += i;
        Boolean flag = false;
        for (int j = chars.length - 1; j >= 0; j--) {
            int a = chars[j];
            if (flag) {
                a++;
                flag = false;
            }
            if (a > '9') {
                flag = true;
                a = a - '9' + '0' - 1;
            }
            res.append((char) a);
        }
        if (flag) {
            res.append('1');
        }
        return res.reverse().toString();
    }
    

    열 한 번 째 문제: O (1) 의 시간 복잡 도 에서 노드 삭제
    주문서 에 링크 의 헤드 포인터 와 삭제 할 지침 을 주 고 함수 가 O (1) 의 시간 복잡 도 에서 삭제 하도록 정의 합 니 다.
    문제 풀이 의 사고 방향.
  • 노드 의 비 꼬리 노드 를 삭제 하고 다음 노드 의 값 을 현재 노드 로 복사 한 다음 에 다음 노드
  • 를 삭제 합 니 다.
  • 삭제 할 노드 는 끝 노드 이 고 처음부터 삭제 할 노드 의 앞 노드 를 찾 아 삭제 합 니 다
  • public void O1DeleteNode(ListNode head, ListNode needDelete) {
        if (needDelete.next != null) {
            ListNode next = needDelete.next.next;
            needDelete.val = needDelete.next.val;
            needDelete.next = next;
        } else {
            ListNode cursor = head;
            while (cursor != null) {
                if (cursor.next == needDelete) break;
                cursor = cursor.next;
            }
            if (cursor == null) return;
            cursor.next = needDelete.next;
        }
    }
    

    열 두 번 째 문제: 배열 순 서 를 조정 하여 홀수 가 짝수 앞 에 있 도록 한다.
    하나의 정수 배열 을 입력 하여 하나의 함 수 를 실현 하여 이 배열 의 숫자의 순 서 를 조정 하여 모든 홀수 가 배열 의 앞부분 에 있 고 모든 짝수 가 배열 의 후반 부분 에 있 으 며 홀수 와 홀수, 짝수 와 짝수 간 의 상대 적 인 위치 가 변 하지 않도록 합 니 다.
    문제 풀이 의 사고 방향.
  • 정렬 의 안정성 을 확보 해 야 한다
  • 거품 알고리즘 으로 정렬
  • public void reOrderArray(int[] array) {
        if (array.length <= 1) {
            return;
        }
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = i; j < array.length - 1; j++) {
                if (array[j] % 2 == 0 && array[j + 1] % 2 == 1) swap(array, j, j + 1);
            }
        }
    }
    private void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
    

    13 번 문제: 링크 에서 마지막 k 번 째 노드
    링크 를 입력 하여 이 링크 의 마지막 k 번 째 노드 를 출력 합 니 다.
    문제 풀이 의 사고 방향.
  • 두 개의 지침, 빠 른 지침 이 먼저 k 걸음 을 한 다음 에 느 린 지침 이 앞으로 이동 하고 빠 른 지침 이 끝 날 때 느 린 지침 은 마지막 k 번 째 노드
  • 를 가리킨다.
  • 역수 k 개 노드 가 존재 하지 않 는 상황 을 고려 해 야 한다
  • public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode cursor = head;
        ListNode cursorK = head;
        int i = 0;
        while (cursorK != null) {
            cursorK = cursorK.next;
            if (i >= k) {
                cursor = cursor.next;
            }
            i++;
        }
        if (i < k) {
            return null;
        }
        return cursor;
    }
    

    열 다섯 번 째 문제: 반전 링크
    링크 를 입력 하고 링크 를 반전 시 킨 후 새 링크 의 헤더 를 출력 합 니 다.
    문제 풀이 의 사고 방향.
  • 세 개의 지침
  • public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = head, cur = head.next, next;
        pre.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    

    마지막 에 쓰다
    면접 문 제 는 아직 많 지만 이 글 은 지면 에 국한 되 어 15 ~ 1 선 인터넷 면접 문제 만 공유 합 니 다.본인 이 디자인 한 면접 문제 에 대하 여 본인 은 이미 완전한 PDF 면접 문제 집합 으로 정리 하 였 습 니 다. 필요 한 자바 엔지니어 친구 들 에 게 무료 로 공유 하고 아래 전송 문 을 클릭 하면 무료 로 수령 할 수 있 습 니 다.
    전송 문
  • 웅지 는 성공 의 길 을 안내 하 는 것 이다.
  • 자신 감 은 포기 하지 않 는 부 름 이다.
  • 열정 은 성공 자의 마음 이다.
  • 인내심 은 어 려 운 날 카 로 운 검 을 쫓 는 것 이다.
  • 책임감 은 성공 을 향 한 필연 이다.
  • 오 심이 당신 과 함께 하루 하루 를 보 내 기 를 바 랍 니 다!
  • 여러분 의 면접 이 순 조 롭 고 성공 하 기 를 진심으로 바 랍 니 다!
  • 좋은 웹페이지 즐겨찾기