LeetCodeWeeklyContest-178

本文主要是介绍LeetCodeWeeklyContest-178，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

178周赛

rank：1112 / 3304
ac：2/4
score：7/19

有多少小于当前数字的数字

签到题，暴力即可

通过投票对团队排名

其实就是统计一下在各个名次的次数，然后排下序即可。

int len,n;
int cnt[26+1][1005];
bool cmp(int a,int b){for(int i=0;i<n;i++){if(cnt[a][i]!=cnt[b][i]) return cnt[a][i]>cnt[b][i];}return a<b;
}
class Solution {
public:string rankTeams(vector<string>& votes) {memset(cnt,0,sizeof(cnt));len = votes.size(),n = votes[0].length();if(len==1||n==1) return  votes[0];for(int i=0;i<len;i++){for(int j=0;j<n;j++){cnt[votes[i][j]-'A'][j]++;}}vector<int> ch(n);for(int i=0;i<n;i++){ch[i] = votes[0][i]-'A';}sort(ch.begin(),ch.end(),cmp);string res;for(int i=0;i<n;i++){res += 'A'+ch[i];}return res;}
};

二叉树中的列表

其实就是判断是不是子树，双重dfs
类似：剑指Offer ：树的子结构

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSubPath(ListNode* head, TreeNode* root) {if(root==NULL) return false;return check(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);}bool check(ListNode* head, TreeNode* root){if(head==NULL) return true;if(root==NULL) return false;return head->val==root->val&&(check(head->next,root->left)||check(head->next,root->right));}
};

使网格图至少有一条有效路径的最小代价

参考：SPFA——BFS的一种扩展

class Solution {
public:bool isok(int x,int y,int m ,int n){return x>=0&&x<m&&y>=0&&y<n;}int minCost(vector<vector<int>>& g) {int dis[150][150],vis[150][150];int m = g.size(),n = g[0].size();int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};memset(dis,0x3f3f,sizeof(dis));memset(vis,0,sizeof(vis));queue<pair<int,int>> qu;qu.push(make_pair(0,0)); vis[0][0]=1,dis[0][0]=0;while(!qu.empty()){int xx = qu.front().first,yy = qu.front().second;qu.pop(); vis[xx][yy] = 0;for(int i=1;i<=4;i++){int xto = xx+dx[i],yto = yy + dy[i];if(isok(xto,yto,m,n)){int tmp = 0;if(g[xx][yy]==i) tmp = dis[xx][yy];else tmp = dis[xx][yy]+1;if(tmp<dis[xto][yto]){dis[xto][yto] = tmp;if(!vis[xto][yto]){qu.push(make_pair(xto,yto));vis[xto][yto] = 1;}}}}}return dis[m-1][n-1];}
};