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 {

    /**
     * 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù) n，
     * 請(qǐng)你輸出斐波那契數(shù)列的第 n 項(xiàng)（從 0 開(kāi)始，第 0 項(xiàng)為 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);
    }

    /**
     * 非遞歸方式，遞歸的數(shù)據(jù)結(jié)構(gòu)使用的棧，那就是使用棧的方式
     * */
    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 {

    /**
     * 輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。
     * */
    public int NumberOf1(int n) {
        int count;
        count = 0;

        while(n != 0) {
            n = n & (n-1);// 與操作就是二進(jìn)制的操作，適用原碼和補(bǔ)碼
            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;// 標(biāo)記正負(fù)

        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 {

    /**
     * 輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，
     * 使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，
     * 并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
     *
     * 時(shí)空復(fù)雜度較高的算法：
     * 新建一個(gè)數(shù)組b，用來(lái)保存奇數(shù)，在重新變量一次，保存偶數(shù)
     * 時(shí)空復(fù)雜度0(n)
     * */
    public void reOrderArray1(int [] array) {
        int n,i,j;
        n = array.length;

        int[] b = new int[n];

        j = 0;// 用來(lái)保存數(shù)組B的下標(biāo)
        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];
        }
    }

    /**
     * 采用的冒泡交換以及快速排序的思想：
     * 設(shè)定兩個(gè)游標(biāo)，游標(biāo)分別用來(lái)標(biāo)記奇數(shù)和偶數(shù)的下標(biāo)，然后交換二者
     * 注意交換二者是無(wú)法保證順序的，交換的ij之間還有進(jìn)行平移。
     * */
    public void reOrderArray(int [] array) {

        int n,i,j,temp,p;

        n = array.length;
        i = 0;
        j = 0;
        while (i<n && j<n) {
            // i標(biāo)記偶數(shù)下標(biāo)
            while (i<n) {
                if (array[i]%2 ==0){
                    break;
                } else {
                    i++;
                }
            }
            j = i;
            // j標(biāo)記奇數(shù)下標(biāo)
            while (j<n) {
                if (array[j]%2 !=0){
                    break;
                } else {
                    j++;
                }
            }
            if (i<n && j<n) {
                // 此時(shí)ij已經(jīng)在遇到的第一個(gè)偶數(shù)和奇數(shù)停下，把ij之間的內(nèi)容平移
                temp = array[j];
                for (p=j; p>i; p--) {
                    array[p] = array[p-1];
                }
                array[i] = temp;
                // 此時(shí)把i,j標(biāo)記到 未交換前的偶數(shù)位置的下一個(gè)
                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!