《剑指Offer》笔记题解思路技巧优化 Java版本——新版leetcode_Part_5

😍😍😍 相知

当你踏入计算机科学的大门，或许会感到一片新奇而陌生的领域，尤其是对于那些非科班出身的学子而言。作为一位非科班研二学生，我深知学习的道路可能会充满挑战，让我们愿意迎接这段充满可能性的旅程。

最近，我开始了学习《剑指Offer》和Java编程的探索之旅。这不仅是一次对计算机科学的深入了解，更是对自己学术生涯的一次扩展。或许，这一切刚刚开始，但我深信，通过努力与坚持，我能够逐渐驾驭这门技艺。

在这个博客中，我将深入剖析《剑指Offer》中的问题，并结合Java编程语言进行解析。

让我们一起踏上这段学习之旅，共同奋斗，共同成长。无论你是已经驾轻就熟的Java高手，还是像我一样初出茅庐的学子，我们都能在这里找到彼此的支持与激励。让我们携手前行，共同迎接知识的挑战，为自己的未来打下坚实的基石。

这是我上一篇博客的，也希望大家多多关注！

1. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_1
2. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_2
3. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3
4. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_4

🙌🙌🙌 相识

根据题型可将其分为这样几种类型：

1. 结构概念类（数组，链表，栈，堆，队列，树）
2. 搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）
3. 双指针定位类（快慢指针，指针碰撞，滑动窗口）
4. 排序类（快速排序，归并排序）
5. 数学推理类（动态规划，数学）

😢😢😢 开始刷题

🟢1. LCR 158. 库存管理 II——数组中出现次数超过一半的数字

题目跳转：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/description/

排序法

class Solution {public int inventoryManagement(int[] stock) {//复杂度O(nlgn)Arrays.sort(stock);return stock[stock.length/2];}
}

摩尔投票法
要投票当领导 依次遍历 我们知道众数的领导一定赢 如果不一样 就抵消！

class Solution {public int inventoryManagement(int[] stock) {if(stock.length <= 2){return stock[0];}int x = stock[0];int sum = 1;for(int i =1;i<stock.length;i++){if(sum == 0){x = stock[i];sum = 1;}else{if(x == stock[i]){sum++;} else {sum--;}}}return x;}
}

---

🟢2. LCR 159. 库存管理 III——最小的k个数

题目跳转：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/

排序

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {if(cnt>=stock.length)return stock;Arrays.sort(stock);int[] result = new int [cnt];for(int i = 0;i<cnt;i++){result[i] = stock[i];}return result;}
}

学会个函数

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {if(cnt>=stock.length)return stock;Arrays.sort(stock);return Arrays.copyOfRange(stock, 0, cnt);}
}

快排

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 最后一个参数表示我们要找的是下标为k-1的数return quickSearch(arr, 0, arr.length - 1, k - 1);}private int[] quickSearch(int[] nums, int lo, int hi, int k) {// 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；int j = partition(nums, lo, hi);if (j == k) {return Arrays.copyOf(nums, j + 1);}// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);}// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。private int partition(int[] nums, int lo, int hi) {int v = nums[lo];int i = lo, j = hi + 1;while (true) {while (++i <= hi && nums[i] < v);while (--j >= lo && nums[j] > v);if (i >= j) {break;}int t = nums[j];nums[j] = nums[i];nums[i] = t;}nums[lo] = nums[j];nums[j] = v;return j;}
}

---

🔴3. LCR 160. 数据流中的中位数——数据流中的中位数

题目跳转：https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/description/

直接重排变成有序数组 挺暴力的

class MedianFinder {List<Integer> list = null;/** initialize your data structure here. */public MedianFinder() {list = new ArrayList<>();}public void addNum(int num) {list.add(num);}public double findMedian() {Collections.sort(list);if(list.size() % 2 == 0){return (double)(list.get(list.size()/2 -1) + list.get(list.size()/2))/2.0;}else{return (double)list.get(list.size()/2);}}
}

大根堆和小根堆

