濬哲的博客

LeetCode24.两两交换链表中的节点

题目链接：24.两两交换链表中的节点

题目要点与解题思路

这题考察的是模拟，因为在操作的时候一些链会断开，所以一定要想清楚如何暂存节点，并且本题适合用 dummy 处理，因为 head 没有人指着，和后面的逻辑有所不同

我的解法是步骤 3-步骤 2-步骤 1，代码如下：

链表理论基础

我突然在想为什么新建链表节点必须用 new ListNode()，而不能直接用 ListNode()呢？
因为链表是动态分配的，new ListNode()会在堆上分配内存，而 ListNode()是在栈上分配内存。栈上的变量在函数结束后会被自动销毁，而堆上的变量需要手动释放。
如果用 ListNode()，这个函数结束了会自动销毁变量，造成悬空指针，而链表一般需要全局区调用，所以不能放在栈上。

理解了这个点，这对于内存的堆空间和栈空间应该就更明白了

LeetCode203.移除链表元素

题目链接：203.移除链表元素

题目要点与解题思路

这是非常基础的链表删除操作，不是很想展开讲了，只需要记住下面几点：

• 建议使用 dummy 节点，避免处理头节点的特殊情况
• 删除节点只需要用到一个 cur 指针，cur-> next = cur->next->next; 这样就可以了
• 别忘记 delete dummy 和要删除的节点

前言

我们在进行 markdown 写作的时候，通常会在文章中插入图片，而 markdown 的图片管理也是很烦人的事情。另外加上 hexo 的一些特性，导致图片本地预览和线上发布不一致，网上也有不少用插件来解决的方法，比如hexo-asset-img。但是我觉得网上的大多数实践还不够完美，下面我就给出我自己的解决方案。

为什么要绑定域名

在使用 Hexo 搭建个人博客时，默认的域名是 GitHub Pages 提供的二级域名（如 username.github.io）。为了提升网站的专业性和可识别性，我们通常会选择绑定一个自定义的顶级域名（如 example.com）。

并且对于程序员来讲，拥有一个属于自己的域名看起来超酷的！

LeetCode209.长度最小的子数组

题目链接：209.长度最小的子数组

题目要点与解题思路

暴力解法

不难想到暴力解法，时间复杂度是，就是以每一个元素为起始位置，然后往下看，直到找到满足要求的子数组。这种情况下结束位置会被反复遍历

滑动窗口

滑动窗口就是不断调节起始位置和终止位置，然后找到满足要求的子数组
在暴力循环中，一个 for 遍历起始位置，一个 for 遍历结束位置，结束位置是从每个起始位置开始枚举

我们思考能否用一个 for 循环来解决这个问题：
首先应该表示起始位置还是终止位置呢？ 答案是终止位置，因为如果是起始位置的话一定会落入重复遍历终止位置的困境
我们移动终止位置，不断增长窗口，当窗口内的元素和大于等于目标值时，开始移动起始位置，直到窗口内的元素和小于目标值为止

LeetCode704.二分查找

题目链接：704.二分查找

题目要点与解题思路

首先我们明确一下二分查找的条件：

1. 数组是有序的
2. 数组中没有重复元素（否则返回的下标可能会不唯一）

然后要注意二分查找的边界条件，有两种写法，左闭右开和左闭右闭，我是用的左闭右闭的写法。

双指针有大用处：
027.移除元素

双指针还能延伸出滑动窗口，很多子数组之类的就是滑动窗口问题
字节后端一面中的编程题就是一道滑动窗口

最长非重复子字符串的长度，abcabc这种，最长子字符串是3

这道题完全可以仿照209.长度最小的子数组来做

题目简介

题目链接

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

思路

这道题很容易把人绕晕进去，如果找不到一个统一的写法，会产生大量的逻辑判断。下面我给出一个很巧妙的方法，不光是对这种正方形有用，同时也适用于长方形

我们访问的顺序就是最外面这一圈，像是剥洋葱一样，一条一条的把边剥开，然后每次处理的就是一个新的矩形，代码其实非常好理解，up,down, left, right分别表示矩形的上下左右边界，count表示当前要填入的数字，vec是结果矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int up = 0, down = n - 1, left = 0, right = n - 1;
        int count = 1;
        vector<vector<int>> vec(n, vector<int>(n, 0));
        while (1) {
            for (int i = left; i <= right; i++) vec[up][i] = count++;
            if (++up > down) break;
            for (int i = up; i <= down; i++) vec[i][right] = count++;
            if (--right < left) break;
            for (int i = right; i >= left; i--) vec[down][i] = count++;
            if (--down < up) break;
            for (int i = down; i >= up; i--) vec[i][left] = count++;
            if (++left > right) break;
        }
        return vec;
    }
};

时间复杂度O(n^2)，空间复杂度O(n^2)

题目简介

题目链接

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

题目简介

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题