> 算法训练 - Yuyy
Yuyy
Yuyy

算法训练
文章归档

LeetCode:链表的中间结点_876

思路 一次遍历链表,寻找中间节点。两个信息,一、要遍历完,二、遍历完时需要遍历到中间节点。所以需要两个指针,并且速度是1:2。注意题目要求中点为两个时,取后面个。 题目 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返…

   19   2021-09-06   去看看

LeetCode:合并K个升序链表_23

思路 这题是21的升级版,从两路归并到多路归并,其中运用了优先队列来优化。感觉这题谈不上困难,只是运用了两个知识点,逻辑不复杂。 题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。   示例 …

   14   2021-09-06   去看看

LeetCode:合并两个有序链表_21

思路 基础班双指针,还有归并的思想 题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。    示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出…

   15   2021-09-04   去看看

LeetCode:二叉树展开为链表_114

思路 最终需要的结果是前序遍历,最简单的方式就是递归前序遍历,结果存到队列里,最后再组装。难一点的就是一边遍历一边组装结果,如果是递归,遍历左节点时,将父节点的右节点更改为左节点(题目要求的结果),那么会影响右节点的遍历(已经被替换成左节点了)。所…

   18   2021-09-03   去看看

LeetCode117. 填充每个节点的下一个右侧节点指针_II

思路 116题还能通过画图看出规律,但这是升级版,非完美二叉树。这题很容易想到用层次遍历,但是是中等难度,肯定不是最优解。 分析下,层次遍历时间复杂度O(N),已经做到极致了。那么只能从空间复杂度下手,层次遍历空间复杂度为O(N),如果不存副本,倒是可以优化。…

   20   2021-09-02   去看看

LeetCode560. 和为K的子数组

思路 首先想到的是暴力求解,双重循环得出所有连续子串,但是多半要超时。没想到其他办法。看了题解,学到了前缀和的概念,这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上,结合了hash来优化,也就是两数之和那道题。 两个地方需要注意。一、需要…

   18   2021-09-02   去看看

排序算法(冒泡,快排,插入)

冒泡排序 @Test public void test() { int[] arr = new int[]{3, 4, 1, 76, 3, 889, 8, 4}; for (int i = 0; i < arr.length - 1; i++) { for (int j = arr.length - 2; j >= i; j--) { if (arr[j + 1] < arr[j]) { …

   131   2021-05-20   去看看

查找第K小/大数据,千万数据排序

思路 刚开始我以为这题的考点是如何快速读取文件(因为这是公司多线程学习分享后布置的作业),我就用多线程来解题。后来出题人跟我说:200m测试数据时我的程序OOM了,我才醒悟这题的考点不是快速读取文件,而是大文件排序。 这题挺有意思的,解题运用了多路归并,有…

   156   2021-03-17   去看看

LeetCode1114. 按序打印

一、思路 多个线程顺序执行,方法有很多,例如CountDownLatch,wait,volatile,join,semaphore,Automatic。。。 二、问题 我们提供了一个类: public class Foo {   public void first() { print("first"); }   public void second() { print("second"); }   p…

   220   2021-03-04   去看看

LeetCode877. 石子游戏

一、思路 第一时间想到的是动态规划,后来看题解发现,这玩意没那么复杂。 A和B比赛,没有平局,有两种结局。一、A赢B输,二、A输B赢。但是题中说亚历克斯先开始,言外之意就是主动权在他那里,只需提前计算出A赢还是B赢,然后照着赢的那个做即可。 言而总之,只要亚…

   173   2021-03-03   去看看
加载更多
友情链接
标签
归档
近期文章