class MedianFinder {Queue<Integer> min, max;/** initialize your data structure here. */public MedianFinder() {min = new PriorityQueue<>(); // ⼩根，保存较⼤的max = new PriorityQueue<>((x, y) -> (y - x));// ⼤根}public void addNum(int num) {// 如果是偶数if(min.size() == max.size()){min.add(num);max.add(min.poll());} else {max.add(num);min.add(max.poll());}}public double findMedian() {// 如果是偶数if(min.size() == max.size()){return (min.peek() + max.peek()) / 2.0;} else {return max.peek() * 1.0;}}
}

---

🟢4. LCR 161. 连续天数的最高销售额——连续子数组的最大和

题目跳转：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/description/

class Solution {public int maxSales(int[] sales) {int[] maxsale = new int[sales.length];int sum = -101;maxsale[0] = sales[0];sum = Math.max(sum,maxsale[0]);for(int i = 1;i<sales.length;i++){if(maxsale[i-1]>=0){maxsale[i] = maxsale[i-1]+sales[i];}else{maxsale[i] = sales[i];}sum = Math.max(sum,maxsale[i]);}return sum;}
}

---

🔴5. LCR 162. 数字 1 的个数——1~n整数中1出现的次数

题目跳转：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/description/

给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。
示例 1：
输入：num = 0 输出：0 示例 2：
输入：num = 13 输出：6
解释：1（1次）、10（1次）、11（2次）、12（1次）、13（1次） 共 6次

如果你想的是这个，别想了 超时警告

class Solution {
public:int countDigitOne(int n) {int count = 0;for (int i = 1; i <= n; i++) {count += countOne(i);}return count;}int countOne(int n) {int num = 0;while (n) {if (n % 10 == 1) {num++;}n /= 10;}return num;}
};```

//3101592/**计算从1-n出现1的总次数*就是计算1-n所有整数 个位+十位+百位+..为1的总和*举个例子：把百位固定*3101 5 92  我们把百位 5>1 取出来 *5前面可以取0-3101，5后面可以取0-99*一共有（3101+1）*100（百位）种组合使百位为1**再举个例子：把千位固定*310 1 592  我们把千位1=1取出来 这里可以分两种情况：*  1前面可以取0-309时 1后面可以取0-999*  1前面取310，1后面可以取0-592*一共有（310）*1000（千位）+（592+1）种组合使千位为1*再举最后一个例子：把万位固定*31 0 1592，把万位0<1 前面可以取0-30,0后面可以取0-9999*一共有（31）*10000（万位）种组合使万位为1*我们可以分别计算一个数的个位百位...对应的组合数，最后相加*基本情况就是上面的例子，分别对应的位元素 是大于1，等于1，等于0*/

class Solution {public int digitOneInNumber(int num) {if(num<=0)return 0;long  base = 1;long  res = 0;while(base<=num){long b = num % base;long a = num / base;long cur = a%10;a/=10;if(cur>1)res +=(a+1)*base;else if(cur==1) res +=(a*base+b+1);else res += a*base;base*=10;}return (int)res;}
}

---

🟡6. LCR 163. 找到第 k 位数字——数字序列中某一位的数字

题目跳转：https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/description/

/* 数字范围    数量  位数    占多少位1-9        9      1       9*1=910-99      90     2       90*2=180100-999    900    3       900*3=27001000-9999  9000   4       9000*4=36000  ...例如 2901 = 9 + 180 + 2700 + 12 即一定是4位数,第12位   n = 12;数据为 = 1000 + (12 - 1)/ 4  = 1000 + 2 = 1002定位1002中的位置 = (n - 1) %  4 = 3    s.charAt(3) = 2;
*/

class Solution {public int findKthNumber(int n) {if(n<=9)return n;long bit = 1;int i = 1;long count = 9;while(count < n){n = (int)(n - count);bit = bit * 10;i++;count = bit * i * 9;}// 确定是在这个区间的哪个数long num = bit + (n - 1) / i;// 确定在 Num 的那个字符int index = (n - 1) % i + 1;int res = (int)(num / Math.pow(10, i - index)) % 10;return res;}
}

---

🟡7. LCR 164. 破解闯关密码——把数组排成最小的数

题目跳转：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/description/

class Solution {public String crackPassword(int[] password) {String[] passwordstring = new String[password.length];for(int i = 0;i < password.length;i++){//passwordstring[i] = password[i]+"";passwordstring[i] = String.valueOf(password[i]);}StringBuilder stringbuilder = new StringBuilder();Arrays.sort(passwordstring,(a,b)-> ((a+b).compareTo(b+a)));for(int i = 0;i < passwordstring.length;i++){stringbuilder.append(passwordstring[i]);}return stringbuilder.toString();}
}

学习快排

class Solution {public String crackPassword(int[] password) {String[] passwordstring = new String[password.length];for(int i = 0;i < password.length;i++){//passwordstring[i] = password[i]+"";passwordstring[i] = String.valueOf(password[i]);}quickSort(passwordstring,0,passwordstring.length-1);StringBuilder stringbuilder = new StringBuilder();for(int i = 0;i < passwordstring.length;i++){stringbuilder.append(passwordstring[i]);}return stringbuilder.toString();}public void quickSort(String[] arr,int left ,int right){if(left>right){return;}int i = partition(arr, left, right);quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}int partition(String[] arr, int left, int right){String pivot = arr[left]; // 中间值int i = left;int j = right;while (i < j) {while (i <= j && (arr[i] + pivot).compareTo(pivot +arr[i]) <= 0) {i++;}while (i <= j && (arr[j] + pivot).compareTo(pivot +arr[j]) >= 0) {j--;}if(i >= j){break;}String temp = arr[i];arr[i] = arr[j];arr[j] = temp;}arr[left] = arr[j];arr[j] = pivot;return j;}   
}

---

🟡8. LCR 165. 解密数字——把数字翻译成字符串

题目跳转：https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/description/

class Solution {public int crackNumber(int ciphertext) {String string = ciphertext+"";int temp = string.length();int [] dp = new int[temp+1];dp[0] = 1;dp[1] = 1;for(int i = 2;i<=temp;i++){if(string.charAt(temp-i)>'2'||string.charAt(temp-i)=='0'){dp[i] = dp[i-1];}else if (string.charAt(temp-i)=='2'){if(string.charAt(temp-i+1)<='5'){dp[i]=dp[i-1]+dp[i-2];}else{dp[i] = dp[i-1];}}else{dp[i]=dp[i-1]+dp[i-2];}}return dp[temp];}
}

---

🟡9. LCR 166. 珠宝的最高价值——礼物的最大价值

题目跳转：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/

class Solution {public int jewelleryValue(int[][] frame) {if(frame.length==0||frame[0].length==0)return 0;// 动态规划int [][] dp = new int[frame.length][frame[0].length];for(int i = 0;i<frame.length;i++){for(int j = 0;j<frame[i].length;j++){if(i==0&&j==0){dp[i][j] = frame[i][j];}else if(i!=0&&j==0){dp[i][j] = frame[i][j]+dp[i-1][j];}else if(j!=0&&i==0){dp[i][j] = frame[i][j]+dp[i][j-1];}else{dp[i][j] = frame[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[frame.length-1][frame[0].length-1];}
}

---

🟡10. LCR 167. 招式拆解 I——最长不含重复字符的子字符串

题目跳转：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/

自己写的

class Solution {public int dismantlingAction(String arr) {if(arr.length()==0||arr.length()==1)return arr.length();char [] chararr = arr.toCharArray();int left = 0;int right = 0;HashMap<Character,Integer> hashMap = new HashMap<>();int [] result = new int[chararr.length];int max = 1;for(int i = 0;i<chararr.length;i++){if(i == 0) {result[0] = 1;hashMap.put(chararr[0],1);continue;}int temp = result[i-1]+1;if(hashMap.containsKey(chararr[i])&&hashMap.get(chararr[i])!=0){while(hashMap.containsKey(chararr[i])&&hashMap.get(chararr[i])!=0){hashMap.put(chararr[left],hashMap.get(chararr[left])-1);temp--;left++;if(left==right)break;}result[i]= temp;}else if(!hashMap.containsKey(chararr[i])||(hashMap.containsKey(chararr[i])&&hashMap.get(chararr[i])==0)){temp = result[i-1]+1;result[i]= temp;}max = Math.max(max,result[i]);hashMap.put(chararr[i],1);}return max;}
}

优化版本

class Solution {// 优化版本public int lengthOfLongestSubstring(String s) {if(s == null || s.length() <= 0){return 0;}// 优化 => 单个变量Map<Character,Integer> map = new HashMap<>();//int[] dp = new int[s.length()];int a = 1;map.put(s.charAt(0), 0);int res = 1;for(int i = 1; i < s.length(); i++){if(!map.containsKey(s.charAt(i))){a = a + 1;// 就是没有刷新 a 之前，a表示dp[i-1]}else{int k = map.get(s.charAt(i));a = i - k <= a ? i - k : a + 1;}res = Math.max(res, a);map.put(s.charAt(i), i);}return res;// 时间On,空间On}
}

---