剑指Offer--LeetCode刷题篇_day02

申明： 未经许可，禁止以任何形式转载，若要引用，请标注链接地址
全文共计6077字，阅读大概需要3分钟
欢迎关注我的个人公众号：不懂开发的程序猿

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：

输入：numbers = [3,4,5,1,2]
输出：1
1
2

示例 2：

输入：numbers = [2,2,2,0,1]
输出：0
1
2

【二分查找】

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
1
2

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
1
2

【尝试通过】通过测试用例：54 / 83

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        for (char[] chars1 : board) {
            for (char c : chars1) {
                for (char ch : chars) {
                    if (ch==c){
                        System.out.println(ch);
                    }
                }
                
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
1
2
3

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
1
2
3

提示：

• 2 <= n <= 58

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}
1
2
3
4
5
6
7
8
9

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3

示例 2：

输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
1
2
3

示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
1
2
3

提示：

• 输入必须是长度为 32 的 二进制串 。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        String binaryString = Integer.toBinaryString(n);
        for (char c : binaryString.toCharArray()) {
            if (c=='1'){
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

补充：实现从键盘输入一个十进制的数输出为二进制

    @Test
    public void binaryToDecimal() {
        //实现从键盘输入一个十进制的数输出为二进制

        System.out.println("从键盘输入一个十进制的数输出为二进制: ");
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();

        //方式一：
        String str = "";

        while (num != 0) {
            str = num % 2 + str;
            num = num / 2;

        }
        System.out.println(str);

        //方式二：调用Integer.toBinaryString()
        System.out.println(Integer.toBinaryString(num));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

【快速幂运算】

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剑指 Offer 17. 打印从1到最大的n位数

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

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
1
2

说明：

• 用返回一个整数列表来代替打印
• n 为正整数

class Solution {
    public static int[] printNumbers(int n) {
        int maxNum = (int) (Math.pow(10, n) - 1);

        int[] arr = new int[maxNum];
        for (int i = 1; i <= maxNum; i++) {
            arr[i - 1] = i;
        }

        return arr;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

剑指 Offer 18. 删除链表的节点

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

返回删除后的链表的头节点。

注意 此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
1
2
3

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
1
2
3

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    //删除链表的节点
    public ListNode deleteNode(ListNode head, int val) {
        //特例处理： 当应删除头节点 head 时，直接返回 head.next 即可。
        if (head.val == val) {
            return head.next;
        }
        //初始化： pre = head , cur = head.next 。
        ListNode pre = head, cur = head.next;

        //定位节点： 当 cur 为空 或 cur 节点值等于 val 时跳出
        while (cur != null && cur.val != val) {

            //保存当前节点索引，即 pre = cur 。
            pre = cur;
            //遍历下一节点，即 cur = cur.next 。
            cur = cur.next;
        }

        //删除节点： 若 cur 指向某节点，则执行 pre.next = cur.next ；若 cur 指向 null ，代表链表中不包含值为 val 的节点。
        if (cur!=null){
            pre.next=cur.next;
        }
        //返回值： 返回链表头部节点 head 即可。
        return head;
    }
}
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

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
1
2
3

提示：

1. 0 <= nums.length <= 50000
2. 0 <= nums[i] <= 10000

class Solution {
    public int[] exchange(int[] nums) {
       //方法一
        int i = 0, j = nums.length - 1;
        while (i < j) {
            if (nums[i]%2!=0){
                i++;
            }else {
                int temp = nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                j--;
            }
        }
        return nums;
        
        
        //方法二：双指针

        //指针 i 从左向右寻找偶数；
        //指针 j 从右向左寻找奇数；
        //将 偶数 nums[i] 和 奇数 nums[j] 交换。
        int i = 0, j = nums.length - 1, temp;

        //循环交换： 当 i = j 时跳出；
        while (i < j) {

            //指针 i 遇到奇数则执行 i = i + 1 跳过，直到找到偶数；
            while (i < j && (nums[i] % 2 != 0)) {
                i++;
            }
            // 指针 j 遇到偶数则执行 j = j - 1 跳过，直到找到奇数；
            while (i < j && (nums[j] % 2 == 0)) {
                j--;
            }

            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
        
        
    }
}
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
43
44
45
46

–end–