目录
1. 整数替换
1.1 算法原理
1.1.1 解法一: 递归 + 记忆化搜索
返回值: 数值 n 转为 1 的最小操作数
函数体:
- if(n == 偶) return dfs(n / 2) + 1;
- if(n == 奇) return min(dfs(n - 1), dfs(n + 1)) + 1;
记忆化搜索(减少重复递归带来的时间消耗):
- 使用 memo 记录计算过的值(Map 创建)
1.1.2 解法二: 贪心
解法二: 贪心
将 n 以二进制的形式看待:
- n 为偶数: 除2
- n 为奇数: 分类讨论
1.2 算法代码
class Solution {
/**
* 贪心
* @param n_
* @return
*/
public int integerReplacement(int n_) {
long n = n_;
int ret = 0;
while(n != 1) {
if(n == 3) return ret += 2;// 特殊情况
if(n % 2 == 0) n /= 2;
else {
// 贪心
long val = n % 4;
if(val == 3) n += 1;
else n -= 1;
}
ret++;
}
return ret;
}
/**
* 递归 + 记忆化搜索
*/
Map<Long, Integer> memo = new HashMap<>();
public int integerReplacement1(int n) {
return dfs(n);
}
public int dfs(long n) {
if(memo.containsKey(n)) return memo.get(n);
if(n == 1) return 0;
if(n % 2 == 0) {
memo.put(n, dfs(n / 2) + 1);
return memo.get(n);
}
else {
memo.put(n, Math.min(dfs(n + 1), dfs(n - 1)) + 1);
return memo.get(n);
}
}
}2. 俄罗斯套娃信封问题
2.1 算法原理
2.1.1 解法一: 动态规划
预处理: 按照左端点进行排序
问题转换: 最长套娃序列的长度 => 最长递增递增子序列
- 状态表示dp[i]: 以 i 位置的信封为结尾的所有套娃序列中, 最长套娃序列的长度
- 状态转移方程: dp[i] = max(dp[j] + 1) j < i && e[j][0] > e[i][0] && e[j][1] > e[i][1]
- 初始化: Arrays.fill(dp, 1);
- 建表顺序: 从左往右
- 返回值: dp 表中的最大值
2.1.2 解法二: 重写排序规则 + 贪心 + 二分
问题转换: 最长递增子序列
- 重写排序规则:
1. 当左端点不同时, 左端点从小到大进行排序
2. 当左端点相同时, 右端点从大到小进行排序
- 贪心
<最长递增子序列> (根据右端点的值, 寻找最长递增子序列)
- 二分
<最长递增子序列> (二分寻找插入位置 => O(log N))
2.2 算法代码
class Solution {
/**
* 重写排序规则 + 贪心 + 二分
* @param envelopes
* @return
*/
public int maxEnvelopes(int[][] envelopes) {
// 重写排序规则
Arrays.sort(envelopes, (a, b) -> {
// 左端点不同时, 按照左端点升序排序
if(a[0] != b[0]) return a[0] - b[0];
// 左端点相同时, 按照右端点逆序排序
else return b[1] - a[1];
});
int n = envelopes.length;
List<Integer> list = new ArrayList<>();
list.add(envelopes[0][1]);
for(int i = 1; i < n; i++) {
// 比最后一个数还大, 直接插入
if(envelopes[i][1] > list.get(list.size() - 1)) {
list.add(envelopes[i][1]);
continue;
}
int left = 0, right = list.size() - 1;
// 二分插入 + 贪心
while(left < right) {
int mid = left + (right - left) / 2;
// 贪心
if(list.get(mid) < envelopes[i][1]) left = mid + 1;
else right = mid;
}
list.set(left, envelopes[i][1]);
}
return list.size();
}
/**
* 动态规划 O(N^2) 超时
* @param envelopes
* @return
*/
public int maxEnvelopes1(int[][] envelopes) {
// 1. 排序(左端点)
Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
int n = envelopes.length, ret = 1;
int[] dp = new int[n];
// 初始化
Arrays.fill(dp, 1);
for(int i = 1; i < n; i++) {
int a = envelopes[i][0], b = envelopes[i][1];
for(int j = i - 1; j >= 0; j--) {
if(a > envelopes[j][0] && b > envelopes[j][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
}3. 可被三整除的最大和
3.1 算法原理
解法一: 正难则反 + 贪心
正难则反: 求出所有数的累加和(sum), 删除一些尽可能小的数, 使得 sum % 3 == 0
贪心:
分类讨论:
x : % 3 == 1 的数
y : % 3 == 2 的数
- 情况1 : sum % 3 == 0 直接返回 sum 即可.
- 情况2 : sum % 3 == 1, 则 sum 可由以下两种情况构成:
1. 由 x1 和 (sum - x1) 构成, 并且 x1 % 3 == 1, (sum - x1) % 3 == 0
2. 由 y1, y2 和 (sum - y1 - y2) 构成, 并且 y % 3 == 2((y1 + y2) % 3 == 1), (sum - y1 - y2) % 3 == 0
返回 Math.max(sum - x1, sum - y1 - y2)
- 情况3 : sum % 3 == 2, 则 sum 可由以下两种情况构成:
1. 由 y1 和 (sum - y1) 构成, 并且 y1 % 3 == 2, (sum - y1) % 3 == 0
2. 由 x1, x2 和 (sum - x1 - x2) 构成, 并且 x % 3 == 1((x1 + x2) % 3 == 2), (sum - x1 - x2) % 3 == 0
返回 Math.max(sum - y1, sum - x1 - x2)
3.2 算法代码
class Solution {
public int maxSumDivThree(int[] nums) {
// 防溢出
int INF = 0x3f3f3f3f;
int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;
for(int x : nums) {
sum += x;
if(x % 3 == 1) {
if(x < x1) {
x2 = x1;
x1 = x;
}else if(x < x2) {
x2 = x;
}
}else if(x % 3 == 2){
if(x < y1) {
y2 = y1;
y1 = x;
}else if(x < y2) {
y2 = x;
}
}
}
if(sum % 3 == 0) return sum;
else if(sum % 3 == 1) {
return Math.max(sum - x1, sum - y1 - y2);
}else {
return Math.max(sum - y1, sum - x1 - x2);
}
}
}4. 距离相等的条形码
4.1 算法原理
贪心 + 模拟
贪心策略: 对同一批数, 隔一个位置放一个
先处理出现次数最多的那个数.
4.2 算法代码
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
Map<Integer, Integer> hash = new HashMap<>();
// 记录出现最多的数
int maxVal = 0, maxCnt = 0;
for(int x : barcodes) {
hash.put(x, hash.getOrDefault(x, 0) + 1);
int cnt = hash.get(x);
if(cnt > maxCnt) {
maxCnt = cnt;
maxVal = x;
}
}
// 处理出现最多的数
int index = 0;
for(int i = 0; i < maxCnt; i++) {
barcodes[index] = maxVal;
index += 2;
}
// 处理剩余的数
hash.remove(maxVal);
for(int x : hash.keySet()) {
int cnt = hash.get(x);
while(cnt-- != 0) {
if(index >= barcodes.length) index = 1;
barcodes[index] = x;
index += 2;
}
}
return barcodes;
}
}5. 重构字符串
5.1 算法原理
贪心.
本题思想与上题一致, 唯一需要多处理的一点是: 结果可能不存在.
5.2 算法代码
class Solution {
public String reorganizeString(String s) {
char maxVal = ' ';
int maxCount = 0, n = s.length();
int[] hash = new int[26];
for(int i = 0; i < n; i++) {
char ch = s.charAt(i);
hash[ch - 'a']++;
if(hash[ch - 'a'] > maxCount) {
maxCount = hash[ch - 'a'];
maxVal = ch;
}
}
// 处理出现次数最多的字符
int index = 0;
char[] ret = new char[n];
while(maxCount-- != 0) {
if(index >= n) return "";
ret[index] = maxVal;
index += 2;
}
// 处理剩余字符
hash[maxVal - 'a'] = 0;
for(int i = 0; i < 26; i++) {
char ch = (char)('a' + i);
while(hash[i]-- != 0) {
if(index >= n) index = 1;
ret[index] = ch;
index += 2;
}
}
return new String(ret);
}
public String reorganizeString1(String s) {
Map<Character, Integer> hash = new HashMap<>();
char maxVal = 'x';
int maxCount = 0, n = s.length();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
hash.put(ch, hash.getOrDefault(ch, 0) + 1);
if(hash.get(ch) > maxCount) {
maxCount = hash.get(ch);
maxVal = ch;
}
}
int index = 0;
char[] ret = new char[n];
while(maxCount-- != 0) {
if(index >= n) return "";
ret[index] = maxVal;
index += 2;
}
hash.remove(maxVal);
for(char ch : hash.keySet()) {
int count = hash.get(ch);
while(count-- != 0) {
if(index >= n) index = 1;
ret[index] = ch;
index += 2;
}
}
return new String(ret);
}
}END
标签：index,专题,return,int,sum,算法,envelopes,hash,贪心 From： https://blog.csdn.net/2401_83595513/article/details/144113587