欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer三天挑战赛32~45

程序员文章站 2022-07-03 19:24:52
文章目录剑指 Offer 22. 链表中倒数第k个节点解剑指 Offer 24. 反转链表解剑指 Offer 25. 合并两个排序的链表解剑指 Offer 32 - III. 从上到下打印二叉树 III解==剑指 Offer 33. 二叉搜索树的后序遍历序列==解剑指 Offer 34. 二叉树中和为某一值的路径解==剑指 Offer 35. 复杂链表的复制==解剑指 Offer 22. 链表中倒数第k个节点输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节...

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其层次遍历结果:

[
[3],
[20,9],
[15,7]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 这道题硬写也能写出来, 但是使用技巧性就很方便, 比如对返回值ans判断是不是偶数, 如果是偶数,那么就不需要反转链表数据, 如果是奇数就需要使用Collections.reverse来反转链表中的数据,其他操作和层序遍历一样
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            if (ans.size() % 2 != 0) {
                Collections.reverse(temp);
            }
            ans.add(temp);
        }
        return ans;
    }
}

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

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

参考以下这颗二叉搜索树:

 5
/ \

2 6
/
1 3
示例 1:

输入: [1,6,3,2,5]
输出: false

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 这道题很有意思, 要清楚后序遍历结果的最后一个元素肯定是每一颗子树的根节点,它前面的数据最前边是左子树数据, 中间部分的数据是右子树数据
  • 那么我倒叙遍历数组中的数据, 并附加一个栈配合,如果此时数组下标数据大于根节点数据root说明有错误, 然后如果此时栈不为空,并且此时栈底数据大于数据下标数据,说明此时栈底数据是数组坐标的父节点,但是要找到最亲父节点所以要使用while循环,最后所有的数据都要入栈
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--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!stack.isEmpty() && (stack.peek() > postorder[i])) {
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}

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

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 很机智的一道题, 采用先序遍历的思路, 每次只要节点不为空就加入到linkedList中, 只要此时sum为0并且此时这个节点是叶子节点, 那么说明这是一个结果,保存他, 否则先用先序遍历访问其左子树和右子树, 最后不要忘了删除一开始加进去的这个数据,
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<List<Integer>> ans;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        ans = new ArrayList<>();
        fun(new LinkedList<>(), sum, root);
        return ans;
    }

    private void fun(LinkedList<Integer> list, int sum, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            ans.add(new ArrayList<>(list));
        }
        fun(list, sum, root.left);
        fun(list, sum, root.right);
        list.removeLast();
    }
}

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

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 使用一个map用于建立原先链表节点和新建链表节点的映射关系, 然后用原先链表节点通过map的get操作来设置新建链表节点的复杂联系关系.
  • 注意最后返回也是map.get后新建的链表节点
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        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 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 这道题是原先将二叉搜索树改为双向链表, 那道题的话只需要使用中序遍历,然后保存head节点,处理per节点就可以
  • 这道题比上面说到的题难了一点, 就是他是双向循环式的, 你还得保存队尾节点, 而队尾节点也是就最大值的那个节点, 最后让头节点的left指向尾节点, 尾节点的rigth指向头节点即可
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {

    private Node head, per, tail;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return root;
        }
        fun(root);
        head.left = tail;
        tail.right = head;
        return head;
    }

    private void fun(Node root) {
        if (root == null) {
            return;
        }
        treeToDoublyList(root.left);
        if (head == null) {
            head = root;
        }
        if (per != null) {
            root.left = per;
            per.right = root;
        }
        per = root;
        treeToDoublyList(root.right);
        if (tail == null || tail.val < root.val) {
            tail = root;
        }
    }
}

剑指 Offer 37. 序列化与反序列化二叉树(非递归)

题目描述
请实现两个函数,分别用来序列化和反序列化二叉树

二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。

二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树
示例1
输入
复制
{8,6,10,5,7,9,11}
返回值
复制
{8,6,10,5,7,9,11}

  • 下面这是一种非递归的写法, 序列化的过程是使用一个队列,每次在队列中取一个节点, 如果不为null则拼接其val和, 并且将其左节点有右节点放入队列, 如果此时节点为null, 则拼接#和,
  • 对于反序列化,首先将字符串使用,分割, 然后初始化好节点数组用于存放节点,只要对应的parts位置不为# 就初始化该节点, 然后使用一个for循环构建二叉树,使用双下标,一个表示0开始, 一个在1开始, 1开的用于建立每个0开始下标左子树和右子树
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        if (root == null) {
            return builder.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                builder.append(cur.val);
                builder.append(',');
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                builder.append("#,");
            }
        }
        String str = builder.toString();
        return str.substring(0, str.length() - 1);
  }
    
    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
       String[] parts = str.split(",");
        return fun(parts);
    }
    
    private TreeNode fun(String[] parts) {
        TreeNode[] nodes = new TreeNode[parts.length];
        for (int i = 0; i < parts.length; i++) {
            if (!parts[i].equals("#")) {
                nodes[i] = new TreeNode(Integer.parseInt(parts[i]));
            }
        }
        for (int i = 0, j = 1; j < parts.length; i++) {
            if (nodes[i] != null) {
                nodes[i].left = nodes[j++];
                nodes[i].right = nodes[j++];
            }
        }
        return nodes[0];
    }
}

