剑指 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
示例 2：
输入：numbers = [2,2,2,0,1] 输出：0
【二分查找】
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; elseif (numbers[m] < numbers[j]) j = m; else j--; } return numbers[i]; } }
剑指 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
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false
【尝试通过】通过测试用例：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; } }
剑指 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
示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
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; } }
剑指 Offer 15. 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011) 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000) 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n =4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n =-3） 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
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; } }
补充：实现从键盘输入一个十进制的数输出为二进制
@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)); }
剑指 Offer 16. 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-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; } }
剑指 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]
说明：
- 用返回一个整数列表来代替打印
- 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; } }
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意 此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
- 题目保证链表中节点的值互不相同
- 若使用 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; } }
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 500000 <= 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; } } }
END
