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
分享
相关文章
Java 排序神器:Comparable 和 Comparator 该怎么选?
嗨,大家好,我是小米!今天和大家聊一聊Java社招面试中常考的经典问题——Comparable和Comparator的区别。Comparable定义对象的自然排序,适用于单一固定的排序规则;Comparator则是策略接口,用于定义自定义排序规则,适用于多样化或多变的排序需求。掌握这两者的区别是理解Java排序机制的基础,也是面试中的加分题。结合实际项目场景深入探讨它们的应用,能更好地打动面试官。如果你觉得有帮助,欢迎点赞、收藏、分享,期待你的一键三连!我们下期见~ 我是小米,一个喜欢分享技术的程序员,关注我的微信公众号“软件求生”,获取更多技术干货!
62 20
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
104 4
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
61 1
|
7月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
57 0
Leetcode第三十三题(搜索旋转排序数组)
|
7月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
115 0
|
7月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
44 0
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
87 2
|
12月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
110 1
AI助理

你好,我是AI助理

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