剑指offer

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

该篇是关于算法的剑指offer刷题系列

剑指offer72题

数组

JZ3 数组中重复的数字

描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤𝑛≤10000 0≤n≤10000

进阶：时间复杂度𝑂(𝑛) O(n) ，空间复杂度𝑂(𝑛) O(n)

示例

1
2
3
输入：[2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的

解题

方案1：

暴力法(for + for)

方案2：

哈希表

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def duplicate(self , numbers: List[int]) -> int:

        # write code here
        # 法2：哈希表
        record = {} // // 用来记录已遍历的数
        for num in numbers:
            if num not in record: # 未记录则添加
                record[num] = 1 # value可以任意
            else: return num # 已记录则返回该数
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int duplicate (int[] numbers) {
        // write code here
        if (numbers == null || numbers.length == 0){
            return -1;
        }
        HashSet<Integer> record = new HashSet<>(); // 用来记录已遍历的数
        
        for (int num : numbers){
            if (record.contains(num)){ // 已记录则直接return该值
                return num;
            }
            else{
                record.add(num); // 未记录则添加
            }
        }
        
        return -1;
    }
}
方案3：

可以使用两数之和的index<--->value思想

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        # write code here

        # 利用好已知的[0, n-1] --> 使用idx<-->value思想（两数之和）
        if ( len(numbers) < 2 ): return -1
        record = [0] * len(numbers) # 利用已知条件

        for num in numbers:
            record[num] += 1 # value ——> idx
            if record[num] == 2: return num

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int duplicate (int[] numbers) {
        // write code here
        // 关键点：长度为n的数组里的所有数字都在0到n-1的范围内
        /**
        * 利用 index <--> value 思想
        * 1. 可定义一个zero_like(numbers), 即定义一个与numbers等长的元素集合为零的数组
        * 2. 遍历numbers，让其元素值作为自定义数组的索引（这里就利用了题目给定的一个关键点信息）
        * 3. 遍历一个索引添加一个，让其值由原来的0实现++，索引定位元素值大于1（或者等于2）的时候返回该元素
         */
         int[] record = new int[numbers.length]; // 1.
         for (int i = 0; i < numbers.length; i++){
            record[numbers[i]]++; // 2.
            if (record[numbers[i]] == 2){
                return numbers[i];
            }
         }
        return -1;
    }
}
方案3优化：

将两个List用一个原始List实现

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        # write code here
        # 对于第一次不同： 对num 和 index对应（不对应进行交换），对应则返回
        for idx in range(len(numbers)):
            while idx != numbers[idx]:
                if numbers[idx] == numbers[numbers[idx]]: #why？？？
                    return numbers[idx]    
                numbers[numbers[idx]], numbers[idx] = numbers[idx], numbers[numbers[idx]] # why不能把后换前
            
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int duplicate (int[] numbers) {
        // write code here
        for (int i  = 0; i < numbers.length; i++){
            while (i != numbers[i]){ //idx和value不同
                if (numbers[i] == numbers[numbers[i]]){ // 
                    return numbers[i];
                }
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] =  numbers[i];
                numbers[i] = temp;
            }
        }
        return -1;
    }
}

JZ5 替换空格

描述

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围:0≤𝑙𝑒𝑛(𝑠)≤1000 0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

示例

1
2
输入："We Are Happy"
返回值："We%20Are%20Happy"

解题

方案1：

直接遍历，遇到则转换，将遍历结果添加到新的String中。

补充知识点：java中String追加char的三种方法——Add Cahr To String For Java

1
2
3
4
5
6
7
8
9
10
class Solution:
    def replaceSpace(self , s: str) -> str:
        # write code here
        new_s = ""
         for char in s:
             # for char in list(s): # 改用list？效率为啥提高了？
             if char == " ":
                 char = "%20"
             new_s += char
         return new_s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public String replaceSpace (String s) {
        // write code here
      	//String newS = s.replace(" ", "%20");
        String newS = "";
      	char[] ch = s.toCharArray();
        for (char c: ch){ // 别放在forEach里面，会降低效率
            if (c == ' '){
                newS += '%';
                newS += '2';
                newS += '0';
            }
            else newS = newS + c;
        }
        return newS;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public String replaceSpace (String s) {
        // write code here
      	// 使用StringBuffer
        StringBuffer sb = new StringBuffer();
        char[] ch = s.toCharArray(); // 别放在forEach里面，会降低效率
        for (char c: ch){
            if (c == ' '){
                sb.append('%');
                sb.append('2');
                sb.append('0');
            }else sb.append(c);
        }
        return sb.toString();
    }
}
方案2：

字符串扩容，扩容 空格字符*2 个单元，倒序遍历字符串，追加到扩容字符，按照条件进行添加处理

JZ17 打印从1到最大的n位数

描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

  1. 用返回一个整数列表来代替打印
  2. n 为正整数，0 < n <= 5

示例

1
2
输入：1
返回值：[1,2,3,4,5,6,7,8,9]

解题

方案1：

直接暴力遍历（注意边界条件）

1
2
3
4
5
class Solution:
    def printNumbers(self , n: int) -> List[int]:
        # write code here
        return [number for number in range(1, 10**n)]

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int[] printNumbers (int n) {
        // write code here
        int[] res = new int[(int)Math.pow(10,n) - 1];
        for (int i = 1; i < Math.pow(10, n); i++){
            res[i-1] = i;
        }
        return res;
    }
}
方案2：

JZ21 调整数组顺序使奇数位于偶数前面(一)

