《剑指Offer》笔记&题解&思路&技巧&优化_Part_1
- 😍😍😍 相知
- 🙌🙌🙌 相识
- 😢😢😢 开始刷题
- 1. LCR 120. 寻找文件副本——数组中重复元素
- 2. LCR 121. 寻找目标值 - 二维数组——二维数组中查找
- 3. LCR 122. 路径加密——替换空格
- 4. LCR 123. 图书整理 I——从尾到头打印链表
- 5. LCR 124. 推理二叉树——重建二叉树
- 6. LCR 125. 图书整理 II——用两个栈实现队列
- 7. LCR 126. 斐波那契数——斐波那契数列
- 8. LCR 127. 跳跃训练——青蛙跳台阶问题
- 9. LCR 128. 库存管理 I——旋转数组的最小值
😍😍😍 相知
当你踏入计算机科学的大门,或许会感到一片新奇而陌生的领域,尤其是对于那些非科班出身的学子而言。作为一位非科班研二学生,我深知学习的道路可能会充满挑战,让我们愿意迎接这段充满可能性的旅程。
最近,我开始了学习
《剑指Offer》
和Java编程的探索之旅。这不仅是一次对计算机科学的深入了解,更是对自己学术生涯的一次扩展。或许,这一切刚刚开始,但我深信,通过努力与坚持,我能够逐渐驾驭这门技艺。在这个博客中,我将深入剖析
《剑指Offer》
中的问题,并结合Java编程语言进行解析。让我们一起踏上这段学习之旅,共同奋斗,共同成长。无论你是已经驾轻就熟的Java高手,还是像我一样初出茅庐的学子,我们都能在这里找到彼此的支持与激励。让我们携手前行,共同迎接知识的挑战,为自己的未来打下坚实的基石。
(得了!看吧!一起学习、一起努力!!!)
LeetCode估计版权原因,把剑指Offer系列题都下降了,估计大家根据题目是找不到了,但是LeetCode其实是换汤不换药,把剑指offer的题目和描述改了一下而已,其他的依然不变。按照我的标题继续冲!
🙌🙌🙌 相识
根据题型可将其分为这样几种类型:
- 结构概念类(数组,链表,栈,堆,队列,树)
- 搜索遍历类(深度优先搜索,广度优先搜索,二分遍历)
- 双指针定位类(快慢指针,指针碰撞,滑动窗口)
- 排序类(快速排序,归并排序)
- 数学推理类(动态规划,数学)
😢😢😢 开始刷题
1. LCR 120. 寻找文件副本——数组中重复元素
题目跳转:https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/description
- 这道题在原书上绝对不是简单级别啊!
- 它考察的是程序员的沟通能力,先问面试官要时间/空间需求!
-
只是时间优先就用哈希表 时间: O ( n ) O(n) O(n) 空间 O ( n ) O(n) O(n)
class Solution {public int findRepeatDocument(int[] documents) {// 定义数据结构Map<Integer,Integer> hashmap = new HashMap<>();// 遍历for(int temp :documents){if(hashmap.containsKey(temp))return temp; else hashmap.put(temp,1);}return 0;} }
-
还有空间要求,就用指针+原地排序数组 时间: O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n)) 空间 O ( 1 ) O(1) O(1)
class Solution {public int findRepeatDocument(int[] documents) {Arrays.sort(documents);for(int i = 0;i<documents.length-1;i++){if(documents[i]!=documents[i+1])continue;else return documents[i];}return 0;} }
-
0 ≤ documents[i] ≤ n-1
由于!这个限制的存在,我们可以利用鸽巢原理,所以我们可以将见到的元素 放到索引的位置,如果交换时,发现索引处已存在该元素,则重复 O ( n ) O(n) O(n)空间 O ( 1 ) O(1) O(1)class Solution {public int findRepeatDocument(int[] documents) {for(int i = 0;i<documents.length;++i){while(documents[i]!=i){if(documents[i]==documents[documents[i]])return documents[i];int k = documents[documents[i]];documents[documents[i]] = documents[i];documents[i] = k;}}return 0;} }
-
学会这个思想了嘛??真的???ok!来个难的!
41.缺失的第一个正数 https://leetcode.cn/problems/first-missing-positive/description/
代码给你附上了!
class Solution {public int firstMissingPositive(int[] nums) {for(int i = 0;i < nums.length;i++){while (nums[i]>0&&nums[i]<=nums.length){if (nums[i] == nums[nums[i]-1]) break; // 已经在对应位置int temp = nums[nums[i]-1];nums[nums[i]-1] = nums[i];nums[i] = temp;}}for(int i = 0;i < nums.length;i++){if(i+1!=nums[i])return i+1;}return nums.length+1;}
}
765.情侣牵手 https://leetcode.cn/problems/couples-holding-hands/description/
class Solution {public int minSwapsCouples(int[] row) {// /2 是n就是低n对(0开始)int result = 0;for(int i=1;i<row.length-1;i++){if(i%2 == 0)continue;if((row[i-1]/2)==(row[i]/2)) continue;for(int j = i+1;j<row.length;j++){if((row[i-1]/2)==(row[j]/2)){int k = row[j];row[j] = row[i];row[i] = k;result++;break;}}}return result;}
}
2. LCR 121. 寻找目标值 - 二维数组——二维数组中查找
题目跳转:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/
不废话
想到暴搜时间复杂度—— O ( n 2 ) O(n^2) O(n2)
暴搜这么优化啊!想到二分时间复杂度—— O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))
class Solution {public boolean findTargetIn2DPlants(int[][] plants, int target) {//个人反应//暴力搜素//二分法if(plants.length==0||plants[0].length==0)return false;int m = plants.length;int n = plants[0].length; int left = 0;int right = 0; int mid = 0;for(int i = 0;i<m;i++){left = 0;right = n-1; while(left<=right){mid = (right-left)/2+left;if(plants[i][mid]==target)return true;if(plants[i][mid]<target)left = mid+1;else{right = mid-1;}}}return false;}
}
再优化一版本!
看图说话!
class Solution {public boolean findTargetIn2DPlants(int[][] plants, int target) {if(plants.length==0||plants[0].length==0)return false;int m = plants[0].length-1;int n = 0; while(m>=0&&m<plants[0].length&&n>=0&&n<plants.length){if(plants[n][m]<target) n++;else if(plants[n][m]>target) m--;else return true;}return false;}
}
3. LCR 122. 路径加密——替换空格
题目跳转:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/description/
时间复杂度—— O ( n ) O(n) O(n),空间复杂度—— O ( n ) O(n) O(n)
class Solution {public String pathEncryption(String path) {return path.replace("."," ");}
}
但是!学一种数据结构!!
class Solution {public String pathEncryption(String path) {StringBuilder stringBuilder = new StringBuilder();for(int i =0;i<path.length();i++){stringBuilder.append(path.charAt(i)=='.'?' ':path.charAt(i));}return stringBuilder.toString();}
}
扩容!但是Java本身是不支持这样扩容的 但是模拟一下,加深印象!但是别学!
class Solution {public String pathEncryption(String path) {int count = 0;for(int i = 0;i<path.length();i++){if(path.charAt(i)=='.')count++;}char[] a = new char[path.length()+(1-1)*count];int temp = a.length-1;for(int i = path.length()-1;i >= 0;i--){if(path.charAt(i)!='.') a[temp--] = path.charAt(i);else{a[temp--] = ' ';}}return new String(a);}
}
4. LCR 123. 图书整理 I——从尾到头打印链表
题目跳转:https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/
栈——时间复杂度—— O ( n ) O(n) O(n),空间复杂度—— O ( n ) O(n) O(n)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int[] reverseBookList(ListNode head) {if(head==null) return new int[0];Stack<Integer> stack = new Stack();int count = 0;while(head!=null){count++;stack.push(head.val);head = head.next;}int [] result = new int[count];int a = 0;while(!stack.isEmpty()){result[a++] = stack.peek();stack.pop();}return result;}
}
反转链表
反转链表的代码 然后直接顺序都即可
class Solution {public ListNode reverseList(ListNode head) {if (head==null||head.next==null) return head;ListNode result_zero = null;ListNode cur = head;while(cur!=null){ListNode head_temp = cur.next;cur.next = result_zero;result_zero= cur;cur = head_temp;}return result_zero;}}
- 递归反转——时间复杂度—— O ( n ) O(n) O(n),空间复杂度—— O ( n ) O(n) O(n)
class Solution {public ListNode reverseList(ListNode head) {// head == null 防止参数Head本身就为null// haed.next == null,用来让递归停止到尾结点,就开始返回;if (head == null || head.next == null) return head;ListNode node = reverseList(head.next); // 保存尾结点;head.next.next = head; // 翻转指针;head.next = null; // 置空,递归已保存上一个结点,置空不影响连接return node; // 返回尾结点}
}
- 原地反转——时间复杂度—— O ( n ) O(n) O(n),空间复杂度—— O ( 1 ) O(1) O(1)
// 双指针
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;ListNode temp = null;while (cur != null) {temp = cur.next;// 保存下一个节点cur.next = prev;prev = cur;cur = temp;}return prev;}
}
// 递归
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}
// 从后向前递归
class Solution {ListNode reverseList(ListNode head) {// 边缘条件判断if(head == null) return null;if (head.next == null) return head;// 递归调用,翻转第二个节点开始往后的链表ListNode last = reverseList(head.next);// 翻转头节点与第二个节点的指向head.next.next = head;// 此时的 head 节点为尾节点,next 需要指向 NULLhead.next = null;return last;}
}
倒推数组,反向填充——时间复杂度—— O ( n ) O(n) O(n),空间复杂度—— O ( 1 ) O(1) O(1)
class Solution {public int[] reverseBookList(ListNode head) {if(head==null) return new int[0];ListNode temp = head;int count = 0;while(temp!=null){count++;temp = temp.next;}int [] result = new int[count];for(int i = result.length-1;i>=0;i--){result[i]=head.val;head= head.next;}return result;}
}
5. LCR 124. 推理二叉树——重建二叉树
题目跳转:https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/description/
知识点:
- 前序遍历列表:第一个元素永远是
根节点 (root)
- 中序遍历列表:根节点 (root)
左边
的所有元素都在根节点的左分支
,右边
的所有元素都在根节点的右分支
算法思路:
- 通过【前序遍历列表】确定【根节点 (root)】
- 将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
- 递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {//重建一开始是真的有点绕啊,但是其实理清了也还好,无非就是通过每次传进去的两个数组来构建新的二叉树//三部曲试一下吧//首先是啥时候结束//当传入的数组长度为0的时候就该结束了int length = preorder.length;if(length == 0 ) return null;//接下来是我们应该返回什么,那当然就是返回重建子树的根节点咯//每一层应该做些什么呢?//应该通过传进来的两个数组,根据他们之间的关系,来构建子树,并把新的参数传递下去//那么现在传进来了两个数组,一个是前序遍历的数组,那么首位必定是根节点,先拿下int rootValue = preorder[0];//有了数组的根节点以后我们自然需要的是左右子树,根据中序遍历的特点,只要找到了根节点,那么他两边自然//就是他的左右子树了//那么先在中序遍历的数组中找到根节点,并把它的坐标保存起来int rootIndex = 0; for(int i = 0; i < length; i++){if(inorder[i] == rootValue){rootIndex = i;break;}}//至此我们已经找到了根和左右子树,那么设置一下根节点的左右节点,自然就是递归后返回的左右子树的根节点//先把我们的根节点创建出来TreeNode root = new TreeNode(rootValue);root.left = buildTree(Arrays.copyOfRange(preorder,1,rootIndex + 1),Arrays.copyOfRange(inorder,0,rootIndex));root.right = buildTree(Arrays.copyOfRange(preorder,1+rootIndex,length),Arrays.copyOfRange(inorder,rootIndex+1,length));//至于传入的数组如何分割可以自己通过测试用例来分析,这里不赘述了//至此节点创建,左右节点的设置均已完成,返回rootreturn root;}}
学会这个函数嗷!以后不能忘啦Arrays.copyOfRange(arr,0,k)
截取arr
下标0
到k-1
6. LCR 125. 图书整理 II——用两个栈实现队列
题目跳转:https://blog.csdn.net/weixin_46225503/article/details/135412406
学会用栈!
class CQueue {Stack<Integer> stack_one;Stack<Integer> stack_two;public CQueue() {stack_one = new Stack<>();stack_two = new Stack<>();}public void appendTail(int value) {stack_one.push(value);}public int deleteHead() {if(stack_one.isEmpty())return -1;while(!stack_one.isEmpty()){stack_two.push(stack_one.peek());stack_one.pop();}int value = stack_two.peek();stack_two.pop();while(!stack_two.isEmpty()){stack_one.push(stack_two.peek());stack_two.pop();}return value;}
}
学会用LinkedList!
class CQueue {LinkedList<Integer> stack1;LinkedList<Integer> stack2;public CQueue() {stack1 = new LinkedList<>();stack2 = new LinkedList<>();}public void appendTail(int value) {stack1.push(value);}public int deleteHead() {if (stack2.isEmpty()) {if (stack1.isEmpty()) return -1;while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.pop();} else return stack2.pop();}
}
class CQueue {LinkedList<Integer> linkedList;public CQueue() {linkedList = new LinkedList<>();}public void appendTail(int value) {linkedList.addLast(value);}public int deleteHead() {if(linkedList.isEmpty())return -1;return linkedList.removeFirst();}
}
学会队列!https://blog.csdn.net/weixin_46225503/article/details/135412739
class CQueue {Queue<Integer> queue;public CQueue() {queue = new LinkedList<>();} public void appendTail(int value) {queue.add(value);}public int deleteHead() {if(queue.isEmpty())return -1;return queue.poll(); }
}
7. LCR 126. 斐波那契数——斐波那契数列
题目跳转:https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
哈希表!
class Solution {private Map<Integer,Integer> hashMap = new HashMap();private final int mod = 1000000007;public int fib(int n) {hashMap.put(0,0);hashMap.put(1,1);if(hashMap.containsKey(n))return hashMap.get(n);else{int result = 0;result = (fib(n-1) + fib(n-2))%mod;hashMap.put(n,result);return result;}}
}
数组!
class Solution {public int fib(int n) {if (n == 0 || n == 1)return n;int[] ans = new int[n+1];ans[0] = 0;ans[1] = 1;for(int i =2;i<=n;i++){ans[i] = (ans[i-1]+ans[i-2])%1000000007;}return ans[n];}
}
那为什么不递归呢?Good Question!
8. LCR 127. 跳跃训练——青蛙跳台阶问题
题目跳转:https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/
与上一题相似
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)
f ( 0 ) = 1 , f ( 1 ) = 1 , f ( 2 ) = 2 f(0)=1, f(1)=1, f(2)=2 f(0)=1,f(1)=1,f(2)=2
class Solution {public int trainWays(int num) {if(num==0)return 1;if(num==1) return 1;if(num==2) return 2;int[] arr = new int[num+1];arr[0] = 0;arr[1] = 1;arr[2] = 2;for(int i = 3;i <= num;i++){arr[i] = (arr[i-1]+arr[i-2])%1000000007;}return arr[num];}
}
9. LCR 128. 库存管理 I——旋转数组的最小值
题目跳转:https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
排序
class Solution {public int stockManagement(int[] stock) {Arrays.sort(stock);return stock[0];}
}
如果你想到这个!你别逼我扇你!调用API 虽然顾得,但是还是要写点有实力的东西!
那好吧~ 换一个!
遍历
class Solution {public int stockManagement(int[] stock) {if(stock.length==1) return stock[0];if(stock.length==2) return Math.min(stock[0],stock[1]);int result = stock[0];for(int i = 1;i<stock.length;i++){if(result>stock[i])result = stock[i];}return result;}
}
没啥营养!
再换!
class Solution {public int stockManagement(int[] numbers) {int left = 0;int right = numbers.length - 1;if (numbers[left] < numbers[right]) {return numbers[left];}while (left < right) {int mid = (left + right) / 2;// 如果右边的比中间的大,那么说明右边的部分一定是有序的。if (numbers[right] > numbers[mid]) {right = mid;// 右边的小于中间的,说明左边的一定是有序的。} else if (numbers[right] < numbers[mid]) {left = mid + 1;// 如果相等,想要判断哪一边是有序的比较难,需要考虑很多临界条件。// 上次理解的难点正在这里,这次也在这里卡了思路。// 但换个思路就很好解决了。// 即:我不需要确认当前的状态,我只需要保证答案在我的区间内,并且逐渐压缩区间,直到出现变动即可。// 由于此时numbers[right] == numbers[mid],所以right --并不会影响答案依旧在left和right的区间内。} else {right --;}}return numbers[left];}
}
要学会二分法!!!!
简单来个测试 去写一个二分!
class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length-1;int mid = 0; if(nums[left]>=target) return 0;if(nums[right]==target)return right;if(nums[right]<target) return right+1;while(left<right){mid = (right-left)/2+left;if(nums[mid]==target)return mid;else if(nums[mid]>target){right = mid;}else{left = mid+1;}}return left;}
}