Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.1k 阅读时长 ≈ 4 分钟

By Long Luo

在 Leetcode 做 链表 相关的题时，给出的测试用例总是数组或者字符串形式，比如 61. 旋转链表 这道题，Testcase如下所示：

示例 1：

img

输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]

问题

如果在本地测试代码时，每次测试代码的时候，都需要自己创建测试用例，或者调用leetcode给的例子，都需要手动去创建一个链表的话，但这样效率太低！针对这种情况，写了几个工具函数用来处理链表的代码，可供大家参考。

测试代码

个人测试链表测试代码如下：

1
2
3
4
5
6
7
public static void main(String[] args) {
    ListNode test1 = LinkedListUtils.constructListNode(new int[]{1, 2, 3, 4, 5});
    System.out.println("[4,5,1,2,3] ?=" + LinkedListUtils.printLinkedList(rotateRight(test1, 2)));

    ListNode test2 = LinkedListUtils.constructListNode(new int[]{0, 1, 2});
    System.out.println("[2,0,1] ?=" + LinkedListUtils.printLinkedList(rotateRight(test2, 4)));
}

打印链表

Leetcode上链表最后输出形式：

输出：[4,5,1,2,3]

打印方法很简单，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static String printLinkedList(ListNode head) {
    if (head == null) {
        return "[]";
    } else if (head.next == null) {
        return "[" + head.val + "]";
    }

    StringBuilder sb = new StringBuilder();
    sb.append("[");
    while (head.next != null) {
        sb.append(head.val);
        if (head != null) {
            sb.append(",");
        }
        head = head.next;
    }
    sb.append(head.val).append("]");

    return sb.toString();
}
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 14k 阅读时长 ≈ 12 分钟

By Long Luo

我的Leetcode的解题：

Chinese Solutions

Leetcode题目难度题解
1. 两数之和Easy2种方法：暴力 和 HashMap
2. 两数相加Medium2种方法：模拟 和 递归
4. 寻找两个正序数组的中位数Hard4种方法：合并数组，暴力法，二分搜索，划分数组
15. 三数之和Medium3种方法：暴力，Hash，双指针
18. 四数之和Medium4种方法：暴力，双指针，DFS，HashMap
22. 括号生成Medium2种方法：暴力法 和 回溯法
28. 实现 strStr()Easy理解KMP算法：从入门到推导
29. 两数相除Medium3种方法：暴力法，二分搜索，递归
42. 接雨水Hard5种解法：木桶原理，按行求，动态规划，双指针，单调栈
43. 字符串相乘Medium另辟蹊径，快速傅里叶变换(FFT)计算大数乘法
70. 爬楼梯Easy面试算法题：爬楼梯，N级楼梯有多少种走法？
148. 排序链表Medium4种方法：暴力，List，自顶向下归并排序，自底向上归并排序
155. 最小栈Easy3种方法：辅助栈，栈，链表
171. Excel 表列序号Easy仿照Excel的列编号，给定一个数字，输出该列编号字符串
209. 长度最小的子数组Medium5种方法：暴力，双指针，前缀和，前缀和 + 二分查找，二分查找
225. 用队列实现栈Easy如何改变队列元素顺序？
230. 二叉搜索树中第K小的元素Medium二叉搜索树中第K小的元素
232. 用栈实现队列Easy顺序翻转，使用两个栈：一个入队，一个出队
268. 丢失的数字Medium4种方法：排序，哈希表，异或，数学公式
299. 猜数字游戏Medium从遍历2次优化到遍历1次
318. 最大单词长度乘积Medium3种方法：从暴力状态压缩到位运算优化
384. 打乱数组Medium2种方法：暴力 和 洗牌算法
390. 消除游戏Medium经典算法：从约瑟夫问题说开去…
396. 旋转函数Medium3种方法：暴力法，动态规划，前缀和 + 滑动窗口
407. 接雨水 IIHard2种方法：优先队列存储每层围栏最低高度，BFS更新每个方块存水高度
超大数字的加减乘除 415. 字符串相加, 445. 两数相加 IIMedium超大数字的四则运算是如何实现的呢？
419. 甲板上的战舰Medium4种方法：一次遍历，DFS，统计战舰起点
423. 从英文中重建数字Medium找规律，依次确定数字的次数，逐步消元法
438. 找到字符串中所有字母异位词Medium滑动窗口：从HashMap，数组，再到统计字母数量之差
458. 可怜的小猪Hard从 经典面试问题 到 信息论
509. 斐波那契数Easy9种求斐波那契数(Fibonacci Numbers)的算法
519. 随机翻转矩阵Medium2种方法：暴力法 和 降维 + 哈希表
525. 连续数组Medium2种方法：暴力，前缀和 + 哈希表
559. N叉树的最大深度Easy3种方法：递归，DFS和BFS
594. 最长和谐子序列Easy4种方法：暴力枚举，排序 + 枚举，哈希表
598. 范围求和 IIEasy求所有操作的交集
686. 重复叠加字符串匹配Medium3种方法：暴力，字符串哈希，KMP
700. 二叉搜索树中的搜索Easy3种方法：递归，迭代，BFS
859. 亲密字符串Easy简单的字符串模拟
912. 排序数组Medium排序算法(Sorting Algorithms)
997. 找到小镇的法官Easy图论，计算各节点的入度和出度
1044. 最长重复子串Hard3种方法：从暴力到二分，二分搜索 + 字符串哈希，后缀数组
1218. 最长定差子序列Medium序列动态规划 + HashMap
1385. 两个数组间的距离值Easy2种方法：模拟 和 二分搜索
1705. 吃苹果的最大数目Medium贪心 + 优先队列：每天找最邻近过期的苹果吃
1816. 截断句子Easy3种方法：正则表达式，模拟和优化
meituan-002. 小美的仓库整理Medium记一道美团面试编程题的解题过程：从暴力到优化
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

