头像

小呆呆

九歌粉丝团




离线:50分钟前



小呆呆
5小时前

题目描述

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

样例

输入:
"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;
    }
}



小呆呆
5小时前

题目描述

给定一个范围在  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;
    }
}



题目描述

如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是 等差数列 。更正式地,数列 s 是等差数列,只需要满足:对于每个有效的 is[i+1] - s[i] == s[1] - s[0] 都成立。

例如,下面这些都是 等差数列

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的数列 不是等差数列

1, 1, 2, 5, 7

给你一个由 n 个整数组成的数组 nums,和两个由 m 个整数组成的数组 lr,后两个数组表示 m 组范围查询,其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。

返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列answer[i] 的值就是 true;否则answer[i] 的值就是 false

样例

输入:nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
输出:[true,false,true]
解释:
第 0 个查询,对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询,对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询,对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。
输入:nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
输出:[false,true,false,false,true,true]

提示:

  • n == nums.length
  • m == l.length
  • m == r.length
  • 2 <= n <= 500
  • 1 <= m <= 500
  • 0 <= l[i] < r[i] < n
  • -10^5 <= nums[i] <= 10^5

算法分析

暴力

对于每个区间[left, right],用一个辅助数组temp存其该区间的数,进行从小到大排序,判断该区间[left, right]中的每两个数的差分是否一致即可

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

Java 代码

class Solution {
    static int[] temp = new int[510];
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        int n = nums.length;
        int m = l.length;
        List<Boolean> ans = new ArrayList<Boolean>();
        for(int i = 0;i < m;i ++)
        {
            int left = l[i], right = r[i];
            for(int j = left; j <= right;j ++)
            {
                temp[j] = nums[j];
            }
            Arrays.sort(temp, left, right + 1);

            boolean flag = true;
            int d = temp[left + 1] - temp[left];
            for(int j = left + 1;j <= right;j ++)
            {
                if(temp[j] - temp[j - 1] != d)
                {
                    flag = false;
                    break;
                }
            }
            ans.add(flag);
        }

        return ans;
    }
}



题目描述

LeetCode 设计了一款新式键盘,正在测试其可用性。测试人员将会点击一系列键(总计 n 个),每次一个。

给你一个长度为 n 的字符串 keysPressed ,其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表,其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下,接下来每个键都 恰好 在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ,第 0 次按键的持续时间为 releaseTimes[0]

注意,测试期间,同一个键可以在不同时刻被多次按下,而每次的持续时间都可能不同。

请返回按键 持续时间最长 的键,如果有多个这样的键,则返回 按字母顺序排列最大 的那个键。

样例

输入:releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出:"c"
解释:按键顺序和持续时间如下:
按下 'c' ,持续时间 9(时间 0 按下,时间 9 松开)
按下 'b' ,持续时间 29 - 9 = 20(松开上一个键的时间 9 按下,时间 29 松开)
按下 'c' ,持续时间 49 - 29 = 20(松开上一个键的时间 29 按下,时间 49 松开)
按下 'd' ,持续时间 50 - 49 = 1(松开上一个键的时间 49 按下,时间 50 松开)
按键持续时间最长的键是 'b' 和 'c'(第二次按下时),持续时间都是 20
'c' 按字母顺序排列比 'b' 大,所以答案是 'c'
输入:releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出:"a"
解释:按键顺序和持续时间如下:
按下 's' ,持续时间 12
按下 'p' ,持续时间 23 - 12 = 11
按下 'u' ,持续时间 36 - 23 = 13
按下 'd' ,持续时间 46 - 36 = 10
按下 'a' ,持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ,持续时间 16

提示:

  • releaseTimes.length == n
  • keysPressed.length == n
  • 2 <= n <= 1000
  • 0 <= releaseTimes[i] <= 109
  • releaseTimes[i] < releaseTimes[i+1]
  • keysPressed 仅由小写英文字母组成

算法分析

求数组差分的最大值,假设res是当前差分的最大值,c是当前差分最大的字符,能修改值有两种情况

  • 1、后面存在差分距离d > res,更新res
  • 2、后面存在差分距离d == res 且 当前字符比记录的字符c还大,更新resc

时间复杂度 $O(n)$

Java 代码

class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int n = releaseTimes.length;
        int res = releaseTimes[0];
        char c = keysPressed.charAt(0);
        for(int i = 1;i < n;i ++)
        {
            int d = releaseTimes[i] - releaseTimes[i - 1];
            if(d > res || (d == res && c - keysPressed.charAt(i) < 0))
            {
                res = d;
                c = keysPressed.charAt(i);
            }
        }

        return c;
    }
}


活动打卡代码 LeetCode 455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        int cnt = 0;
        while(i < g.length && j < s.length)
        {
            while(j < s.length && s[j] < g[i]) j ++;

            if(j < s.length) cnt ++;
            i ++;
            j ++;        
        }
        return cnt;
    }
}


活动打卡代码 LeetCode 454. 四数相加 II

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;
    }
}



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;
    }
}



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;
        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;
    }
}



/**
 * 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;
    }
}