【Leetcode Sheet】Weekly Practice 22

Leetcode Test

1349 参加考试的最大学生数(12.26)

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

学生必须坐在状况良好的座位上。

提示：

• seats 只包含字符 '.' 和``'#'
• m == seats.length
• n == seats[i].length
• 1 <= m <= 8
• 1 <= n <= 8

【记忆化搜索】1349. 参加考试的最大学生数 - 力扣（LeetCode）

class Solution {
public:int maxStudents(vector<vector<char>>& seats) {int m = seats.size(), n = seats[0].size();unordered_map<int, int> memo;auto isSingleRowCompliant = [&](int status, int row) -> bool {for (int j = 0; j < n; j++) {if ((status >> j) & 1) {if (seats[row][j] == '#') {return false;}if (j > 0 && ((status >> (j - 1)) & 1)) {return false;}}}return true;};auto isCrossRowsCompliant = [&](int status, int upperRowStatus) -> bool {for (int j = 0; j < n; j++) {if ((status >> j) & 1) {if (j > 0 && ((upperRowStatus >> (j - 1)) & 1)) {return false;}if (j < n - 1 && ((upperRowStatus >> (j + 1)) & 1)) {return false;}}}return true;};function<int(int, int)> dp = [&](int row, int status) -> int {int key = (row << n) + status;if (!memo.count(key)) {if (!isSingleRowCompliant(status, row)) {memo[key] = INT_MIN;return INT_MIN;}int students = __builtin_popcount(status);if (row == 0) {memo[key] = students;return students;}int mx = 0;for (int upperRowStatus = 0; upperRowStatus < 1 << n; upperRowStatus++) {if (isCrossRowsCompliant(status, upperRowStatus)) {mx = max(mx, dp(row - 1, upperRowStatus));}}memo[key] = students + mx;}return memo[key];};int mx = 0;for (int i = 0; i < (1 << n); i++) {mx = max(mx, dp(m - 1, i));}return mx;}
};

2660 保龄球游戏的获胜者(12.27)

给你两个下标从 0 开始的整数数组 player1 和 player2 ，分别表示玩家 1 和玩家 2 击中的瓶数。

保龄球比赛由 n 轮组成，每轮的瓶数恰好为 10 。

假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：

• 如果玩家在该轮的前两轮的任何一轮中击中了 10 个瓶子，则为 2xi 。
• 否则，为 xi 。

玩家的得分是其 n 轮价值的总和。

返回

• 如果玩家 1 的得分高于玩家 2 的得分，则为 1 ；
• 如果玩家 2 的得分高于玩家 1 的得分，则为 2 ；
• 如果平局，则为 0 。

提示：

• n == player1.length == player2.length
• 1 <= n <= 1000
• 0 <= player1[i], player2[i] <= 10

【模拟】

int score(const int *player, int playerSize) {int res = 0;for (int i = 0; i < playerSize; i++) {if ((i > 0 && player[i - 1] == 10) || (i > 1 && player[i - 2] >= 10)) {res += 2 * player[i];}else {res += player[i];}}return res;
}int isWinner(int* player1, int player1Size, int* player2, int player2Size){int s1 = score(player1, player1Size);int s2 = score(player2, player2Size);return s1 == s2 ? 0 : s1 > s2 ? 1 : 2;
}

2735 收集巧克力(12.28)

给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

• 同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

【枚举】

// 求和函数
long long sum(int *f, int n) {long long ans = 0;for (int i = 0; i < n; i++) {ans += f[i];}return ans;
}long long minCost(int *nums, int numsSize, int x){int n = numsSize;int *f = (int *)malloc(sizeof(int) * n);// 赋值num给fmemcpy(f, nums, sizeof(int) * n);// f求和，初始anslong long ans = sum(f, n);// k对应加成本次数for (int k = 1; k < n; k++) {// i代表从前往后的巧克力for (int i = 0; i < n; i++) {f[i] = fmin(f[i], nums[(i + k) % n]);}ans = fmin(ans, (long long)k * x + sum(f, n));}free(f);return ans;
}

2706 购买两块巧克力(12.29)

给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。

你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。

提示：

• 2 <= prices.length <= 50
• 1 <= prices[i] <= 100
• 1 <= money <= 100

【排序】

int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}int buyChoco(int* prices, int pricesSize, int money){qsort(prices,pricesSize,sizeof(int),cmp);int ret=money-prices[0]-prices[1];if(ret<0){return money;}return ret;
}

【1次遍历，找最小和次小】

int buyChoco(int* prices, int pricesSize, int money) {int fi = INT_MAX, se = INT_MAX;for (int i = 0; i < pricesSize; i++) {int price = prices[i];if (price < fi) {se = fi;fi = price;} else if (price < se) {se = price;}}return money < fi + se ? money : money - fi - se;
}

1185 一周中的第几天(12.30)

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

提示：

• 给出的日期一定是在 1971 到 2100 年之间的有效日期。

【模拟】

char * dayOfTheWeek(int day, int month, int year){char * week[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};int monthDays[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};int days = 365 * (year - 1971) + (year - 1969) / 4;for (int i = 0; i < month - 1; ++i) {days += monthDays[i];}if ((year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) && month >= 3) {days += 1;}days += day;return week[(days + 3) % 7];
}

1154 一年中的第几天(12.31)

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。

提示：

• date.length == 10
• date[4] == date[7] == '-'，其他的 date[i] 都是数字
• date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日

【模拟】

int dayOfYear(char* date) {int year=0,month=0,day=0,count=0,n=strlen(date);for(int i=0;i<n;i++){int t;if(i>=0 && i<=3){//yeart=date[i]-'0';year=year*10+t;}else if(i>=5 && i<=6){//montht=date[i]-'0';month=month*10+t;}else if(i>=8 && i<=9){//dayt=date[i]-'0';day=day*10+t;}}//闰年bool flag=0;if((year%400==0) || (year%4==0 && year%100!=0)){flag=1;}//每个月days打表int monthday[12]={31,28,31,30,31,30,31,31,30,31,30,31};if(flag){monthday[1]+=1;}for(int i=1;i<month;i++){count+=monthday[i-1];}count+=day;return count;
}

【cpp库函数】

class Solution {
public:int dayOfYear(string date) {tm dt;istringstream(date) >> get_time(&dt, "%Y-%m-%d");return dt.tm_yday + 1;}
};

为什么这周少一天

乐，因为之前一直是周二按每leetcode周的第一天来算的。正好今天是年底&&周日，遂直接总结吧。

ps：最后还是没有master algorithm before 2024。个人能力有限，任重而道远。