腐烂的橘子（图论）
mxn的网格grid中，每个单元格有以下三个值之一：
- 0：代表空单元格
- 1：代表新鲜橘子
- 2：代表腐烂橘子
每分钟，腐烂橘子会向4个方向腐烂。
返回直到单元格没有新鲜橘子必须经过的最小分钟数，如果不可能，返回1。
前言
每分钟腐烂的橘子会使上下左右相邻的新鲜橘子腐烂，这其实是一个模拟广度优先搜索的过程。
所谓广度优先搜索，就是从起点触发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。
上下左右相邻的新鲜橘子就是该腐烂橘子尝试访问的同一层的节点，路径长度就是腐烂的时间。
class Solution {
private:
//记录橘子全部腐烂所需时间
int badTime[10][10];
//记录新鲜橘子数
int cnt = 0;
//方向
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
memset(badTime, -1, sizeof(badTime));
//广度优先搜索必用队列，存入烂橘子
queue<pair<int, int>> badOranges;
//腐烂橘子存入队列+设置腐烂时间+记录新鲜橘子数
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] == 2){
badOranges.emplace(i,j);
badTime[i][j] = 0;
}else if(grid[i][j] == 1){
++cnt;
}
}
}
int ans = 0;
//开始BFS
while(!badOranges.empty()){
auto [row, col] = badOranges.front();
badOranges.pop();
//开始感染
for(int i=0; i<4; i++){
//相邻橘子坐标
int dx = row + dir_x[i];
int dy = col + dir_y[i];
//越界访问 已经访问过 没有橘子
if(dx < 0 || dx >=m || dy < 0 || dy >= n || badTime[dx][dy] != -1 || grid[dx][dy] == 0){
continue;
}
badTime[dx][dy] = badTime[row][col] + 1;
badOranges.emplace(dx,dy);
if(grid[dx][dy] == 1){
--cnt;
ans = badTime[dx][dy];
if(cnt == 0){
break;
}
}
}
}
return cnt == 0 ? ans : -1;
}
};
全排列
class Solution {
public:
void backtrace(vector<vector<int>>&res, vector<int>&nums, int first, int len){
// 所有数都填完了
if(first == len){
res.emplace_back(nums);
return;
}
for(int i=first; i<len; i++){
swap(nums[i], nums[first]);
backtrace(res, nums, first+1, len);
swap(nums[i], nums[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
backtrace(res, nums, 0, nums.size());
return res;
}
};
子集
迭代法实现子集枚举
排序
#include <iostream>
using namespace std;
void selectSort(int arr[]) {
int n = sizeof(arr);
cout << n << endl;
if (arr == nullptr || n < 2) {
return;
}
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
void bubbleSort(int arr[]) {
for (int i = 0; i < sizeof(arr) - 1; i++) {
for (int j = 0; j < sizeof(arr) - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
void insertSort(int arr[]) {
for (int i = 1; i < sizeof(arr); i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
}
else {
break;
}
}
}
}
/* 在有序列表里查找一个元素最快二分法 */
int findElement(int arr[], int x) {
int left = 0, right = sizeof(arr) - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x) {
return mid;
}
else if (arr[mid] < x) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
void printArr(int arr[]) {
int n = sizeof(arr);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
/* 在一个有序数组中，找到>=某个数最左侧的位置 */
int finGreaterdElement(int arr[], int x) {
int left = 0, right = sizeof(arr) - 1;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] >= x) {
right = mid;
}
else if (arr[mid] < x) {
left = mid+1;
}
}
return left;
}
int main() {
int arr[] = { 4,2,2,1,7,2,6,7,5 };
//selectSort(arr);
//bubbleSort(arr);
insertSort(arr);
printArr(arr);
/*cout << findElement(arr, 4) << endl;*/
cout << finGreaterdElement(arr, 2) << endl;
return 0;
}
最小和分割
给一个正整数num，把它分割成num1和num2，满足：
- num1和num2要包含所有num中出现的数
- num1和num2可以包含前导0。
class Solution {
public:
int splitNum(int num) {
string strnum = to_string(num);
sort(strnum.begin(), strnum.end());
int num1 = 0;
int num2 = 0;
for(int i=0; i<strnum.size(); i++){
if(i % 2 == 0){
num1 = (num1)*10 + (strnum[i]-'0');
}else{
num2 = (num2)*10 + (strnum[i]-'0');
}
}
return (num1+num2);
}
};
最小时间差
将timePoints排序后，最小时间差必然出现在timePoints的两个相邻时间，或者timePoints的两个首尾时间中。
class Solution {
private:
int getMinutes(string &t){
return ((t[0]-'0')*10 + t[1]-'0')*60 + (t[3]-'0')*10 + t[4]-'0';
}
public:
int findMinDifference(vector<string>& timePoints) {
sort(timePoints.begin(), timePoints.end());
int ans = INT_MAX;
int t0Minutes = getMinutes(timePoints[0]);
int preMinutes = t0Minutes;
for(int i=1; i<timePoints.size(); i++){
int minutes = getMinutes(timePoints[i]);
ans = min(ans, minutes-preMinutes);
preMinutes = minutes;
}
ans = min(ans, t0Minutes + 1440 - preMinutes);
return ans;
}
};
