Likou Brush Question 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]

/*
Iterate over the elements first,将所有元素加起来,然后对数组进行排序,Remove the largest element first,Then accumulate the sum and subtract the removed element,Determine the relationship between the sum of the two,If the conditions are met then directbreakThe description found all matching numbers,The loop continues to remove large elements if the loop is not satisfied
*/

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
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处

不会做,After reading the analysis, I almost understand,Two brushes another day

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

    public List<String> restoreIpAddresses(String s) {
        //x.x.x.x  ipThe address is at least 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++){
        	//若开头为0starts and the number of digits is greater than1位  则直接结束循环,例如 01,不存在01.xx.xx.xx这样的ip地址
        	if(s.substring(0,i).charAt(0) == '0' && i != 1) {
        		break;
        	}
        	//String转成int,Judge his size from this
            target = Integer.valueOf(s.substring(0,i));
            //约束条件,Each interval is the longest3位,最短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;
        }
        //The remaining length does not qualify for the next operation,prune
        if(s.length()-start < 4-level || s.length()-start > (4-level)*3) {
        	return;
        }
        //控制循环次数
        int flag = 1;
        int target = 0;
        //The interval is incremented
        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);
                //Except for the last interval,After adding the corresponding string, you need to add it at the end '.'
                if(level != 4){
                    sb.append('.');
                }             
                backTrack(sb,s,i+1,level);
                //这一步很关键,Restoring the state needs to take into account the newly added ones'.',偏移值为level-1
                sb.delete(start+level-1,sb.length());
            }
            //The maximum number of cycles is 3次
            if(flag == 4){
                break;
            }
        }
    }
}