Af3185c1d5f39dffcb190608b3fbfb4b
学而思2020春招算法题

今天学弟分享了一下学而思2020年春招算法题,整理一下,希望对有需要的小伙伴有帮助

[TOC]

斐波那契数列

题干

  有一对兔子,3个月后,每个月都会生一对兔子,生下的兔子过了3个月,也会每月生一对兔子,假设兔子不会死亡,n个月后总共有多少兔子?

思路

  这道题我们可以首先列一下前几个月的兔子数,找一下有没有什么规律。

  可以看到这是一个斐波那契数列,这里给出两种解法,分别是递归法,和动态规划法。(这里建议使用动态规划法,递归法存在大量的重复计算,即f(5) = f(4) + f(3),但是f(4),f(3)在之前的运算中就已经计算过了,此时是重复计算)

代码

递归法:

public int function(int n){
    if(n == 1 || n == 2){
        return 1;
    }
    return function(n - 1) + function(n - 2);
}

动态规划法:

public int function(int n){
    if(n <= 2){
        return 1;
    }
    int pre1 = 1;
    int pre2 = 2;
    for(int i = 3;i <=n; i++){
        int cur = pre1 + pre2;
        pre1 = pre2;
        pre2 = cur;
    }
    return pre1;
}

数组问题

题干

  输入一个升序数组和一个整数,如果这个数在数组里则返回下标,不在数组里面,就插入到数组,然后返回下标。

思路

  这道题就比较有意思了,解法有很多种,java中的数组不支持动态扩容,所以需要我们去写扩容和数据搬移的逻辑,这里首先先给出一个取巧的办法,我们可以把数组放到ArrayList里,然后利用ArrayList支持动态扩容的特性,来解决这个问题(方法1)。当然我们也可以手写这部分逻辑(方法2)

代码

方法1:

public class Main {
    private int position;

    private Integer[] getOrInsertElement(Integer[] arr, int target) {
        List<Integer> list = new ArrayList<>(Arrays.asList(arr));
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) <= target){
                position = i;
            }
        }
        if(list.get(position) != target){
            position++;
            list.add(position,target);
        }
        Integer[] newArr = new Integer[list.size()];
        return list.toArray(newArr);
    }
}

方法2:

public class Main {

    private int position;

    private int[] getOrInsertElement(int[] arr, int target) {
        // 输入校验
        if (arr == null || arr.length == 0) {
            throw new RuntimeException("输入数据非法!");
        }
        int max = arr[arr.length - 1];
        // 扩容位置在数组末尾
        if (target > max) {
            return insertTargetElement(arr, target, arr.length - 1);
        }
        //查询数组中,小于等于target的第一个位置
        int pos = getMinOrEqualsTargetPosition(arr, target);
        if (arr[pos] == target) {
            this.position = pos;
            return arr;
        }
        return insertTargetElement(arr, target, pos);
    }

    private int[] insertTargetElement(int[] arr, int target, int pos) {
        // 扩容
        int[] newArr = Arrays.copyOf(arr, arr.length + 1);
        // 数据搬运
        System.arraycopy(arr, pos, newArr, pos + 1, arr.length - pos);
        newArr[pos + 1] = target;
        this.position = pos + 1;
        return newArr;
    }

    private int getMinOrEqualsTargetPosition(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        int result = 0;
        while (i <= j) {
            int mid = i + ((j - i) >> 1);
            if (arr[mid] < target) {
                i = mid + 1;
                result = mid;
            } else if (arr[mid] > target) {
                j = mid - 1;
            } else {
                return mid;
            }
        }
        return result;
    }
}

测试代码:

public static void main(String[] args) {
    int[] arr = {1, 4, 5, 6, 7, 8, 10};
    Main main = new Main();
    int[] newArr = main.getOrInsertElement(arr, 11);
    System.out.println("原数组:" + Arrays.toString(arr));
    System.out.println("目标值下标:" + main.position);
    System.out.println("扩容后的数组:" + Arrays.toString(newArr));
}

  最后,期待您的订阅和点赞,专栏每周都会更新,希望可以和您一起进步,同时也期待您的批评与指正!

© 著作权归作者所有
这个作品真棒,我要支持一下!
一个坚持原创的小专栏。分享编程知识,提升工作效率,致力于通过简单的语言,把编程这点事讲清楚。涵盖内容:java、设...
0条评论
top Created with Sketch.