Summary of common array questions in Java interviews (2)

1. Fibonacci Sequence

[Topic]

Everyone knows the Fibonacci Sequence. Now we are asked to enter an integer n. Please output the nth term of the Fibonacci sequence (starting from 0, the 0th term is 0).

(Video tutorial recommendation: java course)

[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. Rectangular coverage

[Title]

We can use the small rectangle of 21 to cover the larger rectangle horizontally or vertically. How many ways are there to cover a large 2*n rectangle with n small rectangles of size 21 without overlapping?

For example, when n=3, there are 3 covering methods for a 2*3 rectangular block:

Code:

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 】

The most straightforward way to solve the problem is to find the rules. From the summarized rules, we can see that this is the way to realize the Fibonacci sequence; the other is to answer the question according to the meaning of the question and find the method of n. , it is easy to think of solving this type of problem from n-1, and the first block is horizontal (f[n-2]) or vertical (f[n-1]), corresponding to different situations

(Recommendations for more related interview questions: java interview questions and answers)

3. The number of 1’s in binary

[Topic]

Input an integer and output the number of 1's in the binary representation of the number. Negative numbers are expressed in two's complement.

[Code]

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;
    }
}

[Thinking]

The one's complement of a negative number: The sign bit remains unchanged, and the remaining bits are inverted bit by bit. The complement of a negative number: in its one's complement On the basis of 1

If an integer is not 0, then at least one bit of this integer is 1. If we subtract 1 from this integer, then the original 1 on the rightmost side of the integer will become 0, and all the 0s after the original 1 will become 1 (if there are 0s after the rightmost 1). All remaining bits will be unaffected.

For example: a binary number 1100, the third digit from the right is the rightmost 1. After subtracting 1, the third digit becomes 0, the two following 0s become 1, and the previous 1 remains unchanged, so the result is 1011. We find that the result of subtracting 1 is to change the rightmost one All bits starting with 1 are inverted. At this time, if we do the AND operation between the original integer and the result after subtracting 1, all bits starting from the rightmost 1 of the original integer will become 0. For example, 1100&1011=1000. In other words, if you subtract 1 from an integer and then perform an AND operation with the original integer, the 1 on the rightmost side of the integer will be turned into 0. Then there are as many 1's as there are in the binary system of an integer. times such an operation.

4. Integer power of a value

[Title]

Given a floating-point number base of double type and an integer exponent of type int. Find base raised to the exponent power.
Ensure that base and exponent are not 0 at the same time

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

This question is not difficult, and the algorithm is not very complicated, but the edge It is easy to miss corners and corners.

The first point is the positive and negative of exponent. It is easy to miss the negative number

Secondly, the cases of base==0 and exponent==0 are What’s different

Finally, when base is multiplied cumulatively, it cannot be used by itself, because base is constantly getting bigger.

5. Adjust the order of the array so that odd numbers are in front of even numbers

[Topic]

Input an array of integers and implement a function to adjust the order of numbers in the array so that all The odd numbers are located in the first half of the array, and all the even numbers are located in the second half of the array, ensuring that the relative positions between odd numbers and odd numbers, and even numbers and even numbers remain unchanged.

[Code]

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));
    }
}

[Thinking]

Obviously, the way to create a new array is a tricky way. The question requires that operations be performed on this array. , the second method is to operate on this array, and this dual-cursor progressive method is very close to the idea of ​​quick sort.

Related recommendations:Getting started with java

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