头像

小呆呆

九歌粉丝团




离线:6小时前



题目描述

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^282^28 - 1 之间,最终结果不会超过 2^31 - 1

样例

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出:
2

解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

算法分析

  • 1、记录C[]D[]中每对元素的和sum = C[i] + D[j],用哈希表记录 该总和sum 和 出现的次数
  • 2、由于A[i] + B[j] + C[k] + D[l] = 0,即等价与 C[k] + D[l] = - (A[i] + B[j]),枚举A[]数组和B[]数组所有元素,计算val = - (A[i] + B[j]),若哈希表存在val,表示存在组合满足题意,把val对应的次数加入到总个数res

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < C.length;i ++)
            for(int j = 0;j < D.length;j ++)
            {
                int sum = C[i] + D[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }

        int res = 0;
        for(int i = 0;i < A.length;i ++)
            for(int j = 0;j < B.length;j ++)
            {
                int sum = A[i] + B[j];
                int val = sum * (-1);
                if(map.containsKey(val))
                    res += map.get(val);
            }

        return res;
    }
}



题目描述

给定一个长度为 n非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1

样例

输入:
[1,2,3]

输出:
3

解释:
只需要3次移动(注意每次移动会增加两个元素的值):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

算法分析

最小移动次数使数组元素相等,只关心让元素是一致即可

从相对方向来看:将除了一个元素之外的全部元素+1,等价于将该元素-1,找到最小值minv,枚举整个数组,累计nums[i] - minv差值的总和

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int minMoves(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        int minv = 0x3f3f3f3f;
        for(int i = 0;i < n;i ++)
        {
            minv = Math.min(minv, nums[i]);
        }

        int res = 0;
        for(int i = 0;i < n;i ++)
            res += nums[i] - minv;

        return res;
    }
}



题目描述

在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以纵坐标并不重要,因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 x_startx_end, 且满足  x_start ≤ x ≤ x_end,则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后,可以无限地前进。我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。

给你一个数组 points ,其中 points [i] = [x_start,x_end] ,返回引爆所有气球所必须射出的最小弓箭数。

样例

输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:对于该样例,x = 6 可以射爆 [2,8],[1,6] 两个气球,以及 x = 11 射爆另外两个气球
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
输入:points = [[1,2]]
输出:1
输入:points = [[2,3],[2,3]]
输出:1

提示:

  • 0 <= points.length <= 10^4
  • points[i].length == 2
  • -2^31 <= x_start < x_end <= 2^31 - 1

算法分析

  • 1、将每个区间按右端点从小到大进行排序

  • 2、从前往后枚举每个区间,初始选定end值为无穷小

    • 若当前区间中包含该点end,则直接跳过
    • 否则,选择当前区间的右端点

证明:

  • (1)找到cnt个点,满足题意情况,则最优解Ans <= cnt
  • (2)找到cnt个点,即找到cnt个区间,且区间从左到右依次排好,且没有相同的交集,则说明可能有区间没有被这cnt个点覆盖过,所以最优解Ans >= cnt
    • Ans == cnt,证毕

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    static int N = 10000 + 10;
    static Pair[] pair = new Pair[N];
    public int findMinArrowShots(int[][] points) {
        //区间选点问题
        int n = points.length;
        if(n == 0) return 0;
        for(int i = 0;i < n;i ++)
        {
            int l = points[i][0], r = points[i][1];
            pair[i] = new Pair(l, r);
        }
        //按右端点排序
        Arrays.sort(pair, 0, n, (x, y) -> {
            if(x.r <= y.r)//注意:这里不能写成return x.r - y.r,会爆掉
                return -1;
            return 1;
        });

        int cnt = 1;
        //(也可以赋值成无穷小,cnt从0开始,不过这里数据范围比较紧,先赋值成第一个区间的右端点比较好)
        int end = pair[0].r;
        for(int i = 1;i < n;i ++)
        {
            int l = pair[i].l, r = pair[i].r;
            if(l > end)
            {
                cnt ++;
                end = r;
            }
        }
        return cnt;
    }
}
class Pair
{
    int l, r;
    Pair(int l, int r)
    {
        this.l = l;
        this.r = r;
    }
}



题目描述

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  • 1、首先找到需要删除的节点;
  • 2、如果找到了,删除它。

说明: 要求算法时间复杂度为 O(h),h 为树的高度。

样例

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

算法分析

