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

1. 정렬된 배열에 숫자가 나타나는 횟수

[제목]

정렬된 배열에 숫자가 나타나는 횟수를 셉니다.

(학습 영상 추천: java 영상 튜토리얼)

[Code]

public int GetNumberOfK(int [] array , int k) {

        if (array.length==0 || array==null) return 0;

        int i,n,count;
        n = array.length;

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

        return count;
    }

    public int high(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] <= k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }

    public int low(int[] a, int k) {
        int start,end,mid;

        start = 0;
        end = a.length-1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (a[mid] >= k) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }

[Thinking]

배열은 정렬된 배열이므로 이진 검색 방법을 사용하여 k가 처음 나타나는 위치와 마지막 발생 위치, 시간 복잡도는 O(logN)O(logN)

두 점의 전제: 순서(순서는 두 점을 즉시 생각해야 합니다!)

2. 3+ …+n

[제목]

1+2+3+…+n을 찾으세요. 곱셈과 나눗셈, while, if, else, switch, Case 및 기타 키워드와 조건문을 사용할 수 없습니다. 판단 진술(A?B:C).

【Code】

	public int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && (sum += Sum_Solution(n-1))>0;
        return sum;
    }

Thinking】

루프와 판단을 사용할 수 없으므로 루프 대신 재귀를 사용하고 판단 대신 단락 원리를 사용합니다

단락 및 실행 순서는 다음과 같습니다. 왼쪽에서 오른쪽으로 첫 번째 조건문을 결정한 후 표현식이 false로 평가된 후에는 두 번째 조건문을 실행할 필요가 없습니다. 두 번째 조건이 참인지 거짓인지에 관계없이 전체 표현식의 불리언 값이 거짓이어야 한다는 것은 명백하기 때문입니다. 단락은 두 번째 조건을 건너뛰고 실행하지 않습니다. 이러한 원칙을 바탕으로 위와 같은 결과가 나왔습니다. 단락 회로와 프로그래밍에서의 유연한 사용은 매우 중요합니다.

n=0, sum=0이면 && 뒤에 오는 내용은 실행되지 않고 sum=0이 바로 반환됩니다

3. 밧줄을 자르세요

[제목]

길이 n의 밧줄을 드립니다 , 로프를 정수 길이의 m개 섹션(m과 n은 모두 정수, n>1 및 m>1)으로 자르고, 로프의 각 섹션 길이는 k[0], k[1]로 기록됩니다. .., k [m]. k [0] xk [1] x...xk [m]의 가능한 최대 곱은 무엇입니까? 예를 들어 줄의 길이가 8이라면 각각 길이가 2, 3, 3인 3개의 조각으로 잘라냅니다. 이때 얻을 수 있는 최대 제품은 18개입니다.

[코드]

    /**
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（m、n 都是整数，n>1 并且 m>1），
     * 每段绳子的长度记为 k [0],k [1],...,k [m]。
     * 请问 k [0] xk [1] x...xk [m] 可能的最大乘积是多少？
     * 例如，当绳子的长度是 8 时，
     * 我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。
     *
     * 使用动态规划
     * 要点：边界和状态转移公式
     * 使用顺推法：从小推到大
     * dp[x] 代表x的最大值
     * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可
     * */
    public int cutRope(int target) {

        // 由于2,3是划分的乘积小于自身，对状态转移会产生额外判断
        if (target <= 3) return target-1;
        int[] dp = new int[target+1];
        int mid,i,j,temp;

        // 设定边界
        dp[2] = 2;
        dp[3] = 3;

        for (i=4; i<=target; i++) {
            // 遍历到中间即可
            mid = i >> 1;
            // 暂存最大值
            temp = 0;
            for (j=1; j<=mid; j++) {
                if (temp < j*dp[i-j]) {
                    temp = j*dp[i-j];
                }
            }
            dp[i] = temp;
        }

        return dp[target];

    }

Thinking

 *
 * 使用动态规划
 * 要点：边界和状态转移公式
 * 使用顺推法：从小推到大
 * dp[x] 代表x的最大值
 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可
 * 但是需要注意。2和3这两个特殊情况，因为他们的分解乘积比自身要大，所以特殊处理

(추가로 공유할 인터뷰 질문: java 인터뷰 질문 및 답변)

4 슬라이딩 윈도우의 최대값

[질문]

배열 제공 슬라이딩 윈도우의 크기, 슬라이딩 윈도우의 모든 값 중 최대값을 찾습니다. 예를 들어, 입력 배열이 {2,3,4,2,6,2,5,1}이고 슬라이딩 윈도우의 크기가 3이라면 총 6개의 슬라이딩 윈도우가 있고 최대값은 ​​{4,4,6, 6,6,5}입니다. 배열 {2,3,4,2,6,2,5,1}에 대해 다음과 같은 6개의 슬라이딩 창이 있습니다. 4],2,6,2,5 ,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5 ,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4 ,2,6,[2,5,1]}.

【Code】

package swear2offer.array;

import java.util.ArrayList;

