#yyds干货盘点# LeetCode刷题集171 - 180

2021年11月24日 阅读数:5
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集171 - 180,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释node

本系列有一些SQL查询问题算法

171. Excel表列序号

给定一个Excel表格中的列名称,返回其相应的列序号。数组

例如,markdown

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1:架构

输入: "A"
输出: 1
示例 2:app

输入: "AB"
输出: 28
示例 3:ide

输入: "ZY"
输出: 701函数

class Solution {
    public int titleToNumber(String s) {
 char[] charArray = s.toCharArray();
        int res = 0;
        for(int i = 0; i < charArray.length; i++) {
            res = res*26 + (charArray[i] - 'A' + 1);
        }

        return res;
    }
}

172. 阶乘后的零

给定一个整数 n,返回 n! 结果尾数中零的数量。布局

示例 1:ui

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

PS:
首先题目的意思是末尾有几个0
好比6! = 【1 2 3 4 5 6】
其中只有2
5末尾才有0,因此就能够抛去其余数据 专门看2 5 以及其倍数 毕竟 4 25末尾也是0
好比10! = 【2
456810】
其中 4能拆成22 10能拆成25
因此10! = 【2(22)5(23)(222)(25)】
一个2和一个5配对 就产生一个0 因此10!末尾2个0

转头一想 2确定比5多 因此只数5的个数就好了

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while(n >= 5) {
            count += n / 5;
            n /= 5;
        }
        return count;
    }
}

173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例:
在这里插入图片描述

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示:

next() 和 hasNext() 操做的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。
你能够假设 next() 调用老是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
 private TreeNode root;
    private List<Integer> inOrder;
    private Iterator<Integer> it;
    //中序遍历

    private void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            inOrder.add(root.val);
            inorder(root.right);
        }
    }

    public BSTIterator(TreeNode root) {
        this.root=root;
        this.inOrder = new ArrayList<>();
        inorder(this.root);
        it=this.inOrder.iterator();
    }

    /** @return the next smallest number */
    public int next() {
        return this.it.next();
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(this.it.hasNext())
            return true;
        return false;
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

174. 地下城游戏

一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。咱们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并经过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。若是他的健康点数在某一时刻降至 0 或如下,他会当即死亡。

有些房间由恶魔守卫,所以骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其余房间要么是空的(房间里的值为 0),要么包含增长骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增长健康点数)。

为了尽快到达公主,骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士可以拯救到公主所需的最低初始健康点数。

例如,考虑到以下布局的地下城,若是骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。

-2 (K)  -3  3
-5  -10 1
10  30  -5 (P)

说明:

骑士的健康点数没有上限。

任何房间均可能对骑士的健康点数形成威胁,也可能增长骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
int row=dungeon.length;
        int col=dungeon[0].length;
        //这个数组表示在i,j位置骑士须要的最小生命值
        int[][] dp=new int[row][col];
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=0;j--){
                if(i==row-1&&j==col-1){ //终点的状况
                    dp[i][j]=Math.max(1, 1-dungeon[i][j]);
                }else if(i==row-1){ //最后一行的状况
                    dp[i][j]=Math.max(1, dp[i][j+1]-dungeon[i][j]);
                }else if(j==col-1){ //最后一列的状况
                    dp[i][j]=Math.max(1, dp[i+1][j]-dungeon[i][j]);
                }else{  
                    dp[i][j]=Math.max(1, Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}

175. 组合两个表

SQL架构
表1: Person

+-------------+---------+
| 列名         | 类型     |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+

PersonId 是上表主键
表2: Address

+-------------+---------+
| 列名         | 类型    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+

AddressId 是上表主键

编写一个 SQL 查询,知足条件:不管 person 是否有地址信息,都须要基于上述两表提供 person 的如下信息:

FirstName, LastName, City, State

/* Write your T-SQL query statement below */

select FirstName, LastName, 
(select City from Address where Address.PersonId = Person.PersonId ) as City,
(select State from Address where Address.PersonId = Person.PersonId ) as State 
from Person

176. 第二高的薪水

SQL架构
编写一个 SQL 查询,获取 Employee 表中第二高的薪水(Salary) 。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

例如上述 Employee 表,SQL查询应该返回 200 做为第二高的薪水。若是不存在第二高的薪水,那么查询应返回 null。

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+
/* Write your T-SQL query statement below */

select max(Salary) SecondHighestSalary
from employee
where
salary<(select max(salary) from employee)

177. 第N高的薪水

编写一个 SQL 查询,获取 Employee 表中第 n 高的薪水(Salary)。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

例如上述 Employee 表,n = 2 时,应返回第二高的薪水 200。若是不存在第 n 高的薪水,那么查询应返回 null。

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+
CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
BEGIN 
    RETURN (
        /* Write your T-SQL query statement below. */

   Select Distinct Salary 
        FROM Employee
        Order by Salary DESC
        OFFSET (@N-1) ROWS FETCH NEXT 1 ROWS ONLY
    );
END

178. 分数排名

SQL架构
编写一个 SQL 查询来实现分数排名。若是两个分数相同,则两个分数排名(Rank)相同。请注意,平分后的下一个名次应该是下一个连续的整数值。换句话说,名次之间不该该有“间隔”。

+----+-------+
| Id | Score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

例如,根据上述给定的 Scores 表,你的查询应该返回(按分数从高到低排列):

+-------+------+
| Score | Rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

PS:
b是查询的不重复的成绩,和降序的数字序列

SELECT b.Score AS Score,b.Rank FROM Scores INNER JOIN
 (
SELECT Score,ROW_NUMBER() OVER (ORDER BY Score DESC) AS Rank FROM
 (SELECT DISTINCT(Score) AS Score FROM Scores)
a
)b ON b.Score = Scores.Score
ORDER BY b.Rank

179. 最大数

给定一组非负整数,从新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能很是大,因此你须要返回一个字符串而不是整数。

class Solution {
      /**
     * @param nums 一组非负整数
     * @return - String.compareTo() 是按照 lexicographically, 字典顺序排列的
     * - 利用compareTo, 来倒序排列 string, 恰好就获得咱们要的结果.
     */
    public String largestNumber(int[] nums) {
        //合法性
        if (nums == null || nums.length == 0) {
            return "";
        }
        //数字数组->字符数组  转化
        String[] strArr = new String[nums.length];
        for (int i = 0; i < strArr.length; i++) {
            strArr[i] = String.valueOf(nums[i]);
        }
        //重写排序规则 12-14ms
       // Arrays.sort(strArr, new Comparator<String>() {
       //     @Override
       //     public int compare(String o1, String o2) {
       //         //继承此方法的时候,要自定义比较器,conpareTo方法返回值为1(升序),0,-1(降序)。
       //         //返回正值 交换;负值不交换
       //         return (o2 + o1).compareTo((o1 + o2));
       //     }
       // });
        //Lambda表达式 重写排序规则 速度慢了5倍 72-82ms
        Arrays.sort(strArr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        //字符数组->字符串 转化
        StringBuilder sb = new StringBuilder();
        for (String aStrArr : strArr) {
            sb.append(aStrArr);
        }
        String result = sb.toString();
        //特殊状况 若干个零
        if (result.charAt(0) == '0') {
            result = "0";
        }
        return result;
    }
}