LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解

简介: LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解

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;
}

目录
打赏
0
0
0
0
51
分享
相关文章
|
7月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
78 1
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
Java 中数组Array和列表List的转换
|
1月前
|
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
81 10
|
2月前
|
《从头开始学java,一天一个知识点》之:数组入门:一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间?** - 看了三天教程,连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;,大脑突然空白 - 写出的代码总是莫名报NPE,却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」!我们承诺:每天1分钟,地铁通勤、午休间隙即可完成学习;直击痛点,只讲高频考点和实际开发中的「坑位」;拒绝臃肿,没有冗长概念堆砌,每篇都有可运行的代码标本。明日预告:《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧,帮助你快速掌握Java数组的精髓。
78 23
Java快速入门之数组、方法
### Java快速入门之数组与方法简介 #### 一、数组 数组是一种容器,用于存储同种数据类型的多个值。定义数组时需指定数据类型,如`int[]`只能存储整数。数组的初始化分为静态和动态两种: - **静态初始化**:直接指定元素,系统自动计算长度,如`int[] arr = {1, 2, 3};` - **动态初始化**:手动指定长度,系统给定默认值,如`int[] arr = new int[3];` 数组访问通过索引完成,索引从0开始,最大索引为`数组.length - 1`。遍历数组常用`for`循环。常见操作包括求和、找最值、统计特定条件元素等。
Java 中数组的多种定义方式
本文深入解析了Java中数组的多种定义方式,涵盖基础的`new`关键字创建、直接初始化、动态初始化,到多维数组、`Arrays.fill()`方法以及集合类转换为数组等高级用法。通过理论与实践结合的方式,探讨了每种定义方法的适用场景、优缺点及其背后的原理,帮助开发者掌握高效、灵活的数组操作技巧,从而编写更优质的Java代码。
68 0
Java 复制数组
本文介绍了Java中数组的基础知识与常用操作,包括数组的概念、创建、访问元素、遍历、复制、排序和搜索等方法。同时详细讲解了数组的五种赋值方式,并通过代码示例演示了求总和平均值、最大最小值、升序降序排序及Arrays类的常用方法。内容深入浅出,适合初学者学习掌握Java数组的核心功能与应用场景。
Java基础(六):数组
Java基础(六):数组
60 10
Java基础(六):数组
Java数组:静态初始化与动态初始化详解
本文介绍了Java中数组的定义、特点及初始化方式。
233 12
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
68 4
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等