public class Windows {

    /**
     * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
     * 例如，如果输入数组 {2,3,4,2,6,2,5,1} 及滑动窗口的大小 3，
     * 那么一共存在 6 个滑动窗口，他们的最大值分别为 {4,4,6,6,6,5}
     *
     * 思路：
     * 先找出最开始size大小的最大值，以及这个最大值的下标
     * 然后每次增加一个值，先判断滑动窗口的第一位下标是否超过保存最大值的下标
     * 如果超过就要重新计算size区域的最大值，
     * 如果未超过就使用最大值与新增的元素比较，获取较大的
     * */
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        int i;
        int[] temp;
        temp = getMax(num,0,size);

        if (size<=0 || num==null || num.length==0) return list;

        // 当窗口大于数组长度
        if (num.length <= size) return list;

        // 把第一个滑动窗口最大值加入数组
        list.add(temp[0]);

        // 从新的窗口开始计算，上一个窗口的最大值和下标保存在temp中
        for (i=size; i<num.length; i++) {
            // 上一个最大值还在滑动窗口区域内
            if (i-size < temp[1]) {
                if (temp[0] < num[i]) {
                    temp[0] = num[i];
                    temp[1] = i;
                }
            } else {
                temp = getMax(num,i-size+1,size);
            }
            list.add(temp[0]);
        }

        return list;
    }

    public int[] getMax (int[] num, int s, int size) {
        int [] res = new int[2];
        int e = s + size;
        // 当窗口大于数组长度
        if (e>num.length) e = num.length;

        int temp = Integer.MIN_VALUE;
        int k = 0;
        for (int i=s; i<e; i++) {
            if (temp < num[i]) {
                temp = num[i];
                k = i;
            }
        }

        res[0] = temp;
        res[1] = k;

        return res;
    }

}

* 아이디어:

* 먼저 초기 크기의 최대값과 이 최대값의 첨자를 구합니다.

* 그런 다음 값이 추가될 때마다 먼저 슬라이딩 윈도우의 첫 번째 위치를 결정합니다. 첨자가 최대값을 저장하는 첨자를 초과하는지 여부

* 초과하는 경우 크기 영역의 최대값을 다시 계산하고,

* 초과하지 않는 경우 최대값을 사용하여 새 요소와 비교하여 더 큰 값을 얻습니다.

추가 보충 사항 : 이 질문과 같이 예외가 발생하는 경우 size>num.length가 발생하면 null이 발생하지만 가장 큰 발생이라고 생각하므로 이때 면접관과 의사 소통해야합니다.

5. 배열에서 반복되는 숫자

[제목]

길이가 n인 배열의 모든 숫자는 0에서 n-1 사이에 있습니다. 배열의 일부 숫자가 반복되는데, 얼마나 많은 숫자가 반복되는지 알 수 없습니다. 각 숫자가 몇 번이나 반복되는지 모르겠습니다. 배열에서 반복되는 숫자를 찾아보세요. 예를 들어 입력이 길이 7의 배열 {2,3,1,0,2,5,3}인 경우 해당 출력은 처음 반복되는 숫자 2입니다.

【Code】

    /**
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的。
     * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * 例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，
     * 那么对应的输出是第一个重复的数字 2。
     *
     * 思路：
     * 看到 长度n，内容为0-n-1；瞬间就应该想到，元素和下标的转换
     *
     * 下标存的是元素的值，对应的元素存储出现的次数，
     * 为了避免弄混次数和存储元素，把次数取反，出现一次则-1，两次则-2
     * 把计算过的位置和未计算的元素交换，当重复的时候，可以用n代替
     * */
    public boolean duplicate(int numbers[],int length,int [] duplication) {

        if (length == 0 || numbers == null) {
            duplication[0] = -1;
            return false;
        }

        int i,res;
        i = 0;
        while (i < length) {
            // 获取到数组元素
            res = numbers[i];
            // 判断对应位置的计数是否存在
            if (res < 0 || res == length) {
                i++;
                continue;
            }

            if (numbers[res] < 0) {
                numbers[res] --;
                numbers[i] = length;
                continue;
            }

            numbers[i] = numbers[res];
            numbers[res] = -1;
        }

        res = 0;
        for (i=0; i<length; i++) {
            if (numbers[i] < -1) {
                duplication[res] = i;
                return true;
            }
        }

        return false;
    }

* 아이디어:

* 길이 n을 보고 내용이 0-n-1이면 바로 요소와 첨자의 변환을 떠올려야 합니다

* 첨자는 의 값을 저장합니다 에 해당하는 요소는 발생 횟수를 저장합니다.

* 횟수와 저장된 요소의 혼동을 피하기 위해 한 번 나타나면 -1, 두 번 나타나면 숫자를 반전시킵니다. it will -2

* 계산된 위치를 계산되지 않은 요소와 교환합니다. 반복할 때 대신 n을 사용할 수 있습니다

관련 권장 사항: Java 시작하기

위 내용은 Java 인터뷰의 일반적인 배열 질문 요약(5)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!