每日leetcode——JZ51 数组中的逆序对

2022-03-25
阅读 2 分钟
679
题目在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。要求:空间复杂度 O(n),时间复杂度 O(nlogn) {代码...} 思路最简单的思路是暴力求解,遍历数组每个元素,然后挨个和之后的元素比较。这种做法时间复杂度是O(n^2)。最优思路是,利用...

二叉树和堆

2022-03-24
阅读 2 分钟
649
二叉树:就是最多只能有两个叉的树结构。图中1是普通的二叉树,2、3是两种特殊的二叉树。2是满二叉树满二叉树:叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点

每日leetcode——JZ40 最小的K个数

2022-03-24
阅读 2 分钟
949
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。

常见排序算法及复杂度

2022-03-23
阅读 7 分钟
970
两层循环外层循环:遍历数组中待排序部分内层循环:当前元素和它后面的元素比较大小,如果逆序就交换位置;下一个元素和它后面的元素比较大小,如果逆序就交换位置...直到结束

每日leetcode——JZ22 链表中倒数最后k个结点

2022-03-22
阅读 1 分钟
672
最直接的思路是:翻转整个链表,然后再遍历节点,这样做就是空间复杂度O(n),时间复杂度O(n)空间复杂度O(1),则不能存储额外的链表,意味着只能在原链表上操作。如果先遍历一遍链表,得到链表的长度,再减去k,得到倒数第k个节点是正序第几个节点,这样的做法时间复杂度又不满足O(n)了。

每日leetcode——JZ6 从尾到头打印链表

2022-03-22
阅读 1 分钟
651
第一反应这不就是反转链表吗,但仔细审题后,发现和翻转链表并不一样。题目要求的是,返回链表翻转后的每个节点的值。如果用翻转链表的思路,要先翻转链表,再遍历翻转链表的每个节点。这么做无论空间还是时间复杂度都不够简洁。

每日leetcode——328. 奇偶链表

2022-03-21
阅读 1 分钟
633
题目给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个...

每日leetcode——234. 回文链表

2022-03-21
阅读 2 分钟
612
第一个想到的就是,直接把整个链表翻转,然后和原来的链表比较。但是题目要求时间复杂度O(n),空间复杂度O(1),这个思路要保存翻转后的链表,空间复杂度首先就不满足了。

每日leetcode——25. K 个一组翻转链表

2022-03-21
阅读 2 分钟
512
题目给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。进阶:你可以设计一个只使用常数额外空间的算法来解决此问题吗?你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。 {...

每日leetcode——203. 移除链表元素

2022-03-20
阅读 1 分钟
714
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

每日leetcode——239. 滑动窗口最大值

2022-03-20
阅读 2 分钟
780
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

每日leetcode——232. 用栈实现队列

2022-03-20
阅读 1 分钟
685
使用两个栈,stack_in栈模拟队列push,stack_out栈模拟队列poppop时,如果stack_out空栈,将stack_in栈依次pop到stack_out中然后stack_out再pop

每日leetcode——42. 接雨水

2022-03-14
阅读 6 分钟
987
暴力解法虽然简单,但是这道题的暴力思路一时我还没反应过来,花了挺久时间才想明白咋回事。首先,大体思路就是,遍历每个柱子,也就是遍历数组每个元素,然后每个元素为中心,向左、右两侧遍历寻找比它高的最高的柱子,这样就能计算出这个柱子上方能接多少水。

每日leetcode——739. 每日温度

2022-03-12
阅读 1 分钟
655
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指在第 i 天之后,才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。

每日leetcode——946. 验证栈序列

2022-03-11
阅读 1 分钟
708
给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

每日leetcode——155. 最小栈

2022-03-11
阅读 4 分钟
994
只用一个栈也可以解决问题。辅助栈的方法,是新增一个栈用来维护最小值。而只用一个栈,就只需要新增一个变量来保存最小值。在数据出入栈的同时,通过一些方法,将最小值的变化记录在数据栈中。

每日leetcode——224.基本计算器

2022-03-08
阅读 7 分钟
873
题目给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。 {代码...} 思路计算器类的题目,224、227、772,只需要一个思路:逆波兰表达式+栈。a+b,逆波兰表达式:a,b,+例如:s = '2+(35/4+7(2+3))/4'定义两个栈:stack栈 用来存放数字以外的符号:运算符、括号res栈 用来存放数字,以及pop出来的运算...

每日leetcode——138. 复制带随机指针的链表

2022-03-06
阅读 2 分钟
648
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

每日leetcode——92. 反转链表 II

2022-03-06
阅读 1 分钟
865
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

每日leetcode——4. 寻找两个正序数组的中位数

2022-03-04
阅读 3 分钟
1.1k
题目给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。 {代码...} 归并排序利用归并排序的思想,在两个数组开头,设置两个指针,比较两个指针的大小,小的向后移动,直到找到中位数。这个方法时间复杂度是O(m+n),达...

每日leetcode——3. 无重复字符的最长子串

2022-02-28
阅读 2 分钟
1.1k
题目给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 {代码...} 暴力枚举思路一:以每个字符为开始,遍历字符串,用一个字典保存遍历的字符,遇到重复的就结束,用一个数组保存本次无重复子串的长度,返回最大的 {代码...} 滑动窗口 {代码...}

每日leetcode——142. 环形链表 II

2022-02-27
阅读 3 分钟
995
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

每日leetcode——86. 分隔链表

2022-02-26
阅读 1 分钟
628
题目给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。 {代码...} 一开始题目都没读懂...其实题目的意思就是:比如示例中的数组,小于3的都放到前面,大于等于3的都放到后面,并且不改变相对顺...

每日leetcode——160. 相交链表

2022-02-25
阅读 1 分钟
945
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

每日leetcode——206.反转链表

2022-02-25
阅读 1 分钟
705
题目给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 {代码...} 题解考察链表结构的理解,递归方法的实现 {代码...}

每日leetcode——删除有序数组中的重复项

2022-02-25
阅读 1 分钟
842
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

每日leetcode——21. 合并两个有序链表

2022-02-24
阅读 2 分钟
1.1k
时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。

每日leetcode——20.有效的括号

2022-02-24
阅读 1 分钟
581
'()[]'和'([])'这两种有效情况,可以看出,只要右括号前面是左括号,它们一定是一对,可以相互抵消的。利用栈的思想可以很好的解决题目,有种消消乐的感觉。

每日leetcode——最长公共前缀

2022-02-23
阅读 3 分钟
1.2k
最直接的思路:选取第一个字符串假设为前缀。用这个前缀的每一个字符,去和所有其他字符串比较,如果其他字符串在该位置也是这个字符,那这个字符就属于前缀;反之,前缀就到此结束。

每日leetcode——回文数

2022-02-23
阅读 1 分钟
1.1k
题目给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。 {代码...} 转成字符串翻转最简单最低效的方法,因为将数字转成字符串需要开辟额外的空间,会提升空间复杂度。 {代码...} 利用除法反转数...