提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【刷题day07】LeetCode（力扣）每日一刷。[876. 链表的中间结点][142. 环形链表 II][121. 买卖股票的最佳时机]

LeetCode链表 每日 刷题 力扣 股票 II 中间
2023-06-13 09:15:10 时间

CSDN话题挑战赛第2期 参赛话题：学习笔记

刷题打卡，第七天

题目一、876. 链表的中间结点

原题链接：876. 链表的中间结点

题目描述：

给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

解题思路： 已经给定非空链表的头节点，那么就不需要判断链表是否为空了； 我们通过循环记录链表节点的个数，将记录的个数除以2得到指针需要移动的次数，返回移动完后的节点即可。

解题代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode curr = head;//创建新节点记录给定头节点
        int total = 0;       //total记录节点总数
        while(curr != null){ //不为空
            total++;         //记录节点数+1
            curr = curr.next;//指针指向下一节点
        }
        for(int i = 0;i < total>>1;++i){//total>>1,相当于总数 / 2
            head = head.next;           //指针扫过一半节点，抵达中间节点 
        }
        return head;//返回中间节点
         
    }

}

提交结果：

题目二、142. 环形链表 II

原题链接：142. 环形链表 II

题目描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。

解题思路： 使用不可重复的set集合来存放节点元素，不断扫描数组，若遇到无法存放节点的情况，说明节点重复，重复节点就是入环的第一个节点。 如果存在节点的下一节点为null，说明无环，直接返回null。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set set = new HashSet();//创建不可重复的单列集合
        while(pos != null){     //节点不为空时
            if(set.add(pos)){   //节点元素放入集合中
                pos = pos.next; //指针后移
            }else{              //节点无法放入集合，说明已经扫描过
                return pos;     //直接返回，这就是入环节点
            }
        }
        return null;            //存在节点下一位为空，说明无环，返回空
    }
}

提交结果：

题目三、121. 买卖股票的最佳时机

原题链接：121. 买卖股票的最佳时机

题目描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题思路：

遍历数组中每一天的股价，记录最低值min，遍历到比min大的股价，就计算差值，最终返回最大的差值，就代表最大利润。

解题代码：

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];//表示最低的价格
        int max = 0;        //表示最高的利润

        for(int i = 0;i < prices.length;++i){
            if(prices[i] <= min){//如果这天股价更低
                min = prices[i]; //将股价记录为min
            }else if(max < prices[i]-min){//如果这天股价高，计算与min差值
                max = prices[i]-min;      //若结果高于记录max，更新最大利润
            }
            
        }
        return max;               //返回最大利润
    }
}

贵在坚持：

相关文章