剑指offer题目记录
仅作为个人笔记使用【每日一道题】
3.数组中的重复数字
题目描述：
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input: { 2, 3, 1, 0, 2, 5} Output: 2 12345
<mark>解题思路</mark>：
最优解题：要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。
对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。
以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复
class Solution {
public int findRepeatNumber(int[] nums) {
int temp;
for(int i=0;i<nums.length;i++){
//这个while循环其实对数组进行了一次排序，让下标和值对应
while (nums[i]!=i){
if(nums[i]==nums[nums[i]]){
return nums[i];
}
temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
}
return -1;
}
}
说明：
以(2,3,1,0,2,5)为例：
num[0] = 2 != 0 进入while循环 交换num[0]和num[2]的值：(1,3,2,0,2,5)
此时：num[0] = 1 依然不等于0 继续交换 (3,1,2,0,2,5)
num[0] = 3 继续交换 (0,1,2,3,2,5)
此时满足num[0] = 0 继续for循环
1，2，3都满足条件 当i=4的时候
num[4] = 2 进入while循环 首先判断num[4]==num[num[4]]=2返回num[4]也就是2
<mark>第二种解题</mark>：使用HashSet：
思路:创建一个HashSet集合 遍历nums数组 先判断集合中是否有该元素 如果有直接返回该数字 如果没有加入集合中
class Solution {
public int findRepeatNumber(int[] nums) {
//使用HashSet解题
//首先判断nums是否为空或者是否长度为0
if(nums==null||nums.length==0){
return -1;
}
//创建一个HashSet集合
HashSet<Integer> hashset = new HashSet<>();
for(int n:nums){
if(hashset.contains(n)){
return n;
}
else{
hashset.add(n);
}
}
return -1;
}
}
hashset.add(n);
}
}
return -1;
}
}
4.二维数组中的查找
题目描述：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[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。
<mark>解题思路</mark>：
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//如果二维数组为空或长度等于0 返回false
if(matrix.length == 0 || matrix == null)
return false;
//分别获取行和列的长度
int rows = matrix.length;
int cols = matrix[0].length;
//从右上角开始缩小范围
int r = 0, c = cols - 1;
while(r <= rows-1 && c >= 0) {
if(target == matrix[r][c])
return true;
//如果这个数比matrix[r][c]大只有可能在这一行下面
else if(target > matrix[r][c])
r++;
//如果这个数比matrix[r][c]小只有可能在这一列左边
else
c--;
}
return false;
}
}
5.替换空格
题目描述：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”
<mark>解题思路</mark>：比较容易想到的办法：创建一个StringBuilder对象然后利用其append方法 先循环判断这个字符串是否有空格，
如果是空格.append("%20")，如果不是空格，.append(“s[i]”)
class Solution {
public String replaceSpace(String s) {
StringBuilder string = new StringBuilder();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (c == ' '){
string.append("%20");
} else {
string.append(c);
}
}
return string.toString();
}
}
<mark>第二种办法</mark>：由于每次替换会导致由一个字符变为三个字符，所以先创建一个长度为s的三倍长的数组，并且定义一个size来记录数组的实际长度 初始化size=0，遍历字符串，如果当前字符是空格 则array[size]=’%’ array[size+1]=‘2’ array[size+2]=‘0’，如果是普通字符array[size]=c，并且size++。
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
//先运算再加1 size[0]='%'
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
}
从尾到头打印链表
<mark>题目描述</mark>：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
<mark>解题思路</mark>：
当看到从尾到头打印 也就是逆序 后进先出想到栈，创建一个栈存放链表元素，当链表不为空时，依次将链表元素压入栈，然后创建以一个数组，
长度为栈的大小，使用循环将栈中元素依次放入数组即可。
<mark>代码</mark>：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
ListNode temp = head;
while (head != null) {
stack.push(head);
head = head.next;
}
int size = stack.size();
int[] print = new int[size];
for (int i = 0; i < size; i++) {
print[i] = stack.pop().val;
}
return print;
}
}
10.1斐波那契数列
<mark>题目描述</mark>：
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
<mark>解题思路</mark>：
首先想到的是传统的递归算法，但是深度过大递归会导致栈溢出，我们可以将前2个数之和保存起来留在下次使用，使用动态规划
递归解决：【超时】
class Solution {
public:
int fib(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
return (fib(n-1)+fib(n-2))%1000000007;
}
};
动态规划：
class Solution {
public int fib(int n) {
int a = 0, b = 1, sum;
for(int i = 0; i < n; i++){
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
10.2青蛙跳台阶问题
<mark>题目描述</mark>：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：输入：n = 7
输出：21
示例 3：输入：n = 0
输出：1
<mark>解题思路</mark>：本题和斐波那契数列本质相同，青蛙要跳n阶台阶，那么它最后一次只有两种可能，要么跳一阶要么跳两阶，
f(n)=f(n-1)+f(n-2)，同斐波那契数列，唯一不同的是启始数字不同，
- 青蛙跳台阶问题： f(0)=1f(0)=1 , f(1)=1f(1)=1 , f(2)=2f(2)=2 ；
- 斐波那契数列问题： f(0)=0f(0)=0 , f(1)=1f(1)=1 , f(2)=1f(2)=1 。
动态规划：
class Solution {
public int numWays(int n) {
int a =1; int b = 1;int sum;
for(int i = 0;i < n;i++){
sum = (a+b)%1000000007;
a = b;
b = sum;
}
return a;
}
}
10.3变态青蛙跳台阶问题
<mark>题目描述</mark>：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
<mark>解题思路</mark>：
我们可以分多种情况讨论:
- 当跳一次的时候，一次跳１级或者2级的时候，都只有１种
- 当n>2的时候，下次可能会跳１~n级之间，当下次跳１级的时候，还剩下f(n－１)，跳2级的时候，剩下f(n-2),3级的时候,剩下f(n-3),
类推到下次跳n-1级的时候，剩下f(n-(n-1))＝f(1),当为n级时，剩下f(n-n)=f(0),
所以总共有f(n)=f(n-1)+f(n-2)+…+f(1)+f(0) - f(n-1) = f(n-2)+…+f(1)+f(0)
- 所以：f(n) = 2f(n-1) 所以f(n)是一个等比数列
- 因为f(1) = 1 f(2) = 2
- f(n) = pow(2, n - 1)
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
11.旋转数组的最小数字
<mark>题目描述</mark>：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：输入：[2,2,2,0,1]
输出：0
<mark>解题思路</mark>：
- 最容易想到的就是直接排序后数组的第一个元素肯定是最小的元素 但时间复杂度高
- 一看到排序数组的查找 应该考虑使用二分法
排序解决：
class Solution {
public int minArray(int[] numbers) {
Arrays.sort(numbers);
return numbers[0];
}
}
二分法：
class Solution {
public int minArray(int[] numbers) {
int left = 0, right = numbers.length - 1;
while (left < right) {
//找出left和right中间值的索引
int mid = left + (right - left) / 2;
if (numbers[mid] > numbers[right]) {
//如果中间值大于最右边的值，说明旋转之后最小的
//数字肯定在mid的右边，比如[3, 4, 5, 6, 7, 1, 2]
left = mid + 1;
} else if (numbers[mid] < numbers[right]) {
//如果中间值小于最右边的值，说明旋转之后最小的
//数字肯定在mid的前面，比如[6, 7, 1, 2, 3, 4, 5],
//注意这里mid是不能减1的，比如[3，1，3]，我们这里只是
//证明了numbers[mid]比numbers[right]小，但有可能
//numbers[mid]是最小的，所以我们不能把它给排除掉
right = mid;
} else {
//如果中间值等于最后一个元素的值，我们是没法确定最小值是
// 在mid的前面还是后面，但我们可以缩小查找范围，让right
// 减1，因为即使right指向的是最小值，但因为他的值和mid
// 指向的一样，我们这里并没有排除mid，所以结果是不会有影响的。
//比如[3，1，3，3，3，3，3]和[3，3，3，3，3，1，3],中间的值
//等于最右边的值，但我们没法确定最小值是在左边还是右边
right--;
}
}
return numbers[left];
}
}
14剪绳子
【这个结论比较重要 要牢记 复习重点】
<mark>题目描述</mark>：
给你一根长度为 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
<mark>解题思路</mark>:
数论：【记忆】
1. 任何大于1的数都可由2和3相加组成（根据奇偶证明）
2. 因为2*2=1*4，2*3>1*5, 所以将数字拆成2和3，能得到的积最大
3. 因为2*2*2<3*3, 所以3越多积越大
<mark>解题</mark>:
当n<=3时 按照理论应该3就是最优解 但是题目要求必须至少剪一段 所以2+1
当n>3时候 n/3=3x+b n%3可能有三种情况
1. n%3=0 直接返回3^x即可
2. n%3=1 此时注意 因为2*2>3*1 所以应该把其中一个3拆分出来 变成2*2
3. n%3=2 返回2*3^x即可
<mark>代码</mark>：
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;
}
}
2021/8/10 力扣204 计数质数
解决方法：埃氏筛：
boolean[] arr = new boolean[n];
//把arr数组全部设置为true
Arrays.fill(arr,true);
for(int i = 2;ii<n;i++){
if(arr[i]){
for(int j =ii;j<n;j+=i){
arr[j] = false;
}
}
}
//遍历
int count = 0;//记录质数个数
for(int i= 2;i<n;i++){
if(arr[i]){
count++;
}
}
return count;
}
京公网安备 11010502036488号