函数是deleteNode(TreeNode root, int key),根据二叉搜索树的性质,我们可以进行以下三步:

  • 1、当前节点值比key小,则需要递归到删除当前节点的左子树中key对应的值,返回deleteNode(root.left,key)
  • 2、当前节点值比key大,则需要递归到删除当前节点的右子树中key对应的值,返回deleteNode(root.right,key)
  • 3、当前节点等于key,则需要删除当前节点,并保证二叉搜索树的性质不变

对于一棵二叉搜索树要删除当前节点(第3步),我们一般会面临如下情况:

  • (1):当前节点没有左子树
  • (2):当前节点没有右子树
  • (3):当前节点既有左子树又有右子树

48c5fb57b64ddff5edfca2c3af57fad4493d255c37f35d6bc77651048cdcb294-排列方案.png

对于第一种情况来说:我们要删除节点5(root),直接 return root.right 即可。

对于第二种情况来说:我们要删除节点5(root),直接 return root.left 即可。

对于第三种情况来说:我们要删除节点5(root),只需将root的左子树放到root的右子树的最下面的左叶子节点的左子树上即可。如图所示:

ce9864e7052d98fbe006fbd350ceaf691fee1ed85a6ad9cc9f21e1e5295b0f0d-调整图.png

时间复杂度 $O(h)$

参考文献

源于LeetCode 这篇题解

Java 代码

