每日刷题记录 (十七)

文章目录

第一题: 剑指 Offer 33. 二叉搜索树的后序遍历序列

LeetCode: 剑指 Offer 33. 二叉搜索树的后序遍历序列

描述:
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

解题思路:

1. 因为是后序遍历, 从后往前遍历
2. 因为最后一个肯定是根节点, 直接入栈.
3. 此时栈不为空, 比较当前遍历到的值是否大于当前栈顶元素. - 大于, 继续入栈, 只要比当前栈顶元素大, 就是右树- 小于, 就循环去出栈, 并标记当前栈顶元素.这里相当于左树
4. 如果当前进入左树, 标记了栈顶元素, 那么就仅需比较, 当前遍历的值是否大于标记的值, 如果大于, 直接返回false, 这里相当于左子树内容大于根.
5. 遍历结束, 如果都满足要求, 就返回true;

代码实现:

classSolution{publicbooleanverifyPostorder(int[] postorder){Stack<Integer> stack =newStack<>();int root =Integer.MAX_VALUE;for(int i = postorder.length -1; i >=0;i--){// 如果这里的root被标记了(进入左树), 比较是否这个值大于根据节点if(postorder[i]> root){returnfalse;}// 只要这里小于栈顶元素, 弹出栈顶元素, 相当于把右树弹出.while(!stack.isEmpty()&& postorder[i]< stack.peek()){// 标记新的根节点
                root = stack.pop();}
            stack.push(postorder[i]);}returntrue;}}

第二题: 剑指 Offer 34. 二叉树中和为某一值的路径

LeetCode: 剑指 Offer 34. 二叉树中和为某一值的路径

描述:
给你二叉树的根节点

root

和一个整数目标和

targetSum

，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

解题思路:

1. 使用回溯解题.
2. 如果 root 为空 就直接返回
3. 每次将节点加入list中. 并让 target -= root.val
4. 如果当前的 target == 0 并且左右子树都为 null, 直接添加到结果集中.
5. 否则进入左子树, 进入右子树.

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */classSolution{List<List<Integer>> res =newArrayList<>();List<Integer> list =newArrayList<>();publicList<List<Integer>>pathSum(TreeNode root,int target){dfs(root,target);return res;}publicvoiddfs(TreeNode root,int target){if(root ==null)return;
        list.add(root.val);
        target -= root.val;if(target ==0&& root.left ==null&& root.right ==null){
            res.add(newArrayList<>(list));}else{dfs(root.left,target);dfs(root.right,target);}
        list.remove(list.size()-1);}}

第三题: 剑指 Offer 35. 复杂链表的复制

LeetCode: 剑指 Offer 35. 复杂链表的复制

描述:
请实现

copyRandomList

函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个

next

指针指向下一个节点，还有一个

random

指针指向链表中的任意节点或者

null

。

解题思路:

1. 哈希表的方式, 存储节点.
2. 首先让 cur=head, 遍历链表, 将元素都添加到哈希表中,
3. 再次让 cur=head, 遍历链表, 通过当前的cur来得到哈希表中存储的节点, 然后将next和random进行链接
4. 返回哈希表中存储的头节点

代码实现:

classSolution{publicNodecopyRandomList(Node head){Node cur = head;Map<Node,Node> map =newHashMap<>();while(cur !=null){
            map.put(cur,newNode(cur.val));
            cur = cur.next;}
        cur = head;while(cur !=null){// 注意这里的链接方法.
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;}return map.get(head);}}

第四题: 剑指 Offer 38. 字符串的排列

LeetCode: 剑指 Offer 38. 字符串的排列

描述:
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

解题思路:

1. 这里使用回溯的方法
2. 使用一个 boolean 数组进行标记来剪枝
3. 该题主要注意的剪枝, - 剪枝1: 不能使用重复的元素. (所以对s要进行排序,转成char[]数组来排序, 使用boolean来判断)- 剪枝2: 不能重复使用同一个元素. (这里对使用过的进行标记, 如果使用了, 就直接跳过)

代码实现:

classSolution{List<String> list =newArrayList<>();publicString[]permutation(String s){boolean[] tmp =newboolean[s.length()];char[] ch = s.toCharArray();// 注意题目中没有说s是不重复的,所以需要排序Arrays.sort(ch);bfs(ch,tmp,newStringBuilder());String[] ans =newString[list.size()];for(int i =0; i < list.size(); i++){
            ans[i]= list.get(i);}return ans;}publicvoidbfs(char[] ch,boolean[] tmp,StringBuilder sb){if(sb.length()== ch.length){
            list.add(sb.toString());return;}for(int i =0; i < ch.length; i++){// 剪枝1if(i >0&& ch[i]== ch[i-1]&& tmp[i-1]){continue;}// 剪枝2if(tmp[i]){continue;}
            tmp[i]=true;
            sb.append(ch[i]);bfs(ch,tmp,sb);
            sb.deleteCharAt(sb.length()-1);
            tmp[i]=false;}}}

第五题: 剑指 Offer 42. 连续子数组的最大和

LeetCode: 剑指 Offer 42. 连续子数组的最大和

描述:
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

解题思路:

1. 这里使用动态规划解题
2. 状态 F(i) : 以当前i下标结尾的最大连续数组的和.
3. 状态转移方程: F(i) = Math.max( nums[i], F(i-1)+nums[i])
4. 初始状态: F(0) = nums[0]
5. 返回结果: 返回 Math.max(F(i))

代码实现:

classSolution{publicintmaxSubArray(int[] nums){int[] dp =newint[nums.length];
        dp[0]= nums[0];int max = nums[0];for(int i =1; i < nums.length; i++){
            dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
            max =Math.max(dp[i],max);}return max;}}

第六题: 剑指 Offer 44. 数字序列中某一位的数字

LeetCode: 剑指 Offer 44. 数字序列中某一位的数字

描述:
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

解题思路:

1. 这题是找规律的题

范围位数数据量所有的数位量1 ~ 919910 ~ 99290180100 ~ 99939002700…………start ~ start*10-1digit9 * start9 * digit * start

1. 按照规律, 首先可以先定位到该数在哪一个范围
2. 再根据start求出当前的值. start +( n - 1 ) / digit
3. 找到这个值, 再根据 (n-1)%digit, 得到这个值的第这个位.

代码实现:

classSolution{publicintfindNthDigit(int n){int digit =1;// 因为范围过大, 还涉及到乘法, 要考虑溢出使用longlong count =9;long start =1;while(n > count){
            n -= count;
            digit++;
            start *=10;
            count = digit * start *9;}// 得到原来的数long num = start +(n -1)/ digit;String ans = num+"";// 根据这个数转成字符串, 来得到该位下的值.return ans.charAt((n -1)% digit)-'0';}}