获取当前薪水第二多的员工的信息

题目描述

有一个员工表employees简况如下:

img

有一个薪水表salaries简况如下:

img

请你查找薪水排名第二多的员工编号emp_no、薪水salary、last_name以及first_name，不能使用order by完成，以上例子输出为:

img

比较自连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
select
e.emp_no,s.salary,e.last_name,e.first_name
from 
salaries s join employees e 
on s.emp_no = e.emp_no
where e.emp_no = 
(
    select 
    s1.emp_no
    from
    salaries s1 join salaries s2 
    on s1.salary < s2.salary
    group by s1.salary
    having count(distinct s2.salary)=1
)

展开全文 >>

加起来和为目标值的组合

题目描述

给出一组候选数\ C C 和一个目标数\ T T，找出候选数中起来和等于\ T T 的所有组合。
\ C C 中的每个数字在一个组合中只能使用一次。

注意：

  • 题目中所有的数字（包括目标数\ T T ）都是正整数
  • 组合中的数字 (a_1, a_2, … , a_ka1,a2,…,a**k) 要按非递增排序 (a_1 \leq a_2 \leq … \leq a_ka1≤a2≤…≤a**k).
  • 结果中不能包含重复的组合
  • 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例1

输入

复制

1
[100,10,20,70,60,10,50],80

返回值

复制

1
[[10,10,60],[10,20,50],[10,70],[20,60]]

说明

1
给定的候选数集是[100,10,20,70,60,10,50]，目标数是80

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] nums, int target) {
        this.target = target;
        ArrayList<Integer> list = new ArrayList<>();
        // 这里排序很重要
        Arrays.sort(nums);
        dfs(nums,0,0,list);
        return res;
    }
    int target = 0;
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public void dfs(int []nums,int index,int sum,ArrayList<Integer> list){
        if(index > nums.length||sum>target)return;
        if(sum == target){
            if(!res.contains(list)){
                res.add(new ArrayList(list));
            }
            return;
        }
        // 回溯
        for(int i=index;i<nums.length;i++){
            list.add(nums[i]);
            dfs(nums,i+1,sum+nums[i],list);
            list.remove(list.size()-1);
        }
    }
}

展开全文 >>

复原IP地址

93. 复原 IP 地址

难度中等569

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是 无效 IP 地址。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

1
2
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

回溯

关键点：

  • 注意不能含有前导0
  • 每一个域的值不能大于255
  • 中间点的数量应该是三
  • StringBuilder到最后赋值的时候不能删除字符，否则返回上一层回溯的过程就不正确了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<String> restoreIpAddresses(String s) {
        if(s.length()>12)return list;
        dfs(s,0,0);
        return list;
    }

    List<String> list = new ArrayList<>();
    StringBuilder bd = new StringBuilder();
    // count用来计数点的数量,最终点的数量应该是3
    public void dfs(String s,int index,int count){
        // 因为是下一次循环,这里应该写成4
        if(index==s.length()&&count==4){
            String temp = bd.toString();
            temp = temp.substring(0,temp.length()-1);
            list.add(temp);
            return;
        }
        
        for(int i=index+1;i<=index+3&&i<=s.length();i++){
            String temp = s.substring(index,i);
            // 判断是否大于255
            if(Integer.parseInt(temp)>255)continue;
            // 不能以0开头并且当前的字符不是0
            if(temp.startsWith("0")&&temp.length()>1)continue;
            count++;
            bd.append(temp);
            bd.append(".");
            dfs(s,i,count);
            count--;
            bd.deleteCharAt(bd.length()-1);
            bd.delete(bd.length()-temp.length(),bd.length());
        }
    }
}

展开全文 >>

粉刷房子3

1473. 粉刷房子 III

难度困难63

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

  • houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
  • cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

示例 1：

1
2
3
4
5
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

1
2
3
4
5
输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

1
2
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

示例 4：

