经典150(针对hot100补充)
# 数组/字符串
# 88. 合并两个有序数组 (opens new window)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] arr1 = new int[m];
for(int i=0;i<m;i++)
arr1[i] = nums1[i];
int[] arr2 = nums2;
int i=0,j=0;
for(int p=0;p<m+n;p++){
if(i==m)
nums1[p] = arr2[j++];
else if(j==n)
nums1[p] = arr1[i++];
else if(arr1[i]<arr2[j])
nums1[p] = arr1[i++];
else
nums1[p] = arr2[j++];
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 27. 移除元素 (opens new window)
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
if(n==0)
return 0;
int j = 0;
for(int i=0;i<n;i++){
if(nums[i]!=val){
nums[j] = nums[i];
j++;
}
}
return j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 26. 删除有序数组中的重复项 (opens new window)
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if(n<2)
return n;
int j=1;
for(int i=1;i<n;i++){
if(nums[i]!=nums[j-1]){
nums[j] = nums[i];
j++;
}
}
return j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 80. 删除有序数组中的重复项 II (opens new window)
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if(n<3)
return n;
int j=2;
for(int i=2;i<n;i++){
if(nums[i]!=nums[j-2]){
nums[j] = nums[i];
j++;
}
}
return j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 122. 买卖股票的最佳时机 II (opens new window)
# 274. H 指数 (opens new window)
# 380. O(1) 时间插入、删除和获取随机元素 (opens new window)
# 134. 加油站 (opens new window)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// 全程油量，局部油量（<0起始位置需要改）
int sum = 0,partSum = 0;
int start = 0;
int n = gas.length;
for(int i=0;i<n;i++){
sum += gas[i]-cost[i];
partSum += gas[i]-cost[i];
if(partSum<0){
partSum = 0;
start = i+1;// 能说明前面都不是答案，只能向后继续寻找
}
}
if(sum<0)
return -1;
return start;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 135. 分发糖果 (opens new window)
# 13. 罗马数字转整数 (opens new window)
# 12. 整数转罗马数字 (opens new window)
# 58. 最后一个单词的长度 (opens new window)
# 14. 最长公共前缀 (opens new window)
# 151. 反转字符串中的单词 (opens new window)
# 6. Z 字形变换 (opens new window)
# 28. 找出字符串中第一个匹配项的下标 (opens new window)
# 68. 文本左右对齐 (opens new window)
# 双指针
# 125. 验证回文串 (opens new window)
# 392. 判断子序列 (opens new window)
# 167. 两数之和 II - 输入有序数组 (opens new window)
# 滑动窗口
# 209. 长度最小的子数组 (opens new window)
# 30. 串联所有单词的子串 (opens new window)
# 矩阵
# 36. 有效的数独 (opens new window)
# 289. 生命游戏 (opens new window)
# 哈希表
# 383. 赎金信 (opens new window)
# 205. 同构字符串 (opens new window)
# 290. 单词规律 (opens new window)
# 242. 有效的字母异位词 (opens new window)
# 202. 快乐数 (opens new window)
# 219. 存在重复元素 II (opens new window)
# 区间
# 228. 汇总区间 (opens new window)
# 57. 插入区间 (opens new window)
# 452. 用最少数量的箭引爆气球 (opens new window)
# 栈
# 71. 简化路径 (opens new window)
# 150. 逆波兰表达式求值 (opens new window)
# 224. 基本计算器 (opens new window)
# 链表
# 92. 反转链表 II (opens new window)
为什么需要构造dummy节点？
当节点个数为1时或l=1时，p0节点没有指向；
class Solution {
public ListNode reverseBetween(ListNode head, int l, int r) {
ListNode dummy = new ListNode(-1,head);
ListNode p = dummy;
for(int i=0;i<l-1;i++)
p = p.next;
ListNode pre = null,cur = p.next;
for(int i=0;i<r-l+1;i++){
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
p.next.next = cur;
p.next = pre;
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 82. 删除排序链表中的重复元素 II (opens new window)
方法一：递归
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// 没有节点或者只有一个节点，必然没有重复元素
if(head==null || head.next==null)
return head;
// 不同则head保留
if(head.val!=head.next.val){
head.next = deleteDuplicates(head.next);
return head;
}else{
// 找到不重复的值，返回对不重复节点的递归结果
ListNode notDup = head.next.next;
while(notDup!=null && notDup.val==head.val)
notDup = notDup.next;
return deleteDuplicates(notDup);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
方法二：一次遍历
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur!=null){
while(cur.next!=null && cur.next.val==cur.val)
cur = cur.next;
if(pre.next==cur)
pre = pre.next;
else
pre.next = cur.next;
cur = cur.next;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 61. 旋转链表 (opens new window)
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null || k==0)
return head;
int n = 0;
ListNode tail = head;
for(ListNode p = head;p!=null;p = p.next){
tail = p;
n++;
}
k %= n;
ListNode p = head;
for(int i=0;i<n-k-1;i++)
p = p.next;
tail.next = head;
head = p.next; //p.next为分割后段的头节点
p.next = null; //p为分割前段的尾节点
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 86. 分隔链表 (opens new window)
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(-1);// <=x部分
ListNode dummy2 = new ListNode(-1);// >x部分
ListNode p1=dummy1,p2=dummy2;
ListNode p = head;
while(p!=null){
if(p.val>=x){
p2.next = p;
p2 = p2.next;
}else{
p1.next = p;
p1 = p1.next;
}
// 断开原链表中每个节点的next指针
ListNode tmp = p.next;
p.next = null;
p = tmp;
}
// 两部分连接
p1.next = dummy2.next;
return dummy1.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24