LeetCode题解 链表的冒泡排序

可以使用 https://leetcode-cn.com/problems/sort-list/ 进行测试。

但是本题的要求不是时间复杂度$O(N*logN)$,而是要求使用冒泡排序算法

题解:## Python Solution

```python
class Solution:
def sortList(self, head: ListNode) -> ListNode:
outer = head
inner = head
while outer:
while inner and inner.next:
if inner.val > inner.next.val:
temp = inner.val
inner.val = inner.next.val
inner.next.val = temp
inner = inner.next
outer = outer.next
inner = head
return head
```
***复杂度分析***
- 时间复杂度:$O(N^2)$
- 空间复杂度:$O(1)$

## 扩展

如何剪枝?比如提前退出循环, 比如内层循环没必要每次都到最后,因为外层一趟一定会就位一个数字(这个就是大的数),因此内层循环应该每次都少一步。 虽然复杂度仍然是$O(N^2)$

如何在Matplotlib条形图后面绘制网格线 - python

x = ['01-02', '02-02', '03-02', '04-02', '05-02'] y = [2, 2, 3, 7, 2] fig, ax = plt.subplots(1, 1) ax.bar(range(len(y)), y, width=…

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。

LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。

10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924

LeetCode题解烧绳子

烧一根不均匀的绳要用一个小时,如果要准确判断一个小时十五分钟,至少需要几根绳子?注意:- 每一根绳子虽然都可以烧一个小时,但均匀程度都不一样题解:三根1. 第一根点燃一头的同时,第二根两头同时点燃。2. 点燃两头的绳子燃尽时,同时点燃第一根绳子的另一头 并开始计时3. 等第一根绳子燃尽 再点燃第三根绳子的一头4. 燃尽 一小时十五分钟

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