101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
分析：这道题既可以用深度优先搜索，也可以用广度优先搜索。此处先用广度优先搜索来做。
建立两个队列，lq和rq，每次比较队首的两个元素是否相等。
lq队列的队首l出列后，将它的left和right分别入队；
rq队列的队首r出列后，将它的right和left分别入队。
因为判断是否对称是这样比较的：
l->left 与 r->right
l->right 与 r->left比较。
|
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 |
/** * 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 isSymmetric(TreeNode* root) { if(root == NULL) return true; queue<TreeNode*> lq, rq; if(root->left != NULL) lq.push(root->left); if(root->right != NULL) rq.push(root->right); TreeNode *l, *r; while(!lq.empty() && !rq.empty()) { l = lq.front(); lq.pop(); r = rq.front(); rq.pop(); if(l == NULL && r == NULL) continue; if(l == NULL || r == NULL || l->val != r->val) return false; lq.push(l->left); rq.push(r->right); lq.push(l->right); rq.push(r->left); } if(lq.empty() && rq.empty()) return true; else return false; } }; |
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
分析：二叉树的层序遍历，使用广度优先搜索，建立一个队列q。
每次将队首temp结点出队列的同时，将temp的左孩子和右孩子入队
用size标记入队后的队列长度
row数组始终为当前层的遍历结果，然后用while(size–)语句保证每一次保存入row的只有一层。
每一次一层遍历完成后，将该row的结果存入二维数组v。
|
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 |
/** * 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: vector<vector<int>> levelOrder(TreeNode* root) { vector<int> row; vector<vector<int>> v; queue<TreeNode *> q; if(root == NULL) return v; q.push(root); TreeNode *temp; while(!q.empty()) { int size = q.size(); while(size--) { temp = q.front(); q.pop(); row.push_back(temp->val); if(temp->left != NULL) { q.push(temp->left); } if(temp->right != NULL) { q.push(temp->right); } } v.push_back(row); row.clear(); } return v; } }; |
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析：这道题既可以用广度优先搜索，又可以用深度优先搜索。这里用广度优先搜索解决。
建立一个存储结点的队列q。设指针p指向队首。将p出队的同时将p->left和p->right入队~
若发现p既没有left结点也没有right结点（就是说p是叶子结点）的时候直接return ans
否则在每一层遍历完成后ans++;
和上一题层序遍历相似，只是在层序遍历的过程中加入了判断是否已经是叶子结点。如果是叶子结点就直接返回当前的层数~
|
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 |
/** * 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: int minDepth(TreeNode* root) { if(root == NULL) return 0; queue<TreeNode *> q; q.push(root); TreeNode* p; int ans = 1; while(!q.empty()) { int size = q.size(); while(size--) { p = q.front(); if(p->left == NULL && p->right == NULL) return ans; if(p->left != NULL) q.push(p->left); if(p->right != NULL) q.push(p->right); q.pop(); } ans++; } return ans; } }; |
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
分析：这道题既可以用动态规划的方法来做，又可以用广度优先搜索的方法做。这里先用广度优先搜索的方法来做。
建立一个队列，并把n入队~~这个时候从后往前检索所有平方小于n的数，并把他们逐一入队；然后将temp值为队首的值，再从后往前检索所有平方小于temp的数，并把他们逐一入队。。直到有一次入队时候发现该数字为0时return。
比如设13为根节点，13 – 3 * 3 = 4， 13 – 2 * 2 = 9， 13 – 1 * 1 = 12，
4， 9， 12就是root的三个child，是第二层；
再下面一层，4 – 2 * 2 = 0， 4 – 1 * 1 = 3，4的child是0和3
因为发现了一个0，说明此时该层就为该数最少需要的平方和数字的个数~~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int numSquares(int n) { queue<int> q; q.push(n); int ans = 1; while(!q.empty()) { int size = q.size(); while(size--) { int temp = q.front(); q.pop(); for(int i = sqrt(temp); i >= 1; i--) { if(i*i == temp) return ans; q.push(temp-i*i); } } ans++; } return ans; } }; |
199. Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].
分析：这道题可以用广度优先搜索也可以用深度优先搜索。这里用广度优先方法解决：
如果root为空，则返回空vector。
建立存放TreeNode指针的队列，将root结点入队；
出队root的同时入队root的存在的left和right结点；
按照层序遍历的方式，把每一层的最后一个结点的值存入vector中，最后返回vector。
|
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 |
/** * 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: vector<int> rightSideView(TreeNode* root) { vector<int> v; queue<TreeNode*> q; if(root == NULL) return v; q.push(root); TreeNode* h; while(!q.empty()) { int size = q.size(); while(size--) { h = q.front(); q.pop(); if(h->left != NULL) q.push(h->left); if(h->right != NULL) q.push(h->right); } v.push_back(h->val); } return v; } }; |
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
分析：和层序遍历一样的代码，只需要加几行代码就行~~~因为要之字型存储这个二叉树~~~所以只不过在行数为双数的时候需要对当前行进行一次所有元素的倒置~可以用stack也可以用数组头尾两两交换的方法~~只需要在存入二维数组vector<vector> v之前倒置好row数组，再push_back到v里面就行~
|
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 42 43 44 45 46 |
/** * 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: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<int> row; vector<vector<int>> v; queue<TreeNode *> q; if(root == NULL) return v; q.push(root); TreeNode *temp; int lev = 0; while(!q.empty()) { int size = q.size(); while(size--) { temp = q.front(); q.pop(); row.push_back(temp->val); if(temp->left != NULL) { q.push(temp->left); } if(temp->right != NULL) { q.push(temp->right); } } if(lev % 2) { int n = row.size(); for(int i = 0; i < n/2; i++) { swap(row[i], row[n-i-1]); } } v.push_back(row); lev++; row.clear(); } return v; } }; |
再上一道POJ上面的题目：
POJ 3126-Prime Path-广度优先搜索bfs
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You do not know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
|
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <cmath> //sqrt()函数 using namespace std; int a, b; bool book[15000];//book用来标记该数字有没有使用过,book是标记的意思啦。 struct node { int num; int step; }; struct node queue[15000]; bool isprime(int x) { if (x == 2 || x == 3) return 1; else if (x % 2 == 0 || x <= 1) return 0; else if (x > 3) { for (int i = 3; i <= sqrt((double)x); i += 2) {//一开始直接写的sqrt(x),Compile Error 了，查了一下发现sqrt只支持 float double 和 long double 三个原型，果断改成了sqrt((double)x)。不过当然也可以用i * i <= x 啦。 if (x % i == 0) return 0; } } return 1; } void bfs() { int head = 0; int tail = 0; queue[tail].num = a; queue[tail].step = 0; book[a] = true; tail++; while (head < tail) { if (queue[head].num == b) { cout << queue[head].step << endl; return ; } int first = queue[head].num % 10; int second = queue[head].num / 10 % 10; //个位 for (int i = 1; i <= 9; i += 2) { //个位数如果是偶数一定是不符合的，所以这里写 i += 2 int c = queue[head].num / 10 * 10 + i; if (!book[c] && isprime(c) && c != queue[head].num) { queue[tail].num = c; queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊 book[c] = true; tail++; } } //十位 for (int i = 0; i <= 9; i++) { int c = queue[head].num / 100 * 100 + i * 10 + first; if (!book[c] && isprime(c) && c != queue[head].num) { queue[tail].num = c; queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊 book[c] = true; tail++; } } //百位 for (int i = 0; i <= 9; i++) { int c = queue[head].num / 1000 * 1000 + i * 100 + second * 10 + first; if (!book[c] && isprime(c) && c != queue[head].num) { queue[tail].num = c; queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊 book[c] = true; tail++; } } //千位 for (int i = 1; i <= 9; i++) { int c = queue[head].num % 1000 + i * 1000; if (!book[c] && isprime(c) && c != queue[head].num) { queue[tail].num = c; queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊 book[c] = true; tail++; } } head++; } cout << "Impossible" << endl; return ; } int main() { int n; cin >> n; while (n--) { cin >> a >> b; memset(book, false, sizeof(book)); bfs(); } return 0; } |
POJ 3278-Catch That Cow-广度优先搜索
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X – 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
|
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 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <queue> #include <memory.h> using namespace std; #define MAX 100005 queue<int> q; int step[MAX]; bool visit[MAX]; int n, k; int head, tail; int bfs() { q.push(n); step[n] = 0; visit[n] = 1; while (!q.empty()) { head = q.front(); q.pop(); for (int i = 0; i < 3; i++) { if(i == 0) tail = head - 1; else if (i == 1) tail = head + 1; else tail = head * 2; if (tail > MAX || tail < 0) continue; if (!visit[tail]) { q.push(tail); step[tail] = step[head] + 1; visit[tail] = 1; } if(tail == k) return step[tail]; } } return -1; } int main() { memset(visit, 0, sizeof(visit)); cin >> n >> k; if (n > k) { cout << n - k; } else { cout << bfs(); } return 0; } |
还有一道蓝桥杯上的题目：
学霸的迷宫-算法提高
问题描述
学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
第一行两个整数n， m，为迷宫的长宽。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
数据规模和约定
有20%的数据满足：1<=n,m<=10
有50%的数据满足：1<=n,m<=50
有100%的数据满足：1<=n,m<=500。
|
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <iostream> using namespace std; struct note { int x; int y; int f; int s; char dir; }; int main() { char a[501][501]; int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } getchar(); } int head = 1; int tail = 1; int book[501][501] = {0}; book[1][1] = 1; int next[4][2] = { {1, 0}, {0, -1}, {0, 1}, {-1, 0} }; int tx = 1; int ty = 1; struct note que[250001]; que[tail].x = 1; que[tail].y = 1; que[tail].f = 0; que[tail].s = 0; tail++; int flag = 0; while (head < tail) { for (int k = 0; k <= 3; k++) { tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; if (tx < 1 || tx > n || ty < 1 || ty > m) continue; if (a[tx][ty] == '0' && book[tx][ty] == 0) { book[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; que[tail].f = head; que[tail].s = que[head].s + 1; if (k == 0) que[tail].dir = 'D'; else if (k == 1) que[tail].dir = 'L'; else if (k == 2) que[tail].dir = 'R'; else if (k == 3) que[tail].dir = 'U'; tail++; } if (tx == n && ty == m) { flag = 1; break; } } if (flag == 1) { break; } head++; } cout << que[tail - 1].s << endl; char t[250001]; int temp = tail - 1; for (int i = que[tail - 1].s; i >= 1; i--) { t[i] = que[temp].dir; temp = que[temp].f; } for (int i = 1; i <= que[tail - 1].s; i++) { cout << t[i]; } return 0; } |