[数据结构与算法]【2022.12.18】备战春招Day13——每日一题 + 234. 回文链表 + 139. 单词拆分

【每日一题】1703. 得到连续 K 个 1 的最少相邻交换次数

题目描述

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻
两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

题目解析

假设k等于1的个数，要把这些1聚成连续的，最少需要交换多少次？

假设第$i$个1的下标为$q_i$，设最左边的1移到下标$x$处。

$q_0$移到$x$， $q_1$移到$x+1$，$q_2$移到$x+2$
可以转换为 $q_0$移到$x$， $q_1?1$移到$x$，$q_2?2$移到$x$。
设$p_i=q_i?i$，则问题转换为所有$p_i$到x的距离和的最小值。

回到原问题，可以枚举，第i个1是连续1的最左边的那个1。

class Solution {
    public int minMoves(int[] nums, int k) {
        // p = q - i
        List<Integer> p = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1){
                p.add(i - p.size());
            }
        }
        //前缀和
        int m = p.size();
        int[] s = new int[m + 1];
        for(int i = 0; i < m; i++){
            s[i + 1] = s[i] + p.get(i);
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i <= m - k; i++){
            ans = Math.min(ans, s[i] + s[i + k] - s[i + k / 2] * 2 - p.get(i + k / 2) * (k % 2));
        }
        return ans;
    }
}

【leetcode hot 100】234. 回文链表

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

题目解析

需要进行两次遍历 + 数组存储。

第一次遍历：将链表转换为数组
第二次遍历：判断数组是否为回文。

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        for(int i = 0; i < list.size() / 2; i++){
            if(list.get(i) != list.get(list.size() - i - 1)){
                return false;
            }
        }
        return true;

    }
}

【代码随想录】139. 单词拆分

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

题目解析

【动态规划】：判断当前的字符串是否能有之前的字符串 + 字典中的字符串拼接组成。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> word_set = new HashSet<>(wordDict);
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                if(f[j] == true && word_set.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.length()];
    }
}