0%

LeetCode 第 178 场周赛

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int>ret;
for(int i = 0; i < nums.size(); i++) {
int cur = 0;
for(int j = 0; j < nums.size(); j++) {
if(i != j && nums[j] < nums[i]) cur++;
}
ret.push_back(cur);
}
return ret;
}
};

2. 通过投票对团队排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
struct node{
string ch;
int rank[26];
bool operator < (node b)const{
for(int i = 0; i < 26; i++) {
if(rank[i] > b.rank[i]) return true;
if(rank[i] < b.rank[i]) return false;
}
return ch < b.ch;
}
node(){}
};
string rankTeams(vector<string>& votes) {
string allchar = votes[0];
int len = allchar.length();
node all[26];
for(int i = 0; i < len; i++) { // init
all[(allchar[i] - 'A')].ch = allchar[i];
for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++) all[j].rank[k] = 0;
}
for(int i = 0; i < votes.size(); i++) {
for(int j = 0; j < len; j++) {
all[(votes[i][j]) - 'A'].rank[j]++;
}
}

sort(all, all + 26);
// for(int i = 0; i < len ; i++) {
// cout << all[i].ch << " : ";
// for(int j = 0; j < len; j++) cout << all[i].rank[j] << " "; cout << "\n";
// } cout << endl;
string ans = "";
for(int i = 0; i < len; i++) {
ans += all[i].ch;
//cout << all[i].rank[0] << " " << all[i].rank[1] << " " << all[i].rank[2] << endl;
}
return ans;
}
};

3. 二叉树中的列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 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 solve(ListNode* head, TreeNode* root) {
if(head == NULL) return true;
if(root == NULL || root -> val != head -> val) return false;
return solve(head -> next, root -> left) || solve(head -> next, root -> right);
}
bool isSubPath(ListNode* head, TreeNode* root) {
if(root == NULL) return false;
return solve(head, root) || isSubPath(head, root -> left) || isSubPath(head, root -> right);

}
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int n, m;
struct point{
int x, y, c;
point(){}
point(int x, int y, int c):x(x), y(y), c(c){}
friend bool operator < (point a, point b) {
return a.c > b.c;
}
};
bool is_ok(point p) {
return (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m);
}
int minCost(vector<vector<int>>& grid) {
priority_queue<point> pq;
int vis[100][100];
memset(vis, -1, sizeof vis);
int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //按照右左下上的顺序
n = grid.size(), m = grid[0].size();
point cur = point(0, 0, 0);
pq.push(cur);
vis[0][0] = 0;
while(!pq.empty()) {
cur = pq.top();
pq.pop();
for(int i = 0; i < 4; i++) {
point nxt = cur;
nxt.x += nx[i]; nxt.y += ny[i];
if(!is_ok(nxt)) continue;
if(grid[cur.x][cur.y] != i + 1) nxt.c++;
if(vis[nxt.x][nxt.y] == -1 || nxt.c < vis[nxt.x][nxt.y]) {
vis[nxt.x][nxt.y] = nxt.c;
pq.push(nxt);
}
}
}
return vis[n-1][m-1];
}
};
如果对您有帮助,请我喝杯奶茶?