2905

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
*     int val;
*     ListNode *next, *random;
*     ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
map<ListNode *, ListNode *> m;
m[NULL] = NULL;
ListNode * t , *t1, *h, *h1;
h1 = h;
t = new ListNode(0);
t1 = t;
//cout << "1" <<endl;
while(h1){
ListNode * temp = new ListNode(h1->val);
m[h1] = temp;
t1->next = temp;

h1 = h1->next;
t1 = t1->next;
//cout << m[h1] << " ";
}
t1 = t->next;
h1 = h;
while(h1){
t1->random = m[h1->random];
h1 = h1->next;
t1 = t1->next;
//cout << m[h1->random] << " ";
}
return t->next;
}
};

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* 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>> res;
vector<int> temp;
vector<vector<int>> findPath(TreeNode* root, int sum) {
if(root == NULL) return res;
dfs(root,sum);
return res;
}
void dfs(TreeNode * r, int sum){
if(r->left == NULL && r->right == NULL){
sum -= r->val;
temp.push_back(r->val);
if(sum == 0){
res.push_back(temp);
}
//回溯
temp.pop_back();
return ;
}
//非叶子节点
sum -= r->val;
temp.push_back(r->val);
if(r->left) dfs(r->left,sum);
if(r->right) dfs(r->right,sum);
temp.pop_back();
return ;
}
};

8个月前

#### 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:
vector<vector<int>> res;
vector<int> temp;
vector<vector<int>> findPath(TreeNode* root, int sum) {
if(root == NULL) return res;
dfs(root,sum);
return res;
}
void dfs(TreeNode * r, int sum){
if(r->left == NULL && r->right == NULL){
sum -= r->val;
temp.push_back(r->val);
if(sum == 0){
res.push_back(temp);
}
//回溯
temp.pop_back();
return ;
}
//非叶子节点
sum -= r->val;
temp.push_back(r->val);
if(r->left) dfs(r->left,sum);
if(r->right) dfs(r->right,sum);
temp.pop_back();
return ;
}
};

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* 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:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == NULL) return "#!";

string res = "";

res += to_string(root->val);
res += "!";

res += serialize(root->left);
res += serialize(root->right);
return res;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//cout <<data<<endl;
queue<string> q;
string temp = "";

for(int i = 0 ; i < data.size(); i ++){
if(data[i] != '!'){
temp += data[i];
}
else{
q.push(temp);
//cout <<temp<<" ";
temp = "";
}
}

return buildtree(q);
}
TreeNode * buildtree(queue<string> &q){
string temp = q.front();
q.pop();

if(temp == "#"){
return NULL;
}
else{
TreeNode * t = new TreeNode(stoi(temp));
t->left = buildtree(q);
t->right = buildtree(q);
return t;
}
}
};

8个月前

## 正反序列化 C++代码

#### 对于处理负数的问题，我只想说使用库函数，省时省力考虑还周全，何乐而不为？

class Solution {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == NULL) return "#!";

string res = "";

res += to_string(root->val);
res += "!";

res += serialize(root->left);
res += serialize(root->right);
return res;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//cout <<data<<endl;
queue<string> q;
string temp = "";

for(int i = 0 ; i < data.size(); i ++){
if(data[i] != '!'){
temp += data[i];
}
else{
q.push(temp);
//cout <<temp<<" ";
temp = "";
}
}

return buildtree(q);
}
TreeNode * buildtree(queue<string> &q){ //注意此处的引用
string temp = q.front();
q.pop();

if(temp == "#"){
return NULL;
}
else{
TreeNode * t = new TreeNode(stoi(temp));
t->left = buildtree(q);
t->right = buildtree(q);
return t;
}
}
};

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
vector<int> s;
bool verifySequenceOfBST(vector<int> sequence) {
s = sequence;
return fun(0,s.size()-1);
}
bool fun(int l, int r){
if(r-l <= 1)return true;
int mid = s[r];
//int flag = 0;
for(int i = l ; i < r; i++){
if(s[i] < mid) continue;
else{//s[i] > mid
for(int j = i ; j < r; j++){
if(s[j] < mid){
return false;
}
}
return fun(l,i-1)&&fun(i,r-1);
}
}
return fun(l,r-1);
}
};

8个月前

#### C++ 代码

class Solution {
public:
vector<int> s;
bool verifySequenceOfBST(vector<int> sequence) {
s = sequence;
return fun(0,s.size()-1);
}
bool fun(int l, int r){
if(r-l <= 1)return true;
int mid = s[r];
//int flag = 0;
for(int i = l ; i < r; i++){
if(s[i] < mid) continue;
else{//s[i] > mid
for(int j = i ; j < r; j++){
if(s[j] < mid){
return false;
}
}
return fun(l,i-1)&&fun(i,r-1);
}
}
return fun(l,r-1);
}
};

8个月前

#### C++ 代码 姑且称之为遍历即可

class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
if(matrix.size() == 0 || matrix[0].size() == 0) return res;
int n = matrix.size();  // 行
int m = matrix[0].size(); //列

vector<vector<bool>> b(n,vector<bool>(m,false));

int d[4][2] = {
{0,1}, //right
{1,0}, // down
{0,-1}, //left
{-1,0} //up
};

int x = 0 , y = 0;
int k = 0; //k:0-3

res.push_back(matrix[0][0]);
b[0][0] = true;

for(int i = 0; i < m*n - 1; i++){
x += d[k][0];
y += d[k][1];

if(x >= 0 && x < n && y >= 0 && y < m && (!b[x][y])){
res.push_back(matrix[x][y]);
b[x][y] = true;
}
else{//回退
x -= d[k][0];
y -= d[k][1];
k = (k + 1) % 4;
i--;
}
}

return res;
}
};

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
if(matrix.size() == 0 || matrix[0].size() == 0) return res;
int n = matrix.size();  // 行
int m = matrix[0].size(); //列

vector<vector<bool>> b(n,vector<bool>(m,false));

int d[4][2] = {
{0,1}, //right
{1,0}, // down
{0,-1}, //left
{-1,0} //up
};

int x = 0 , y = 0;
int k = 0; //k:0-3
res.push_back(matrix[0][0]);
b[0][0] = true;

for(int i = 0; i < m*n - 1; i++){
x += d[k][0];
y += d[k][1];

if(x >= 0 && x < n && y >= 0 && y < m && (!b[x][y])){
res.push_back(matrix[x][y]);
b[x][y] = true;
}
else{
x -= d[k][0];
y -= d[k][1];
k = (k + 1) % 4;
i--;
}
}
return res;
}
};

8个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* 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) {

queue<TreeNode *> q;
vector<vector<int>> res;
vector<int> temp;

if(root == NULL) return res;
q.push(root);
q.push(NULL);

while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t){//t != NULL
temp.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
else{ //t == NULL
res.push_back(temp);
temp.clear();
if(!q.empty()) q.push(NULL);
}
}
//翻转奇数行
for(int i = 0; i < res.size(); i++){
if(i%2 == 1){//翻转res[i][0] ---res[i][k]
int j = 0;
int k = res[i].size() - 1;
while(j < k){
swap(res[i][j++],res[i][k--]);
}
}
}
return res;
}
};