Java 인터뷰의 일반적인 배열 질문 요약(2)
- 王林앞으로
- 2020-11-09 15:27:381651검색
1. 피보나치 수열
[주제]
이제 피보나치 수열의 n번째 항목을 입력해야 합니다. (0부터 시작하여 0번째 항목은 0입니다.) ).
(추천 동영상 튜토리얼: java 강좌)
[Code]
package swear2offer.array;
public class FeiBoNaQi {
/**
* 大家都知道斐波那契数列，现在要求输入一个整数 n，
* 请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
* 0,1,1,2,3,5
* n<=39
* */
public int Fibonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n== 2) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
/**
* 非递归方式，递归的数据结构使用的栈，那就是使用栈的方式
* */
public int NoRecursive(int n) {
if (n>2) {
int[] a = new int[n+1];
a[0] = 0;
a[1] = 1;
a[2] = 1;
for (int i=3; i<=n; i++) {
a[i] = a[i-1] + a[i-2];
}
return a[n];
} else {
if (n == 0) return 0;
else return 1;
}
}
public static void main(String[] args) {
System.out.println(new FeiBoNaQi().Fibonacci(39));
System.out.println(new FeiBoNaQi().Fibonacci(39));
}
}2. 직사각형 덮기
[주제]
21개의 작은 직사각형을 사용하여 가로 또는 세로로 더 큰 직사각형을 덮을 수 있습니다. 크기가 2*n인 큰 직사각형을 크기가 21인 n개의 작은 직사각형으로 겹치지 않고 덮는 방법은 몇 가지입니까?
예를 들어 n=3인 경우 2*3 직사각형 블록에는 3가지 덮는 방법이 있습니다.
코드:
package swear2offer.array;
public class Rectangle {
/**
* f[0] = 0;
* f[1] = 1;
* f[2] = 2;
* f[3] = 3;
* f[4] = 5;
* f[5] = 8;
* f[n] = f[n-1] + f[n-2]
* */
public int RectCover(int target) {
if (target < 4) return target;
int[] f = new int[target + 1];
int i;
for (i=0; i<4; i++) f[i] = i;
for (i=4; i<=target; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[target];
}
public static void main(String[] args) {
System.out.println(new Rectangle().RectCover(5));
}
}[Thinking]
문제를 해결하는 가장 간단한 방법은 규칙을 찾는 것입니다. , 요약된 규칙을 보면 이것이 피보나치 수열을 구현하는 방법임을 알 수 있으며, 다른 하나는 문제의 의미에 따라 답을 찾고 n의 방법을 찾는 것이라고 생각하면 쉽습니다. n-1의 문제이고 첫 번째 블록은 수평(f[n-2])이고 수직(f[n-1])이며 다양한 상황에 해당합니다.
(관련 인터뷰 질문 권장: java 인터뷰 질문 및 답변)
3.2진수 1
[제목]
정수를 입력하고 1의 개수를 이진수로 출력합니다. 음수는 2의 보수로 표현됩니다.
【코드】
package swear2offer.array;
public class Binary {
/**
* 输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
* */
public int NumberOf1(int n) {
int count;
count = 0;
while(n != 0) {
n = n & (n-1);// 与操作就是二进制的操作，适用原码和补码
count ++;
}
return count;
}
}【생각】
음수의 일의 보수: 부호 비트는 그대로 유지되고, 나머지 비트는 반전됩니다. 음수의 보수: 일의 보수를 기준으로 +1.
정수가 0이 아닌 경우 이 정수의 최소 한 비트는 1입니다. 이 정수에서 1을 빼면 정수의 가장 오른쪽에 있는 원래 1은 0이 되고, 원래 1 뒤의 모든 0은 1이 됩니다(가장 오른쪽 1 뒤에 0이 있는 경우). 나머지 모든 비트는 영향을 받지 않습니다.
예: 이진수 1100의 경우 오른쪽에서 세 번째 숫자가 가장 오른쪽 1입니다. 1을 빼면 세 번째 자리는 0이 되고, 뒤따르는 두 개의 0은 1이 되고, 첫 번째 1은 그대로 남아 있으므로 결과는 1011이 됩니다. 1을 뺀 결과는 가장 오른쪽의 숫자가 바뀌는 것임을 알 수 있습니다. 1로 시작하는 모든 비트는 거꾸로. 이때, 원래 정수와 1을 뺀 결과를 AND 연산하면 원래 정수의 가장 오른쪽 1부터 시작하는 모든 비트가 0이 됩니다. 예를 들어, 1100&1011=1000 즉, 정수에서 1을 뺀 다음 원래 정수로 AND 연산을 수행하면 정수의 가장 오른쪽에 있는 1이 0으로 변합니다. 그러면 1은 개수만큼 나옵니다. 정수의 이진 시스템에 있는 것과 같은 연산입니다.
4. 값의 정수 거듭제곱
[제목]
double 유형의 부동 소수점 숫자 기반과 int 유형의 정수 지수가 제공됩니다. 지수승으로 거듭제곱된 밑수를 구합니다.
밑수와 지수가 동시에 0이 아닌지 확인하세요
[Code]
package swear2offer.array;
public class Power {
public double Power(double base, int exponent) {
if (base == 0) return 0;
if (exponent == 0) return 1;
int count;
boolean flag;
double temp;
count = 1;
temp = base;
flag = true;// 标记正负
if (exponent < 0){
exponent = -exponent;
flag = false;
}
while (count < exponent) {
base *= temp;
count ++;
}
if (flag) {
return base;
} else {
return 1/base;
}
}
public static void main(String[] args) {
System.out.println(new Power().Power(2,-3));
}
}[Thinking]
이 문제도 어렵지 않고, 알고리즘도 그리 복잡하지 않지만, 모퉁이를 놓치기 쉽습니다
첫 번째 포인트는 지수입니다. 음수의 양수와 음수를 놓치기 쉽습니다
둘째, 기수==0과 지수==0의 상황이 다릅니다
마지막으로 기수의 곱셈은 그 자체를 사용할 수 없습니다. 베이스는 계속 커지고 있어요.
5. 홀수가 짝수 앞에 오도록 배열의 순서를 조정하세요
[Title]
정수 배열을 입력하고 배열의 숫자 순서를 조정하는 함수를 구현하세요. 모든 홀수는 배열의 첫 번째 절반에 있고 모든 짝수는 배열의 두 번째 절반에 있으며, 홀수와 홀수, 짝수와 짝수 사이의 상대 위치가 변경되지 않은 상태로 유지되는지 확인하세요.
[코드]
package swear2offer.array;
import java.util.Arrays;
public class OddEven {
/**
* 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
* 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
* 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*
* 时空复杂度较高的算法：
* 新建一个数组b，用来保存奇数，在重新变量一次，保存偶数
* 时空复杂度0(n)
* */
public void reOrderArray1(int [] array) {
int n,i,j;
n = array.length;
int[] b = new int[n];
j = 0;// 用来保存数组B的下标
for (i=0; i<n; i++) {
if (array[i]%2 != 0) {
b[j] = array[i];
j ++;
}
}
for (i=0; i<n; i++) {
if (array[i]%2 == 0){
b[j] = array[i];
j++;
}
}
for (i=0; i<n; i++) {
array[i] = b[i];
}
}
/**
* 采用的冒泡交换以及快速排序的思想：
* 设定两个游标，游标分别用来标记奇数和偶数的下标，然后交换二者
* 注意交换二者是无法保证顺序的，交换的ij之间还有进行平移。
* */
public void reOrderArray(int [] array) {
int n,i,j,temp,p;
n = array.length;
i = 0;
j = 0;
while (i<n && j<n) {
// i标记偶数下标
while (i<n) {
if (array[i]%2 ==0){
break;
} else {
i++;
}
}
j = i;
// j标记奇数下标
while (j<n) {
if (array[j]%2 !=0){
break;
} else {
j++;
}
}
if (i<n && j<n) {
// 此时ij已经在遇到的第一个偶数和奇数停下，把ij之间的内容平移
temp = array[j];
for (p=j; p>i; p--) {
array[p] = array[p-1];
}
array[i] = temp;
// 此时把i,j标记到 未交换前的偶数位置的下一个
i ++;
j = i;
}
}
}
public static void main(String[] args) {
int[] a = {1,4,6,3,2,5,8};
int[] b = {2,4,6,1,3,5,7};
new OddEven().reOrderArray(b);
System.out.println(Arrays.toString(b));
}
}[생각]
분명히 새 배열을 만드는 방법은 까다로운 방법입니다. 두 번째 방법은 이 배열에서 작업을 수행해야 한다는 것입니다. . 연산, 그리고 이 이중 커서 발전 방식은 퀵 정렬의 개념에 매우 가깝습니다.
관련 권장 사항: Java 시작하기
위 내용은 Java 인터뷰의 일반적인 배열 질문 요약(2)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!