分类: 算法训练

219 篇文章

LeetCode:链表的中间结点_876
思路 一次遍历链表,寻找中间节点。两个信息,一、要遍历完,二、遍历完时需要遍历到中间节点。所以需要两个指针,并且速度是1:2。注意题目要求中点为两个时,取后面个。 题目 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。   示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 …
LeetCode:合并K个升序链表_23
思路 这题是21的升级版,从两路归并到多路归并,其中运用了优先队列来优化。感觉这题谈不上困难,只是运用了两个知识点,逻辑不复杂。 题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。   示例 1: 输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,…
thumbnail
LeetCode:合并两个有序链表_21
思路 基础班双指针,还有归并的思想 题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。    示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [],…
thumbnail
LeetCode:二叉树展开为链表_114
思路 最终需要的结果是前序遍历,最简单的方式就是递归前序遍历,结果存到队列里,最后再组装。难一点的就是一边遍历一边组装结果,如果是递归,遍历左节点时,将父节点的右节点更改为左节点(题目要求的结果),那么会影响右节点的遍历(已经被替换成左节点了)。所以这里用迭代遍历,将遍历顺序存到了栈里,不用担心修改父节点影响遍历了。 题目 给你二叉树的根结点 ro…
thumbnail
LeetCode117. 填充每个节点的下一个右侧节点指针_II
思路 116题还能通过画图看出规律,但这是升级版,非完美二叉树。这题很容易想到用层次遍历,但是是中等难度,肯定不是最优解。 分析下,层次遍历时间复杂度O(N),已经做到极致了。那么只能从空间复杂度下手,层次遍历空间复杂度为O(N),如果不存副本,倒是可以优化。 遍历某一层时,就将下一层串起来,这样下一层就可以直接遍历,不用存到队列里。第一层没有上一…
LeetCode560. 和为K的子数组
思路 首先想到的是暴力求解,双重循环得出所有连续子串,但是多半要超时。没想到其他办法。看了题解,学到了前缀和的概念,这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上,结合了hash来优化,也就是两数之和那道题。 两个地方需要注意。一、需要的前缀和可能出现多次,那么每次都得算上。二、前缀和为0也是一种情况,并且是必要的,需要手动…
thumbnail
排序算法(冒泡,快排,插入)
冒泡排序 @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--) { …
查找第K小/大数据,千万数据排序
思路 刚开始我以为这题的考点是如何快速读取文件(因为这是公司多线程学习分享后布置的作业),我就用多线程来解题。后来出题人跟我说:200m测试数据时我的程序OOM了,我才醒悟这题的考点不是快速读取文件,而是大文件排序。 这题挺有意思的,解题运用了多路归并,有个巧妙的地方估计只有实操才知道——复用流。 题目 查找第K小/大数据 每个法官都有不同的办案能…
LeetCode1114. 按序打印
一、思路 多个线程顺序执行,方法有很多,例如CountDownLatch,wait,volatile,join,semaphore,Automatic。。。 二、问题 我们提供了一个类: public class Foo {   public void first() { print("first"); }   public void second…
LeetCode877. 石子游戏
一、思路 第一时间想到的是动态规划,后来看题解发现,这玩意没那么复杂。 A和B比赛,没有平局,有两种结局。一、A赢B输,二、A输B赢。但是题中说亚历克斯先开始,言外之意就是主动权在他那里,只需提前计算出A赢还是B赢,然后照着赢的那个做即可。 言而总之,只要亚历克斯想赢,就一定能赢。而题中说了假设亚历克斯和李都发挥出最佳水平,亚历克斯一定会发挥好的,…