[数据结构与算法]Java 第 32 课

781. 森林中的兔子

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        n, ans = len(answers), 0
        cnt = Counter(answers)
        for k, v in cnt.items():
            ans += (v + k) // (k + 1) * (k + 1)
            #ans += ceil(v/(k+1)) * (k + 1)
        return ans

class Solution {
    public int numRabbits(int[] answers) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : answers) 
            map.put(x, map.getOrDefault(x, 0) + 1);
       
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int k = entry.getKey(), v =  entry.getValue();
            ans += (k + v) / (k + 1) * (k + 1);
        }
  
        return ans;
    }
}

基础知识

648. 单词替换

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        word = sentence.split()
        d = set(dictionary)
        ans = []
        for w in word:           
            for i in range(len(w)):
                s = w[:i+1]
                if s in d:
                    ans.append(w[:i+1])
                    break
            else: ans.append(w)
        return ' '.join(ans)

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] t = sentence.split(" ");
        List<String> ans = new ArrayList<>();
        Set<String> d = new HashSet(dictionary);
        sign:
        for (String w : t){
            for (int i = 0; i < w.length(); i++){
                String x = w.substring(0, i+1);
                if (d.contains(x)){
                    ans.add(x);
                    continue sign;
                }                
            }
            ans.add(w);
        }
        String s = String.join(" ", ans);
        return s;
    }
}

1897. 重新分配字符使所有字符串都相等

基础知识

1331. 数组序号转换

1002. 查找共用字符

基础知识

389. 找不同

★1700. 无法吃午餐的学生数量

基础知识

229. 求众数 II

1365. 有多少小于当前数字的数字

基础知识

41. 缺失的第一个正数

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:        
        n = len(nums)
        m = n + 1
        # 预处理负数和 >n 的数
        for i in range(n):
            x = nums[i]
            if x > n or x < 0:
                nums[i] = 0
        # 标记 + m
        for i in range(n):
            x = nums[i] % m # 还原
            if x > 0: nums[x-1] += m
        for i in range(n):
            if nums[i] < m: return i+1
        return m

1282. 用户分组

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        d = defaultdict(list)
        ans = []
        for i, g in enumerate(groupSizes):
            d[g].append(i)
        for k, v in d.items():
            for i in range(0, len(v), k):
                ans.append(v[i:i+k])
        return ans

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {        
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < groupSizes.length; i++){      
            int x = groupSizes[i];
            map.computeIfAbsent(x, key->new ArrayList<Integer>()).add(i);          
            List<Integer> sub = map.get(x);
            if (sub.size() == x) {
                ans.add(new ArrayList<>(sub));
                sub.clear();
            }
        }
        return ans;
    }
}

692. 前K个高频单词

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        d = Counter(words)
        ans = sorted(d.keys(), key=lambda x : (-d[x], x))
        return ans[:k]

395. 至少有 K 个重复字符的最长子串

class Solution(object):
    # @lru_cache()
    def longestSubstring(self, s, k):
        if len(s) < k: return 0
        cnt = Counter(s)
        for c, v in cnt.items():
            if v < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() < k) return 0;
        int[] cnt = new int[26];
        int ans = 0;
        for (char c : s.toCharArray()) cnt[c-'a']++;
        for (int i = 0; i < 26; i++){
            if (cnt[i] > 0 && cnt[i] < k && ans < s.length()){
                
                String regex = String.valueOf((char)(i+'a'));
                for (String t : s.split(regex)){
                   
                    ans = Math.max(ans, longestSubstring(t, k));
                }
                return ans;
            }
        }
        return s.length();
    }
}

523. 连续的子数组和

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        acc, d = 0, {0:-1}         
        for i, x in enumerate(nums):
            acc += x            
            key = acc % k # 同余定理
            if key in d:
                if i - d[key] >= 2: return True
            else: d[key] = i  # 保存最小索引        
        return False

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int acc = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++){
            acc += nums[i];
            int rem = acc % k;
            if (map.containsKey(rem)){
                if (i - map.get(rem) >= 2) return true;
            }
            else map.put(rem, i);           
        }
        return false;
    }
}

648. 单词替换

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        word = sentence.split()
        d = set(dictionary)
        ans = []
        for w in word:           
            for i in range(len(w)):
                s = w[:i+1]
                if s in d:
                    ans.append(w[:i+1])
                    break
            else: ans.append(w)
        return ' '.join(ans)

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] t = sentence.split(" ");
        List<String> ans = new ArrayList<>();
        Set<String> d = new HashSet(dictionary);
        sign:
        for (String w : t){
            for (int i = 0; i < w.length(); i++){
                String x = w.substring(0, i+1);
                if (d.contains(x)){
                    ans.add(x);
                    continue sign;
                }                
            }
            ans.add(w);
        }
        String s = String.join(" ", ans);
        return s;
    }
}

