Code – 第237页

LeetCode 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里面就行～

/**
 * 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;
    }
};

/**

* 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;

}

};

LeetCode199. 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～

/**
 * 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;
    }
};

/**

* 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;

}

};

LeetCode上Tag为广度优先搜索BFS(Breadth-first Search)的题目整理

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比较。

/**
 * 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;
        
    }
};

/**

* 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。

/**
 * 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;
    }
};

/**

* 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++;
和上一题层序遍历相似，只是在层序遍历的过程中加入了判断是否已经是叶子结点。如果是叶子结点就直接返回当前的层数~

/**
 * 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;
    }
};

/**

* 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，说明此时该层就为该数最少需要的平方和数字的个数~~

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;
    }
};

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。

/**
 * 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;
    }
};

/**

* 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里面就行~

/**
 * 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;
    }
};

/**

* 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

#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;
}

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.

#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;
}

#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。

#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;
}

#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;

}

【汇编】JMP跳转指令的指令长度、直接转移与间接转移、段内跳转与段间跳转

指令长度=操作码的长度+操作数地址的长度
1.段内跳转
JMP指令占1个字节。
操作数的地址长度 = （目标地址-指令当前地址）//若能用1个字节表示，则占用1个字节,那么整体指令长度为2个字节;若需2个字节表示，则占用2个字节，此时整体指令为3个字节。
比如：
0113 jmp 0185 ;0185h-0113h=72h，72h可用1个字节表示，加上JMP的一个字节，一共指令长度为2个字节；
0113 jmp 0845 ;0845h-0113h=732h，732h需用2个字节表示，加上JMP的一个字节，一共指令长度为3个字节。

2、段间跳转
指令长度为5字节。如jmp 1234:5678，整体指令长度为5.

直接转移 IP = 位移量 + 指令长度
间接转移 IP = 寻址方式求出的EA(有效地址)的值

直接转移中
短转移JMP SHORT OPR 8位位移量
位移量需要满足前后跳转的需要，所以是一个带符号数 转移格式只允许在-128~127之间转移
近转移JMP NEAR PTR OPR 16/32位位移量
16位在实模式下段长为64KB，所以16位位移量可以转移到段内的任一个位置

LeetCode 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

分析：用两个指针ij从头开始遍历字符串。ij分别表示最长字串的首尾下标。如果第j个与i与j当中的某处k重复，那么只需i从k+1开始继续判断是否有重复的就好。当然，在i++一直到k的过程中，不要忘记把已经收录的字符存在标记为不存在。所以用一个book数组标记该字符在i~j当中是否出现过。每一次找到重复的字符的时候判断j-i是否比最大值大。一个特例是，如果i~j中一直让j到了最后一个字符都没有重复但是此时的j-i是最长的长度，所以要在return语句前再加上一句判断j-i的大小是否比当前maxlen大。因为i和j都只遍历了字符串一次，所以时间复杂度为O(n)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0, len = s.length();
        int maxlen = 0;
        int book[256] = {0};
        while(j < len) {
            if(book[s[j]] == 1) {
                maxlen = max(maxlen, j - i);
                while(s[i] != s[j]) {
                    book[s[i]] = 0;
                    i++;
                }
                i++;
            } else {
                book[s[j]] = 1;
            }
            j++;
        }
        maxlen = max(maxlen, j - i);
        return maxlen;
    }
};

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int i = 0, j = 0, len = s.length();

int maxlen = 0;

int book[256] = {0};

while(j < len) {

if(book[s[j]] == 1) {

maxlen = max(maxlen, j - i);

while(s[i] != s[j]) {

book[s[i]] = 0;

i++;

}

i++;

} else {

book[s[j]] = 1;

}

j++;

}

maxlen = max(maxlen, j - i);

return maxlen;

}

};

LeetCode上Tag为贪心算法(Greedy)的题目整理

330. Patching Array
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.
题目大意：
给一个有序非负整数列nums和一个整数n，最少需要添加多少个数可以使得[1,n]间的每一个数都可以被数列中若干个数的和来表示。输出最小需要添加多少个数字。
分析：
假设[0,t)是暂时能够满足题意的区间，当t<=n的时候，对于每下一个nums[i]：
0.如果nums[i]比t小，那么[0,t)区间内的每一个数加上nums[i]后，区间就被扩展为[0,t+nums[i])了。
1.如果nums[i]比t大，那么必须要加入一个数才能满足扩展区间后的连续性。能加入的这个数当然是越大越好，但是不能超过t，因为超过t的话就会有t之后这个数之前的区间不满足。所以可以令t=t+t，这是它能扩展的最大区间了。此时用cnt计数，cnt+1表示加入了一个数（这个数是t）。
注意点：一开始全都用的int结果在测试用例Last executed input:[1,2,31,33] 2147483647 这个用例下面超时了
后来机智的想了一下发现是如果t当前的值很大又执行了t = t + t会溢出导致t变成了一个很小的值，然后再while肯定超时啦。
所以把int t = 1改为long long int类型就AC啦。啦啦啦。

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int len = nums.size();
        long long int t = 1;
        int cnt = 0;
        int i = 0;
        while(t <= n) {
            if(i < len && nums[i] <= t) {
                t = t + nums[i];
                i++;
            } else {
                t = t + t;
                cnt++;
            }
        }
        return cnt;
    }
};

class Solution {

public:

int minPatches(vector<int>& nums, int n) {

int len = nums.size();

long long int t = 1;

int cnt = 0;

int i = 0;

while(t <= n) {

if(i < len && nums[i] <= t) {

t = t + nums[i];

i++;

} else {

t = t + t;

cnt++;

}

return cnt;

}

};

134. Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
分析：
gas[i] – cost[i]为车行驶的代价。要想能走完一圈，必须时刻保持从出发点到终点始终行驶代价总和temp >= 0
0.假设从0开始出发，累积temp0一直是>=0的。到点A的时候发现<0了。此时可以想：从0~A的temp0小于0，而前面的0~某点的代价总和一直是>=0的，所以可以得知前面任何一点都不能作为出发点了，因为temp0 – 0~某点的代价总是小于0的不满足题意。所以只能从下一个结点开始尝试。
1.从A+1结点开始出发，累积temp1一直是>=0的。到点B的时候发现<0了。此时可以想：从A+1 ~ B的temp1小于0，那么前面的A+1到某点的代价总和一直是>=0的，所以可以得知前面任何一点都不能作为出发点了，因为temp1 – A+1~某点的代价总是小于0不和题意的。所以就从下一点开始尝试….
2.终于有一次可以从D开到n-1这个点了。只要看能不能车再从0开到D-1了。也就是想看temp2+temp0+temp1的过程中可不可能总代价小于0.结论是只要所有点总代价total>=0，那么一定可以开一圈。可以这么证明：total>=0 temp0 和temp1都是在最后一个点game over的前面都是正数那么ok，最后一个数是导致<=0的点，但是去掉了temp0这个负数，总代价毫无疑问还是大于0的不用说。所以说最后只要total>=0那么就一定可以走结束一圈。啊哦- -我竟然说了这么多=_=

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if(gas.empty())
            return -1;
        int total = 0, temp = 0, index = 0;
        for(int i = 0; i < gas.size(); i++) {
            total += gas[i] - cost[i];
            if(temp >= 0) {
                temp += gas[i] - cost[i];
            } else {
                temp = gas[i] - cost[i];
                index = i;
            }
        }
        return total >= 0 ? index : -1;
    }
};

class Solution {

public:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

if(gas.empty())

return -1;

int total = 0, temp = 0, index = 0;

for(int i = 0; i < gas.size(); i++) {

total += gas[i] - cost[i];

if(temp >= 0) {

temp += gas[i] - cost[i];

} else {

temp = gas[i] - cost[i];

index = i;

}

return total >= 0 ? index : -1;

}

};

55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
题目解释：
从下标为0的地方开始，A[i]表示当前i处能够跳跃的最大长度。（也就是也就是i处最远能跳到下标i + nums[i]处。）判断能不能跳啊跳到最后一个下标的地方。
分析：设立distance为当处在i下标的时候，前面所能够达到的所有长度的最大值（因为是最大值，所以0~最大值的所有下标都可以遍历到），当i <= distance的所有下标都可以遍历，然后更新distance的值为distance = max(distance, i + nums[i]);
最后判断能够最远到达的distance是否够的到最后一个下标n-1，不能的话返回false，能的话返回true

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int distance = 0;
        for(int i = 0; i < nums.size() - 1 && i <= distance; i++) {
            distance = max(distance, i + nums[i]);
        }
        return distance >= (nums.size() - 1);
    }
};

class Solution {

public:

bool canJump(vector<int>& nums) {

int distance = 0;

for(int i = 0; i < nums.size() - 1 && i <= distance; i++) {

distance = max(distance, i + nums[i]);

}

return distance >= (nums.size() - 1);

}

};

122. Best Time to Buy and Sell Stock II
My Submissions QuestionEditorial Solution
Total Accepted: 83388 Total Submissions: 198240 Difficulty: Medium
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
分析：贪心算法，在每一小段上升序列中最大差值累加得到结果。就是说在股票价格处于上升期的时候，在最低点买入，在最高点卖出。而且可知，每一小段的最大差值就是这段序列的最后一个点的价格减去这段序列第一个点的价格，与每一次从第一个点与第二点的差值一直累加所得结果相同：ans += prices[i] – prices[i – 1];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int ans = 0;

for(int i = 1; i < prices.size(); i++) {

if(prices[i] > prices[i - 1])

ans += prices[i] - prices[i - 1];

}

return ans;

}

};