Page 14 of 61

LeetCode刷题【468】验证IP地址

2022 年 6 月 29 日 / / 0 Comments

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。

一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:

  • 1 <= xi.length <= 4
  • xi 是一个 十六进制字符串 ，可以包含数字、小写英文字母( 'a' 到 'f' )和大写英文字母( 'A' 到 'F' )。
  • 在 xi 中允许前导零。

例如 "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

示例 1：

输入：queryIP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

示例 2：

输入：queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

示例 3：

输入：queryIP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

提示：

  • queryIP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

Related Topics

  • 字符串

👍 200👎 0

拆解方法 & Java的split的坑
先说坑
示例"1,2,".split(",").length 这个分出来结果是[1,2],长度不是3，末尾的 , 会被省略

然后本题思路

  1. 字符串长度小于7个的直接NEITHER
  2. 接下来只要预判前5个字符，根据是否出现.或者:来区分用IPv4还是IPv6的方法去校验
  3. 分别根据IPv4还是IPv6的区别使用.或者:来拆分，这里会遇到split方法的坑
  4. 再接下来校验拆分后每一段的规则
  5. IPv4的长度为0-3个字符，每个字符只能是数字，不能有先导0,最终数字要小于256
  6. IPv6的长度为0-4个字符，每个字符只能是0-9或者A-F或者A-F

每个方法各自封装处理

代码

class Solution {

    String IPV4 = "IPv4";
    String IPV6 = "IPv6";
    String NEITHER = "Neither";

    public String validIPAddress(String queryIP) {
        if (queryIP.length() < 7){
            return NEITHER;
        }
        for (int i = 0; i < 6; i++) {
            if (queryIP.charAt(i) == '.'){
                return isIpv4(queryIP);
            }
            if (queryIP.charAt(i) == ':'){
                return isIpv6(queryIP);
            }
        }
        return NEITHER;
    }

    /**
     * 验证IPv4类型的IP字符串
     * @param queryIP
     * @return
     */
    public String isIpv4(String queryIP){
        String[] ipv4Nums = queryIP.split("\\.");
        if (ipv4Nums.length != 4 || queryIP.charAt(queryIP.length()-1) == '.'){
            return NEITHER;
        }

        for (String ipv4Num : ipv4Nums) {
            if (!isIpv4Num(ipv4Num)){
                return NEITHER;
            }
        }
        return IPV4;
    }

    /**
     * 验证IPv4的每一段
     * @param ipv4NumStr
     * @return
     */
    public boolean isIpv4Num(String ipv4NumStr){
        //单个长度大于3个 或者为空
        if (ipv4NumStr.length()>3 || ipv4NumStr.length()==0){
            return false;
        }
        //长度大于1的首个字符不能为0
        if (ipv4NumStr.length()>1 && ipv4NumStr.charAt(0) == '0'){
            return false;
        }
        int num = 0;
        for (int i = 0; i < ipv4NumStr.length(); i++) {
            int tmp = ipv4NumStr.charAt(i) - '0';
            if (tmp < 0 || tmp > 9){
                return false;
            }
            num *= 10;
            num += tmp;
        }
        return num < 256;
    }


    /**
     * 验证IPv6的字符串
     * @param queryIP
     * @return
     */
    public String isIpv6(String queryIP){
        String[] ipv6Nums = queryIP.split("\\:");
        if (ipv6Nums.length != 8 || queryIP.charAt(queryIP.length()-1) == ':'){
            return NEITHER;
        }
        for (String ipv6Num : ipv6Nums) {
            if (!isIpv6Num(ipv6Num)){
                return NEITHER;
            }
        }
        return IPV6;
    }

    /**
     * 验证IPv6的每一段
     * @param ipv6NumStr
     * @return
     */
    public boolean isIpv6Num(String ipv6NumStr){
        if (ipv6NumStr.length() > 4 || ipv6NumStr.length() < 1){
            return false;
        }
        for (int i = 0; i < ipv6NumStr.length(); i++) {
            char c = ipv6NumStr.charAt(i);
            if (!(c - '0' >=0 && c - '9' <= 0)&&
                !(c - 'A' >=0 && c - 'F' <= 0)&&
                !(c - 'a' >=0 && c - 'f' <= 0)){
                return false;
            }
        }
        return true ;
    }
}

