Delayeddesire

#### C++ 代码(简单易懂的bfs版本)

// 使用层序遍历的方式序列化二叉树(bfs 版本)
/**
* 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:
string str;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root)                                  // 空树的情况
{
str += "null ";
return str;
}

queue<TreeNode*> q;
q.push(root);
while(q.size())
{
auto node = q.front();
q.pop();

if(node == nullptr) str += "null ";
else
{
str += (to_string(node->val) + ' ');
q.push(node->left);
q.push(node->right);
}
}

return str;
}

int getval(string& data, int cur, int next)
{
int val = 0;
if(data[cur] != '-')
for(int i = cur; i < next; ++i) val = val * 10 + data[i] - '0';
else
{
for(int i = cur + 1; i < next; ++i) val = val * 10 + data[i] - '0';
val = -val;
}

return val;
}
// Decodes your encoded data to tree.
// 思路：使用队列，从根节点开始，层层去构建二叉树的结点。
TreeNode* deserialize(string data) {
// 1. 先构建根节点
queue<TreeNode*> q;
auto root = new TreeNode(-1);
int cur = 0, next = 0;
while(next < data.size() && data[next] != ' ') next++;       // 此时 next 是第一个空格的位置
if(data[cur] == 'n') return nullptr;
else
{
int val = getval(data, cur, next);
root->val = val;
q.push(root);
}

// 2. 使用队列逐步向下一层扩展(bfs)
cur = next + 1;
next = cur;
while(q.size())
{
auto node = q.front();
q.pop();
if(node == nullptr) continue;

// 解析左节点，解析后链接
TreeNode* left = nullptr;
while(next < data.size() && data[next] != ' ') next++;
if(data[cur] != 'n')
{
int val = getval(data, cur, next);
left = new TreeNode(val);
}
node->left = left;
q.push(left);
cur = next + 1;
next = cur;

// 解析右结点,解析后链接
TreeNode* right = nullptr;
while(next < data.size() && data[next] != ' ') next++;
if(data[cur] != 'n')
{
int val = getval(data, cur, next);
right = new TreeNode(val);
}
node->right = right;
q.push(right);
cur = next + 1;
next = cur;
}

return root;
}
};


#### C++ 代码

/**
* 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:
string str;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
dfs(root);
return str;
}

// 使用前序遍历序列化二叉树
void dfs(TreeNode* root)
{
if(root == nullptr)            // 如果当前为空结点，那么将其序列化为 null;
{
str += "null ";
return;
}
else                           // 当前不为空结点时，将结点中的值序列化为相应的值
str +=  (to_string(root->val) + ' ');

dfs(root->left);                // 递归处理左子树
dfs(root->right);               // 递归处理右子树
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int cur = 0;
return d_dfs(data, cur);
}

TreeNode* d_dfs(string data, int& cur)
{
if(cur >= data.size()) return nullptr;                // 字符串解析完毕，直接返回null;

// 解析不同结点的字符串区间
int c = cur;                                          // 根节点字符串的区间[cur, c - 1]
while(c < data.size() && data[c] != ' ') c++;

if(data[cur] == 'n')
{
cur = c + 1;                                      // 当前为空结点，直接跳过处理下一个结点。
return nullptr;
}
else
{
auto root = new TreeNode(-1);

int val = 0;                                      // 处理正负数
if(data[cur] == '-')
{
for(int i = cur + 1; i < c; ++i) val = val * 10 + data[i] - '0';
val = -val;
}
else
for(int i = cur; i < c; ++i) val  = val * 10 + data[i] - '0';

root->val = val;

// 递归处理左子树，右子树
cur = c + 1;
root->left = d_dfs(data, cur);
root->right = d_dfs(data, cur);     // 在处理右子树的时候，cur 已经被改变过了(左子树 null 那一步改变的)
return root;
}
}
};
// 总结：本答案使用 "前序遍历" 序列化
// 本题难点在于对序列化后的字符串进行解析操作。对二叉树序列化的时候将空结点进行了 null 标记，这样才使得我们
// 可以利用一个序列构造出二叉树，因此，我们只需严格的按照 "根，左，右" 的方式一个值一个值(包括 null)来构建出
// 完整的二叉树。
// 实现细节: 在构建过程中由于全局只需要一个指针，利用指针严格的依次解析每一个值，因此我们对指针的传递使用引用传递。


11

#### C++ 代码(未使用库函数)

// 反转字符串的操作：
// 1. 先反转整个字符串。
// 2. 再逐个反转各个单词即可。
class Solution {
public:
string reverseWords(string s) {
if(!s.size()) return string();

// 1. 反转整个字符串
for(int i = 0, j = s.size() - 1; i <= j; i++, j--)
{
swap(s[i], s[j]);
}

// 2. 逐个反转各个单词
int k = 0;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] != ' ' && i != s.size() - 1) continue;          // 空格与字符串结尾都作为一个单词的结束。

int j = 0;
if(i != s.size() - 1) j = i - 1;                        // 当前为空格
else j = i;                                             // 当前为字符串结尾
while(k <= j)
{
swap(s[k], s[j]);
k++;
j--;
}

k = i + 1;                                              // 跳到下一个单词的首位置
}

return s;
}
};


#### C++ 代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

// 求出两个链表的长度
int lengthA = 0, lengthB = 0;
while(curA) {curA = curA->next; lengthA++;}
while(curB) {curB = curB->next; lengthB++;}

// 较长链表先走差值步
int n = abs(lengthA - lengthB);
if(lengthA > lengthB)
else

// 两个链表一起走
{
}

}
};


#### C++ 代码

// 快慢指针
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

first = first->next, second = second->next->next;  // 方便进入循环
while(first != second)
{
first = first->next;                           // 慢指针一次走一步
second = second->next->next;                   // 快指针一次走两步

if(!first || !second) return nullptr;          // 若没有环，则直接返回 nullptr
}

// 此时就是第一次的相遇点
while(first != second)
{
first = first->next;
second = second->next;
}

// 此时就是环入口
return second;
}
};


#### C++ 代码(简单易懂)

// 二叉树层序遍历的变形(null标记)
/**
* 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>> printFromTopToBottom(TreeNode* root) {
if(!root) return vector<vector<int>>();

vector<vector<int>> res;
vector<int> temp;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
int curnum = 0;                       // 统计当前二叉树的层数
while(q.size())
{
auto cur = q.front();
q.pop();
if(cur)
{
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
else
{
curnum++;
if(curnum % 2 == 1) res.push_back(temp);
else res.push_back(vector<int>(temp.rbegin(), temp.rend()));
temp.clear();
if(q.size())                  // 当前的null不是最后一个null继续加入，否则就不再加入null了。
q.push(nullptr);
}
}

return res;
}
};


#### C++ 代码

class Solution {
public:

vector<int> printMatrix(vector<vector<int> > matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return vector<int>();

vector<int> v;
int n = matrix.size(), m = matrix[0].size();

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<bool>> flags(n, vector<bool>(m, false));            // 标记已经走过的位置
int x = 0, y = 0;
int k = 1;                                                        // 起始方向为 "右"
for(int i = 0; i < m * n; ++i)
{
v.push_back(matrix[x][y]);
flags[x][y] = true;
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || flags[nx][ny])   // 当前位置出界，改变方向
{
k = (k + 1) % 4;
nx = x + dx[k], ny = y + dy[k];                           // 重新计算新坐标的位置
}

x = nx;                                                       // 合法坐标
y = ny;
}

return v;
}
};


#### C++ 代码

class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
// 判断边界条件
if(!pushV.size() && !popV.size()) return true;
int n = pushV.size();
int m = popV.size();
if(n != m) return false;

// 利用一个栈来模拟操作
stack<int> stk;
int i = 0, j = 0;
while(j < m)
{
if(stk.empty() || stk.top() != popV[j])
{
stk.push(pushV[i]);
++i;
}

if(stk.top() == popV[j])
{
stk.pop();
++j;
}
}

if(stk.empty())
return true;
else
return false;
}
};


#### C++ 代码

// 两栈实现一个队列(主栈，临时栈)
// 主栈：用来实现队列的基本操作
// 临时栈：当主栈操作 peek, pop 函数时，临时储存数据，操作完后再将数据拷贝到主栈中
class MyQueue {
public:
stack<int> s, t;
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
s.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
int n = s.size() - 1;           // 需要转移的个数
while(n--)
{
t.push(s.top());
s.pop();
}

int temp = s.top();
s.pop();

int m = t.size();
while(m--)
{
s.push(t.top());
t.pop();
}

return temp;
}

/** Get the front element. */
int peek() {
int n = s.size() - 1;           // 需要转移的个数
while(n--)
{
t.push(s.top());
s.pop();
}

int temp = s.top();

int m = t.size();
while(m--)
{
s.push(t.top());
t.pop();
}

return temp;
}

/** Returns whether the queue is empty. */
bool empty() {
return s.empty();
}
};

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/


### 算法1

#### C++ 代码

class Solution {
public:
int duplicateInArray(vector<int>& nums) {
// 判断边界条件
for(auto e : nums)
{
if(e < 0 || e > nums.size() - 1)
return -1;
}

// 哈希表统计数字个数
int n = nums.size();
unordered_map<int, int> hash(n);

for(auto e : nums)
{
hash[e]++;
if(hash[e] >= 2)
{
return e;
}
}

return -1;
}
};


### 算法2

#### C++ 代码

class Solution {
public:
int duplicateInArray(vector<int>& nums) {
// 判断边界条件
int n = nums.size();
for(auto e : nums)
{
if(e < 0 || e > n - 1)
return -1;
}

// 交换法
for(int i = 0; i < n; ++i)
{
while(i != nums[i] && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
if(i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];
}

return -1;
}
};