LeetCode Weekly Contest 184 题解

一、String Matching in an Array

题目 String Matching in an Array

题意:给一组字符串,如果当前的字符串在其他的字符串中被包含,其他的字符串被删除,返回最后留下来的字符串。

时间复杂度 O(n^2)

空间复杂度 O(n)

class Solution {
    public List<String> stringMatching(String[] words) {
         if (words == null || words.length == 0) {
            return null;
        }
        Set<String> set = new HashSet<>();
        Arrays.sort(words, Comparator.comparingInt(String::length));

        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    set.add(words[i]);
                }
            }
        }
        return new ArrayList<>(set);
    }
}

二、Queries on a Permutation With Key

题目 Queries on a Permutation With Key

题意:给一个需要查询的数组queries, 需要准备一个数组P从1开始有序的自增到m,每次查询完成需要将查询的数字放置到数组的第一个位置,返回查询数组queries中数值在数组P中的位置。

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int[] ret = new int[queries.length];
        int[] p = new int[m];
        for (int i = 1; i <= m; i++) {
            p[i - 1] = i;
        }
        int index = 0;
        for (int k = 0; k < queries.length; k++) {
            int position = search(p, queries[k]);
            ret[index++] = position;
            move(p, position);
        }
        return ret;
    }
    public void move(int[] p, int position) {
         int temp = p[position];
        while (position > 0) {
            p[position] = p[position - 1];
            position--;
        }
        p[0] = temp;
    }

    public int search(int[] p, int query) {
        for (int i = 0; i < p.length; i++) {
            if (p[i] == query) {
                return i;
            }
        }
        return -1;
    }
}

三、HTML Entity Parser

题目 HTML Entity Parser

题意:字符串替换

class Solution {
    public String entityParser(String text) {
       Map<String, String> map = new HashMap<>();
        map.put("&quot;", "\"");
        map.put("&apos;", "'");
        map.put("&amp;", "&");
        map.put("&gt;", ">");
        map.put("&lt;", "<");
        map.put("&frasl;", "/");

        for (String key : map.keySet()) {
            if (text.contains(key)) {
                text = text.replaceAll(key, map.get(key));
            }
        }
        return text;  
    }
}

四、Number of Ways to Paint N × 3 Grid

题目 Number of Ways to Paint N × 3 Grid

题意:使用3种颜色涂3个格子,网格的数量是 NX3的,要求是相邻的不能同色(水平和垂直方向颜色不能一样)

比赛没有做出来,后面看了别人的题解,考察动态规划的题目 参考题解

class Solution {
    public int numOfWays(int n) {
        long a121 = 6, a123 = 6, b121, b123, mod = (long) 1e9 + 7;
        for (int i = 1; i < n; i++) {
            b121 = a121 * 3 + a123 * 2;
            b123 = a121 * 2 + a123 * 2;
            a121 = b121 % mod;
            a123 = b123 % mod;
        }
        return (int) ((a121 + a123) % mod);
    }
}

总结

动态规划算法需要弄明白,每次比赛基本上有出现。

仅有 1 条评论
  1. justhost justhost

    66666666

添加新评论