LeetCode刷题【786】第 K 个最小的素数分数

2022 年 6 月 29 日 / / 0 Comments

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

 

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

 

提示：

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] 是一个 素数 ，i > 0
  • arr 中的所有数字 互不相同 ，且按 严格递增 排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2
Related Topics
  • 数组
  • 二分查找
  • 排序
  • 堆（优先队列）

  • 👍 221
  • 👎 0

    • 优先队列两种实现

    首先，直接上来一个优先队列，自定义排序。

    为了实现这个自定义的排序，我们需要记录几个东西

    1. 分子
    2. 分母
    3. 为了便于比较，相除后的小数值也可以事先计算好，比较的时候就直接比较这个数字即可
    4. 把所有的都放进去之后，我们就开始从头部取出K个即可
    5. 最终得到第K个的分子分母即可

    理解起来也相对比较简单

    代码

    class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<double[]> queue = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                if (o1[2] >= o2[2]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i : arr) {
            for (int j : arr) {
                queue.offer(new double[]{(double)i,(double)j,((double)i)/j});
            }
        }
        while (--k > 0){
            queue.poll();
        }
        return new int[]{(int)queue.peek()[0],(int)queue.peek()[1]};
    }
}

    写完这个之后思考一下，我们真的需要把所有的值都算一遍全都存进优先队列么？答案是否定的，

    1. 我们可以把数据分别按照分母分成arr[]数组长度个分组，
    2. 分别维护一个指针，指向当前对应的分子，
    3. 这样我们的优先队列只要维护比较arr[]数组长度个值即可，每当从队列头部取出一个对象时，只需把分子位置往后挪动一位，重新放入队列
    4. 如果分子指针位置已经到达了arr[]数组尾部，则不再需要往队列中添加

    代码

    class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (((double)arr[o1[0]])/arr[o1[1]] >= ((double)arr[o2[0]])/arr[o2[1]]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            queue.offer(new int[]{0,i});
        }
        while (--k > 0) {
            int[] top = queue.poll();
            if (top[0] < arr.length){
                top[0]++;
                queue.offer(top);
            }
        }
        return new int[]{arr[queue.peek()[0]],arr[queue.peek()[1]]};
    }

}

    LeetCode刷题【438】找到字符串中所有字母异位词

    2022 年 6 月 29 日 / / 0 Comments

    给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

    异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

     

    示例 1:

    输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

     示例 2:

    输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

     

    提示:

    • 1 <= s.length, p.length <= 3 * 104
    • s 和 p 仅包含小写字母
    Related Topics
    • 哈希表
    • 字符串
    • 滑动窗口

  • 👍 929
  • 👎 0

    • 滑动窗口+哈希表统计，联动可以参考下76题最小覆盖子串

    类似的可以看下76题，非常相似
    滑动窗口，带注释
    区别就是76题是非固定长度窗口，本题中窗口长度固定

    class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length()){
            return new ArrayList<>();
        }
        int[] arr =  new int[26];
        int count = 0;
        for (int i = 0; i < p.length(); i++) {
            arr[p.charAt(i)-'a']++;
            if (arr[p.charAt(i)-'a'] == 1){
                count++;
            }
            arr[s.charAt(i)-'a']--;
            if (arr[s.charAt(i)-'a'] == 0){
                count--;
            }
        }
        List<Integer> res = new ArrayList<>();
        if (count == 0){
            res.add(0);
        }
        int idx = p.length()-1;
        while (++idx < s.length()){
            arr[s.charAt(idx-p.length())-'a']++;
            if (arr[s.charAt(idx-p.length())-'a'] == 1){
                count++;
            }
            arr[s.charAt(idx)-'a']--;
            if (arr[s.charAt(idx)-'a'] == 0){
                count--;
            }
            if (count == 0){
                res.add(idx-p.length()+1);
            }
        }
        return res;
    }
}

    LeetCode刷题【560】和为 K 的子数组

    2022 年 6 月 29 日 / / 0 Comments

    给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

     

    示例 1：

    输入：nums = [1,1,1], k = 2