By Long Luo

148. 排序链表 。

暴力 + ArrayList

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;

    List<Integer> nodeList = new ArrayList<>();
    while (pNode != null) {
        nodeList.add(pNode.val);
        pNode = pNode.next;
    }

    Collections.sort(nodeList);

    ListNode dummyNode = new ListNode(-1);
    pNode = dummyNode;
    for (int i = 0; i < nodeList.size(); i++) {
        pNode.next = new ListNode(nodeList.get(i));
        pNode = pNode.next;
    }

    return dummyNode.next;
}

123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;

    List<ListNode> nodeList = new ArrayList<>();
    while (pNode != null) {
        nodeList.add(pNode);
        pNode = pNode.next;
    }

    nodeList.sort(Comparator.comparingInt(o -> o.val));

    ListNode dummyNode = new ListNode(-1);
    ListNode preNode = dummyNode;
    for (int i = 0; i < nodeList.size(); i++) {
        pNode = nodeList.get(i);
        preNode.next = pNode;
        pNode.next = null;
        preNode = pNode;
    }

    return dummyNode.next;
}

复杂度分析

  • 时间复杂度：\(O(nlogn + n)\)
  • 空间复杂度：\(O(n)\)

归并排序

1
2
3



复杂度分析

  • 时间复杂度：\(O(nlogn + n)\)
  • 空间复杂度：\(O(n)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 230. 二叉搜索树中第K小的元素 题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点root，和一个整数$k$，请你设计一个算法查找其中第$k$个最小元素（从$1$开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
 
提示：
树中的节点数为 n 。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4
 
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第$k$小的值，你将如何优化算法？

方法一：中序遍历 + 递归

思路与算法：

二叉搜索树具有如下性质：

  • 结点的左子树只包含小于当前结点的数。
  • 结点的右子树只包含大于当前结点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。

因为二叉搜索树和中序遍历的性质，所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是，我们可以通过中序遍历找到第\(k\)个最小元素。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int kthSmallest(TreeNode root, int k) {
	List<Integer> nums = new ArrayList<>();
	inOrder(root, nums);
	return nums.get(k - 1);
}

public void inOrder(TreeNode root, List<Integer> numberList) {
	if (root == null) {
		return;
	}

	inOrder(root.left, numberList);
	numberList.add(root.val);
	inOrder(root.right, numberList);
}

复杂度分析：

  • 时间复杂度：\(O(N)\)，其中\(N\)是树的节点数。

  • 空间复杂度：\(O(N)\)，需要额外存储每个节点的值。

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 22. 括号生成 题解。

方法一：暴力法

思路与算法：

直接生成所有 \(2^{2n}\) 个’(‘和’)’字符构成的序列，然后我们检查每一个是否有效即可。

为了生成所有序列，我们可以使用递归。长度为 \(n\) 的序列就是在长度为 \(n-1\) 的序列前加一个’(‘或’)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量 \(balance\) 表示左括号的数量减去右括号的数量。如果在遍历过程中 \(balance\) 的值小于零，或者结束时 \(balance\) 的值不为零，那么该序列就是无效的，否则它是有效的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public List<String> generateParenthesis(int n) {
	if (n < 1) {
		return new ArrayList<>();
	}

	List<String> ans = new ArrayList<>();
	generateAll(new char[2 * n], 0, ans);
	return ans;
}

public void generateAll(char[] current, int pos, List<String> result) {
	if (pos == current.length) {
		if (valid(current)) {
			result.add(new String(current));
		}
	} else {
		current[pos] = '(';
		generateAll(current, pos + 1, result);
		current[pos] = ')';
		generateAll(current, pos + 1, result);
	}
}

public boolean valid(char[] current) {
	int balance = 0;
	for (char c : current) {
		if (c == '(') {
			++balance;
		} else {
			--balance;
		}
		if (balance < 0) {
			return false;
		}
	}
	return balance == 0;
}

复杂度分析

  • 时间复杂度：\(O(2^{2n}n)\)，对于 \(2^{2n}\) 个序列中的每一个，我们用于建立和验证该序列的复杂度为 \(O(n)\)。

  • 空间复杂度：\(O(n)\)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 \(O(1)\) 的空间，最多递归 \(2n\) 层，因此空间复杂度为 \(O(n)\)。

阅读全文 »
0%