// 这题的循环条件index和maxIndex两个都变，比较少见
class Solution {
public boolean canJump(int[] nums) {
int N = nums.length;
int maxIndex = nums[0];
int index = 0;
while (index <= maxIndex) { // 注意小于等于
maxIndex = Math.max(maxIndex, index + nums[index]);
if (maxIndex >= N - 1) return true;
index++;
}
return false;
}
}
// 每一步找到下一次最大覆盖范围，也是下一次遍历的终点
class Solution {
public int jump(int[] nums) {
int step = 0;
int farest = 0;
int index = 0;
while (farest < nums.length - 1) {
int tmp = farest;
for (;index <= tmp; index++) {
farest = Math.max(farest, index + nums[index]);
}
step++;
}
return step;
}
}
class Solution {
public int numRabbits(int[] answers) {
if (answers.length == 0) return 0;
Map<Integer, Integer> counts = new HashMap<>();
for (int ans : answers) {
counts.put(ans, counts.getOrDefault(ans, 0) + 1);
}
int res = 0;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
res += (value + key) / (key + 1) * (key + 1); // 向上取整
}
return res;
}
}
// 头尾双指针，贪心策略移动指针
class Solution {
public int maxArea(int[] height) {
int begin = 0;
int end = height.length - 1;
int ans = 0;
while (begin < end) {
int width = end - begin;
if (height[begin] < height[end]) {
ans = Math.max(ans, width * height[begin]);
begin++;
} else {
ans = Math.max(ans, width * height[end]);
end--;
}
}
return ans;
}
}
// 利用了字符串的字典排序
class Solution {
public String largestNumber(int[] nums) {
String[] strings = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strings[i] = String.valueOf(nums[i]);
}
Comparator<String> cmp = (str1, str2) -> {
String s1 = str1 + str2;
String s2 = str2 + str1;
return s2.compareTo(s1);
};
Arrays.sort(strings);
if (strings[0].equals("0")) return "0";
StringBuilder sb = new StringBuilder();
for (String str : strings) {
sb.append(str);
}
return sb.toString();
}
}
// 一次遍历，记录上一次增长区间的长度，下一次减区间的长度大于这个长度时，需要多加1
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int ret = 1;
int inc = 1, dec = 0, pre = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] >= ratings[i - 1]) {
dec = 0;
pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
ret += pre;
inc = pre;
} else {
dec++;
if (dec == inc) {
dec++;
}
ret += dec;
pre = 1;
}
}
return ret;
}
}
// 分別满足左规则和有规则
class Solution0 {
public int candy(int[] ratings) {
int N = ratings.length;
int[] candies = new int[N];
Arrays.fill(candies, 1);
// 满足左规则
for (int i = 1; i < N; i++) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
int sum = 0;
for (int i = N - 2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) {
candies[i] = Math.max(candies[i], candies[i+1] + 1);
}
sum += candies[i];
}
return sum + candies[N-1];
}
}
// lo 和 hi表示取值的区间，维护好这两个变量
class Solution {
public boolean checkValidString(String s) {
int lo = 0;
int hi = 0;
for (char c : s.toCharArray()) {
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
if (hi < 0) return false;
if (lo < 0) lo = 0;
}
return lo == 0;
}
}
// 字符串字典排序，类似与最大数
class Solution {
public String minNumber(int[] nums) {
int n = nums.length;
String[] strings = new String[n];
for (int i = 0; i < n; i++) {
strings[i] = String.valueOf(nums[i]);
}
Comparator<String> cmp = (x, y) -> {
String s1 = x + y;
String s2 = y + x;
return s1.compareTo(s2);
};
Arrays.sort(strings, cmp);
StringBuilder sb = new StringBuilder();
for (int index = 0; index < n; index++) {
sb.append(strings[index]);
}
return sb.toString();
}
}
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int res = 0;
int total = 0;
int curSum = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
curSum += diff;
if (curSum < 0) {
res = i + 1;
curSum = 0;
}
}
if (total < 0) return -1;
return res;
}
}
// 二分查找，一次过
class Solution {
public int splitArray(int[] nums, int m) {
int left = 0;
int right = 0;
for (int num : nums) {
right += num;
if (left < num) {
left = num;
}
}
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = count(nums, mid);
if (cnt <= m) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public int count(int[] nums, int target) {
int cnt = 1;
int sum = 0;
for (int num : nums) {
if (sum + num > target) {
cnt++;
sum = num;
} else {
sum += num;
}
}
return cnt;
}
}
// 和410题一样
class Solution {
public int shipWithinDays(int[] weights, int days) {
int left = 0;
int right = 0;
for (int num : weights) {
right += num;
if (left < num) {
left = num;
}
}
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = count(weights, mid);
if (cnt <= days) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public int count(int[] nums, int target) {
int cnt = 1;
int sum = 0;
for (int num : nums) {
if (sum + num > target) {
cnt++;
sum = num;
} else {
sum += num;
}
}
return cnt;
}
}
// 利润等于每次加上上升时候的差值
class Solution {
public int maxProfit(int[] prices) {
int sum = 0;
for (int i = 0; i < prices.length - 1; i++) {
sum += Math.max(prices[i+1] - prices[i], 0);
}
return sum;
}
}
// 单调栈即可
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new ArrayDeque<>();
for (char c : num.toCharArray()) {
while (!deque.isEmpty() && k > 0 && deque.peekLast() > c) {
deque.pollLast();
k--;
}
deque.offer(c);
}
while (!deque.isEmpty() && k > 0) {
deque.pollLast();
k--;
}
StringBuilder sb = new StringBuilder();
boolean flag = true;
while (!deque.isEmpty()) {
if (deque.peekFirst() == '0' && flag) {
deque.poll();
continue;
}
flag = false;
sb.append(deque.poll());
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
// 用数组记录每个字符的最远位置，然后遍历，记录当前遍历过字符的最远字符下标
class Solution {
public List<Integer> partitionLabels(String s) {
int n = s.length();
int[] position = new int[26];
for (int i = 0; i < n; i++) {
int index = s.charAt(i) - 'a';
position[index] = i;
}
int len = 0;
int maxPosition = 0;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
len++;
int index = s.charAt(i) - 'a';
if (position[index] > maxPosition) maxPosition = position[index];
if (i == maxPosition) {
res.add(len);
len = 0;
}
}
return res;
}
}
// 模拟交换即可，图论可用来解释
class Solution {
public int minSwapsCouples(int[] row) {
int n = row.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(row[i], i);
}
int res = 0;
for (int i = 0; i < n; i += 2) {
int cp = row[i] ^ 1;
if (row[i + 1] != cp) {
res++;
int index = map.get(cp);
row[index] = row[i + 1];
map.put(row[index], index);
}
}
return res;
}
}
// 统计字符数量
class Solution {
public int longestPalindrome(String s) {
int[] counts = new int[128];
for (char c : s.toCharArray()) {
counts[c]++;
}
int sum = 0;
for (int num : counts) {
sum += num / 2 * 2;
}
if (sum < s.length()) sum++;
return sum;
}
}
// 单调栈 + flag数组
class Solution {
public String removeDuplicateLetters(String s) {
int[] counts = new int[26];
boolean[] flag = new boolean[26];
for (char c : s.toCharArray()) counts[c - 'a']++;
Deque<Character> deque = new ArrayDeque<>();
for (char c : s.toCharArray()) {
int index = c - 'a';
if (flag[index]) {
counts[index]--;
continue;
}
while (!deque.isEmpty() && deque.peekLast() > c) {
if (counts[deque.peekLast() - 'a'] > 1) {
char out = deque.pollLast();
flag[out - 'a'] = false;
counts[out - 'a']--;
} else {
break;
}
}
flag[index] = true;
deque.offer(c);
}
StringBuilder sb = new StringBuilder();
while (!deque.isEmpty()) {
sb.append(deque.poll());
}
return sb.toString();
}
}
class Solution {
public boolean validPalindrome(String s) {
int lo = -1;
int hi = s.length() ;
while (++lo < --hi) {
if (s.charAt(lo) != s.charAt(hi)) return validPalindrome(s, lo - 1, hi) || validPalindrome(s, lo, hi + 1);
}
return true;
}
public boolean validPalindrome(String s, int left, int right) {
while (++left < --right) {
if (s.charAt(left) != s.charAt(right)) return false;
}
return true;
}
}
// 找到右边比左边第一个要大的值，交换即可
class Solution {
public int maximumSwap(int num) {
char[] digits = String.valueOf(num).toCharArray();
int[] position = new int[10];
for (int i = 0; i < digits.length; i++) {
position[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.length; i++) {
int cur = digits[i] - '0';
for (int k = 9; k > cur; k--) {
if (position[k] > i) {
char tmp = digits[i];
digits[i] = (char)('0' + k); // 这里改成digits[position[k]]也行
digits[position[k]] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}
}
// 左区间值排序
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Comparator<int[]> cmp = (x, y) -> {
return x[0] - y[0];
};
Arrays.sort(intervals, cmp);
int n = intervals.length;
int res = 0;
int left = intervals[n - 1][0];
for (int i = n - 2; i >= 0; i--) {
if (intervals[i][1] > left) {
res++;
} else {
left = intervals[i][0];
}
}
return res;
}
}
// 右区间值排序
class Solution0 {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> {
if (a[1] == b[1]) return 0;
else if (a[1] < b[1]) return -1;
else return 1;
});
int right = intervals[0][1];
int cnt = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < right) {
cnt++;
} else {
right = intervals[i][1];
}
}
return cnt;
}
}
// 左顺序，右降序，没插入个空位就是比现在插入的要大的
class Solution {
public int[][] reconstructQueue(int[][] people) {
Comparator<int[]> cmp = (x, y) -> {
return x[0] != y[0] ? x[0] - y[0] : y[1] - x[1];
};
Arrays.sort(people, cmp);
int[][] res = new int[people.length][];
for (int[] arr : people) {
int cnt = arr[1];
for (int i = 0; i < people.length && cnt >= 0; i++) {
if (res[i] == null) {
cnt--;
}
if (cnt == -1) {
res[i] = arr;
}
}
}
return res;
}
}
// 右降序，左顺新，插入法
class Solution0 {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
ArrayList<int[]> link = new ArrayList<>();
for (int[] arr : people) {
if (arr[1] < link.size()) {
link.add(arr[1], arr);
} else {
link.add(arr);
}
}
return link.toArray(new int[people.length][]);
}
}
// 桶思想 + 贪心
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] counts = new int[26];
for (char c : tasks) {
counts[c - 'A']++;
}
Arrays.sort(counts);
int buckets = counts[25];
int maxCount = 1;
for (int i = 25; i >= 1; i--) {
if (counts[i] == counts[i - 1]) {
maxCount++;
} else {
break;
}
}
return Math.max(tasks.length, (buckets - 1) * (n + 1) + maxCount);
}
}
// 选排序后面用双指针，贪心策略为记录之前以一次指针的位置
class Solution {
public int triangleNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n - 2; i++) {
int start = i + 2;
for (int j = i + 1; j < n - 1 && nums[i] != 0; j++) {
while (start < n) {
if (nums[start] >= nums[i] + nums[j]) break;
start++;
}
res += start - j - 1;
}
}
return res;
}
}
// 先排序然后用二分法
class Solution0 {
public int triangleNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int index = binarySearch(nums, j + 1, n, nums[i] + nums[j]);
res += index - j - 1;
}
}
return res;
}
// 找小于x的最大值
public int binarySearch(int[] nums, int left, int right, int x) {
while (left < right) {
int middle = left + (right - left) / 2;
if (x <= nums[middle]) right = middle;
else left = middle + 1;
}
return left;
}
}
// 暴力能过90%用例左右
class Solution1 {
public int triangleNumber(int[] nums) {
int n = nums.length;
int res = 0;
for (int i = 0; i < n - 2; i++) {
int a = nums[i];
for (int j = i + 1; j < n - 1;j++) {
int b = nums[j];
for (int k = j + 1; k < n;k++ ) {
int c = nums[k];
if (a + b > c && Math.abs(a - b) < c) {
res++;
}
}
}
}
return res;
}
}
1353. 最多可以参加的会议数目，优先队列
1388. 3n块披萨，优先队列
// 贪心，模拟，注意边界时的处理即可
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int cnt = 0;
for (int i = 0; i < flowerbed.length && cnt < n; i++) {
if (flowerbed[i] == 1) continue;
int pre = i == 0 ? 0 : flowerbed[i-1];
int next = i == flowerbed.length - 1 ? 0 : flowerbed[i+1];
if (pre == 0 && next == 0) {
cnt++;
flowerbed[i] = 1;
}
}
return cnt >= n;
}
}
253. 会议室II，优先队列
// remainder[i] 表示除三余数为i的当前最大和
class Solution {
public int maxSumDivThree(int[] nums) {
int[] remainder = new int[3];
for (int num : nums) {
int a = remainder[0] + num;
int b = remainder[1] + num;
int c = remainder[2] + num;
remainder[a % 3] = Math.max(remainder[a % 3], a);
remainder[b % 3] = Math.max(remainder[b % 3], b);
remainder[c % 3] = Math.max(remainder[c % 3], c);
}
return remainder[0];
}
}
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
for (int i = 0, j = 0; i < g.length && j < s.length; j++) { // 这个是遍历饼干，不是胃口
if (s[j] >= g[i]) {
i++;
res++;
}
}
return res;
}
}
// 贪心，先排数量最多的字符，排在偶数下标，然后在排其他，注意排字符时的细节处理
class Solution {
public String reorganizeString(String s) {
int n = s.length();
int[] counts = new int[26];
int maxCnt = 0;
int maxCntIndex = 0;
for (char c : s.toCharArray()) {
counts[c - 'a']++;
if(counts[c - 'a'] > maxCnt) {
maxCnt = counts[c - 'a'];
maxCntIndex = c - 'a';
}
if (maxCnt > (n + 1) / 2) return "";
}
int index = 0;
char[] res = new char[n];
for (int i = 0; i < maxCnt; i++) {
res[index] = (char)(maxCntIndex + 'a');
index += 2;
}
for (int i = 0; i < 26; i++) {
while (counts[i]-- > 0 && i != maxCntIndex) {
if (index >= n) {
index = 1;
}
res[index] = (char)(i + 'a');
index += 2;
}
}
return new String(res);
}
}
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
ten++;
if (five > 0) five--;
else return false;
} else {
if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}
class Solution {
public int wiggleMaxLength(int[] nums) {
int pre = 0;
int res = 1;
int n = nums.length;
for (int i = 1; i < n; i++) {
int cur = nums[i] - nums[i-1];
if ((pre >= 0 && cur < 0) || (pre <= 0 && cur > 0)) {
res++;
pre = cur; // 注意这里放里面，防止单调不增或者单调不减的情况
}
}
return res;
}
}
// 对右端进行排序
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (x, y) -> {
return x[1] > y[1] ? 1 : -1; // 排序不能用x[1] - y[1], 否则可能整数溢出
});
int right = points[0][1];
int res = 1;
for (int[] point : points) {
if (point[0] > right) {
res++;
right = point[1];
}
}
return res;
}
}
330. 按要求补齐数组，困难遗留
// 维护好buyPrice
class Solution {
public int maxProfit(int[] prices, int fee) {
int buyPrice = prices[0] + fee;
int profit = 0;
for (int price : prices) {
if (buyPrice > price + fee) {
buyPrice = price + fee;
} else if (buyPrice < price) {
profit += price - buyPrice;
buyPrice = price;
}
}
return profit;
}
}
// 一次遍历
class Solution {
public int findUnsortedSubarray(int[] nums) {
int first = -1;
int last = -1;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < max) {
last = i;
} else {
max = nums[i];
}
int tmp = nums[nums.length - i - 1];
if (tmp > min) {
first = nums.length - i - 1;
} else {
min = tmp;
}
}
return first == last ? 0 : last - first + 1;
}
}
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 1; i >= 2; i--) {
if (nums[i - 1] + nums[i - 2] > nums[i]) {
return nums[i] + nums[i - 1] + nums[i - 2];
}
}
return 0;
}
}
871. 最低加油次数，困难遗留
// 确定峰谷峰顺序，贪心交换即可
class Solution {
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int pre = nums[i - 1];
int cur = nums[i];
if (i % 2 == 0) {
if (cur < pre) {
nums[i] = pre;
nums[i - 1] = cur;
}
} else {
if (cur > pre) {
nums[i] = pre;
nums[i - 1] = cur;
}
}
}
}
}
// 同581题
class Solution {
public int[] subSort(int[] array) {
int first = -1;
int last = -1;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
if (array[i] < max) {
last = i;
} else {
max = array[i];
}
int tmp = array[array.length - i - 1];
if (tmp > min) {
first = array.length - i - 1;
} else {
min = tmp;
}
}
return new int[] {first, last};
}
}
LCP15. 游乐园的迷宫,困难，遗留
class Solution {
public int minCostToMoveChips(int[] position) {
int odd = 0;
int even = 0;
for (int pos : position) {
if ((pos & 1) == 0) {
odd++;
} else {
even++;
}
}
return Math.min(odd, even);
}
}
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}
}