描述

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：0≤𝑛≤50000≤n≤5000，数组中每个数的值 0≤𝑣𝑎𝑙≤100000≤val≤10000

要求：时间复杂度 𝑂(𝑛)O(n)，空间复杂度 𝑂(𝑛)O(n)

进阶：时间复杂度 𝑂(𝑛2)O(n2)，空间复杂度 𝑂(1)O(1)

示例

1
2
输入：[1,2,3,4]
返回值：[1,3,2,4]

解题

方案1：

奇偶拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        # write code here
        # 双指针->> 左边找新奇数，右边找
        new_arr = [0] * len(array)

        count = 0 #奇数计数器
        for num in array:
            if num % 2 == 1:
                count += 1
        tow = 0
        for idx in range(len(array)):
            if not array[idx] % 2:
                new_arr[count] = array[idx]
                count += 1
            else: 
                new_arr[tow] = array[idx]
                tow += 1
        return new_arr

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        # write code here
        # 双指针->> 左边找新奇数，右边找
        new_arr = []
        for num in array:
            if num % 2:
                new_arr += [num] # new_arr.append(num)
        for num in array:
            if not num % 2:
                new_arr += [num] # new_arr.append(num)
        return new_arr
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int[] printNumbers (int n) {
        // write code here
        int[] res = new int[(int)Math.pow(10,n) - 1];
        for (int i = 1; i < Math.pow(10, n); i++){
            res[i-1] = i;
        }
        return res;
    }
}
方案2：

全排列（考虑大数情况）

Z81 调整数组顺序使奇数位于偶数前面(二)

描述

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

数据范围：0≤𝑛≤500000≤n≤50000，数组中每个数的值 0≤𝑣𝑎𝑙≤100000≤val≤10000

要求：时间复杂度 𝑂(𝑛)，空间复杂度 𝑂(1)

示例1

1
2
输入：[1,2,3,4]
返回值：[1,3,2,4]

说明：

1
[3,1,2,4]或者[3,1,4,2]也是正确答案

解题

方案1：

同JZ21

方案2：

双指针

JZ39 数组中出现次数超过一半的数字

描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：𝑛≤50000n≤50000，数组中元素的值 0≤𝑣𝑎𝑙≤100000≤val≤10000

要求：空间复杂度：𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)

输入描述：

保证数组输入非空，且保证有解

案例

1
2
输入：[1,2,3,2,2,2,5,4,2]
返回值：2

解题

方案1：

利用排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        if not numbers: return -1 #空list判断
        if len(numbers)==1: return numbers[0] # 单元素返回

        lenght = len(numbers) / 2 # 用于判断
        numbers.sort() # 原地排序
        count = 1 # 用来记录当前遍历元素的相同值个数
        maxlen = 0 # 记录已遍历元素中相同值最多元素的个数
        res = -1 # 记录最多元素本身
        for idx in range(len(numbers) - 1):
            if maxlen > lenght: return res 
            if numbers[idx] == numbers[idx + 1]: # 利用排序的功能
                count += 1
                maxlen = max(maxlen, count) 
                res = numbers[idx + 1]
            else: count = 1

        return res


1

链表

JZ6 从尾到头打印链表

描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

img

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

示例1

1
2
输入：{1,2,3}
返回值：[3,2,1]

解题

方案1：

顺序存储，倒序输出——>>时间$O(n)$，空间$O(n)$​

补充：Java Collections交换Arraylist元素位置

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        # write code here
        # 1.顺序存放，倒序输出
        if not listNode: return []
        res = []
        while(listNode): # listNode是可迭代对象，listNode.val不是可迭代对象，只是一个值
            res.append(listNode.val)
            listNode = listNode.next
        return [res[idx] for idx in range(len(res)-1, -1, -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
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        // ArrayList<Integer> result = new ArrayList<>();
        if (listNode == null){
            return res;
        }

        while(listNode != null){
            res.add(listNode.val);
            listNode = listNode.next;
        }

        // 主要就是使用双指针进行交换，这里使用补充知识（集合工具类）
        int l = 0;
        for (int i = res.size() - 1; i > l; i--){ // 边界条件考虑不用 i >= l
            Collections.swap(res, l++, i);
        }
        
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      	// 使用同一个ArrayList记录
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null){
            return res;
        }

        while(listNode != null){
            res.add(listNode.val);
            listNode = listNode.next;
        }

        // 主要就是使用双指针进行交换

        return result;
    }
}
方案2：

JZ18 删除链表的节点

描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动

2.题目保证链表中节点的值互不相同

3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:

0<=链表节点值<=10000

0<=链表长度<=10000

示例1

1
2
输入：{2,5,1,9},5
返回值：{2,1,9}

解题

方案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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        """
        :param head: ListNode类 
        :param val: int整型 
        :return: 删除val值(节点)后的ListNode
        """
        # write code here
        # 遍历链表，当前遍历的next值为val则指向next的next，如果不是，遍历的next依旧是其next
        if not head: return head
        if head.val == val: return head.next

        # 为防止遍历中改变原始链表，应当copy一份head，并指定一个指针用于定位删除元素
        temp = head.next
        cur = head  # temp为copy，cur为删除定位
        while temp:  # 当删除最后一个元素，使用temp.next判断会失误
            if temp.val == val:
                cur.next = temp.next
                return head  # 共用元素，所以可以这样操作
            temp = temp.next  # 遍历的步骤
            cur = cur.next  # 这个就好比指针遍历的+=1
        return head
1

方案2：

xxxx