1 反转链表
1.1 题目
反转链表
反转一个单链表。
输入: 1->2->3->4->5
输出: 5->4->3->2->1
1.2 解题思路
解法1：迭代
迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每次处理都会改变状态、直至到达最终状态
从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next
1、将下一个节点指针保存到next变量 next = curr.next
2、将下一个节点的指针指向prev，curr.next = prev
3、准备处理下一个节点，将curr赋值给prev
4、将下一个节点赋值为curr，处理一个节点
解法2：递归
递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历
大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr
将所有的小问题解决，大问题即解决
只需每个元素都执行curr.next.next = curr，curr.next = null两个步骤即可
为了保证链不断，必须从最后一个元素开始
1.3 题解代码
package algorithm.leetcode; 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 node = iterate(node1); ListNode node_1 = recursion(node1); System.out.println(node_1); } }
2 统计N以内的素数
2.1 题目
素数：只能被1和自身整除的数，0、1除外
2.2 解题思路与题解代码
解法1：暴力算法
直接从2开始遍历，判断是否能被2到自身之间的数整除
代码展示
public class CountPrimes { public int countPrimes(int n) { int ans = 0; for (int i = 2; i < n; ++i) { ans += isPrime(i) ? 1 : 0; } return ans; } //i如果能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可 public boolean isPrime(int x) { for (int i = 2; i * i <= x; ++i) { if (x % i == 0) { return false; } } return true; } }
解法1：埃氏筛
利用合数的概念(非素数)，素数*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; }
将合数标记为true，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
3 删除排序数组中的重复项
3.1 题目
一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
3.2 解题思路
双指针算法：
数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要nums[i]=nums[j]，我们就增加 j 以跳过重复项。
当遇到 nums[j] ！= nums[i]时，跳过重复项的运行已经结束，必须把nums[j]）的值复制到 nums[i +1]。然后递增 i，接着将再次重复相同的过程，直到 j 到达数组的末尾为止。
3.3 题解代码
public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; }
