力扣刷题(复习版)

文章目录

- 题目：最大重复子字符串
- - 题解
- 题目：面试题 16.07. 最大数值
- - 题解
- 题目：最大字符串配对数目
- - 题解
- 题目：字符串中第二大的数字
- - 题解
- 题目：统计最大组的数目
- - 题解
- 题目：删除每行中的最大值
- - 题解
- 总结

题目：最大重复子字符串

原题链接：最大重复子字符串
在这里插入图片描述

题解

方法：暴力延长word的重复次数并比较,用contains()函数

 public static int maxRepeating(String sequence, String word) {int maxRepeat = 0;StringBuilder repeatedWord = new StringBuilder(word);// 循环尝试增加word的重复次数，直到不再是子字符串while (sequence.contains(repeatedWord)) {maxRepeat++;repeatedWord.append(word);}return maxRepeat;}

题目：面试题 16.07. 最大数值

原题链接：面试题 16.07. 最大数值

题解

方法：通过计算两个整数差值的符号位

表达式 a * (1 - sign) + b * sign 能够实现两个值的二选一效果

 public int maximum(int a, int b) {long diff = (long)a - (long)b;long sign = (diff >>> 63) & 1;return (int)(a * (1 - sign) + b * sign);}

题目：最大字符串配对数目

原题链接：最大字符串配对数目
在这里插入图片描述

在这里插入图片描述

题解

public static int maximumNumberOfStringPairs(String[] words) {HashSet<String> set = new HashSet<>();int count = 0;for (String word : words) {String reversed = "" + word.charAt(1) + word.charAt(0);// 检查反转字符串是否已经存在于 set 中if (set.contains(reversed)) {count++;}set.add(word);}return count;}

题目：字符串中第二大的数字

原题链接：字符串中第二大的数字
在这里插入图片描述

题解

方法1：

 public static int secondHighest(String s) {Set<Integer> set = new HashSet<>();for (char c : s.toCharArray()) {if (Character.isDigit(c)) {set.add(c - '0');}}int firstMax = -1;int secondMax = -1;for (Integer i : set) {if (i > firstMax) {secondMax = firstMax;firstMax = i;} else if (i > secondMax && i < firstMax) {secondMax = i;}}return secondMax;}

方法2：
先找到最大值删除，如果set不为空，继续寻找最大值(答案)

 public static int secondHighest11(String s) {Set<Integer> set = new HashSet<>();for (char c : s.toCharArray()) {if (Character.isDigit(c)) {set.add(c - '0');}}int maxValue = -1;for (Integer i : set) {if (i > maxValue) {maxValue = i;}}set.remove(maxValue);if (set.size() == 0) return -1;maxValue = -1;for (Integer i : set) {if (i > maxValue) {maxValue = i;}}return maxValue;}

题目：统计最大组的数目

原题链接：统计最大组的数目
在这里插入图片描述

题解

方法：利用 map 将相同的数位和作为键(哈希表)

public static int sumDigit(int i) {int res = 0;while (i > 0) {res += i % 10;i /= 10;}return res;
}public static int countLargestGroup(int n) {int maxCnt = 0;HashMap<Integer, Integer> map = new HashMap<>();for (int i = 1; i <= n; i++) {int sum = sumDigit(i);int count = map.getOrDefault(sum, 0) + 1;map.put(sum, count);maxCnt = Math.max(maxCnt, count);}int res = 0;for (Integer value : map.values()) {if (value == maxCnt) {res++;}}return res;
}

题目：删除每行中的最大值

原题链接：删除每行中的最大值
在这里插入图片描述

题解

方法：通过逐列查找每一行未使用的最大值，并将其标记为已使用，然后将每列的最大值累加得到最终结果。主要利用 used 数组来跟踪已经处理过的元素。

public boolean[][] used = new boolean[51][51];// 找到一行中最最大的元素  并标记已处理public int findMaxByRow(int[][] grid, int row) {int maxValue = -1;int maxIndex = -1;for (int i = 0; i < grid[0].length; i++) {if (!used[row][i] && grid[row][i] > maxValue) {maxValue = grid[row][i];maxIndex = i;}}if (maxIndex != -1) {used[row][maxIndex] = true;}return maxValue;}public int deleteGreatestValue(int[][] grid) {int res = 0;for (int j = 0; j < grid[0].length; j++) { int maxValue = -1;for (int i = 0; i < grid.length; i++) { int maxByRow = findMaxByRow(grid, i);if (maxValue < maxByRow)maxValue = maxByRow;}res += maxValue;}return res;}