当先锋百科网

首页 1 2 3 4 5 6 7

单链表的反转

递归方式:

public Node preNode(Node head) {
        if(head == null || head.next == null)
            return head;
        Node preNode = preNode(head.next);
        head.next.next = head;
        head.next = null;
        return preNode;
    }

合并两个有序链表

public static Node mergeNode(Node node, Node node2) {
        Node head = new Node(-1);
        Node current = head;
        Node currentNode1 = node;
        Node currentNode2 = node2;
        while (currentNode1 != null && currentNode2 != null) {//注意此处是针对两个链表同等长度的情况,如果长度不同还要分开处理
            if (currentNode1.num <= currentNode2.num) {
                current.next = currentNode1;
                currentNode1 = currentNode1.next;
            } else {
                current.next = currentNode2;
                currentNode2 = currentNode2.next;
            }
            current = current.next;
        }
        return head.next;
    }

斐波那契数列问题

1、生兔子:有一对兔子,从出生后第四个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子。假如兔子都不死,计算第十个月兔子的总数?

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

2、跳台阶问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

    public static int jumpFloor(int n) {
        if (n <= 0)
            return 0;
        if (n <= 2)
            return n;
        return jumpFloor(n - 1) + jumpFloor(n - 2);
    }

给定一个数组arr,返回子数组的最大累加和

    private static int maxSum(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        int max = Integer.MIN_VALUE;
        int current = 0;
        for (int i = 0; i < array.length; i++) {
            current = current + array[i];
            max = Math.max(current, max);
            current = current < 0 ? 0 : current;
        }
        return max;
    }

给定一个数组arr、或者字符串,返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

    public static int maxLength(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;
        int maxLength = 0;
        int len = s.length();
        while (left < len && right < len) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return maxLength;
    }

改进版: 东西理解了之后发现就能创新

//最长无重复字符串
    public static int maxLength(String s) {
        int left = 0;
        int right = 0;
        int len = s.length();
        int maxLength = Integer.MIN_VALUE;
        Set<Character> set = new HashSet<>();
        while (left < len && right < len) {
            System.out.println("left = "+left+"; right = " + right);
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                set.clear();//原来是left ++ 一个一个删除,这回直接删除,比原来的节省时间
                left = right;
//                set.remove(s.charAt(left));
//                left++;
            }
        }
        return maxLength;
    }

给出一个整数数组,请在数组中找出两个加起来等于目标值的数,

    public static int[] sum(int[] data, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i =0;i<data.length;i++) {
            int value = target - data[i];
            if(map.containsKey(value)) {
                result[0] = i;
                result[1] = map.get(value);
                map.put(data[i], i);
            }
        }
        return result;
    }

数组a中只有一个数出现一次,其他数都出现了2次,找出这个数字

    public static int find1From2(int[] a){
        int len = a.length, res = 0;
        for(int i = 0; i < len; i++){
            res = res ^ a[i];
        }
        return res;
    }