模板
queue <pair<int, int>> Q;if (grid[x][y] == 1){Q.push(make_pair(x, y));res += 1;visited[x][y] = true;while(!Q.empty()){pair<int, int >temp = Q.front();Q.pop();for (int i = 0; i < 4; i ++){int x = temp.first + xMove[i];int y = temp.second + yMove[i];if (x < 0 || y < 0 ||x >= grid.size() || y >= grid[0].size()){continue;}Q.push(make_pair(x,y));visited[x][y] = true;}}}return res;
200 Number of islands
元组的使用
遍历每个点
if 没有访问过bfs
bfs方法：
先判断是否是1 然后再进行bfs
#include <vector>;#include <iostream>;#include <queue>;using namespace std;class Solution {public:int numIslands(vector<vector<char>>& grid) {//if (grid.empty() || grid[0].empty()) return 0;int m = grid.size(), n = grid[0].size(), res = 0;vector<vector<int>> moveDirection = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };vector<vector<bool>> visited(m, vector<bool>(n));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {//if (visited[i][j] == false){res = BFS(grid, i, j, visited, moveDirection, res);}}}return res;}int BFS(vector<vector<char>>& grid, int x, int y, vector<vector<bool>>& visited, vector<vector<int>> moveDirection, int res) {queue<pair<int, int>> q;if (grid[x][y] == '1') {q.push(make_pair(x, y));res += 1;}visited[x][y] = true;while (!q.empty()) {//typair<int, int> t = q.front();q.pop();for (int k = 0; k < 4; ++k) {int x = t.first + moveDirection[k][0], y = t.second + moveDirection[k][1];if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) {continue;}visited[x][y] = true;q.push(make_pair(x, y));}}return res;}
69. Binary Tree Level Order Traversal(树中的二叉树，需要记录每一层的个数)
struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (root == NULL){return result;}queue<TreeNode*> Q;Q.push(root);while(!Q.empty()){int size = Q.size();vector<int> level;for (int i = 0; i < size; i++){TreeNode *head = Q.front();Q.pop();level.push_back(head->val);if (head->left != NULL){Q.push(head -> left);}if (head->right != NULL){Q.push(head -> right);}}result.push_back(level);}return result;}};
615. Course Schedule(拓扑排序， 含方法)
1 统计每点的入度
- 将入度为0的点放入queue
- 每次拿出一个点去掉临边的入度减一
发现有入度为0的点，丢入queue
class Solution {public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {bool result;int count = 0;if (numCourses == 0 || prerequisites.size() == 0) {return true;}vector<int> indegree(numCourses);//push all the courses in to unordered_mapfor (int i = 0; i < prerequisites.size(); i++) {indegree[prerequisites[i][0]] += 1;}queue <int> Q;for (int i = 0; i < indegree.size(); i++) {if (indegree[i] == 0) {Q.push(i);}}while (!Q.empty()) {int course = Q.front();Q.pop();count += 1;for (int i = 0; i < prerequisites.size(); i++) {if (prerequisites[i][1] == course) {indegree[prerequisites[i][0]] -= 1;if (indegree[prerequisites[i][0]] == 0) {Q.push(prerequisites[i][0]);}}}}return (count == numCourses);}};
616. Course Schedule II
当set中有重复的时候我们要用multiset
class Solution {
public:
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: the course order
*/
vector<int> findOrder(int numCourses, vector<pair<int, int>> &prerequisites) {
// write your code here
vector<unordered_multiset<int>> course(numCourses);
int m = prerequisites.size();
vector<int> indegree(numCourses);
queue <int> Q;
vector <int> result;
//int count = 0;
for (int i = 0; i < m; i ++){
indegree[prerequisites[i].first] += 1;
course[prerequisites[i].second].insert(prerequisites[i].first);
}
for (int i = 0; i < numCourses; i ++){
if (indegree[i] == 0){
Q.push(i);
}
}
while(!Q.empty()){
int temp = Q.front();
Q.pop();
result.push_back(temp);
for (auto it = course[temp].begin(); it != course[temp].end(); it ++){
indegree[*it] -= 1;
if (indegree[*it] == 0){
Q.push(*it);
}
}
}
for (int i = 0; i < result.size(); i ++)
cout << result[i];
if (result.size() == numCourses){
return result;
}
return vector<int>();
}
};
骑士的最短路径
class Solution {
public:
/**
* @param grid: a chessboard included 0 (false) and 1 (true)
* @param source: a point
* @param destination: a point
* @return: the shortest path
*/
int shortestPath(vector<vector<bool>> &grid, Point &source, Point &destination) {
// write your code here
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> moveDirection = {{1, 2}, {2, 1}, {1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}};
int res = 0;
queue <Point> Q;
Q.push(source);
vector<vector<int>> pathLength (n, vector<int> (m, INT_MAX));
pathLength [source.x][source.y] = 0;
while(!Q.empty()){
Point startNode = Q.front();
Q.pop();
for (int i = 0; i < 8; i++){
int x = startNode.x + moveDirection[i][0];
int y = startNode.y + moveDirection[i][1];
if (x >= 0 && x < n && y >= 0 && y < m &&
!grid[x][y] && pathLength[startNode.x][startNode.y] + 1 < pathLength[x][y]){
//Point newPoint(startNode.x + moveDirection[i][0], startNode.y + moveDirection[i][1]);
pathLength[x][y] = pathLength[startNode.x][startNode.y] + 1;
Q.push(Point(x, y));
}
}
}
if (pathLength[destination.x][destination.y] == INT_MAX)
return -1;
return pathLength[destination.x][destination.y];
}
};
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
// Write your code here
unordered_map<int, int> pos, pre;
for (int i = 0; i < org.size(); ++i) pos[org[i]] = i;
for (auto& seq : seqs) {
for (int i = 0; i < seq.size(); ++i) {
if (pos.find(seq[i]) == pos.end()) {
return false;
}
if (i > 0 && pos[seq[i - 1]] >= pos[seq[i]]) {
return false;
}
if (pre.find(seq[i]) == pre.end()) {
pre[seq[i]] = (i > 0) ? pos[seq[i - 1]] : -1;
} else {
pre[seq[i]] = max(pre[seq[i]], (i > 0) ? pos[seq[i - 1]] : -1);
}
}
}
for (int i = 0; i < org.size(); ++i) {
if (pre[org[i]] != i - 1)
return false;
}
return true;
}
};
Sequence Reconstruction
入度初度均需考虑
特殊情况包括
[1] [[ ], [ ]] [1] [[1]等
class Solution {
public:
/**
* @param org: a permutation of the integers from 1 to n
* @param seqs: a list of sequences
* @return: true if it can be reconstructed only one or false
*/
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
// write your code here
if(org.size() == 1){
for(int i = 0; i < seqs.size(); i++){
for(int j = 0; j < seqs[i].size(); j++){
if(org[0] == seqs[i][j]){
return true;
}
}
}
return false;
}
if(org.size() == 0){
return true;
}
for(int i = 0; i < seqs.size(); i++){
for(int j = 0; j < seqs[i].size(); j++){
if(seqs[i][j] > org.size() || seqs[i][j] < 1){
return false;
}
}
}
vector <int> indegree(org.size() + 1);
vector <vector<int>> outdegree(org.size() + 1, vector<int>());
for (int i = 0; i < seqs.size(); i++) {
for (int j = 1; j < seqs[i].size(); j++) {
indegree[seqs[i][j]] += 1;
}
}
for (int i = 0; i < seqs.size(); i++) {
for (int j = 1; j < seqs[i].size(); j++) {
outdegree[seqs[i][j - 1]].push_back(seqs[i][j]);
}
}
queue <int> Q;
for (int i = 1; i < org.size() + 1; i++) {
if (indegree[i] == 0) {
Q.push(i);
}
}
vector <int> topoOrder;
while (!Q.empty()) {
if (Q.size() > 1) {
return false;
}
int number = Q.front();
Q.pop();
topoOrder.push_back(number);
for (int i = 0; i < outdegree[number].size(); i++) {
indegree[outdegree[number][i]] -= 1;
if (indegree[outdegree[number][i]] == 0) {
Q.push(outdegree[number][i]);
}
}
outdegree[number].clear();
}
return topoOrder == org;
}
};
leetcode 133 clone graph
以node为单位，建立一个map的一一对应关系
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node){
return nullptr;
}
unordered_map <Node*, Node*> cloneGraph;
queue <Node*> Q;
Q.push(node);
Node* newNode = new Node(node -> val);
cloneGraph[node] = newNode;
Node * tempNode;
vector <Node *> alreadyBuild;
alreadyBuild.push_back(node);
while (!Q.empty()){
Node *currentNode = Q.front();
Q.pop();
for (int i = 0; i < currentNode -> neighbors.size(); i++){
tempNode = currentNode -> neighbors[i];
// 判断是否已经遍历
if (!(find (alreadyBuild.begin(), alreadyBuild.end(), currentNode -> neighbors[i]) == alreadyBuild.end())){
cloneGraph[currentNode] -> neighbors.push_back(cloneGraph[tempNode]);
}
else{
Node * newNode = new Node(tempNode -> val);
cloneGraph[tempNode] = newNode;
cloneGraph[currentNode] -> neighbors.push_back(cloneGraph[tempNode]);
Q.push(tempNode);
alreadyBuild.push_back(tempNode);
}
}
}
return cloneGraph[node];
}
};
127. Topological Sorting
map初始化，统计入度，找到入度为0的点入队，bfs
class Solution {
public:
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
// write your code here
vector <DirectedGraphNode*> result;
unordered_map <DirectedGraphNode*, int> indegree;
for (int i = 0; i < graph.size(); i++){
indegree[graph[i]] = 0;
}
for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph[i]->neighbors.size(); j++) {
if (indegree.find(graph[i]->neighbors[j]) == indegree.end())
indegree[graph[i]->neighbors[j]] = 1;
else
indegree[graph[i]->neighbors[j]] += 1;
}
}
queue <DirectedGraphNode*> Q;
for (int i = 0; i < indegree.size(); i++) {
if (indegree[graph[i]] == 0) {
Q.push(graph[i]);
}
}
while (!Q.empty()) {
DirectedGraphNode* currentNode = Q.front();
Q.pop();
result.push_back(currentNode);
for (int i = 0; i < currentNode->neighbors.size(); i++) {
indegree[currentNode->neighbors[i]] -= 1;
}
indegree[currentNode] -= 1;
for (int i = 0; i < indegree.size(); i++) {
if (indegree[graph[i]] == 0) {
Q.push(graph[i]);
}
}
}
return result;
}
};
7. Serialize and Deserialize Binary Tree
注意字符串之间的转化
class Solution {
public:
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
string serialize(TreeNode* root) {
// write your code here
if (root == NULL){
return "";
}
queue<TreeNode*> Q;
Q.push(root);
string res;
res += to_string(root->val);
while (Q.size() != 0) {
TreeNode* temp = Q.front();
Q.pop();
if (temp->left != NULL) {
Q.push(temp->left);
res.push_back(',');
res += to_string(temp->left->val);
}
else {
res.push_back(',');
res.push_back('#');
}
if (temp->right != NULL) {
Q.push(temp->right);
res.push_back(',');
res += to_string(temp->right->val);
}
else {
res.push_back(',');
res.push_back('#');
}
}
return res;
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
TreeNode* deserialize(string& data) {
// write your code here
if (data.size() == 0){
return NULL;
}
int pos = 0;
queue<TreeNode*> Q;
// get int
string tempINT = "";
while (data[pos] != ',' && pos < data.size()) {
tempINT.push_back(data[pos]);
pos++;
}
TreeNode* root = new TreeNode(atoi(tempINT.c_str()));
Q.push(root);
while (Q.size() > 0) {
TreeNode* temp = Q.front();
Q.pop();
pos++;
tempINT = "";
// find int num
while (data[pos] != ',') {
tempINT.push_back(data[pos]);
pos++;
}
if (tempINT != "#") {
temp->left = new TreeNode(atoi(tempINT.c_str()));
Q.push(temp -> left);
}
// right node
pos++;
tempINT = "";
// find int num
while (data[pos] != ',' && pos < data.size()) {
tempINT.push_back(data[pos]);
pos++;
}
if (tempINT != "#") {
temp->right = new TreeNode(atoi(tempINT.c_str()));
Q.push(temp -> right);
}
}
return root;
}
};
900
递归，找到上下边界，再判断
class Solution {
public:
/**
* @param root: the given BST
* @param target: the given target
* @return: the value in the BST that is closest to the target
*/
int closestValue(TreeNode * root, double target) {
// write your code here
if (root == NULL){
return root->val;
}
TreeNode* upperBound = findUpperBound(root, target);
TreeNode* lowerBount = findLowerBound(root, target);
if (upperBound == NULL){
return lowerBount-> val;
}
if (lowerBount == NULL){
return upperBound-> val;
}
return (upperBound->val - target) < (target - lowerBount->val)? upperBound->val: lowerBount->val;
}
TreeNode * findLowerBound(TreeNode * root, double target){
if(root == NULL){
return NULL;
}
if(root->val > target){
return findLowerBound(root->left, target);
}
TreeNode * lower = findLowerBound(root->right, target);
if (lower == NULL){
return root;
}
return lower;
}
TreeNode * findUpperBound(TreeNode * root, double target){
if(root == NULL){
return NULL;
}
if(root->val < target){
return findUpperBound(root->right, target);
}
TreeNode * upper = findUpperBound(root->left, target);
if (upper == NULL){
return root;
}
return upper;
}
};
120. Word Ladder(难，两边bfs)
class Solution {
public:
/*
* @param start: a string
* @param end: a string
* @param dict: a set of string
* @return: An integer
*/
int ladderLength(string& start, string& end, unordered_set<string>& dict) {
// write your code here
// record visited string
unordered_set<string> visited_left;
unordered_set<string> visited_right;
queue <string> Q_left;
queue <string> Q_right;
dict.insert(start);
dict.insert(end);
// word size
int length = start.size();
Q_left.push(start);
Q_right.push(end);
// leftcont for howmany layers till now
//
int leftCount = 1, leftLevelCount = 1, leftNewCount = 1;
int rightCount = 0, rightLevelCount = 1, rightNewCount = 1;
while (true){
leftLevelCount = leftNewCount;
leftNewCount = 0;
while (Q_left.size() != 0 && leftLevelCount != 0) {
string temp = Q_left.front();
Q_left.pop();
if (visited_right.count(temp) > 0) {
return leftCount + rightCount;
}
else {
for (int i = 0; i < length; i++) {
for (int j = 0; j < 26; j++) {
string newTemp = temp;
newTemp[i] = char('a' + j);
//cout << newTemp << endl;
if (!visited_left.count(newTemp) && dict.count(newTemp)) {
visited_left.insert(newTemp);
Q_left.push(newTemp);
leftNewCount += 1;
}
}
}
}
leftLevelCount --;
}
leftCount++;
rightLevelCount = rightNewCount;
rightNewCount = 0;
while (Q_right.size() != 0 && rightLevelCount != 0) {
string temp = Q_right.front();
Q_right.pop();
if (visited_left.count(temp) > 0) {
return leftCount + rightCount;
}
else {
for (int i = 0; i < length; i++) {
for (int j = 0; j < 26; j++) {
string newTemp = temp;
newTemp[i] = char('a' + j);
if (!visited_right.count(newTemp) && dict.count(newTemp)) {
visited_right.insert(newTemp);
Q_right.push(newTemp);
rightNewCount += 1;
}
}
}
}
rightLevelCount --;
}
rightCount++;
}
}
};
若有收获，就点个赞吧
0 人点赞