914. 卡牌分组

# class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:        
        counter = [0] * 10000 # 计数
        for x in deck:
            counter[x] += 1
        # 迭代求多个数的最大公约数
        x = 0
        for cnt in counter:
            if cnt > 0:
                x = gcd(cnt, x) 
                if x == 1: return False # 如果某步中gcd是1，直接返回false
        return x >= 2   
    # 辗转相除法
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {        
        int[] counter = new int[10000]; // 计数
        for (int num: deck) {counter[num]++;}
        // 迭代求多个数的最大公约数
        int x = 0;
        for(int cnt: counter) {
            if (cnt > 0) {
                x = gcd(x, cnt); 
                if (x == 1) return false; // 如果某步中gcd是1，直接返回false                
            }
        }
        return x >= 2;
    }    
    // 辗转相除法
    private int gcd (int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}

290. 单词规律

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        d = {}
        if len(words) != len(pattern):return False
        for i, c in enumerate(pattern):
            w = words[i]
            if c not in d: d[c] = w
            elif d[c] != w: return False                
        if len(d) != len(set(words)): return False
        return True

383. 赎金信

997. 找到小镇的法官

229. 求众数 II

575. 分糖果

1189. “气球” 的最大数量

187. 重复的DNA序列

217. 存在重复元素

888. 公平的糖果交换

1452. 收藏清单

219. 存在重复元素 II

202. 快乐数

748. 最短补全词

325. 和等于 k 的最长子数组长度

242. 有效的字母异位词

268. 丢失的数字

76. 最小覆盖子串

3. 无重复字符的最长子串

442. 数组中重复的数据

288. 单词的唯一缩写

244. 最短单词距离 II

246. 中心对称数

249. 移位字符串分组

264. 丑数 II

266. 回文排列

291. 单词规律 II

299. 猜数字游戏

267. 回文排列 II

30. 串联所有单词的子串

311. 稀疏矩阵的乘法

313. 超级丑数

314. 二叉树的垂直遍历

336. 回文对

340. 至多包含 K 个不同字符的最长子串

347. 前 K 个高频元素

348. 设计井字棋

349. 两个数组的交集

350. 两个数组的交集 II

355. 设计推特

356. 直线镜像

358. K 距离间隔重排字符串

359. 日志速率限制器

36. 有效的数独

362. 敲击计数器

379. 电话目录管理系统

380. O(1) 时间插入、删除和获取随机元素

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

387. 字符串中的第一个唯一字符

395. 至少有 K 个重复字符的最长子串

398. 随机数索引

409. 最长回文串

421. 数组中两个数的最大异或值

423. 从英文中重建数字

424. 替换后的最长重复字符

432. 全 O(1) 的数据结构

433. 最小基因变化

438. 找到字符串中所有字母异位词

447. 回旋镖的数量

448. 找到所有数组中消失的数字

451. 根据字符出现频率排序

454. 四数相加 II

457. 环形数组是否存在循环

460. LFU 缓存

480. 滑动窗口中位数

49. 字母异位词分组

491. 递增子序列

496. 下一个更大元素 I

500. 键盘行

508. 出现次数最多的子树元素和

519. 随机翻转矩阵

522. 最长特殊序列 II

523. 连续的子数组和

531. 孤独像素 I

532. 数组中的 k-diff 数对

533. 孤独像素 II

535. TinyURL 的加密与解密

567. 字符串的排列

582. 杀掉进程

588. 设计内存文件系统

594. 最长和谐子序列

599. 两个列表的最小索引总和

604. 迭代压缩字符串

609. 在系统中查找重复文件

616. 给字符串添加加粗标签

621. 任务调度器

632. 最小区间

635. 设计日志存储系统

645. 错误的集合

652. 寻找重复的子树

653. 两数之和 IV - 输入 BST

659. 分割数组为连续子序列

676. 实现一个魔法字典

677. 键值映射

690. 员工的重要性

692. 前K个高频单词

694. 不同岛屿的数量

697. 数组的度

705. 设计哈希集合

706. 设计哈希映射

710. 黑名单中的随机数

711. 不同岛屿的数量 II

720. 词典中最长的单词

726. 原子的数量

73. 矩阵置零

734. 句子相似性

736. Lisp 语法解析

737. 句子相似性 II

740. 删除并获得点数

752. 打开转盘锁

758. 字符串中的加粗单词

