1. Number of times a number appears in a sorted array

[Title]

Count the number of times a number appears in a sorted array.

(Learning video recommendation: java video tutorial)

[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]

Since the array is a Sorted array, so binary search can be used to locate the first and last occurrence of k. The time complexity is O(logN)O(logN)

Prerequisite for binary search: ordering (When it comes to order, you must immediately think of two points!)

2. Find 1 2 3 … n

[Title]

Find 1 2 3 … n, request Keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.

[Code]

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

Thinking]

It is required that loops and judgments cannot be used, so recursion is used instead of loops, and short-circuit principle is used instead of judgments

The order of short-circuiting and execution is from left to right. After determining that the value of the first expression is false, there is no need to execute the second conditional statement. Because it is obvious that regardless of whether the second condition is true or false, the Boolean value of the entire expression must be false. Short-circuiting will skip the second conditional and not execute it. Based on these principles, the above results emerged. Flexible use of short-circuit and in programming is of great significance.

When n=0, sum=0, what follows && will not be executed, and sum=0 is returned directly

3. Cut the rope

[Title]

Given you a rope of length n, please cut the rope into m segments of integer length (m and n are both integers, n>1 and m>1), the length of each segment of rope is recorded as k [0],k[1],…,k[m]. What is the maximum possible product of k [0] xk [1] x...xk [m]? For example, when the length of the rope is 8, we cut it into three pieces with lengths 2, 3, and 3 respectively. The maximum product obtained at this time is 18.

【Code】

    /**
     * 給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長的 m 段（m、n 都是整數(shù)，n>1 并且 m>1），
     * 每段繩子的長度記為 k [0],k [1],...,k [m]。
     * 請問 k [0] xk [1] x...xk [m] 可能的最大乘積是多少？
     * 例如，當(dāng)繩子的長度是 8 時，
     * 我們把它剪成長度分別為 2、3、3 的三段，此時得到的最大乘積是 18。
     *
     * 使用動態(tài)規(guī)劃
     * 要點：邊界和狀態(tài)轉(zhuǎn)移公式
     * 使用順推法：從小推到大
     * 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是劃分的乘積小于自身，對狀態(tài)轉(zhuǎn)移會產(chǎn)生額外判斷
        if (target <= 3) return target-1;
        int[] dp = new int[target+1];
        int mid,i,j,temp;

        // 設(shè)定邊界
        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

 *
 * 使用動態(tài)規(guī)劃
 * 要點：邊界和狀態(tài)轉(zhuǎn)移公式
 * 使用順推法：從小推到大
 * dp[x] 代表x的最大值
 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍歷，取半即可
 * 但是需要注意。2和3這兩個特殊情況，因為他們的分解乘積比自身要大，所以特殊處理

(More related interview questions to share: java interview questions and answers)

4. The maximum value of the sliding window

[Title]

Given an array and the size of the sliding window, find the maximum value of all values ??in the sliding window. For example, if the input array is {2,3,4,2,6,2,5,1} and the size of the sliding window is 3, then there are a total of 6 sliding windows, and their maximum values ??are {4,4,6, 6,6,5}; There are the following 6 sliding windows for the array {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}, {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 {

    /**
     * 給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。
     * 例如，如果輸入數(shù)組 {2,3,4,2,6,2,5,1} 及滑動窗口的大小 3，
     * 那么一共存在 6 個滑動窗口，他們的最大值分別為 {4,4,6,6,6,5}
     *
     * 思路：
     * 先找出最開始size大小的最大值，以及這個最大值的下標(biāo)
     * 然后每次增加一個值，先判斷滑動窗口的第一位下標(biāo)是否超過保存最大值的下標(biāo)
     * 如果超過就要重新計算size區(qū)域的最大值，
     * 如果未超過就使用最大值與新增的元素比較，獲取較大的
     * */
    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;

        // 當(dāng)窗口大于數(shù)組長度
        if (num.length <= size) return list;

        // 把第一個滑動窗口最大值加入數(shù)組
        list.add(temp[0]);

        // 從新的窗口開始計算，上一個窗口的最大值和下標(biāo)保存在temp中
        for (i=size; i<num.length; i++) {
            // 上一個最大值還在滑動窗口區(qū)域內(nè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;
        // 當(dāng)窗口大于數(shù)組長度
        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;
    }

}

* Idea:

* First find the maximum value of the initial size and the subscript of this maximum value

* Then each time a value is added, first determine whether the first subscript of the sliding window exceeds the subscript that saves the maximum value

* If it exceeds, the maximum value of the size area must be recalculated,

* If it is not exceeded, use the maximum value to compare with the new element to obtain a larger value.

Additional supplement: For exceptions thrown, for example, in this question, the case of size>num.length is Throwing null, but I think it is the biggest throw, you should communicate with the interviewer at this time.

5. Repeated numbers in the array

[Title]

All numbers in an array of length n are in the range from 0 to n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated. I don't know how many times each number is repeated. Please find any repeated number in the array. For example, if the input is an array {2,3,1,0,2,5,3} of length 7, the corresponding output is the first repeated number 2.

【Code】

    /**
     * 在一個長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)。
     * 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。
     * 也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。
     * 例如，如果輸入長度為 7 的數(shù)組 {2,3,1,0,2,5,3}，
     * 那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字 2。
     *
     * 思路：
     * 看到 長度n，內(nèi)容為0-n-1；瞬間就應(yīng)該想到，元素和下標(biāo)的轉(zhuǎn)換
     *
     * 下標(biāo)存的是元素的值，對應(yīng)的元素存儲出現(xiàn)的次數(shù)，
     * 為了避免弄混次數(shù)和存儲元素，把次數(shù)取反，出現(xiàn)一次則-1，兩次則-2
     * 把計算過的位置和未計算的元素交換，當(dāng)重復(fù)的時候，可以用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) {
            // 獲取到數(shù)組元素
            res = numbers[i];
            // 判斷對應(yīng)位置的計數(shù)是否存在
            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;
    }

* Idea:

* When you see the length n and the content is 0-n-1; you should immediately think of the conversion of elements and subscripts

* The subscript stores the value of the element, and the corresponding element stores the number of occurrences.

* In order to avoid confusion between the number and the stored element, the number is inverted. If it appears once, -1. Twice then -2

* Exchange the calculated position with the uncalculated element. When repeated, you can use n instead

Related recommendations: Java Getting Started

The above is the detailed content of Summary of common array questions in Java interviews (5). For more information, please follow other related articles on the PHP Chinese website!