输出：2

    示例 2：

    输入：nums = [1,2,3], k = 3
输出：2

     

    提示：

    • 1 <= nums.length <= 2 * 104
    • -1000 <= nums[i] <= 1000
    • -107 <= k <= 107
    Related Topics
    • 数组
    • 哈希表
    • 前缀和

  • 👍 1552
  • 👎 0

    • 连续区间和，必然会想到的内容前缀和数组

    所以在这题目中，我们的思路是这样的

    1. 要求区间和为K的子数组的话，那么就需要判断 在当前位置前面，是否存在前缀和为当前区间和减去K的情况存在
    2. 可以在前缀和数组上遍历，当然我们有更好的选择，哈希表
    3. 在求前缀和数组的过程中，用哈希表统计各个值的前缀和出现次数
    4. 那么当前位置的前缀和 与这个位置之前的 前缀和能组成多少个符合 区间和为K的区间就可以等价🐟， 当前位置之前有多少个 当前位置区间和 减去 K的值的区间和的数量
    5. 边界考虑：当什么都没有的时候有一个区间和为0的情况

    代码

    class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] preSum = new int[nums.length];
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        hashMap.put(0,1);
        int idx = -1;
        int count = 0;

        while (++idx < nums.length){
            preSum[idx] = nums[idx] + (idx>0?preSum[idx-1]:0);
            count += hashMap.getOrDefault(preSum[idx] - k,0);
            hashMap.put(preSum[idx], hashMap.getOrDefault(preSum[idx],0)+1);
        }
        return count;
    }
}

    LeetCode刷题【76】最小覆盖子串

    2022 年 6 月 28 日 / / 0 Comments

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

     

    注意：

    • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

     

    示例 1：

    输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

    示例 2：

    输入：s = "a", t = "a"