1
2
3
输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    // 极大值
    // 选择 Integer.MAX_VALUE / 2 的原因是防止整数相加溢出
    static final int INFTY = Integer.MAX_VALUE / 2;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
        for (int i = 0; i < m; ++i) {
            --houses[i];
        }

        // dp 所有元素初始化为极大值
        int[][][] dp = new int[m][n][target];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dp[i][j], INFTY);
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (houses[i] != -1 && houses[i] != j) {
                    continue;
                }
                
                for (int k = 0; k < target; ++k) {
                    for (int j0 = 0; j0 < n; ++j0) {
                        if (j == j0) {
                            if (i == 0) {
                                if (k == 0) {
                                    dp[i][j][k] = 0;
                                }
                            } else {
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k]);
                            }
                        } else if (i > 0 && k > 0) {
                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j0][k - 1]);
                        }
                    }

                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
                        dp[i][j][k] += cost[i][j];
                    }
                }
            }
        }

        int ans = INFTY;
        for (int j = 0; j < n; ++j) {
            ans = Math.min(ans, dp[m - 1][j][target - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/paint-house-iii/solution/fen-shua-fang-zi-iii-by-leetcode-solutio-powb/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

不相邻最大子序列和

题目描述

给你一个n（$1\leq n\leq10^5$），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。

示例1

输入

复制

1
3,[1,2,3]

返回值

复制

1
4

说明

1
有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4

示例2

输入

复制

1
4,[4,2,3,5]

返回值

复制

1
9

说明

1
其中[4,5]的选取方案是在满足不同时选取相邻位置的数的情况下是最优的答案

备注:

1
输入的值在int范围内

题目意思

类似于小偷问题，不能偷相邻位置的元素

一维动态规划

学习类似于数学归纳法的思想考虑初始条件：

  • 当数组中只有一个元素时，最大收益是偷这一个

  • 当数组中有两个元素时，最大收益是偷两个中的最大值

  • 当数组中有大于两个元素时，最大收益是dp[i] = Math.max(dp[i-1],dp[i-2]+array[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
        long []dp = new long[n];
        if(n==0)return 0;
        if(n==1)return array[0];
        dp[0] = array[0];
        dp[1] = Math.max(array[0],array[1]);
        for(int i=2;i<n;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+array[i]);
        }
        return dp[n-1];
    }

二维动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
        long [][]dp = new long[n][2];
        if(n==1){
            return array[0];
        }else if(n==2){
            return Math.max(array[0],array[1]);
        }
        dp[0][0] = 0;
        dp[0][1] = array[0];
        
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+array[i]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}

展开全文 >>

二叉树根到叶子节点的所有路径的和

题目描述

给定一个仅包含数字\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1\to 2\to 31→2→3,那么这条路径就用\ 123 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：

img

这颗二叉树一共有两条路径，
根节点到叶子节点的路径 1\to 21→2 用数字\ 12 12 代替
根节点到叶子节点的路径 1\to 31→3 用数字\ 13 13 代替
所以答案为\ 12+13=25 12+13=25

示例1

输入

复制

1
{1,0}

返回值

复制

1
10

示例2

输入

复制

1
{1,#,9}

返回值

复制

1
19

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public int sumNumbers (TreeNode root) {
        dfs(root,0);
        return res;
    }
    
    int res = 0;
    public void dfs(TreeNode root,int val){
        if(root==null) return;
        int sum = val*10+root.val;
        if(root.left!=null)dfs(root.left,sum);
        if(root.right!=null)dfs(root.right,sum);
        // 当左右子树都为空的时候再去计算和，否则会重复计算和
        if(root.left==null&&root.right==null){
            res += sum;
            return;
        }
    }
}

展开全文 >>

二叉树的最大路径和

题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
img
返回的结果为6

示例1

输入

复制

1
{-2,1}

返回值

复制

1
1

示例2

输入

复制

1
{-2,#,-3}

返回值

复制

1
-2

深度优先搜索

这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。在这里树没有被看成有向图，而是被当成无向图来寻找路径。因为这个路径的灵活性，我们需要对递归返回值进行一些调整，而不是通常的返回要求的结果。在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，必须往单方向走）。这个返回值是为了提供给它的父结点计算自身的最长路径用，而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。而返回值则是自己的值加上左子树返回值，右子树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。算法的本质还是一次树的遍历，所以复杂度是$O(n)$。而空间上仍然是栈大小$O(logn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Solution {
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return max;
    }    
    int max = Integer.MIN_VALUE;
    public int dfs(TreeNode root){
        if(root==null)return 0;
        int l = Math.max(dfs(root.left),0);
        int r = Math.max(dfs(root.right),0);
        max = Math.max(max,root.val+l+r);
        return root.val+Math.max(l,r);
    }
}

展开全文 >>

字符串出现次数的TopK

题目描述

给定一个字符串数组，再给定整数k，请返回出现次数前k名的字符串和对应的次数。

返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。

对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。

比如”ah1x”小于”ahb”，”231”<”32“

字符仅包含数字和字母

[要求]

如果字符串数组长度为N，时间复杂度请达到O(N \log K)O(NlogK)

示例1

输入

复制

1
["a","b","c","b"],2

返回值

复制

1
[["b","2"],["a","1"]]

说明

1
2
"b"出现了2次，记["b","2"]，"a"与"c"各出现1次，但是a字典序在c前面，记["a","1"]，最后返回[["b","2"],["a","1"]]

示例2

输入

复制

1
["123","123","231","32"],2

返回值

复制

1
[["123","2"],["231","1"]]

说明

1
"123"出现了2次，记["123","2"]，"231"与"32"各出现1次，但是"231"字典序在"32"前面，记["231","1"]，最后返回[["123","2"],["231","1"]]

示例3

输入

复制

1
["abcd","abcd","abcd","pwb2","abcd","pwb2","p12"],3

返回值

复制

1
[["abcd","4"],["pwb2","2"],["p12","1"]]

备注:

$1 \leq N \leq 10^5$

堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;
public class Solution {
    public String[][] topKstrings (String[] strings, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String s:strings){
            map.put(s,map.getOrDefault(s,0)+1);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            Node node = new Node(entry.getKey(),entry.getValue());   
            if(pq.size()<k){
                pq.offer(node);
            }else{
                Node top = pq.peek();
                // 注意这里一定要用compareTo,否则需要比较两个,不然就是错误的
                if(top.compareTo(node)<0){
                    pq.poll();
                    pq.offer(node);
                }
            }
        }
        
        String [][] res = new String[k][2];
        int index = k-1;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            res[index][0] = node.val;
            res[index][1] = String.valueOf(node.cnt);
            index--;
        }
        return res;
    }
    
    private class Node implements Comparable<Node>{
        String val;
        int cnt;
        public Node(String val,int cnt){
            this.val = val;
            this.cnt = cnt;
        }
        
        @Override
        public int compareTo(Node node){
            return this.cnt != node.cnt ? this.cnt-node.cnt : node.val.compareTo(this.val);
        }
    }
}

展开全文 >>

树的直径

题目描述

给定一棵树，求出这棵树的直径，即树上最远两点的距离。

包含n个结点，n-1条边的连通图称为树。

示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11

img

示例1

输入

复制

1
6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]

