周赛 - 😺 第 69 场力扣夜喵双周赛 - 《学习笔记》

5960. 将标题首字母大写
5961. 链表最大孪生和
5962. 连接两字母单词得到的最长回文串
5931. 用邮票贴满网格图

第三题挺简单一题，我不知道在想什么，非得用Set。。。
t4我想到用二位前缀和，但没想到用两次，长知识了！
这次掉大分，有点难过

5960. 将标题首字母大写

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母大写：

如果单词的长度为 1 或者 2 ，所有字母变成小写。
否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的_ _title 。

示例 1：
输入：title = “capiTalIze tHe titLe” 输出：“Capitalize The Title” 解释： 由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。
示例 2：
输入：title = “First leTTeR of EACH Word” 输出：“First Letter of Each Word” 解释： 单词 “of” 长度为 2 ，所以它保持完全小写。其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。
示例 3：
输入：title = “i lOve leetcode” 输出：“i Love Leetcode” 解释： 单词 “i” 长度为 1 ，所以它保留小写。其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

提示：

1 <= title.length <= 100
title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
每个单词由大写和小写英文字母组成，且都是非空的。

思路：
模拟即可

class Solution {
    public String capitalizeTitle(String title) {
        String[] ss = title.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String s : ss) {
            char[] ch = s.toCharArray();
            if (ch.length > 2)
                sb.append(Character.toUpperCase(ch[0]));
            else
                sb.append(Character.toLowerCase(ch[0]));
            for (int i = 1; i < ch.length; i++) {
                char c = Character.toLowerCase(ch[i]);
                sb.append(c);
            }
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

5961. 链表最大孪生和

在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。

比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1：

输入：head = [5,4,2,1] 输出：6 解释： 节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。链表中没有其他孪生节点。所以，链表的最大孪生和是 6 。
示例 2：

输入：head = [4,2,2,3] 输出：7 解释： 链表中的孪生节点为： - 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。 - 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。所以，最大孪生和为 max(7, 4) = 7 。
示例 3：

输入：head = [1,100000] 输出：100001 解释： 链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

提示：

链表的节点数目是 [2, 105] 中的偶数。
1 <= Node.val <= 105

思路：
转成数组处理即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int max = 0;
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int val = list.get(l) + list.get(r);
            max = Math.max(max, val);
            l++;
            r--;
        }
        return max;
    }
}

5962. 连接两字母单词得到的最长回文串

给你一个字符串数组 words 。words 中每个元素都是一个包含两个小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素至多只能使用一次。
请你返回你能得到的最长回文串的长度。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。

示例 1：
输入：words = [“lc”,”cl”,”gg”] 输出：6 解释：一个最长的回文串为 “lc” + “gg” + “cl” = “lcggcl” ，长度为 6 。 “clgglc” 是另一个可以得到的最长回文串。
示例 2：
输入：words = [“ab”,”ty”,”yt”,”lc”,”cl”,”ab”] 输出：8 解释：最长回文串是 “ty” + “lc” + “cl” + “yt” = “tylcclyt” ，长度为 8 。 “lcyttycl” 是另一个可以得到的最长回文串。
示例 3：
输入：words = [“cc”,”ll”,”xx”] 输出：2 解释：最长回文串是 “cc” ，长度为 2 。 “ll” 是另一个可以得到的最长回文串。”xx” 也是。

提示：

1 <= words.length <= 105
words[i].length == 2
words[i] 仅包含小写英文字母。

思路：
用哈希表进行判断

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        int cnt = 0;
        boolean flag = false;
        for (String s : words) {
            String ns = s.charAt(1) + "" +  s.charAt(0);
            if (map.containsKey(ns)) {
                if (map.get(ns) > 0) {
                    cnt += 4;
                    map.merge(ns, -1, Integer::sum);
                } else {
                    map.merge(s, 1, Integer::sum);
                }
            } else {
                map.merge(s, 1, Integer::sum);
            }
        }
        for (String s : map.keySet()) {
            if (map.get(s) > 0 && s.charAt(0) == s.charAt(1)) {
                cnt += 2;
                break;
            }
        }
        return cnt;
    }
}

5931. 用邮票贴满网格图

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：

覆盖所有空格子。
不覆盖任何 被占据 的格子。
我们可以放入任意数目的邮票。
邮票可以相互有重叠部分。
邮票不允许旋转。
邮票必须完全在矩阵内。

如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回_ _false 。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3 输出：true 解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。
示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 输出：false 解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 105
1 <= m n <= 2 105
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 105

思路：
两次二维前缀和
第一次对原数组进行，然后遍历原数组，对所有为0的地方判断该位置右下角能不能放，能放将新数组该位置置为1
第二次对新数组求前缀和，遍历原数组，对每一个0位判断其左上角范围内新数组的前缀和是否大于0，大于0才说明本位置被某张邮票覆盖。

class Solution {
    public boolean possibleToStamp(int[][] g, int h, int w) {
        int n = g.length;
        int m = g[0].length;
        int[][] pre = get(g);
        int[][] cnt = new int[n][m];
        for (int i = 1; i <= n; i++) {
            int x = i - 1;
            for (int j = 1; j <= m; j++) {
                int y = j - 1;
                if (g[x][y] == 0 && i + h - 1 <= n && j + w - 1 <= m && check(i, j, i + h - 1, j + w - 1, pre) == 0)
                    cnt[x][y] = 1;
            }
        }
        int[][] res = get(cnt);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (g[i - 1][j - 1] == 0) {
                    if (check(Math.max(i - h + 1, 1), Math.max(j - w + 1, 1), i, j, res) == 0)
                        return false;
                }
            }
        }
        return true;
    }
    int[][] get(int[][] g) {
        int n = g.length, m = g[0].length;
        int[][] pre = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)  {
            for (int j = 1; j <= m; j++) {
                pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + g[i - 1][j - 1];
            }
        }
        return pre;
    }
    int check(int x, int y, int a, int b, int[][] pre) {
        return pre[a][b] - pre[x - 1][b] - pre[a][y - 1] + pre[x - 1][y - 1];
    }
}