周赛173
1333. 餐厅过滤器
题目：给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 id 从高到低排序。简单起见， veganFriendlyi 和 veganFriendly 为 true 时取值为 1，为 false 时，取值为 0 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：这题是一个排序比较的问题，我的思路是先筛选出满足条件的餐厅，然后再去排序。
代码：
class Solution {
public:
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
int i,j,k,n,temp;
n=restaurants.size();
vector<int>a(n,0);
if(veganFriendly)
{
j=0;
for(i=n-1;i>=0;i--)
{
if(restaurants[i][2]==1 && restaurants[i][3]<=maxPrice && restaurants[i][4]<=maxDistance)
{
a[j]=i;
j++;
}
}
}
else
{
j=0;
for(i=n-1;i>=0;i--)
{
if(restaurants[i][3]<=maxPrice && restaurants[i][4]<=maxDistance)
{
a[j]=i;
j++;
}
}
}
vector<int>b(j,0);
for(i=0;i<j;i++)
{
for(k=0;k<j-i-1;k++)
{
if(restaurants[a[k]][1] < restaurants[a[k+1]][1] || (restaurants[a[k]][1] == restaurants[a[k+1]][1] && restaurants[a[k]][0] < restaurants[a[k+1]][0]))
{
temp=a[k];
a[k]=a[k+1];
a[k+1]=temp;
}
}
}
for(i=0;i<j;i++)
b[i]=restaurants[a[i]][0];
return b;
}
};
而在看了题解之后，学习了sort函数，而这道题就可以利用sort函数进行排序，比冒泡排序算法效率要高
sort函数语法：sort(start,end,cmp)
（1）start表示要排序数组的起始地址；
（2）end表示数组结束地址的下一位；
（3）cmp用于规定排序的方法，可不填，默认升序。
若要实现从大到小排序，则需要加入一个比较函数compare()：boolcompare(inta,intb)
{
returna>b;
}
代码为sort(start,end,compare)
对于这题便可以利用sort函数进行从大到小排序。在此是先排序再筛选，排序时的比较函数compare()要定义成静态变量，static compare()
代码：class Solution {
public: vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
int i,j,k,n,temp;
n=restaurants.size();
sort(restaurants.begin(),restaurants.end(),compare);
vector<int>a(n,0);
if(veganFriendly)
{
j=0;
for(i=0;i<n;i++)
{
if(restaurants[i][2]==1 && restaurants[i][3]<=maxPrice && restaurants[i][4]<=maxDistance)
{
a[j]=restaurants[i][0];
j++;
}
}
}
else
{
j=0;
for(i=0;i<n;i++)
{
if(restaurants[i][3]<=maxPrice && restaurants[i][4]<=maxDistance)
{
a[j]=restaurants[i][0];
j++;
}
}
}
vector<int>b(j,0);
for(i=0;i<j;i++)
b[i]=a[i];
return b;
}
static bool compare (const vector<int> &a,const vector<int> &b){
if(a[1]!=b[1]) return a[1]>b[1];
else return a[0]>b[0];
}
};
CONST关键字
（1）可以定义const常量，具有不可变性。
例如：const int Max=100; Max++会产生错误;
（2）便于进行类型检查，使编译器对处理内容有更多了解，消除了一些隐患。
例如： void f(const int i) { .........} 编译器就会知道i是一个常量，不允许修改；
（3）可以避免意义模糊的数字出现，同样可以很方便地进行参数的调整和修改。 同宏定义一样，可以做到不变则已，一变都变！
如（1）中，如果想修改Max的内容，只需要它修改成：const int Max=you want;即可！
（4）可以保护被修饰的东西，防止意外的修改，增强程序的健壮性。 还是上面的例子，如果在函数体内修改了i，编译器就会报错；
例如： void f(const int i) { i=10;//error! }
（5） 可以节省空间，避免不必要的内存分配。 例如：
#define PI 3.14159 //常量宏
const doublePi=3.14159; //此时并未将Pi放入ROM中 ......
double i=Pi; //此时为Pi分配内存，以后不再分配！
double I=PI; //编译期间进行宏替换，分配内存
double j=Pi; //没有内存分配
double J=PI; //再进行宏替换，又一次分配内存！
const定义常量从汇编的角度来看，只是给出了对应的内存地址，而不是像#define一样给出的是立即数，所以，const定义的常量在程序运行过程中只有一份拷贝，而#define定义的常量在内存中有若干份拷贝。
（6） 提高了效率。
编译器通常不为普通const常量分配存储空间，而是将它们保存在符号表中，这使得它成为一个编译期间的常量，没有了存储与读内存的操作，使得它的效率也很高。
【C++】auto关键字
auto不是一个类型的“声明”，而是一个“占位符”，编译器在编译期会将auto替换为变量实际的类型。使用auto定义变量时必须对其进行初始化，在编译阶段编译器需要根据初始化表达式来推导auto的实际类型。它自动推导变量类型是根据“=”右侧的变量类型决定的。
面试题13.机器人的运动范围
题目：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：从上到下，从左到右遍历整个方格，满足行坐标和列坐标的数位之和大于k的格子并且此方格的上面方格或左边方格满足条件则该方格可进入。在第一行时，判断条件只有当左边满足条件，因此当左边方格不满足时这一行便结束遍历。而从第二行开始，当该行的第一个不满足条件时，证明这一整行都不满足条件，因此后面的所以方格都不用遍历。（注意点：需要将变量初始化）
代码：class Solution {
public:
int movingCount(int m, int n, int k) {
int i=0,j=0,x1=0,x2=0,y1=0,y2=0,temp=0;
int a[m][n];
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=0;
for(i=0;i<m;i++)
{
x1=i%10;
x2=i/10;
if(x1+x2 > k)
break;
temp++;
a[i][0]=1;
for(j=1;j<n;j++)
{
a[i][j]=0;
y1=j%10;
y2=j/10;
if(x1+x2+y1+y2 <= k)
{
if(i==0)
{
if(a[i][j-1]!=1) break;
temp++;
a[i][j]=1;
}
else
{
if(a[i-1][j]==1 || a[i][j-1]==1)
{
temp++;
a[i][j]=1;
}
}
}
else
continue;
}
}
return temp;
}
};
