周賽173

1333. 餐廳過濾器

題目：給你一個餐館信息數(shù)組 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
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路：這題是一個排序比較的問題，我的思路是先篩選出滿足條件的餐廳，然后再去排序。

代碼：
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函數(shù)，而這道題就可以利用sort函數(shù)進行排序，比冒泡排序算法效率要高

sort函數(shù)語法：sort(start,end,cmp)
（1）start表示要排序數(shù)組的起始地址；
（2）end表示數(shù)組結束地址的下一位；
（3）cmp用于規(guī)定排序的方法，可不填，默認升序。
若要實現(xiàn)從大到小排序，則需要加入一個比較函數(shù)compare()：boolcompare(inta,intb)
{
? ? returna>b;
}
代碼為sort(start,end,compare)

對于這題便可以利用sort函數(shù)進行從大到小排序。在此是先排序再篩選，排序時的比較函數(shù)compare()要定義成靜態(tài)變量，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++會產(chǎn)生錯誤;

（2）便于進行類型檢查，使編譯器對處理內(nèi)容有更多了解，消除了一些隱患。

例如： void f(const int i) { .........} 編譯器就會知道i是一個常量，不允許修改；

（3）可以避免意義模糊的數(shù)字出現(xiàn)，同樣可以很方便地進行參數(shù)的調(diào)整和修改。 同宏定義一樣，可以做到不變則已，一變都變！

如（1）中，如果想修改Max的內(nèi)容，只需要它修改成：const int Max=you want;即可！

（4）可以保護被修飾的東西，防止意外的修改，增強程序的健壯性。 還是上面的例子，如果在函數(shù)體內(nèi)修改了i，編譯器就會報錯；

例如： void f(const int i) { i=10;//error! }

（5） 可以節(jié)省空間，避免不必要的內(nèi)存分配。 例如：

#define PI 3.14159 //常量宏

const doublePi=3.14159; //此時并未將Pi放入ROM中 ......

double i=Pi; //此時為Pi分配內(nèi)存，以后不再分配！

double I=PI; //編譯期間進行宏替換，分配內(nèi)存

double j=Pi; //沒有內(nèi)存分配

double J=PI; //再進行宏替換，又一次分配內(nèi)存！

const定義常量從匯編的角度來看，只是給出了對應的內(nèi)存地址，而不是像#define一樣給出的是立即數(shù)，所以，const定義的常量在程序運行過程中只有一份拷貝，而#define定義的常量在內(nèi)存中有若干份拷貝。

（6） 提高了效率。

編譯器通常不為普通const常量分配存儲空間，而是將它們保存在符號表中，這使得它成為一個編譯期間的常量，沒有了存儲與讀內(nèi)存的操作，使得它的效率也很高。

【C++】auto關鍵字

auto不是一個類型的“聲明”，而是一個“占位符”，編譯器在編譯期會將auto替換為變量實際的類型。使用auto定義變量時必須對其進行初始化，在編譯階段編譯器需要根據(jù)初始化表達式來推導auto的實際類型。它自動推導變量類型是根據(jù)“=”右側的變量類型決定的。 ? ?

面試題13.機器人的運動范圍

題目：地上有一個m行n列的方格，從坐標 [0,0] 到坐標 [m-1,n-1] 。一個機器人從坐標 [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進入行坐標和列坐標的數(shù)位之和大于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
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路：從上到下，從左到右遍歷整個方格，滿足行坐標和列坐標的數(shù)位之和大于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;
? ? }
};