760. 找出变位映射

763. 划分字母区间

767. 重构字符串

770. 基本计算器 IV

771. 宝石与石头

791. 自定义字符串排序

792. 匹配子序列的单词数

804. 唯一摩尔斯密码词

811. 子域名访问计数

815. 公交路线

817. 链表组件

819. 最常见的单词

820. 单词的压缩编码

822. 翻转卡片游戏

823. 带因子的二叉树

859. 亲密字符串

865. 具有所有最深节点的最小子树

868. 二进制间距

873. 最长的斐波那契子序列的长度

884. 两句话中的不常见单词

889. 根据前序和后序遍历构造二叉树

890. 查找和替换模式

893. 特殊等价字符串组

895. 最大频率栈

911. 在线选举

916. 单词子集

923. 三数之和的多种可能

929. 独特的电子邮件地址

930. 和相同的二元子数组

939. 最小面积矩形

953. 验证外星语词典

954. 二倍数对数组

957. N 天后的牢房

961. 在长度 2N 的数组中找出重复 N 次的元素

966. 元音拼写检查器

970. 强整数

974. 和可被 K 整除的子数组

981. 基于时间的键值存储

982. 按位与为零的三元组

987. 二叉树的垂序遍历

992. K 个不同整数的子数组

1001. 网格照明

1002. 查找共用字符

1010. 总持续时间可被 60 整除的歌曲

1015. 可被 K 整除的最小整数

1027. 最长等差数列

1036. 逃离大迷宫

1048. 最长字符串链

105. 从前序与中序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

1072. 按列翻转得到最大值等行数

1074. 元素和为目标值的子矩阵数量

1086. 前五科的均分

1090. 受标签影响的最大值

1100. 长度为 K 的无重复字符子串

1122. 数组的相对排序

1123. 最深叶节点的最近公共祖先

1124. 表现良好的最长时间段

1128. 等价多米诺骨牌对的数量

1133. 最大唯一数

1138. 字母板上的路径

1146. 快照数组

1152. 用户网站访问行为分析

1153. 字符串转化

1160. 拼写单词

1165. 单行键盘

1166. 设计文件系统

1169. 查询无效交易

1170. 比较字符串最小字母出现频次

1171. 从链表中删去总和值为零的连续节点

1172. 餐盘栈

1177. 构建回文串检测

1178. 猜字谜

1181. 前后拼接

1198. 找出所有行中最小公共元素

12. 整数转罗马数字

1202. 交换字符串中的元素

1207. 独一无二的出现次数

1213. 三个有序数组的交集

1218. 最长定差子序列

1224. 最大相等频率

1244. 力扣排行榜

1248. 统计「优美子数组」

1257. 最小公共区域

1258. 近义词句子

126. 单词接龙 II

1261. 在受污染的二叉树中查找元素

127. 单词接龙

1275. 找出井字棋的获胜者

128. 最长连续序列

1282. 用户分组

1296. 划分数组为连续数字的集合

1297. 子串的最大出现次数

13. 罗马数字转整数

1311. 获取你好友已观看的视频

133. 克隆图

1331. 数组序号转换

1338. 数组大小减半

1345. 跳跃游戏 IV

1346. 检查整数及其两倍数是否存在

1347. 制造字母异位词的最小步骤数

1348. 推文计数

1357. 每隔 n 个顾客打折

1358. 包含所有三种字符的子字符串数目

1365. 有多少小于当前数字的数字

1366. 通过投票对团队排名

1370. 上升下降字符串

1371. 每个元音包含偶数次的最长子字符串

138. 复制带随机指针的链表

1386. 安排电影院座位

139. 单词拆分

1394. 找出数组中的幸运数

1396. 设计地铁系统

1399. 统计最大组的数目

140. 单词拆分 II

1400. 构造 K 个回文字符串

141. 环形链表

1410. HTML 实体解析器

1418. 点菜展示表

142. 环形链表 II

1426. 数元素

1429. 第一个唯一数字

1436. 旅行终点站

1442. 形成两个异或相等数组的三元组数目

1443. 收集树上所有苹果的最少时间

146. LRU 缓存

1460. 通过翻转子数组使两个数组相等

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

1477. 找两个和为目标值且不重叠的子数组

1481. 不同整数的最少数目

1485. 克隆含随机指针的二叉树

1487. 保证文件名唯一

1488. 避免洪水泛滥

149. 直线上最多的点数

1490. 克隆 N 叉树

1496. 判断路径是否相交

1497. 检查数组对是否可以被 k 整除

1500. 设计文件分享系统

1506. 找到 N 叉树的根节点

1512. 好数对的数目

