算法Leecode

算法Leecode

链表反转

反转一个单链表。

输入: 1->2->3->4->5
输出: 5->4->3->2->1

解法

• 迭代
• 递归

迭代

迭代，重复某一过程，每一次处理结果作为下一次处理的初始值。这些初始值类似于状态，每次处理都会改变状态，直至到达最终状态。

• 从前往后遍历链表；
• 将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev；
• 当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr；
• 处理完后要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next。

赋值变量：

1、将下一个节点指针保存到next变量 next = curr.next 2、将下一个节点的指针指向prev，curr.next = prev 3、准备处理下一个节点，将curr赋值给prev 4、将下一个节点赋值为curr，处理一个节点

递归

递归：以相似的方法重复，类似于树结构。先从根节点找到叶子节点，从叶子节点开始遍历大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr；

将所有的小问题解决，大问题即解决。

只需每个元素都执行两个步骤即可：

curr.next.next = curr;
curr.next = null;

为了保证链不断，必须从后往前，从最后一个元素开始遍历链表。

代码示例

public class ReverseList {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 迭代
    public static ListNode iterate(ListNode head) {
        ListNode prev = null, curr, next;
        curr = head;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 递归
    public static ListNode recursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // ListNode revNode = iterate(node1);
        ListNode revNode2 = recursion(node1);
        System.out.println(revNode2);
    }
}

统计N以内的素数

合数

合数指在大于1的自然数中，除了能被1和本身整除外，还能被其他数整除的数。

最小的合数是4。

素数（质数）

素数又叫质数，指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。

例如：7只能被1和7整除，除此之外不能再被其他数字整除，7就是质数。

最小的质数是2，它也是唯一的偶数质数，最前面的质数依次排列为：2、3、5、7、11、13、17、19、23、29、31等。

100以内的素数共计有25个。

解法

• 暴力算法
• 埃氏筛选

暴力算法

直接从2开始遍历，判断是否能被2到自身之间的数整除。

    public int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

• i++与++i的区别

  • i++ 是先使用 i 的值，再执行 i=i+1；
  • ++i 是先执行 i=i+1 ，再使用 i 的值；

  在上述的循环体中，i++ 和 ++i 的作用是一样的。但是性能是不同的，在大量数据的时候++i的性能要比i++的性能好。原因如下：

  • i++由于是在使用当前值之后再+1，所以需要一个临时的变量来转存。
  • 而++i则是在直接+1，省去了对内存的操作的环节，相对而言能够提高性能。

• i * i <= x 等价于 i < 根号x

  i如果能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可。

埃氏筛选

利用合数的概念(非素数)，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记。

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        return ans;
    }

• isPrime[j] = true;

  将合数标记为true

• int j = i * i;

  j = i * i 从 2 * i 优化而来，系数2会随着遍历递增（j += i，相当于递增了系数2），每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i 必然会遍历到这两个因子。

  当2递增到大于根号n时，其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n、实际上在 i 递增的过程中已经计算过了，i 实际上就相当于根号n。

  例如：

  n = 25 会计算以下2 * 4 = 8，3 * 4 = 12

  但实际上8和12已经标记过，在n = 17时已经计算了 3 * 4，2 * 4

寻找数组的中心索引

中心索引

数组中心索引是数组的一个索引（下标），其左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引,返回-1。

如果数组有多个中心索引,应该返回最靠近左边的那一个。

注意：中心索引可能出现在数组的两端。

思路

1. 首先求出数组长度，若长度为0，可直接返回-1，即找不到；

2. 接着调用sum函数，统计出整个数组的总和，记为total；

3. 然后从第一个元素开始叠加，总和递减当前元素，叠加递增当前元素，直到两个值相等。

4. 若循环结束仍未找到，则说明该数组无中心索引，返回-1。

时间复杂度分析：O（n）

空间复杂度分析：O（1）

AC代码示例

    public static int pivotIndex(int[] nums) {
        // 数组长度为0，直接返回-1
        if (nums.length == 0) {
            return -1;
        }
        int total = Arrays.stream(nums).sum();
        int sum2 = 0;
        for (int i = 0; i < nums.length; i++) {
            sum2 += nums[i];
            if (total == sum2) {
                return i;
            }
            total = total - nums[i];
        }
        return -1;
    }