import java.util.Arrays;
// 2037. Minimum Number of Moves to Seat Everyone
class Solution {
public int minMovesToSeat(int[] seats, int[] students) {
Arrays.sort(seats);
Arrays.sort(students);
int n = seats.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.abs(seats[i] - students[i]);
}
return ans;
}
}
学习笔记： 这是一道简单的排序、贪心的题目。 排一下从小到大，然后减一下差加总就好了。
import java.util.TreeSet;
// 0855. Exam Room
class ExamRoom {
int capacity;
TreeSet<Integer> seats;
public ExamRoom(int n) {
this.capacity = n;
this.seats = new TreeSet<>();
}
public int seat() {
int seatNumber = 0;
if (seats.size() > 0) {
Integer prev = null;
int distance = seats.first();
for (Integer seat : seats) {
if (prev != null) {
int d = (seat - prev) / 2;
if (distance < d) {
distance = d;
seatNumber = prev + distance;
}
}
prev = seat;
}
if (distance < capacity - 1 - seats.last()) {
seatNumber = capacity - 1;
}
}
seats.add(seatNumber);
return seatNumber;
}
public void leave(int p) {
seats.remove(p);
}
}
学习笔记： 这是一道TreeSet的应用题，设计题。 其实就是该用这个数据结构，知道了之后就差需要进行分类讨论每次把新的学生分配到几号座位这个问题了。 第一个位置、最后一个位置，很容易会被忽视，一定要特殊处理。
import java.util.*;
// 2032. Two Out of Three
class Solution {
public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
Map<Integer, Integer> hashMap = new HashMap<>();
for (int num : nums1) {
hashMap.put(num, 1);
}
for (int num : nums2) {
hashMap.put(num, hashMap.getOrDefault(num, 0) | 2);
}
for (int num : nums3) {
hashMap.put(num, hashMap.getOrDefault(num, 0) | 4);
}
List<Integer> ans = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
Integer key = entry.getKey();
Integer value = entry.getValue();
if ((value & (value - 1)) != 0) {
ans.add(key);
}
}
return ans;
}
}
学习笔记： 这是一道非常简单，又考验基本功的好题。 用到了哈希表、位运算。 首先位运算分别或上1和2和4，然后判断一下结果里面有没有多个1。
// 1750. Minimum Length of String After Deleting Similar Ends
class Solution {
public int minimumLength(String s) {
int i = 0;
int j = s.length() - 1;
while (i < j) {
char mark = s.charAt(i);
if (s.charAt(j) != mark) {
break;
}
while (j >= 0 && s.charAt(j) == mark) {
--j;
}
while (i <= j && s.charAt(i) == mark) {
++i;
}
}
return j - i + 1;
}
}
学习笔记： 这是一道贪心算法的题，和昨天一样。 两边字母一样，就可以消除两边全部的，用双指针往内推，最后求出两个指针的距离。
// 2027. Minimum Moves to Convert String
class Solution {
public int minimumMoves(String s) {
char[] charArray = s.toCharArray();
int len = charArray.length;
int ans = 0;
for (int i = 0; i < len; ) {
if (charArray[i] == 'X') {
i += 3;
++ans;
} else {
++i;
}
}
return ans;
}
}
学习笔记： 这是一道简单题，用了贪心算法。 遇到了X那就直接忽视后面两位了，然后遍历一遍解决。
// 1759. Count Number of Homogenous Substrings
class Solution {
public int countHomogenous(String s) {
final long MOD = 1000000007L;
char[] charArray = s.toCharArray();
long cnt = 1;
long ans = 0;
for (int i = 1; i < charArray.length; ++i) {
if (charArray[i] == charArray[i - 1]) {
++cnt;
} else {
ans += (1 + cnt) * cnt / 2;
cnt = 1;
}
}
ans += (1 + cnt) * cnt / 2;
return (int) (ans % MOD);
}
}
学习笔记： 这道题其实不复杂，考察的就是连续几个相同字母的组合。 用到了小学的等差数列求和公式，首相加末项的和乘以项数除以2。
// 1739. Building Boxes
class Solution {
public int minimumBoxes(int n) {
int ans = 0;
for (int i = 1, j = 1; n >= j; ++i, j += i) {
ans = j;
n -= j;
}
for (int i = 1; n > 0; ++i) {
n -= i;
++ans;
}
return ans;
}
}
学习笔记： 这是一道困难题，要把上面的箱子多放点，下面箱子少放点。 主要还是数学算法，对于编程来说倒是没啥。 我其实不是特别喜欢这种数学算法的题目，没有编程上的美感。
// 1754. Largest Merge Of Two Strings
class Solution {
public String largestMerge(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int i = 0;
int j = 0;
StringBuilder sb = new StringBuilder();
while (i < m && j < n) {
int ct = word1.substring(i).compareTo(word2.substring(j));
if (ct > 0) {
sb.append(word1.charAt(i));
++i;
} else {
sb.append(word2.charAt(j));
++j;
}
}
sb.append(word1.substring(i));
sb.append(word2.substring(j));
return sb.toString();
}
}
学习笔记： 这道中等题真是很恶心人，明明看上去逻辑很简单，但是各种边界判断重复情况都会有。 最后看到了有人使用了substring和compareTo这两个函数， 不但很简单，时间也不慢，感觉自己之前一个小时都白写了。 所以遇事不能转牛角尖，有好方法应该直接调用。
// 2011. Final Value of Variable After Performing Operations
class Solution {
public int finalValueAfterOperations(String[] operations) {
int ans = 0;
for (String operation : operations) {
if (operation.charAt(1) == '+') {
++ans;
} else {
--ans;
}
}
return ans;
}
}
学习笔记： 困难题之后果然就是简单题，这道题真是一道水题。 完全不用考虑++c和c++的区别，就看中间这一位是啥。
// 1799. Maximize Score After N Operations
class Solution {
public int maxScore(int[] nums) {
int len = nums.length;
int[] memo = new int[1 << len];
return helper(nums, len, 1, 0, memo);
}
private int helper(int[] nums, int len, int operations, int mask, int[] memo) {
if (operations > (len / 2)) return 0;
if (memo[mask] != 0) return memo[mask];
int ret = 0;
for (int i = 0; i < len; ++i) {
if ((mask & (1 << i)) != 0) continue;
for (int j = i + 1; j < len; ++j) {
if ((mask & (1 << j)) != 0) continue;
int newMask = mask | (1 << i) | (1 << j);
int score = operations * gcd(nums[i], nums[j]);
ret = Math.max(ret, score + helper(nums, len, operations + 1, newMask, memo));
}
}
memo[mask] = ret;
return ret;
}
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
学习笔记： 这是一道苦难的题目，用到了动态规划或者记忆化搜索，还有状态压缩位运算实现。 8个数字尝试两两进行配对，那就算是记忆化搜索，也还是得用动态规划的思想来反向递推。 这道题做起来很困难，所以以后有空还是得回顾。