35.贪心算法2
1.按身高排序（easy）
2418. 按身高排序 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
// 1. 创建⼀个下标数组
int n = names.length;
Integer[] index = new Integer[n];
for (int i = 0; i < n; i++)
index[i] = i;
// 2. 对下标数组排序
Arrays.sort(index, (i, j) -> {
return heights[j] - heights[i];
});
// 3. 提取结果
String[] ret = new String[n];
for (int i = 0; i < n; i++) {
ret[i] = names[index[i]];
}
return ret;
}
}2.优势洗牌（田忌赛马）
870. 优势洗牌 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
// 1. 排序
Arrays.sort(nums1);
Integer[] index2 = new Integer[n];
for (int i = 0; i < n; i++)
index2[i] = i;
Arrays.sort(index2, (i, j) -> {
return nums2[i] - nums2[j];
});
// 2. ⽥忌赛⻢
int[] ret = new int[n];
int left = 0, right = n - 1;
for (int x : nums1) {
if (x > nums2[index2[left]]) {
ret[index2[left++]] = x;
} else {
ret[index2[right--]] = x;
}
}
return ret;
}
}3.最长回文串（easy）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int longestPalindrome(String s) {
// 1. 计数 - ⽤数组模拟哈希表
int[] hash = new int[127];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i)]++;
}
// 2. 统计结果
int ret = 0;
for (int x : hash) {
ret += x / 2 * 2;
}
return ret < s.length() ? ret + 1 : ret;
}
}4.增减字符串匹配（easy）
942. 增减字符串匹配 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int[] diStringMatch(String s) {
int n = s.length();
int left = 0, right = n; // ⽤ left，right 标记最⼩值和最⼤值
int[] ret = new int[n + 1];
for (int i = 0; i < n; i++) {
if (s.charAt(i) == 'I') {
ret[i] = left++;
} else {
ret[i] = right--;
}
}
ret[n] = left; // 把最后⼀个数放进去
return ret;
}
}5.分发饼干（easy）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 排序
Arrays.sort(g);
Arrays.sort(s);
// 利⽤双指针找答案
int ret = 0, m = g.length, n = s.length;
for (int i = 0, j = 0; i < m && j < n; i++, j++) {
while (j < n && s[j] < g[i])
j++; // 找饼⼲
if (j < n)
ret++;
}
return ret;
}
}6.最优除法（medium）
553. 最优除法 - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public String optimalDivision(int[] nums) {
int n = nums.length;
StringBuffer ret = new StringBuffer();
// 先处理两个边界情况
if (n == 1) {
return ret.append(nums[0]).toString();
}
if (n == 2) {
return ret.append(nums[0]).append("/").append(nums[1]).toString();
}
ret.append(nums[0]).append("/(").append(nums[1]);
for (int i = 2; i < n; i++) {
ret.append("/").append(nums[i]);
}
ret.append(")");
return ret.toString();
}
}7.跳跃游戏 Ⅱ（medium）
45. 跳跃游戏 II - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int jump(int[] nums) {
int left = 0, right = 0, ret = 0, maxPos = 0, n = nums.length;
while (left <= right) // 以防跳不到 n - 1 的位置
{
if (maxPos >= n - 1) // 判断是否已经能跳到最后⼀个位置
{
return ret;
}
for (int i = left; i <= right; i++) {
// 更新下⼀层的最右端点
maxPos = Math.max(maxPos, nums[i] + i);
}
left = right + 1;
right = maxPos;
ret++;
}
return -1;
}
}
8.跳跃游戏（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public boolean canJump(int[] nums) {
int left = 0, right = 0, maxPos = 0, n = nums.length;
while (left <= right) {
if (maxPos >= n - 1) {
return true;
}
for (int i = left; i <= right; i++) {
maxPos = Math.max(maxPos, nums[i] + i);
}
left = right + 1;
right = maxPos;
}
return false;
}
}9.加油站（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < n; i++) // 依次枚举所有的起点
{
int rest = 0; // 统计净收益
int step = 0;
for (; step < n; step++) // 枚举向后⾛的步数
{
int index = (i + step) % n; // ⾛ step 步之后的下标
rest = rest + gas[index] - cost[index];
if (rest < 0) {
break;
}
}
if (rest >= 0) {
return i;
}
i = i + step; // 优化
}
return -1;
}
}10.单调递增的数字（medium）
. - 力扣（LeetCode）
题目解析
算法原理
代码
class Solution {
public int monotoneIncreasingDigits(int n) {
// 把数字转化成字符串
char[] s = Integer.toString(n).toCharArray();
int i = 0, m = s.length;
// 找第⼀个递减的位置
while (i + 1 < m && s[i] <= s[i + 1])
i++;
if (i == m - 1)
return n; // 特判⼀下特殊情况
// 回退
while (i - 1 >= 0 && s[i] == s[i - 1])
i--;
s[i]--;
for (int j = i + 1; j < m; j++)
s[j] = '9';
return Integer.parseInt(new String(s));
}
}