力扣刷题180

180. 连续出现的数字

难度中等621

SQL架构

表：Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
id 是这个表的主键。

编写一个 SQL 查询，查找所有至少连续出现三次的数字。

返回的结果表中的数据可以按 任意顺序 排列。

查询结果格式如下面的例子所示：

示例 1:

输入：
Logs 表：
+----+-----+
| Id | Num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+
输出：
Result 表：
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
解释：1 是唯一连续出现至少三次的数字。

# Write your MySQL query statement below
SELECT DISTINCT
    l1.Num AS ConsecutiveNums
FROM
    Logs l1,
    Logs l2,
    Logs l3
WHERE
    l1.Id = l2.Id - 1
    AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num
    AND l2.Num = l3.Num
;

1403. 非递增顺序的最小子序列

难度简单99

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9] 
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。 

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6] 
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。  

示例 3：

输入：nums = [6]
输出：[6]

/*
先遍历一遍元素，将所有元素加起来，然后对数组进行排序，先去掉最大的元素，然后累加的和减去去掉的这个元素，判断两者之和的大小关系，假如满足条件那么直接break了说明找到了所有符合条件的数字了，没有满足循环继续去掉大的元素
*/

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < nums.length; ++i){
            sum += nums[i];
        }
        Arrays.sort(nums);
        int index = nums.length - 1;
        int now = 0;
        while (true){
            res.add(nums[index]);
            sum -= nums[index];
            now += nums[index--];
            if(now > sum) break;
        }
        return res;
    }
}

187重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) {
            /**
emptyList()
作用：返回一个空的List（使用前提是不会再对返回的list进行增加和删除操作）；
好处：
1. new ArrayList()创建时有初始大小，占用内存，emptyList()不用创建一个新的对象，可以减少内存开销；
2. 方法返回一个emptyList()时，不会报空指针异常，如果直接返回Null，没有进行非空判断就会报空指针异常；
注意：此List与常用的List不同，它是Collections类里的静态内部类，在继承AbstractList后并没有实现add()、remove()等方法
             */
            return Collections.emptyList();
        }
        Set<String> result = new HashSet<>();
        Set<String> set = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i <= chars.length - 10; i++) {
            String str = s.substring(i, i+10);
            //substring方法：从beginIndex开始取，到endIndex结束，从0开始数，其中不包括endIndex位置的字符
            if (set.contains(str)) {
                result.add(str);
            } else {
                set.add(str);
            }
        }
        return new ArrayList<>(result);
    }
}

93复制IP地址

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

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

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

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

不会做，看了解析差不多理解，改日二刷

class Solution {
    List<String> list = new ArrayList<String>();

    public List<String> restoreIpAddresses(String s) {
        //x.x.x.x  ip地址最少为4位,最多为12位
        if(s.length() < 4 || s.length() > 12){
            return list;
        }
        StringBuilder sb = new StringBuilder();
        int target = 0;
        for(int i=1;i<4;i++){
        	//若开头为0开头且位数大于1位  则直接结束循环，例如 01，不存在01.xx.xx.xx这样的ip地址
        	if(s.substring(0,i).charAt(0) == '0' && i != 1) {
        		break;
        	}
        	//String转成int，由此判断他的大小
            target = Integer.valueOf(s.substring(0,i));
            //约束条件，每个区间最长3位，最短1位
            if(target < 256 && s.length()-i > 2 && s.length()-i < 10){
                sb.append(target);
                sb.append('.');
                backTrack(sb,s,i,1);
                sb.setLength(0);
            }
        }
        return list;
    }
    public void backTrack(StringBuilder sb,String s,int start,int level){
        if(level > 4) {
    		return;
    	}
        if(start == s.length() && level == 4){
            list.add(sb.toString());
            return;
        }
        //剩余长度不符合接下来的运算，则减枝
        if(s.length()-start < 4-level || s.length()-start > (4-level)*3) {
        	return;
        }
        //控制循环次数
        int flag = 1;
        int target = 0;
        //区间自增
        level++;
        for(int i=start;i<s.length();i++){
        	if(s.substring(start,start+flag).charAt(0) == '0' && flag != 1) {
        		return;
        	}
            target = Integer.valueOf(s.substring(start,start+flag));
            flag++;
            if(target < 256){
                sb.append(target);
                //除了最后一个区间，加入对应字符串之后都需要在结尾加上 '.'
                if(level != 4){
                    sb.append('.');
                }             
                backTrack(sb,s,i+1,level);
                //这一步很关键，恢复状态需要考虑到新加入的'.',偏移值为level-1
                sb.delete(start+level-1,sb.length());
            }
            //循环次数最大为3次
            if(flag == 4){
                break;
            }
        }
    }
}