Java 인터뷰의 일반적인 배열 질문 요약(3)-Java인터뷰 질문들-php.cn

Java 인터뷰의 일반적인 배열 질문 요약(3)

등급: *****

1. 행렬을 시계방향으로 인쇄하세요

(학습동영상 공유: java 강좌)

[제목]

행렬을 바깥쪽에서 안쪽으로 입력하세요. 각각 인쇄하세요. 예를 들어 다음과 같은 4개의 12,16,15,14,13,9,5,6,7,11,10.

[Code]

public ArrayList<Integer> printMatrix(int [][] matrix) {

        int width,height,x,y,count,n;
        height = matrix.length;
        width = matrix[0].length;
        // 遍历游标
        x = 0;
        y = 0;
        count = 0;
        // 元素个数
        n = height * width;

        boolean[][] flag = new boolean[height][width];
        ArrayList<Integer> list = new ArrayList<>();

        while (count < n) {
            // x不变，y增加
            while (y<width && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                y ++;
            }
            y--;
            x++;
            // x增加，y不变
            while (x<height && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                x ++;
            }
            x--;
            y--;
            // x不变，y减少
            while (y>=0 && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                y--;
            }
            y++;
            x--;
            // x变少，y不变
            while (x>=0 && !flag[x][y]) {
                list.add(matrix[x][y]);
                flag[x][y] = true;
                count ++;
                x--;
            }
            x++;
            y++;
        }


        return list;
    }

로그인 후 복사

[Thinking]

을 입력하면 경계를 넘었는지, 커서(x, y)가 x++를 통과하는지 주의를 기울이십시오. 또는 위치 지정이 있는 y++ 이후에는 수동 회전이 필요합니다.

2. 배열의 절반 이상 나타나는 숫자

[제목]

배열의 길이의 절반 이상 나타나는 숫자가 있습니다. 예를 들어 길이가 9인 배열 {1,2,3,2,2,2,5,4,2}를 입력합니다. 배열 길이의 절반보다 긴 숫자 2가 배열에 5번 나타나므로 2가 출력됩니다. 존재하지 않으면 0을 출력한다.

【Code】

package swear2offer.array;

import java.util.Arrays;

public class Half {

    /**
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。
     * 由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。
     * */
    public int MoreThanHalfNum_Solution(int [] array) {

        int n,count,i,k;

        n = array.length;

        if (n == 0) return 0;

        if (n == 1) return array[0];

        // 标记数组
        int[] flag = new int[n];
        // 给数组排序
        Arrays.sort(array);

        count = 1;
        flag[0] = 1;
        for (i=1; i<n; i++) {
            // 因为是排序好的，如果存在相等的
            if (array[i-1] == array[i]) {
                count ++;
            } else {
                count = 1;
            }
            flag[i] = count;
        }

        count = 0;
        k = 0;
        for (i=1; i<n; i++) {
            if (count < flag[i]) {
                count = flag[i];
                k = i;
            }
        }

        return count > n/2 ? array[k] : 0;

    }
}

로그인 후 복사

(추천 관련 면접 질문 : java 면접 질문과 답변)

【Code 2】

기발한 정렬 방법 :

preValue를 사용하여 마지막 방문 값 기록, count 현재 값이 나타나는 횟수를 나타냅니다. 다음 값이 현재 값과 같으면 count++; 0으로 감소하면 새 preValue 값을 교체해야 합니다. 배열 길이의 절반을 초과하는 값, 최종 preValue 이 값이어야 합니다.

	public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0)return 0;
        int preValue = array[0];//用来记录上一次的记录
        int count = 1;//preValue出现的次数（相减之后）
        for(int i = 1; i < array.length; i++){
            if(array[i] == preValue)
                count++;
            else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        int num = 0;//需要判断是否真的是大于1半数
        for(int i=0; i < array.length; i++)
            if(array[i] == preValue)
                num++;
        return (num > array.length/2)?preValue:0;
 
    }

로그인 후 복사

[생각]

0이 아닌 1부터 시작하는 경우 요소가 하나만 있는 경우 일반적으로 특별한 고려가 필요합니다

3. 연속 하위 배열의 최대 합

[주제]

배열이 주어지면 반환합니다. 최대 연속 하위 시퀀스의 합(예: {6,-3,-2,7,-15,1,2,2}), 연속 하위 벡터의 최대 합은 8입니다(0번째부터 3번째까지). )

