一个小时全 Accept 了,题目还算友好~
第一题,找 Good
#include<bits/stdc++.h> using namespace std; int main() { string str = "", s; cin >> str; while (cin >> s) { str += " " + s; } int ans = 0; int i = 0, j = 1, k = 3, onum = 0; bool flag = false; for (int i = 0; i < str.length() - 3; i++) { if (str[i] != 'G') continue; j = max(i + 1, j); for (; j < str.length() - 1; j++) { if (str[j] != 'o') continue; if (onum == 0) onum++; else if (onum == 1) { onum++; break; } } if (j == str.length() - 1) { flag = true; } if (onum == 2) { onum = 0; j++; k = max(j + 1, k); for (; k < str.length(); k++) { if (str[k] != 'd') continue; k++; ans++; break; } if (k == str.length()) { flag = true; } } if (flag) break; } cout << ans << endl; return 0; }第二题,找最长递增路径
#include<bits/stdc++.h> using namespace std; int main() { int rows, cols, i, j; cin >> rows >> cols; vector<vector<int>> matrix(rows, vector<int>(cols)); for (i = 0; i < rows; i++) { for (j = 0; j < cols; j++) { cin >> matrix[i][j]; } } vector<vector<int>> outdegree(rows, vector<int>(cols, 0)); for (i = 0; i < rows; i++) { for (j = 0; j < cols; j++) { if (j != cols-1 && matrix[i][j] < matrix[i][j+1]) outdegree[i][j]++; if (i != rows-1 && matrix[i][j] < matrix[i+1][j]) outdegree[i][j]++; if (j != 0 && matrix[i][j] < matrix[i][j-1]) outdegree[i][j]++; if (i != 0 && matrix[i][j] < matrix[i-1][j]) outdegree[i][j]++; } } vector<pair<int,int>> leaves; for (i = 0; i < rows; i++) { for (j = 0; j < cols; j++) { if (outdegree[i][j] == 0) leaves.emplace_back(i, j); } } int ans = 0; while (!leaves.empty()) { ans++; vector<pair<int,int>> newLeaves; for (int index = 0; index < leaves.size(); index++) { i = leaves[index].first, j = leaves[index].second; if (j != cols-1 && matrix[i][j] > matrix[i][j+1] && --outdegree[i][j+1] == 0) newLeaves.emplace_back(i, j+1); if (i != rows-1 && matrix[i][j] > matrix[i+1][j] && --outdegree[i+1][j] == 0) newLeaves.emplace_back(i+1, j); if (j != 0 && matrix[i][j] > matrix[i][j-1] && --outdegree[i][j-1] == 0) newLeaves.emplace_back(i, j-1); if (i != 0 && matrix[i][j] > matrix[i-1][j] && --outdegree[i-1][j] == 0) newLeaves.emplace_back(i-1, j); } leaves = newLeaves; } cout << ans << endl; return 0; }第三题,删区间
class Solution { public: /** * * @param intervals int整型vector<vector<>> * @return int整型 */ int eraseOverlapIntervals(vector<vector<int> >& intervals) { // write code here if (intervals.size() < 2) return 0; sort(intervals.begin(), intervals.end()); int start = intervals[0][0], end = intervals[0][1]; int ans = 0; for (int i = 1; i < intervals.size(); i++) { if (intervals[i][0] >= end) { start = intervals[i][0]; end = intervals[i][1]; } else if (intervals[i][1] <= end) { start = intervals[i][0]; end = intervals[i][1]; ans++; } } return ans; } };
全部评论
(0) 回帖