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

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

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

解题思路:

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

代码实现:

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

第二题: 剑指 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;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return res;
    }
    public void dfs(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(new ArrayList<>(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. 返回哈希表中存储的头节点

代码实现:

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node,Node> map = new HashMap<>();
        while(cur != null) {
            map.put(cur,new Node(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: 不能重复使用同一个元素. (这里对使用过的进行标记, 如果使用了, 就直接跳过)

代码实现:

class Solution {
    List<String> list = new ArrayList<>();
    public String[] permutation(String s) {
        boolean[] tmp = new boolean[s.length()];
        char[] ch = s.toCharArray();
        // 注意题目中没有说s是不重复的,所以需要排序
        Arrays.sort(ch);
        bfs(ch,tmp,new StringBuilder());
        String[] ans = new String[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    public void bfs(char[] ch, boolean[] tmp,StringBuilder sb){
        if (sb.length() == ch.length) {
            list.add(sb.toString());
            return;
        }
        for(int i = 0; i < ch.length; i++) {
        	// 剪枝1
            if(i > 0 && ch[i] == ch[i-1] && tmp[i-1]){
                continue;
            }
            // 剪枝2
            if(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))

代码实现:

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[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 ~ 9	1	9	9
10 ~ 99	2	90	180
100 ~ 999	3	900	2700
…	…	…	…
start ~ start*10-1	digit	9 * start	9 * digit * start

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

代码实现:

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        // 因为范围过大, 还涉及到乘法, 要考虑溢出使用long
        long 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';
    }
}