By Long Luo
https://leetcode.cn/problemset/lcof/
官方源码：https://github.com/zhedahht/CodingInterviewChinese2
| 题目 | 难度 | 解答 | Source Code |
|---|---|---|---|
| 剑指Offer 03. 数组中重复的数字 | Easy | Java | |
| 剑指Offer 06. 从尾到头打印链表 | Easy | Java | |
| 剑指Offer 09. 用两个栈实现队列 | Easy | Java | |
| 剑指Offer 12. 矩阵中的路径 | Medium | Java | |
| 剑指Offer 15. 二进制中1的个数 | Easy | Java |
By Long Luo
在 Leetcode 做 链表 相关的题时，给出的测试用例总是数组或者字符串形式，比如 61. 旋转链表 这道题，Testcase如下所示：
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
如果在本地测试代码时，每次测试代码的时候，都需要自己创建测试用例，或者调用leetcode给的例子，都需要手动去创建一个链表的话，但这样效率太低！针对这种情况，写了几个工具函数用来处理链表的代码，可供大家参考。
个人测试链表测试代码如下：1
2
3
4
5
6
7public 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
20public 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();
}
By Long Luo
我的 Leetcode 的解题：
By Long Luo
思路与算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public 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;
}
1231
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26public 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;
}
1 |
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. 😉😃💗
By Long Luo
Leetcode 230. 二叉搜索树中第K小的元素 题解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18230. 二叉搜索树中第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
15public 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);
}