1519. 子树中标签相同的节点数

1540. K 次操作转变字符串

1542. 找出最长的超赞子字符串

1546. 和为目标值且不重叠的非空子数组的最大数目

1554. 只有一个不同字符的字符串

1570. 两个稀疏向量的点积

1577. 数的平方等于两数乘积的方法数

159. 至多包含两个不同字符的最长子串

1590. 使数组和能被 P 整除

1593. 拆分字符串使唯一子字符串的数目最大

160. 相交链表

1600. 王位继承顺序

1604. 警告一小时内使用相同员工卡大于等于三次的人

1624. 两个相同字符之间的最长子字符串

1636. 按照频率将数组升序排序

1638. 统计只差一个字符的子串数目

1640. 能否连接形成数组

1650. 二叉树的最近公共祖先 III

1656. 设计有序流

1657. 确定两个字符串是否接近

1658. 将 x 减到 0 的最小操作数

166. 分数到小数

1660. 纠正二叉树

1674. 使数组互补的最少操作次数

1679. K 和数对的最大数目

1684. 统计一致字符串的数目

169. 多数元素

1695. 删除子数组的最大得分

17. 电话号码的字母组合

170. 两数之和 III - 数据结构设计

1711. 大餐计数

1713. 得到子序列的最少操作次数

1726. 同积元组

1737. 满足三条件之一需改变的最少字符数

1740. 找到二叉树中的距离

1742. 盒子中小球的最大数量

1743. 从相邻元素对还原数组

1748. 唯一元素的和

1756. 设计最近使用（MRU）队列

1763. 最长的美好子字符串

1772. 按受欢迎程度排列功能

1775. 通过最少操作次数使数组的和相等

1781. 所有子字符串美丽值之和

1790. 仅执行一次字符串交换能否使两个字符串相等

1794. 统计距离最小的子串对个数

1796. 字符串中第二大的数字

1797. 设计一个验证系统

1804. 实现 Trie （前缀树） II

1805. 字符串中不同整数的数目

1807. 替换字符串中的括号内容

1814. 统计一个数组中好对子的数目

1817. 查找用户活跃分钟数

1832. 判断句子是否为全字母句

1836. 从未排序的链表中移除重复元素

1852. 每个子数组的数字种类数

1857. 有向图中最大颜色值

1865. 找出和为指定值的下标对

1876. 长度为三且各字符不同的子字符串

1893. 检查是否区域内所有整数都被覆盖

1897. 重新分配字符使所有字符串都相等

1906. 查询差绝对值的最小值

1912. 设计电影租借系统

1915. 最美子字符串的数目

1930. 长度为 3 的不同回文子序列

1932. 合并多棵二叉搜索树

1935. 可以输入的最大单词数

1940. 排序数组之间的最长公共子序列

1941. 检查是否所有字符出现次数相同

1948. 删除系统中的重复文件夹

1993. 树上的操作

2001. 可互换矩形的组数

2006. 差的绝对值为 K 的数对数目

2007. 从双倍数组中还原原数组

2013. 检测正方形

2025. 分割数组的最多方案数

2032. 至少在两个数组中出现的值

2034. 股票价格波动

2043. 简易银行系统

205. 同构字符串

2053. 数组中第 K 个独一无二的字符串

2062. 统计字符串中的元音子字符串

2068. 检查两个字符串是否几乎相等

208. 实现 Trie (前缀树)

2080. 区间内查询数字的频率

2083. 求以相同字母开头和结尾的子串总数

2085. 统计出现过一次的公共字符串

2094. 找出 3 位偶数

2099. 找到和最大的长度为 K 的子序列

2103. 环和杆

2107. 分享 K 个糖果后独特口味的数量

2115. 从给定原材料中找到所有可以做出的菜

2121. 相同元素的间隔之和

2122. 还原原数组

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

2133. 检查是否每一行每一列都包含全部整数

2135. 统计追加字母可以获得的单词数

2150. 找出数组中的所有孤独数字

2152. 穿过所有点的所需最少直线数量

2154. 将找到的值乘以 2

2166. 设计位集

2168. 每个数字的频率都相同的独特子字符串的数量

2170. 使数组变成交替数组的最少操作数

2186. 使两字符串互为字母异位词的最少步骤数

2190. 数组中紧跟 key 之后出现最频繁的数字

2196. 根据描述创建二叉树

2201. 统计可以提取的工件

2206. 将数组划分成相等数对

2215. 找出两数组的不同

2225. 找出输掉零场或一场比赛的玩家

2227. 加密解密字符串

2244. 完成所有任务需要的最少轮数

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