输出："a"

    示例 3:

    输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

     

    提示：

    • 1 <= s.length, t.length <= 105
    • s 和 t 由英文字母组成

     

    进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
    Related Topics
  • 哈希表
  • 字符串
  • 滑动窗口

  • 👍 1957
  • 👎 0

    • 滑动窗口，带注释

    一样的，就是统计窗口内待匹配字符出现次数

    1. 统计原t字符串中各个字符的数量
    2. 在字符串s中进行窗口移动操作
    3. 如果还有需要匹配的字符数量，则往右扩展右边界增大窗口
    4. 如果字符数量都匹配达成，则左边界往右可移动缩小窗口
    5. 在窗口移动过程中取到最小的那个子串

    代码

    class Solution {
    public String minWindow(String s, String t) {
        int[] arr = new int[128];
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < t.length(); i++) {
            arr[t.charAt(i)]++;
            hashSet.add(t.charAt(i));
        }
        int count = hashSet.size();
        //count 表示待匹配字符个数
        int l = 0;
        int r = -1;
        int minL = 0;
        int minLen = Integer.MAX_VALUE;

        while (r < s.length()){
            if (count == 0){
                //移动左边，尝试缩减长度
                arr[s.charAt(l)]++;
                //左边界每往右移动一个字符 在在arr[]中这个字符个数加1
                if (hashSet.contains(s.charAt(l)) && arr[s.charAt(l)] == 1){
                    // 如果这个字符在hashSet中，且结果等于1，即表示是从匹配成了变为缺少匹配个数的状态，那么count++;
                    count++;
                }
                //移动左边
                l++;
            }else{
                //移动右边边
                r++;
                if (r == s.length()){
                    break;
                }
                arr[s.charAt(r)]--;
                //右边界每新增一个字符， 在arr[]中减去这个字符个数减1
                if (hashSet.contains(s.charAt(r)) && arr[s.charAt(r)] == 0){
                    //    如果这个字符在hashSet中，如果结果为0 了表示都匹配到了，则count--;
                    count--;
                }
            }
            if (count==0 && r - l < minLen){
                //记下最小子串
                minLen = r - l;
                minL = l;
            }
        }
        return minLen==Integer.MAX_VALUE?"":s.substring(minL,minL+minLen+1);
    }
}

    LeetCode刷题【519】随机翻转矩阵

    2022 年 6 月 27 日 / / 0 Comments

    给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

    尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

    实现 Solution 类：

    • Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
    • int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
    • void reset() 将矩阵中所有的值重置为 0

     

    示例：

    输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

     

    提示：

    • 1 <= m, n <= 104
    • 每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
    • 最多调用 1000 次 flip 和 reset 方法。
    Related Topics
  • 水塘抽样
  • 哈希表
  • 数学
  • 随机化

  • 👍 140
  • 👎 0

    • 分析，实现，【掉坑】，改进

    直接模拟，思路

    1. 声明一个m * n的二维数组，随机翻转一个
    2. 但是接下来的问题就是，如何随机保证横轴和纵轴的坐标的随机概率相等，所以我们可以换个思路，直接声明一个m * n长度的一维数组，在这个长度内随机，而每一个随机数都可以映射回原来的矩阵中，从而保证每一个格子的随机概率是相等的
    3. 下一个问题，之前已经翻转到过的位置不能再随机到。
      • 那么我们就需要记录一下剩余多少位置可以随机，从而在这个范围内进行随机操作
      • 如果在这个范围内随机到的数字是之前原数组中已经翻转过的，那么就从这个位置开始一直往后找到未被翻转的过的那个位置
    4. 最终将随机到的位置坐标重新映射回矩阵坐标中返回即可

    代码

    class Solution {

    int[] matrix;
    int m;
    int n;
    Random random;
    int total;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (matrix[idx]==1){
            idx++;
        }
        total--;
        matrix[idx] = 1;
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        matrix = new int[m * n];
        total = matrix.length;
    }
}

    提交，跑到第19个测试用例，报OOM了，看下入参是10000 * 10000，按照道理java中数组的最大长度根据具体数据类型和JVM配置实际情况应该是一个接近Integer.MAX_VALU - 8的值，最大就是这么多，此时OOM的话，必然应该是限制了内存大小了

    那么我们不妨再换个思路，题面中给出了 最多调用 1000 次 flip 和 reset 方法，我们就可以不用记录整个数组的情况，而是换一种角度，只记录哪些位置被翻转过，使用一个HashSet来存储这些位置信息，那么修改后代码如下

    代码

    class Solution {

    int m;
    int n;
    Random random;
    int total;
    HashSet<Integer> hashSet;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (hashSet.contains(idx)){
            idx++;
        }
        total--;
        hashSet.add(idx);
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        hashSet = new HashSet<>();
        total = m * n;
    }
}

    LeetCode刷题【21】合并两个有序链表

    2022 年 6 月 27 日 / / 0 Comments

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

     

    示例 1：

    输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

    示例 2：

    输入：l1 = [], l2 = []
输出：[]

    示例 3：

    输入：l1 = [], l2 = [0]
输出：[0]

     

    提示：

    • 两个链表的节点数目范围是 [0, 50]
    • -100 <= Node.val <= 100
    • l1 和 l2 均按 非递减顺序 排列
    Related Topics
  • 递归
  • 链表

  • 👍 2490
  • 👎 0

    • 双指针，串珠子

    同剑指Offer25
    这个问题之前给人家形象的比喻讲解过。

    1. 你拿两串珠子，分别按照题意标上有序递增的数字
    2. 另外你再拿一根线，把这两串珠子合并成一串，这时候你会怎么做呢？
      当然是两个原串头上挑小的串起来呀！哪个小串哪个，另外一串没有了就整个串上就完了
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}