返回值

复制

1
11

通用解法

对于此类问题，我们需要构建图来做深度优先搜索。

  • 首先，根据父子关系及边权重构建无向图；

  • 然后，随机找一顶点，利用深度优先搜索找到距离该点最远的顶点remote。

  • 最后，从remote顶点开始深度优先搜索找到最长路径，该路径即为直径。

巧妙解法

我们记录每个节点向下，所能延伸的最远距离 $d_1$，和次远距离$d_2$ ，那么直径就是所有$d_1+d_2$ 的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.*;
public class Solution {
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        List<Node> [] edges = new List[n];
        for(int i=0;i<n;i++){
            edges[i] = new ArrayList<>();
        }
        // 建立邻接表无向图
        for(int i=0;i<Tree_edge.length;i++){
            edges[Tree_edge[i].start].add(new Node(Tree_edge[i].end,Edge_value[i]));
            edges[Tree_edge[i].end].add(new Node(Tree_edge[i].start,Edge_value[i]));
        }
        dfs(edges,Tree_edge[0].start,-1);
        return max;
    }
    
    int max = 0;
    
    public int dfs(List<Node> []edges,int curr,int parent){
        int maxDepth = 0;
        int secondDepth = 0;
        for(Node node:edges[curr]){
            if(node.id == parent)continue;
            int depth = node.weight + dfs(edges,node.id,curr);
            if (depth > maxDepth) {
                secondDepth = maxDepth;
                maxDepth = depth;
            }else if (depth > secondDepth) {
                secondDepth = depth;
            }
            maxDepth = Math.max(maxDepth,depth);
        }
        max = Math.max(max,maxDepth+secondDepth);
        return maxDepth;
    }
    
    private class Node {
        int id;
        int weight;
        public Node(int id,int weight){
            this.id = id;
            this.weight = weight;
        }
    }
}

参考文献

树的直径 - OI Wiki (oi-wiki.org)

展开全文 >>

到目标元素的最小距离

5746. 到目标元素的最小距离

难度简单0

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化 。注意：abs(x) 表示 x 的绝对值。

返回 abs(i - start) 。

题目数据保证 target 存在于 nums 中。

示例 1：

1
2
3
输入：nums = [1,2,3,4,5], target = 5, start = 3
输出：1
解释：nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。

示例 2：

1
2
3
输入：nums = [1], target = 1, start = 0
输出：0
解释：nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 1 。

示例 3：

1
2
3
输入：nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
输出：0
解释：nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • 0 <= start < nums.length
  • target 存在于 nums 中

暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                min = Math.min(Math.abs(i - start), min);
            }
        }
        return min;
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走