数组中重复的数字
剑指 Offer 03. 数组中重复的数字 - 力扣（Leetcode）
题目要求
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
例子：
1
2
3
| 输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
|
限制
2 <= n <= 100000
思路分析
解题方法
- 排序法；时间O(nlogn)，空间O(1)
- 哈希表；时间O(n)，空间O(n)
- 下标法(最优)；时间O(n)，空间O(1)
下标法
通过不停交换元素，使得元素和它所对应的下标相等，即nums[i] = i；当多个元素对应同一个下标，说明找到重复的元素，直接返回；判断条件nums[nums[i]] = nums[i]。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int findRepeatNumber(int[] nums) {
for(int i=0;i<nums.length;i++){
while(nums[i]!=i){
if(nums[i]==nums[nums[i]]){
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}
|
二维数组中的查找
剑指 Offer 04. 二维数组中的查找 - 力扣（Leetcode）
题目要求
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
非递减：递增的时候允许重复；
非递增：递减的时候允许重复；
例子：
现有矩阵 matrix 如下
1
2
3
4
5
6
7
| [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
|
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
思路分析
解题方法
- 二分查找；时间O(nlogm)
- 以数组左下角建立坐标系(最优)；时间O(m+n)
以数组左下角建立坐标系
从二维数组左下角进行观察，可以发现，该元素比它上面的元素大，比它右边的元素小；
如果一个数比左下角元素小，那就向上移动，即col++；如果该数比左下角大，那就向右移动，即row--；
注意：这里的 左下角元素 是随着移动而变化的。
代码实现
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
| class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix==null || matrix.length<=0 || matrix[0].length<=0){
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
int row = rows-1;
int col = 0;
while(row>=0 && col<cols){
if(target>matrix[row][col]){
col++;
}else if(target<matrix[row][col]){
row--;
}else{
return true;
}
}
return false;
}
}
|
替换空格
剑指 Offer 05. 替换空格 - 力扣（Leetcode）
题目要求
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
例子：
1
2
| 输入：s = "We are happy."
输出："We%20are%20happy."
|
限制：
0 <= s 的长度 <= 10000
思路分析
解题方法
- StringBuilder -> append或replace 时间O(n)，空间O(n)
- 扩容 时间O(logn)，空间O(1)
分析
解法一：创建StringBuilder，遍历字符串，使用append方法，遇到字母就直接放入，遇到空格就替换为%20，最后将StringBuilder转换为String返回即可；
解法二：创建数组，将字符串遍历放入数组，然后对数组大小进行扩容，从右向左进行遍历，遇到字母就放在右边，遇到空格就替换为%20；
代码实现
解法一：StringBuilder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public String replaceSpace(String s) {
StringBuilder strB = new StringBuilder();
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' '){
strB.append("%20");
}else{
strB.append(s.charAt(i));
}
}
return strB.toString();
}
}
|
解法二：扩容
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
| class Solution {
public String replaceSpace(String s) {
int count = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' '){
count++;
}
}
char[] res = new char[s.length()+count*2];
int f = res.length-1;
for(int i = s.length()-1;i>=0;i--){
if(s.charAt(i)==' '){
res[f--] = '0';
res[f--] = '2';
res[f--] = '%';
}else{
res[f--] = s.charAt(i);
}
}
return new String(res);
}
}
|
从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表 - 力扣（Leetcode）
题目要求
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
例子：
1
2
| 输入：head = [1,3,2]
输出：[2,3,1]
|
限制：
0 <= 链表长度 <= 10000
思路分析
解题方法
- 栈 时间O(n)，空间O(n)
- 反转链表
- 递归 时间O(n)，空间O(n)；
- 原地反转 时间O(n)，空间O(1)；
- 从右向左放入数组 时间O(n)，空间O(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
|
class Solution {
public int[] reversePrint(ListNode head) {
if(head==null){
return new int[0];
}
int count = 0;
ListNode temp = head;
while(temp!=null){
count++;
temp = temp.next;
}
int[] arr = new int[count];
int f = count-1;
while(head!=null){
arr[f--] = head.val;
head = head.next;
}
return arr;
}
}
|
重建二叉树
剑指 Offer 07. 重建二叉树 - 力扣（Leetcode）
题目要求
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例子：
1
2
| Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
|
例子2：
1
2
| Input: preorder = [-1], inorder = [-1]
Output: [-1]
|
限制：
0 <= 节点个数 <= 5000
思路分析
把根节点3看作 i
前序遍历：preStart [3,9,20,15,7] preEnd
中序遍历：inStart [9,3,15,20,7] inEnd
中序遍历左右子树：[inStart,i-1] [i+1,inEnd]
前序遍历左右子树：[preStart+1,preStart+(i-inStart)] [preStart+(i-inStart)+1,preEnd]
方括号代表左右子树，方括号里的代表左右子树各自的左右子节点；
使用HashMap存放元素和下标：Map<元素,下标>
代码实现
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
38
39
40
41
42
|
class Solution {
Map<Integer,Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || preorder.length<=0){
return null;
}
for(int i = 0;i<inorder.length;i++){
map.put(inorder[i],i);
}
TreeNode root = f(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
return root;
}
TreeNode f(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
if(preStart>preEnd || inStart>inEnd){
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int i = map.get(preorder[preStart]);
root.left = f(preorder,preStart+1,preStart+(i-inStart),inorder,inStart,i-1);
root.right = f(preorder,preStart+(i-inStart)+1,preEnd,inorder,i+1,inEnd);
return root;
}
}
|