[코드]

	/**
     * 给一个数组，返回它的最大连续子序列的和
     *
     * 例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为 8 (从第 0 个开始，到第 3 个为止)
     *
     * 非常典型的dp
     *
     * 动规通常分为顺推和逆推两个不同的方向
     * 要素：边界，状态转移公式，数组代表含义
     * array[]
     * dp[x],从各个正数开始连续到达x时，最大和，即连续子序列的最大和
     * 需要注意：1.从第一个正数开始，2.是连续序列
     * 通常情况下，连续序列的复杂度为O(n),非连续序列为O(n*n)
     * */
    public int FindGreatestSumOfSubArray(int[] array) {
        int n,i,len,res;
        int[] dp;

        n = array.length;

        if (n == 0 || array == null) return 0;
        if (n == 1) return array[0];

        dp = new int[n];
        dp[0] = array[0];
        len = 0;
        res = array[0];
        for (i=1; i<n; i++) {
            len = dp[i-1] + array[i];

            if (dp[i-1] < 0) {
                dp[i] = array[i];
            } else {
                dp[i] = len;
            }

            if (res < dp[i]) res = dp[i];
        }

        return res;
    }

로그인 후 복사

[아이디어]

앞에서 뒤로 트래버스합니다. 가장 큰 연속 부분 수열의 합은 현재 요소와 이전의 가장 큰 연속 부분 수열의 합을 겹쳐서 형성됩니다. 이전의 가장 큰 연속 하위 시퀀스의 합이 0보다 크면 계속해서 누적할 수 있고, 0보다 작으면 이전 하위 시퀀스를 버리고 현재 숫자부터 다시 누적을 시작해야 합니다. 시간 복잡도는 O(n)

4입니다. 정수에서 1이 나타나는 횟수

[제목]

1부터 13까지의 정수에서 1이 나타나는 횟수를 구하고, 1에서 1이 나타나는 횟수를 계산하세요. 100에서 1300까지의 정수? 그래서 그는 1부터 13까지 1이 포함된 숫자를 특별히 세었다. 1, 10, 11, 12, 13이라 총 6번 등장했지만 다음 문제에서는 당황했다. ACMer는 여러분이 그를 도와 문제를 보다 일반화하여 음이 아닌 정수 간격(1에서 n까지 1의 발생 횟수)에서 1의 발생 횟수를 빠르게 찾을 수 있기를 바랍니다.

[코드]

public int NumberOf1Between1AndN_Solution(int n) {
        if (n == 1) return 1;

        int nCount,i,j;
        nCount = 0;

        for (i=1; i<=n; i++) {
            j = i;
            while (j > 0) {
                if (j%10 == 1) nCount++;
                j = j/10;
            }
        }

        return nCount;

    }

로그인 후 복사

[생각]

재귀를 사용하여 작성하지 마세요. 가장 간단한 루프가 가능합니다

5. 보기 흉한 숫자

[제목]

소인수 2, 3만 포함하는 숫자의 이름을 지정하세요. 그리고 5개의 추악한 숫자. 예를 들어 6과 8은 모두 보기 흉한 숫자이지만 14는 소인수 7을 포함하기 때문에 그렇지 않습니다. 우리는 1을 최초의 추악한 숫자로 간주하는 것이 관례입니다. N번째 추악한 숫자를 오름차순으로 찾아보세요.

【코드】

	/**
     * 把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
     * 例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。
     * 习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
     *
     * 从已有的丑数中选取一个，分别*2，*3，*5，再取最小的
     * 最小的索引++，并赋值
     * */
    public int GetUglyNumber_Solution(int index) {
        if (index == 0) return 0;

        int p2,p3,p5,i,temp;

        p2 = p3 = p5 = 0;

        int[] res = new int[index];
        res[0] = 1;

        for (i=1; i<index; i++) {

            res[i] = Math.min(res[p2]*2,Math.min(res[p3]*3,res[p5]*5));

            if (res[i] == res[p2]*2) p2++;
            if (res[i] == res[p3]*3) p3++;
            if (res[i] == res[p5]*5) p5++;
        }

        return res[index-1];
    }

로그인 후 복사

【생각하기】

특정 속성을 가진 시퀀스를 정렬할 때 이 방법을 고려할 수 있습니다.