질문 난이도: * *
(학습 영상 추천: java 강좌)
1. 정렬 순서
[제목]
데이터 [6,2]와 같은 숫자 배열의 정렬된 값을 반환합니다. ,5 ,0]은 [4,2,3,1]을 반환합니다
[Code]
package swear2offer.array;
import java.util.Arrays;
public class SortSequence {
/**
* 返回一个数字数组的排序值
* 比如数据 [6,2,5,0] 的返回是 [4,2,3,1]
* */
public int[] compare(int[] a) {
int i,j,n;
n = a.length;
int [] c = new int[n];
//数组下标从0开始，但是输出的次序从1开始，所以需要初始化数组为1
for (i=0; i<n; i++) {
c[i]++;
}
for (i=0; i<n; i++) {
for (j=0; j<i; j++) {
if (a[j]<a[i]) c[i]++;
else c[j]++;
}
}
return c;
}
public static void main(String[] args) {
int[] a = {6,2,5,0};
System.out.println(Arrays.toString(new SortSequence().compare(a)));
}
}[Thinking]
순서를 얻는 일반적인 방법은 각 요소를 다른 모든 요소와 비교한 다음 크기를 얻는 것입니다. order 인데 여기서는 사다리꼴 비교 순서를 사용합니다
6 6 2 6 2 5 6 2 5 0
비교할 때 비교 요소뿐만 아니라 비교 요소도 판단하는데, 이는 비교 횟수를 줄일 수 있는 if else 코드입니다.
2. 배열 첨자 보조 기록
[제목]
길이가 N이고 요소 값 범위가 [1, N]인 배열 a가 주어지면 각 요소의 발생 횟수와 필요한 시간 복잡도를 계산합니다. O(N)이면 공간 복잡도는 O(1)
[코드]
/**
* 这类要求空间O(1)时间复杂度为O(n)的问题
* 需要在一次遍历并且不声明新数组的情况下求解，这种题目通常要求元素大小跟下标大小一致。
* 所以通常考虑是利用数组存储的元素和数组下标来求解
* 在本题中，数组的元素变成了下标，而数组内元素则表示之前元素出现的次数，0则代表不出现。
* 为了区分元素和次数，可以把次数设定为负值
* */
public void Solution(int[] a) {
int i,n,temp;
n = a.length;
i = 0;
/**
* 只有在temp小于0的时候才会推进循环
* */
while(i < n) {
temp = a[i]-1;
// 如果数组元素小于0，则代表该数已经被替换到其他地方或者已经被计数过从而被覆盖
if (temp < 0) {
i ++;
continue;
}
// 把未记录的数保存在已经记录的位置上，并用负值保存数量
if (a[temp]>0) {
a[i] = a[temp];
a[temp] = -1;
} else {
a[i] = 0; //该数据已经使用过，且表示元素i+1出现0次
a[temp]--;
}
}
}(권장 그래픽 튜토리얼: java 인터뷰 질문 및 답변)
3 정렬된 2차원 배열의 요소 찾기
[제목]
2차원 배열(각각의 1차원 배열은 길이가 동일함)에서는 각 행은 왼쪽에서 오른쪽으로 오름차순으로 정렬되고, 각 열은 위에서 아래로 오름차순으로 정렬됩니다. 함수를 완성하고, 이러한 2차원 배열과 정수를 입력하고, 배열에 정수가 포함되어 있는지 확인하세요.
[코드]
package swear2offer.array;
public class ArrayFind {
/**
* 在一个二维数组中（每个一维数组的长度相同），
* 每一行都按照从左到右递增的顺序排序，
* 每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，
* 判断数组中是否含有该整数。
*
* 思路：
* 从左上出发，需要考虑的情况太多，因为向右和向下都是递增
* 但是从右上出发，向左递减，向下递增，这样就把情况限定在一种。
* */
public boolean Find(int target, int [][] array) {
int l,h,x,y;
h = array.length;
l = array[0].length;
// 游标的横纵坐标
x = l-1;
y = 0;
while (x>=0 && y<h) {
if(array[y][x] == target) {
return true;
}
if (array[y][x]<target) {
y++;
} else {
x--;
}
}
return false;
}
public static void main(String[] args) {
int[][] a = {{1,3,5,6},{2,4,7,8},{5,8,9,12}};
System.out.println(new ArrayFind().Find(11,a));
}
}[생각]
왼쪽 위에서 시작해서 오른쪽, 아래로 갈수록 둘 다 늘어나는데, 오른쪽 위에서 시작해서 왼쪽으로 줄어들다가 아래쪽으로 늘어나기 때문에 고려해야 할 상황이 너무 많아요. 그래서 상황은 하나로 제한됩니다. 특수 배열, 배열의 특수성을 최대한 활용하고 다양한 방향의 방법을 고려합니다.
4. 계단오르기
[주제]
개구리는 한 번에 1단계 또는 2단계씩 점프할 수 있습니다. 개구리가 n레벨 단계를 뛰어넘을 수 있는 방법이 몇 가지인지 알아보세요(다른 결과는 다른 순서로 계산됩니다).
[코드]
package swear2offer.array;
public class Floors {
/**
* 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。
* 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
*
* 获取跳法次数
* */
public int JumpFloor(int target) {
if (target < 3) return target;
// 大于等于3个台阶，次数是第一步调1下和跳2下的个数之和
return JumpFloor(target-1) + JumpFloor(target-2);
}
}5. 비정상적인 점프 계단
[제목]
개구리는 한 번에 1레벨씩 올라갈 수도 있고, 2레벨씩 올라갈 수도 있고... n레벨까지 올라갈 수도 있습니다. 개구리가 n층 계단을 뛰어오르는 방법의 총 횟수를 구하세요.
【코드】
package swear2offer.array;
import java.util.Arrays;
public class FloorsPlus {
/**
* 一只青蛙一次可以跳上 1 级台阶，
* 也可以跳上 2 级…… 它也可以跳上 n 级。
* 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
*
* 动态规划：数组代表含义、边界、转换公式
* 动态规划最重要的是找出阶段之间的变化公式，
* 即，n-1和n之间的状态是如何转移的
*
* f[n]:n阶台阶的跳法
* f[n] = f[n-1]+f[n-2]+...+f[1]+f[0]
* f[n-1]代表最后一步走了1步
* f[n-2]代表最后一步走了2步
* f[1]代表最后一步走了n-1步
* f[0]代表最后一步走了n步
*
* 这里需要注意，f[0]=0,但是最后一步走了n步也算一种方法，
* 所以需要初始化把数组初始化为1，或则单独处理f[0].
*
* */
public int JumpFloorII(int target) {
if (target < 3) return target;
int[] f = new int[target+1];
//单独处理f[0]
f[0] = 1;
f[1] = 1;//边界
int i,j;
for (i=2; i<=target; i++) {
for (j=i-1; j>=0; j--) {
f[i] += f[j];
}
}
return f[target];
}
public int JumpFloorII2(int target) {
if (target < 3) return target;
int[] f = new int[target+1];
//初始化把数组初始化为1
Arrays.fill(f,1);
f[0] = 0;
f[1] = 1;//边界
int i,j;
for (i=2; i<=target; i++) {
for (j=i-1; j>0; j--) {
f[i] += f[j];
}
}
return f[target];
}
}관련 추천: Java 시작하기
위 내용은 Java 인터뷰의 일반적인 배열 질문 요약(1)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
뜨거운 도구
안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
맨티스BT
Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.
VSCode Windows 64비트 다운로드
Microsoft에서 출시한 강력한 무료 IDE 편집기
WebStorm Mac 버전
유용한 JavaScript 개발 도구
