2. 12295. 19 검 지 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]
]
문제 풀이 의 사고 방향.
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 입 니 다.
문제 풀이 의 사고 방향.
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 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 을 되 돌려 주 십시오.
문제 풀이 의 사고 방향.
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 제곱 을 구하 다.
문제 풀이 의 사고 방향.
$$a^n = a^{n/2} * a^{n/2}$$
$$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 까지 출력 한다.
문제 풀이 의 사고 방향.
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 번 째 노드 를 출력 합 니 다.
문제 풀이 의 사고 방향.
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 면접 문제 집합 으로 정리 하 였 습 니 다. 필요 한 자바 엔지니어 친구 들 에 게 무료 로 공유 하고 아래 전송 문 을 클릭 하면 무료 로 수령 할 수 있 습 니 다.
전송 문
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.