大纲
第 1 道题 - 两数之和
题目来源
这是 LeetCode 的 第 1 道算法题 - 两数之和，难度为简单。
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
- 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
- 你可以按任意顺序返回答案。
- 输出示例如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
|
题目答案
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
| public class Test {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (numMap.containsKey(diff)) {
return new int[] {numMap.get(diff), i};
}
numMap.put(nums[i], i);
}
return new int[0];
}
public static void main(String[] args) {
int target = 9;
int[] nums = {2, 7, 11, 15};
int[] result = twoSum(nums, target);
if (result.length == 0) {
System.out.println("[ ]");
} else {
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}
}
|
第 704 道题 - 二分查找
题目来源
这是 LeetCode 的 第 704 道算法题 - 二分查找，难度为简单。
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
| 示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
|
题目分析
- 二分查找的介绍
- 二分查找（Binary Search）也称折半查找，它是一种效率较高的查找算法，时间复杂度是 O (long n)。
- 特别注意，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
- 二分查找的优缺点
- 二分查找算法的优点：查询速度是非常快的，比较次数少，平均性能好。
- 二分查找算法的缺点：必须有个前提就是数组是有序的，而且插入、删除都比较困难。
题目答案
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
| public class BinarySearchDemo {
public static int binarySearch(int[] array, int target) {
int left = 0;
int middle = 0;
int right = array.length - 1;
while (left <= right) {
middle = (left + right) / 2;
if (array[middle] == target) {
return middle;
} else if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
}
|
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
| public class BinarySearchDemo {
public static int binarySearch(int[] array, int target) {
int left = 0;
int middle = 0;
int right = array.length - 1;
while (left <= right) {
middle = left + (right - left) / 2;
if (array[middle] == target) {
return middle;
} else if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
}
|
第 344 道题 - 反转字符串
题目来源
这是 LeetCode 的 第 344 道算法题 - 反转字符串，难度为简单。
题目描述
- 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
- 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O (1) 的额外空间解决这一问题。
1
2
3
4
5
6
7
8
9
| 示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
|
题目分析
![]()
在一般情况下，只要数组是有序的，就应该想到双指针的解题技巧，比如遇到 这些算法题。双指针主要分为两类：
左右指针（left/right）
- 可能相向，可能相背，多用于数组。
- 使用口诀
- 结果比目标，小了要变大，左针右移。
- 结果比目标，大了要变小，右针左移。
快慢指针（slow/fast）
- 也叫 “前后指针”。
- 两个指针同向而行，一快一慢，多用于链表。
- 使用口诀
- 快慢值相等，慢针不动，快针向前一步走。
- 快慢不等值，情形一，慢针向前一步走，快针赋值给慢针，快针向前一步走。
- 快慢不等值，情形二，快针慢针值互换，慢针向前一步走，快针向前一步走。
题目答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class ReverseStringDemo {
public static void reverse(char[] s) {
for (int left = 0; left < s.length; left++) {
int right = s.length - left - 1;
if (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
public static void main(String[] args) {
char[] str = new char[] {'h', 'e', 'l', 'l', 'o'};
reverse(str);
Stream.of(str).forEach(System.out::println);
}
}
|
第 167 道题 - 两数之和 - 输入有序数组
题目描述
- 给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers [index1] 和 numbers [index2] ，则 1 <= index1 < index2 <= numbers.length 。
- 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
- 你所设计的解决方案必须只使用常量级的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
|
题目分析
在一般情况下，只要数组是有序的，就应该想到双指针的解题技巧，比如遇到 这些算法题。双指针主要分为两类：
左右指针（left/right）
- 可能相向，可能相背，多用于数组。
- 使用口诀
- 结果比目标，小了要变大，左针右移。
- 结果比目标，大了要变小，右针左移。
快慢指针（slow/fast）
- 也叫 “前后指针”。
- 两个指针同向而行，一快一慢，多用于链表。
- 使用口诀
- 快慢值相等，慢针不动，快针向前一步走。
- 快慢不等值，情形一，慢针向前一步走，快针赋值给慢针，快针向前一步走。
- 快慢不等值，情形二，快针慢针值互换，慢针向前一步走，快针向前一步走。
题目答案
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
|
public class TwoSumDemo {
public static int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
int[] numbers = new int[] {2, 7, 11, 15};
int[] result = twoSum(numbers, 9);
Arrays.stream(result).forEach(item -> {
System.out.print(item + " ");
});
}
}
|
第 26 道题 - 删除有序数组中的重复项
题目描述
- 给你一个非严格递增排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。
- 考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：
- 更改数组 nums，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
- 返回 k 。
1
2
3
4
5
6
7
8
9
10
11
| 示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1, 2。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。不需要考虑数组中超出新长度后面的元素。
|
题目分析
在一般情况下，只要数组是有序的，就应该想到双指针的解题技巧。双指针主要分为两类：
左右指针（left/right）
- 可能相向，可能相背，多用于数组。
- 使用口诀
- 结果比目标，小了要变大，左针右移。
- 结果比目标，大了要变小，右针左移。
快慢指针（slow/fast）
- 也叫 “前后指针”。
- 两个指针同向而行，一快一慢，多用于链表。
- 使用口诀
- 快慢值相等，慢针不动，快针向前一步走。
- 快慢不等值，情形一，慢针向前一步走，快针赋值给慢针，快针向前一步走。
- 快慢不等值，情形二，快针慢针值互换，慢针向前一步走，快针向前一步走。
题目答案
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
|
public class RemoveDuplicates {
public static int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
public static void main(String[] args) {
int[] array = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
int length = removeDuplicates(array);
System.out.println(length);
}
}
|
第 283 道题 - 移动零
题目描述
- 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
- 请注意，必须在不复制数组的情况下原地对数组进行操作。
1
2
3
4
5
6
7
8
9
| 示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
|
题目来源
这是 LeetCode 的第 283 道算法题 - 移动零，难度为简单。
题目分析
在一般情况下，只要数组是有序的，就应该想到双指针的解题技巧。双指针主要分为两类：
左右指针（left/right）
- 可能相向，可能相背，多用于数组。
- 使用口诀
- 结果比目标，小了要变大，左针右移。
- 结果比目标，大了要变小，右针左移。
快慢指针（slow/fast）
- 也叫 “前后指针”。
- 两个指针同向而行，一快一慢，多用于链表。
- 使用口诀
- 快慢值相等，慢针不动，快针向前一步走。
- 快慢不等值，情形一，慢针向前一步走，快针赋值给慢针，快针向前一步走。
- 快慢不等值，情形二，快针慢针值互换，慢针向前一步走，快针向前一步走。
题目答案
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 class MoveZeroes {
public static void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
int tmp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = tmp;
slow++;
}
fast++;
}
}
public static void main(String[] args) {
int[] array = new int[] {0, 1, 0, 3, 12};
moveZeroes(array);
Arrays.stream(array).forEach(item -> System.out.print(item + " "));
}
}
|
第 27 道目 - 移除元素
题目描述
- 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
- 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回 k。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
|
题目来源
这是 LeetCode 的第 27 道算法题 - 移除元素，难度为简单。
题目分析
在一般情况下，只要数组是有序的，就应该想到双指针的解题技巧。双指针主要分为两类：
左右指针（left/right）
- 可能相向，可能相背，多用于数组。
- 使用口诀
- 结果比目标，小了要变大，左针右移。
- 结果比目标，大了要变小，右针左移。
快慢指针（slow/fast）
- 也叫 “前后指针”。
- 两个指针同向而行，一快一慢，多用于链表。
- 使用口诀
- 快慢值相等，慢针不动，快针向前一步走。
- 快慢不等值，情形一，慢针向前一步走，快针赋值给慢针，快针向前一步走。
- 快慢不等值，情形二，快针慢针值互换，慢针向前一步走，快针向前一步走。
题目答案
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
|
public class RemoveElement {
public static int removeElement(int[] nums, int val) {
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
int tmp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = tmp;
slow++;
}
fast++;
}
return slow;
}
public static void main(String[] args) {
int[] array = new int[] {0, 1, 2, 2, 3, 0, 4, 2};
int length = removeElement(array, 2);
System.out.println(length);
}
}
|