剑指 Offer 37. 序列化与反序列化二叉树(递归)

  • 对于递归版本来说, 序列化的过程就是如果为null就拼接#, 如果不为null就拼接他的val, 然后在拼接他的左子树和右子树, 最后返回string
  • 对于反序列化的过程就是先将其分割,判断是否越界, 然后递归初始化节点
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        if (root == null) {
            builder.append("#,");
            return builder.toString();
        }
        builder.append(root.val).append(",");
        builder.append(Serialize(root.left));
        builder.append(Serialize(root.right));
        return builder.toString();
  }
    
    private int index = 0;
    TreeNode Deserialize(String str) {
       String[] parts = str.split(",");
        return fun(parts);
  }
    
    private TreeNode fun(String[] parts) {
        if (index >= parts.length) {
            return null;
        }
        if (parts[index].equals("#")) {
            index++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(parts[index++]));
        node.left = fun(parts);
        node.right = fun(parts);
        return node;
    }
}

剑指 Offer 38. 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。

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

示例:

输入:s = “abc”
输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 这是一道典型的全排列问题, 利用dfs思想来实现, 而且得使用HashSet保存交换过的字符,避免字符串重复
class Solution {

    public String[] permutation(String s) {
        List<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        fun(chars, 0, list);
        Collections.sort(list);
        String[] ans = new String[list.size()];
        for (int i= 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void fun(char[] chars, int index, List<String> list) {
        if (index == chars.length) {
            list.add(String.valueOf(chars));
        }

        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < chars.length; i++) {
            if (set.contains(chars[i])) continue;
            set.add(chars[i]);
            swap(chars, i, index);
            fun(chars, index + 1, list);
            swap(chars, i, index);
        }
    }

        private void swap(char[] arr, int index, int i) {
        char temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 题意只是为了寻找众数一种是使用map统计找到数量大于一般的那个数据, 再就是使用众数的定义, 众数一定是在排序好的数组的中间
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }
}

剑指 Offer 40. 最小的k个数

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 使用全排序然后获取k个数字也可以,但是效率低所以使用我在这里使用堆排序
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : arr
             ) {
            queue.offer(num);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }
        return ans;
    }
}

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1:

输入:
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 维护俩个优先级队列和一个计数器, big优先级队列是大堆, 放置较小的数据, small是小堆,放置较大的数据,这样小堆的堆顶和大堆的堆顶就是中位数, 但是还要判断数据的个数, 如果是奇数那定在大堆中, 如果是偶数那就是俩个堆顶的数据的平均值
class MedianFinder {

    /** initialize your data structure here. */
    private PriorityQueue<Integer> big = new PriorityQueue<>((o1, o2) -> o2 - o1);
    private PriorityQueue<Integer> small = new PriorityQueue<>();
    private int size = 0;
    public MedianFinder() {

    }
    
    public void addNum(int num) {
        if (size % 2 == 0) {
            small.offer(num);
            big.offer(small.poll());
        } else {
            big.offer(num);
            small.offer(big.poll());
        }
        size++;
    }
    
    public double findMedian() {
        if (size % 2 == 0) {
            return (small.peek() + big.peek()) * 1.0 / 2;
        } else {
            return big.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

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

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

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

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 最经典的一道动态规划,ret初始化为数组下标0的数据,从数组1开始遍历数据, 如果前一个下标数据小于0那么加起来肯定是让和变小了,那么就加0即可, 最后使用ret保存最大累加和
//时间和空间复杂度全为O(N)
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ret = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}

//优化空间复杂度为O(1)
class Solution {
    public int maxSubArray(int[] nums) {
        int ret = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            ret = Math.max(ret, nums[i]);
        }
        return ret;
    }
}

剑指 Offer 43. 1~n 整数中 1 出现的次数

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

示例 1:

输入:n = 12
输出:5
示例 2:

输入:n = 13
输出:6

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”
示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 这个采用分治的思想, 每次对比俩个数据的正反拼接的大小, 使用compareTo判断是否需要互换位置, 我使用的是冒泡排序的思想,也就是最开始放的肯定是最小的数据
class Solution {
    public String minNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                String num1 = "" + nums[i] + nums[j];
                String num2 = "" + nums[j] + nums[i];
                if (num1.compareTo(num2) > 0) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int num: nums) {
            ans.append(num);
        }
        return ans.toString();
    }
}

本文地址:https://blog.csdn.net/Shangxingya/article/details/112779043