/**
 * 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 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;

        if(key < root.val) root.left = deleteNode(root.left, key);
        else if(key > root.val) root.right = deleteNode(root.right, key);
        else
        {
            if(root.left == null) return root.right;
            if(root.right == null) return root.left;

            //找到右子树的左下角
            TreeNode r = root.right;
            while(r.left != null) r = r.left;

            r.left = root.left;

            return root.right;
        } 

        return root;
    }
}



题目描述

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

样例

输入:root = [2,1,3]
输出:[2,1,3]
输入:root = []
输出:[]

提示:

  • 树中节点数范围是 [0, 10^4]
  • 0 <= Node.val <= 10^4
  • 题目数据 保证 输入的树是一棵二叉搜索树。

算法分析

该题也可以用 LeetCode 297.二叉树的序列化与反序列化的解法

下面题解是使用了二叉搜索树的特性(中序遍历是有序的)解决

93f8e1837720be5fe7c235b37122452.png

  • 序列化:对整个二叉树进行先序遍历的序列存起来,同时需要把每个结点的空节点使用"#"进行标记,例如图中的顺序是
    2,1,#,#,4,3,#,#,5,#,#

  • 反序列化:先把字符串中对应的所有数字都扣到一个链表中,即将样例扣成2 1 4 3 5,存到链表中,dfs(List<Integer> s, int l, int r)的作用是在链表中[l, r]的区间形成一棵树后并返回根节点,根据先序遍历和中序遍历构造出一棵唯一的树的原理

    • 1、将[l, r]区间中第一个元素s[l]作为根结点,该值是p
    • 2、在[l, r]区间中找到小于p的区间,递归构造出左子树
    • 3、在[l, r]区间中找到大于p的区间,递归构造出右子树

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    static TreeNode dfs(List<Integer> s, int l, int r)
    {
        if(l > r) return null;
        //选取第一个为根结点
        TreeNode root = new TreeNode(s.get(l));
        //找到第一个比root.val大的元素的位置
        int idx = l + 1, p = s.get(l);
        while(idx <= r && s.get(idx) < p) idx ++;
        root.left = dfs(s, l + 1, idx - 1);
        root.right = dfs(s, idx, r);
        return root;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //把data的所有数字筛出来存到s链表中
        String[] s1 = data.split(",");
        List<Integer> s = new ArrayList<Integer>();
        for(int i = 0;i < s1.length;i ++)
        {
            if(s1[i].equals("#")) continue;
            s.add(Integer.parseInt(s1[i]));
        }
        return dfs(s, 0, s.size() - 1);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    //根据先序遍历的顺序,每次只拿第一元素作为根
    static TreeNode dfs(List<String> list)
    {
        if(list.get(0).equals("#"))
        {
            list.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left = dfs(list);
        root.right = dfs(list);
        return root;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "#";

        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        List<String> list = new ArrayList<String>(Arrays.asList(s));
        return dfs(list);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));



题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

样例

你可以将以下二叉树:

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态,你的序列化和反序列化算法应该是无状态的。


算法分析

  • 序列化:对整个二叉树进行先序遍历的序列存起来,同时需要把每个结点的空节点使用"#"进行标记,例如样例的顺序是1,2,#,#,3,4,#,#,5,#,#

  • 反序列化:对整个字符串按照","进行分割,把所有的元素按序存到链表中(链表元素的顺序是先序序列),按先序遍历的方式拿链表的元素,每次拿第一个元素作为根结点,并删除链表中的第一个元素,然后递归到左儿子做同样的操作,递归到右儿子做同样的操作。注意:若第一个元素是"#",表示该节点是null,直接返回null

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    //根据先序遍历的顺序,每次只拿第一元素作为根
    static TreeNode dfs(List<String> list)
    {
        if(list.get(0).equals("#"))
        {
            list.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left = dfs(list);
        root.right = dfs(list);
        return root;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "#";

        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        List<String> list = new ArrayList<String>(Arrays.asList(s));
        return dfs(list);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));



题目描述

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

样例

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
输入:
"Aabb"

输出:
"bbAa"

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

算法分析

  • pair记录每个字符出现多少次,对pair[]数组按照次数从小到大排序,枚举pair[]数组,将字符出现了多少次连续拼接到结果中。例如a字符出现2次,拼接aa

时间复杂度 $O(nlogn)$

n = 128

Java 代码

class Solution {
    public String frequencySort(String s) {
        int n = s.length();
        int[] c = new int[128];
        for(int i = 0;i < n;i ++)
        {
            c[s.charAt(i)] ++;
        }
        Pair[] pair = new Pair[128];
        for(int i = 0;i < 128;i ++)
        {
            pair[i] = new Pair(c[i], i);
        }
        Arrays.sort(pair, (x, y) -> {
            return y.cnt - x.cnt;
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < 128;i ++)
        {
            char v = (char)pair[i].val;
            while(pair[i].cnt > 0)
            {
                sb.append(v);
                pair[i].cnt --;
            }
        }

        return sb.toString();
    }
}
class Pair
{
    int cnt, val;
    Pair(int cnt, int val)
    {
        this.cnt = cnt;
        this.val = val;
    }
}



题目描述

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

样例

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

算法分析

用负号识别当前数是否用过

  • 1、遍历每个元素,对索引进行标记,将对应索引位置的值变为负数;
  • 2、遍历下索引,看看哪些索引位置上的数不是负数的,位置上不是负数的索引,对应的元素就是不存在的。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

Java 代码

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        int n = nums.length;
        for(int i = 0;i < n;i ++)
        {
            int idx = Math.abs(nums[i]) - 1;
            if(nums[idx] > 0) nums[idx] *= -1;
        }

        for(int i = 0;i < n;i ++)
        {
            if(nums[i] > 0) ans.add(i + 1);
        }
        return ans;
    }
}



题目描述

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ,其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ,且你希望去最右下角的格子 (rows-1, columns-1) (注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动,你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 

样例

ex1.png

输入:heights = [[1,2,2],[3,8,2],[5,3,5]]
输出:2
解释:路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优,因为另一条路劲差值最大值为 3 。

ex2.png

输入:heights = [[1,2,3],[3,8,4],[5,3,5]]
输出:1
解释:路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ,比路径 [1,3,5,3,5] 更优。

ex3.png

输入:heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出:0
解释:上图所示路径不需要消耗任何体力。

提示:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 10^6

算法分析

二分 + bfs

求所有路径上相邻格子之间 高度差绝对值 的 最大值 的最小值,可以往二分方面想

  • 1、通过二分取到某个特定的值x表示,在任意一条路径中,若相邻格子的高度差绝对值 小于等于 x,则表示这两个格子是连通状态
  • 2、使用st[][]数组记录某个点是否被遍历过,从(0, 0)开始进行bfs,观察能否到达(n - 1, m - 1)
  • 3、若该特定值x能从(0, 0)到达(n - 1, m - 1)则把该x值取小,否则取大

时间复杂度 $O(n^2logn)$

Java 代码

class Solution {
    static int N = 110;
    static boolean[][] st = new boolean[N][N];
    static int n, m;
    static int[] dx = new int[]{0, -1, 0, 1};
    static int[] dy = new int[]{-1, 0, 1, 0};
    static boolean check(int x, int[][] heights)
    {
        for(int i = 0;i < n;i ++) Arrays.fill(st[i], false);
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(0, 0));
        st[0][0] = true;
        while(!q.isEmpty())
        {
            Pair t = q.poll();
            for(int i = 0;i < 4;i ++)
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= m) continue;
                if(st[a][b]) continue;
                if(Math.abs(heights[a][b] - heights[t.x][t.y]) > x) continue;

                q.add(new Pair(a, b));
                st[a][b] = true;
            }
        }

        return st[n - 1][m - 1];
    }
    public int minimumEffortPath(int[][] heights) {
        n = heights.length;
        m = heights[0].length;
        int l = 0, r = 1000000;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid, heights)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}
class Pair
{
    int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}