欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

「力扣」周赛第 170周题解(Java)

程序员文章站 2022-07-13 17:36:42
...

这周做出来 2 题。

  • 第 1 题调试了很久,后来才发现,原来只需要一个 ifelse 就解决了;
  • 第 2 题暴力做的,没有想到异或也适用于前缀和;
  • 第 3 题就是基础不好了,是几个基础问题的综合题;
  • 第 4 题这周刚刚总结过回文子串和动态规划的技巧,中午趴在桌子上睡一觉,居然还就找出原因了,打印出 dp 数组看了一眼,就发现状态转移出错了。

感谢朋友“大肥凯”的鼓励,做了几周周赛,几乎困难题都是放弃的,哈哈哈哈。这周困难题不一样了,事后自己做了出来,还是有进步哦。

第 1 题:解码字母到整数映射

竞赛页地址:https://leetcode-cn.com/problems/decrypt-string-from-alphabet-to-integer-mapping/

Java 代码:

public class Solution {

    public String freqAlphabets(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        int len = s.length();

        char[] charArr = new char[]{' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};

        for (int i = 0; i < len; i++) {
            if (i + 2 < len && s.charAt(i + 2) == '#') {
                int index = Integer.parseInt(s.substring(i, i + 2));
                stringBuilder.append((char) (index + 96));
                i += 2;
            } else {
                stringBuilder.append(charArr[s.charAt(i) - '0']);
            }
        }
        return stringBuilder.toString();
    }
}

第 2 题:子数组异或查询

竞赛页地址:https://leetcode-cn.com/problems/xor-queries-of-a-subarray/

方法一:直接计算

Java 代码:

import java.util.Arrays;

public class Solution {

    public int[] xorQueries(int[] arr, int[][] queries) {
        int qLen = queries.length;
        int[] res = new int[qLen];

        for (int i = 0; i < qLen; i++) {
            int leftIndex = queries[i][0];
            int rightIndex = queries[i][1];

            int curRes = 0;
            for (int j = leftIndex; j <= rightIndex; j++) {
                curRes ^= arr[j];
            }
            res[i] = curRes;
        }
        return res;
    }
}

方法二:依然可以使用前缀和的技巧。

Java 代码:

import java.util.Arrays;

public class Solution {

    public int[] xorQueries(int[] arr, int[][] queries) {
        int len = arr.length;

        // 得到前缀异或和数组
        int[] preSum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] ^ arr[i];
        }

        int qLen = queries.length;
        int[] res = new int[qLen];

        for (int i = 0; i < qLen; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            // 注意:这里也是取异或
            res[i] = preSum[right + 1] ^ preSum[left];
        }
        return res;
    }
}

第 3 题:获取你好友已观看的视频

竞赛页地址:https://leetcode-cn.com/contest/weekly-contest-170/problems/minimum-insertion-steps-to-make-a-string-palindrome/

Java 代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {

    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        int len = friends.length;

        // 距离 id 的步数,借助队列,初值为 -1 表示还没有赋值
        int[] distance = new int[len];
        Arrays.fill(distance, -1);

        distance[id] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);

        while (!queue.isEmpty()) {
            Integer top = queue.poll();

            for (int friend : friends[top]) {
                if (distance[friend] == -1) {
                    distance[friend] = distance[top] + 1;
                    queue.offer(friend);
                }
            }
        }

        List<String> res = new ArrayList<>();

        // 以下同「力扣」第 451 题:根据字符出现频率排序

        // 存储了距离为 level 的朋友所看的电影和对应的观看次数
        Map<String, Integer> vatchedTimes = new HashMap<>();

        for (int i = 0; i < len; i++) {
            // 只关心距离为 level 的朋友所看的电影
            if (distance[i] == level) {
                for (String video : watchedVideos.get(i)) {
                    if (vatchedTimes.get(video) == null) {
                        res.add(video);
                        vatchedTimes.put(video, 0);
                    } else {
                        vatchedTimes.put(video, vatchedTimes.get(video) + 1);
                    }
                }
            }
        }

        res.sort((v1, v2) -> {
            if (!vatchedTimes.get(v1).equals(vatchedTimes.get(v2))) {
                return vatchedTimes.get(v1) - vatchedTimes.get(v2);
            }

            return v1.compareTo(v2);
        });
        return res;
    }

    public static void main(String[] args) {
        List<List<String>> watchedVideos = new ArrayList<>();

        List<String> video1 = new ArrayList<>();
        video1.add("A");
        video1.add("B");

        List<String> video2 = new ArrayList<>();
        video2.add("C");


        List<String> video3 = new ArrayList<>();
        video3.add("B");
        video3.add("C");

        List<String> video4 = new ArrayList<>();
        video4.add("D");


        watchedVideos.add(video1);
        watchedVideos.add(video2);
        watchedVideos.add(video3);
        watchedVideos.add(video4);


        int[][] friends = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};

        int id = 0;
        int level = 2;

        Solution solution = new Solution();
        List<String> res = solution.watchedVideosByFriends(watchedVideos, friends, id, level);

        System.out.println(res);
    }
}

第 4 题:让字符串成为回文串的最少插入次数

竞赛页地址:https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

心得:状态转移,即让程序“填表”的时候,方向一定要搞对!

「力扣」周赛第 170周题解(Java)

Java 代码:

import java.util.Arrays;

public class Solution {

    public int minInsertions(String s) {
        int len = s.length();

        int[][] dp = new int[len][len];
        for (int j = 1; j < len; j++) {
            
            // 注意顺序,之后的值一定会被之前参考到
            for (int i = j - 1; i >= 0; i--) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 3) {
                        dp[i][j] = 0;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    if (j - i < 2) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                    }
                }
            }
        }

//        for (int i = 0; i < len; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }
        return dp[0][len - 1];
    }
}
相关标签: 力扣