如何写comparator 用class的方法记录，
401. Kth Smallest Number in Sorted Matrix
指针往斜下发展
- pair 是内部已经有的类，写到外面会混乱
- 用指针指向新建的class ： Pair * temp
- 重新comparator的时候用一个新的名字 比如cmp 或者这里的comparators，否则会冲突
- 小于是升序，大于是降序
小顶堆 <
class Solution {public:/*** @param matrix: a matrix of integers* @param k: An integer* @return: the kth smallest number in the matrix*/class Pair {public:int column, row;int value;Pair(int row, int col, int val) {this->column = col;this->row = row;this->value = val;}};// xiaodingduistruct Comparators {bool operator()(const Pair *a, const Pair *b) {return a->value > b->value;}};vector <int> rows = { 0, 1 };vector <int> columns = { 1, 0 };int kthSmallest(vector<vector<int>> &matrix, int k) {// write your code hereif (k > matrix.size() * matrix[0].size()) {return 0;}vector<vector<int>> visited(matrix.size(), vector<int>(matrix[0].size()));priority_queue <Pair*, vector<Pair*>, Comparators> pq;int num = 0;Pair *temp = new Pair(0, 0, matrix[0][0]);pq.push(temp);visited[0][0] = 1;for (int i = 0; i < matrix.size() * matrix[0].size(); i++) {if (num == k - 1) {return temp->value;}temp = pq.top();pq.pop();for (int j = 0; j < 2; j++) {int newCol = temp->column + columns[j];int newRow = temp->row + rows[j];if (newRow < matrix.size() && newCol < matrix[0].size()&& visited[newRow][newCol] == 0) {Pair *newPair = new Pair(newRow, newCol, matrix[newRow][newCol]);visited[newRow][newCol] = 1;pq.push(newPair);}}num++;}}};
class Solution {
public:
/**
* @param nums: an array of integers
* @param s: An integer
* @return: an integer representing the minimum size of subarray
*/
int minimumSize(vector<int> &nums, int s) {
int sumAll = 0;
for (int i = 0; i < nums.size(); i ++){
sumAll += nums[i];
}
if (sumAll < s){
return -1;
}
// write your code here
int first = 0, last = 0, sum = 0;
int min = nums.size();
for (first = 0; first < nums.size(); first ++){
while(last < nums.size() && sum < s){
sum += nums[last];
last += 1;
}
if (sum >= s){
if (last - first < min){
min = last - first;
}
sum -= nums[first ];
continue;
}
}
return min;
}
};
384. Longest Substring Without Repeating Characters
class Solution {
public:
/**
* @param s: a string
* @return: an integer
*/
int lengthOfLongestSubstring(string &s) {
// write your code here
int first = 0, last = 0, length = 0;
vector <int> visited(256);
for (first = 0; first < s.size(); first ++){
while(last < s.size() && visited[s[last]] == 0){
visited[s[last]] = 1;
last ++;
length = max(length, last - first);
}
visited [s[first]] = 0;
}
return length;
}
};
386. Longest Substring with At Most K Distinct Characters
一直要执行到<
class Solution {
public:
/**
* @param s: A string
* @param k: An integer
* @return: An integer
*/
int lengthOfLongestSubstringKDistinct(string &s, int k) {
// write your code here
int first, last;
vector <int> visited(256);
int diffChar, res;
for (first = 0; first < s.size(); first ++){
while (last != s.size() && diffChar <= k){
if (visited[s[last]] == 0){
diffChar += 1;
}
visited[s[last]] += 1;
last ++;
if (last - first > res && diffChar <= k){
res = last - first;
}
// cout << diffChar << " diff"<< endl;
// cout << first << " first" << last<< " last" <<"\n";
}
// if (last - first > res && diffChar <= k){
// res = last - first;
// }
visited[s[first]] -= 1;
if(visited[s[first]] == 0){
diffChar -= 1;
}
}
return res;
}
};
465. Kth Smallest Sum In Two Sorted Arrays
class Node{
public:
int col, row;
int value;
Node(int row, int column, int rowVal, int colVal){
this -> row = row;
this -> col = column;
this -> value = rowVal + colVal;
}
};
class Solution {
public:
/**
* @param A: an integer arrays sorted in ascending order
* @param B: an integer arrays sorted in ascending order
* @param k: An integer
* @return: An integer
*/
struct cmp{
bool operator() (const Node *a, const Node *b){
return a -> value > b -> value;
}
};
vector <int> columns = {1, 0};
vector <int> rows = {0, 1};
int kthSmallestSum(vector<int> &A, vector<int> &B, int k) {
// write your code here
vector<vector<int>> visited(A.size(), vector<int>(B.size()));
priority_queue <Node*, vector<Node*>, cmp> pq;
Node * newNode = new Node(0, 0, A[0], B[0]);
pq.push(newNode);
Node * temp;
for (int i = 0; i < k; i ++){
temp = pq.top();
pq.pop();
for(int j = 0; j < 2; j ++){
int tempRow = temp -> row + rows[j];
int tempCol = temp -> col + columns[j];
if (tempRow < A.size() && tempCol < B.size() && visited[tempRow][tempCol] == 0){
//cout << "add " << tempRow << ' ' << tempCol << ' ' << i << endl;
Node * tempnewNode = new Node(tempRow, tempCol, A[tempRow], B[tempCol]);
pq.push(tempnewNode);
visited[tempRow][tempCol] = 1;
}
//cout << temp -> value << ' ' << i <<endl;
}
}
return temp -> value;
}
};
1070. Accounts Merge
class Solution {
private:
vector <int> father;
vector <string> findString;
unordered_map <string, int> findPos;
unordered_map <string, string> findName;
int pos;
public:
/**
* @param accounts: List[List[str]]
* @return: return a List[List[str]]
*/
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
void connect(int x, int y) {
int a = find(x);
int b = find(y);
if (a != b) {
father[a] = b;
}
}
vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
// write your code here
vector<vector<string>> res;
unordered_map <int, int> visited;
int temp = 0;
for (int i = 0; i < accounts.size(); i++) {
for (int j = 1; j < accounts[i].size(); j++) {
if (!findPos.count(accounts[i][j])) {
findString.push_back(accounts[i][j]);
father.push_back(pos);
findPos[accounts[i][j]] = pos;
findName[accounts[i][j]] = accounts[i][0];
pos += 1;
}
connect(findPos[accounts[i][j]], findPos[accounts[i][1]]);
}
}
for (int i = 0; i < father.size(); i++) {
if (visited.count(find(i))) {
res[visited[find(i)]].push_back(findString[i]);
}
else {
res.push_back(vector <string> {findName[findString[i]], findString[i]});
visited[find(i)] = temp;
temp++;
}
}
for (int i = 0; i < res.size(); i++) {
sort(res[i].begin() + 1, res[i].end());
}
return res;
}
};
406. Minimum Size Subarray Sum(指针指向区间)
class Solution {
public:
/**
* @param nums: an array of integers
* @param s: An integer
* @return: an integer representing the minimum size of subarray
*/
int minimumSize(vector<int> &nums, int s) {
// write your code here
int start = 0, end = 0, length = 1;
int res = INT_MAX, sum = 0;
while (end != nums.size()){
sum += nums[end];
while (sum >= s){
if (length < res){
res = length;
}
sum -= nums[start];
start += 1;
length --;
}
end++;
length ++;
}
if (res == INT_MAX){
return -1;
}
return res;
}
};
若有收获，就点个赞吧
0 人点赞
