牛客网刷题2

目录

• 前言
• 正文
• • 1. 复杂链表的复制
  • 2.字符串的排列
  • 3.数组中出现次数超过一半的数字
  • 4. 两个链表的第一个公共结点
  • 5. 二叉树的深度
  • 6. 平衡二叉树
  • 7. 和为S的连续正数序列
  • 8.扑克牌顺子
  • 9. 求1+2+3+...+n
  • 数组中重复的数字
  • 构建乘积数组

前言

正文

1. 复杂链表的复制

题目

code

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:unordered_map<RandomListNode*,RandomListNode*> map;RandomListNode* Clone(RandomListNode* head) {if(head==nullptr)return nullptr;RandomListNode* node = head;while(node)//先利用map创建好所有的节点{map[node] = new RandomListNode(node->label);node= node->next;}node = head;while(node)//利用原来的节点，对这些Map做好链接{map[node]->next = map[node->next];map[node]->random = map[node->random];node = node->next;}return map[head];//我只要把新创建的头结点返回就可以了}
};

思路
这题主要的关键点，就在与你懂不懂得用Map这个数据结构。以及，懂不懂得用这个去构建这个ListNode.

2.字符串的排列

题目

code

class Solution {
public:set<string> tempRes;//为了剔除掉重复的，所以用setvector<string> Permutation(string str) {vector<string> strOut;if(str.size()==0)return strOut;Recursion(str,0);for(auto x:tempRes){strOut.push_back(x);}return strOut;}/*void swap(string str,int r,int k){char temp = str[k];str[k] = str[r];str[r] = temp;}*/void Recursion(string str,int index){if(index==str.size()-1)//这个只是为了把最后一个也放进去，然后回溯的时候就会把该放的放进去tempRes.insert(str);for(int i = index;i<str.size();i++){swap(str[index],str[i]);Recursion(str,index+1);}}};

思路
之前理解了，现在又给忘了，证明这题的递归方法是真的很抽象，很难理解。

全排列的一个题目
code

#include<iostream>
using namespace std;
int result[1000];		//结果存放到result数组中。
int visited[1000];      //用于表示某个数是否被用了，如visited[1]==1，说明1被用了
void print(int k) {		//输出函数，输出结果for (int i = 1; i <= k; i++) {cout << result[i] << " ";}cout << endl;
}  
void search(int k) {		//k表示搜索深度，也就是全排列中的第几个数for (int i = 1; i <= 4; i++) {if (visited[i] == 0) {		//for嵌套if：用于判断每个位置可以用哪些数，比如第一个位置可用1234，若选了1，就把visited[1]置为1,下一层搜索。就只剩下234了visited[i] = 1;result[k] = i;if (k == 4)    //找到四个数，就调用输出函数print(k);else {       //否则就搜索下一个数search(k + 1);}visited[i] = 0;		//把i恢复为0，从整体来看，之前把i置1，不管递归调用了多少次，这里的i还是没变对吧，现在把i置0，就实现了一个后退的效果}}
}
int main() {int array[4]={1,2,3,4};   //求这四个数字的全排列。search(1);				//从第一个数开始找return 0;
}

3.数组中出现次数超过一半的数字

题目

code

class Solution {
public:map<int,int> map;int MoreThanHalfNum_Solution(vector<int> num) {if(num.size()==1)return num[0];for(int i =0;i<num.size();i++){map[num[i]]++;}int result = 0;for(int j = 0;j<num.size();j++){if(map[num[j]]>(num.size()/2))result = num[j];}return result;}
};

思路
这题难度还是不大的，就用map做个映射，基本就解决了。

4. 两个链表的第一个公共结点

题目

code

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* head1, ListNode* head2) {if(head1==nullptr||head2 ==nullptr)return nullptr;ListNode *node1 = head1;ListNode *node2 = head2;while(node1!=node2){node1=node1?node1->next:head2;//注意head1代表是第一个链表的非公共部分node2=node2?node2->next:head1;//head2代表的是第二个链表的非公共部分}return node1;}
};

思路
这题的重点，应该是要理解好题意，知道题目给的链表代表的意思是什么。再开始写。

5. 二叉树的深度

题目

方法一：递归
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {if(!root)return 0;int lVal = TreeDepth(root->left);int rVal = TreeDepth(root->right);return max(lVal,rVal)+1;}
};

方法二：队列
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {if(!root)return 0;queue<TreeNode *> q;q.push(root);int level = 0;while(!q.empty()){int size = q.size();while(size--)//若队列还有元素，则证明是还有一层要往上加的{auto node = q.front();q.pop();if(node->left)q.push(node->left);if(node->right)q.push(node->right); }level +=1;}return level;}
};

6. 平衡二叉树

题目

7. 和为S的连续正数序列

题目

code

class Solution {
public:vector<vector<int> > FindContinuousSequence(int sum) {//其实就是滑动窗口的这种题目，只要理解了题意，一般难度就不会很大int tmp = 0;int l = 1;int r = 1;vector<int> path;vector<vector<int>> ret;while(l<=sum/2){if(tmp<sum){tmp+=r;r++;}else if(tmp>sum){tmp-=l;l++;}else{for(int i = l;i<r;i++){path.push_back(i);}ret.push_back(path);path.clear();tmp-=l;++l;}}return ret;}
};

8.扑克牌顺子

题目

code

class Solution {
public:bool IsContinuous( vector<int> num ) {//我这边的想法是：只要最大数-除0外的最小数的值小于等于6，应该都是可以的。if(num.size()==0)return false;int max;int min;int j;map<int,int> map;for(int k =0;k<num.size();k++){map[num[k]]++;if(num[k]!=0&&map[num[k]]>=2)return false;}for(int j = 0;j<num.size();j++){if(num[j]!=0){max = num[j];min = num[j];    break;}}for(int i = j+1;i<num.size();i++){if(num[i]!=0&&num[i]>max)max = num[i];if(num[i]!=0&&num[i]<min)min = num[i];}if(max-min<5)return true;return false;}
};

9. 求1+2+3+…+n

题目

code

class Solution {
public:int Sum_Solution(int n) {bool x = n>1&&(n+=Sum_Solution(n-1));return n;}
};

数组中重复的数字

题目

code

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int duplicate(vector<int>& numbers) {sort(numbers.begin(),numbers.end());for(int i = 1;i<numbers.size();i++){if(numbers[i-1]==numbers[i])//判断是否有相邻的树相等，若是相等，就有重复的数return numbers[i];}return -1;}
};

题解
这个还是比较巧的一种办法，就是简单排个序，然后依靠排序后的性质，通过是否有相同的数字是重复，来知道是否有重复的数字。

构建乘积数组

题目

code

class Solution {
public:vector<int> multiply(const vector<int>& A) {vector<int> B(A.size());for(int i =0;i<A.size();i++){int sum = 1;for(int j = 0;j<A.size();j++){if(j!=i){sum*=A[j];}}B[i] = sum;}return B;}};

题解
这个方法属于比较暴力的方法。

牛客网刷题2

目录

• 前言
• 正文
• • 1. 复杂链表的复制
  • 2.字符串的排列
  • 3.数组中出现次数超过一半的数字
  • 4. 两个链表的第一个公共结点
  • 5. 二叉树的深度
  • 6. 平衡二叉树
  • 7. 和为S的连续正数序列
  • 8.扑克牌顺子
  • 9. 求1+2+3+...+n
  • 数组中重复的数字
  • 构建乘积数组

前言

正文

1. 复杂链表的复制

题目

code

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {
public:unordered_map<RandomListNode*,RandomListNode*> map;RandomListNode* Clone(RandomListNode* head) {if(head==nullptr)return nullptr;RandomListNode* node = head;while(node)//先利用map创建好所有的节点{map[node] = new RandomListNode(node->label);node= node->next;}node = head;while(node)//利用原来的节点，对这些Map做好链接{map[node]->next = map[node->next];map[node]->random = map[node->random];node = node->next;}return map[head];//我只要把新创建的头结点返回就可以了}
};

思路
这题主要的关键点，就在与你懂不懂得用Map这个数据结构。以及，懂不懂得用这个去构建这个ListNode.

2.字符串的排列

题目

code

class Solution {
public:set<string> tempRes;//为了剔除掉重复的，所以用setvector<string> Permutation(string str) {vector<string> strOut;if(str.size()==0)return strOut;Recursion(str,0);for(auto x:tempRes){strOut.push_back(x);}return strOut;}/*void swap(string str,int r,int k){char temp = str[k];str[k] = str[r];str[r] = temp;}*/void Recursion(string str,int index){if(index==str.size()-1)//这个只是为了把最后一个也放进去，然后回溯的时候就会把该放的放进去tempRes.insert(str);for(int i = index;i<str.size();i++){swap(str[index],str[i]);Recursion(str,index+1);}}};

思路
之前理解了，现在又给忘了，证明这题的递归方法是真的很抽象，很难理解。

全排列的一个题目
code

#include<iostream>
using namespace std;
int result[1000];		//结果存放到result数组中。
int visited[1000];      //用于表示某个数是否被用了，如visited[1]==1，说明1被用了
void print(int k) {		//输出函数，输出结果for (int i = 1; i <= k; i++) {cout << result[i] << " ";}cout << endl;
}  
void search(int k) {		//k表示搜索深度，也就是全排列中的第几个数for (int i = 1; i <= 4; i++) {if (visited[i] == 0) {		//for嵌套if：用于判断每个位置可以用哪些数，比如第一个位置可用1234，若选了1，就把visited[1]置为1,下一层搜索。就只剩下234了visited[i] = 1;result[k] = i;if (k == 4)    //找到四个数，就调用输出函数print(k);else {       //否则就搜索下一个数search(k + 1);}visited[i] = 0;		//把i恢复为0，从整体来看，之前把i置1，不管递归调用了多少次，这里的i还是没变对吧，现在把i置0，就实现了一个后退的效果}}
}
int main() {int array[4]={1,2,3,4};   //求这四个数字的全排列。search(1);				//从第一个数开始找return 0;
}

3.数组中出现次数超过一半的数字

题目

code

class Solution {
public:map<int,int> map;int MoreThanHalfNum_Solution(vector<int> num) {if(num.size()==1)return num[0];for(int i =0;i<num.size();i++){map[num[i]]++;}int result = 0;for(int j = 0;j<num.size();j++){if(map[num[j]]>(num.size()/2))result = num[j];}return result;}
};

思路
这题难度还是不大的，就用map做个映射，基本就解决了。

4. 两个链表的第一个公共结点

题目

code

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* head1, ListNode* head2) {if(head1==nullptr||head2 ==nullptr)return nullptr;ListNode *node1 = head1;ListNode *node2 = head2;while(node1!=node2){node1=node1?node1->next:head2;//注意head1代表是第一个链表的非公共部分node2=node2?node2->next:head1;//head2代表的是第二个链表的非公共部分}return node1;}
};

思路
这题的重点，应该是要理解好题意，知道题目给的链表代表的意思是什么。再开始写。

5. 二叉树的深度

题目

方法一：递归
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {if(!root)return 0;int lVal = TreeDepth(root->left);int rVal = TreeDepth(root->right);return max(lVal,rVal)+1;}
};

方法二：队列
code

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:int TreeDepth(TreeNode* root) {if(!root)return 0;queue<TreeNode *> q;q.push(root);int level = 0;while(!q.empty()){int size = q.size();while(size--)//若队列还有元素，则证明是还有一层要往上加的{auto node = q.front();q.pop();if(node->left)q.push(node->left);if(node->right)q.push(node->right); }level +=1;}return level;}
};

6. 平衡二叉树

题目

7. 和为S的连续正数序列

题目

code

class Solution {
public:vector<vector<int> > FindContinuousSequence(int sum) {//其实就是滑动窗口的这种题目，只要理解了题意，一般难度就不会很大int tmp = 0;int l = 1;int r = 1;vector<int> path;vector<vector<int>> ret;while(l<=sum/2){if(tmp<sum){tmp+=r;r++;}else if(tmp>sum){tmp-=l;l++;}else{for(int i = l;i<r;i++){path.push_back(i);}ret.push_back(path);path.clear();tmp-=l;++l;}}return ret;}
};

8.扑克牌顺子

题目

code

class Solution {
public:bool IsContinuous( vector<int> num ) {//我这边的想法是：只要最大数-除0外的最小数的值小于等于6，应该都是可以的。if(num.size()==0)return false;int max;int min;int j;map<int,int> map;for(int k =0;k<num.size();k++){map[num[k]]++;if(num[k]!=0&&map[num[k]]>=2)return false;}for(int j = 0;j<num.size();j++){if(num[j]!=0){max = num[j];min = num[j];    break;}}for(int i = j+1;i<num.size();i++){if(num[i]!=0&&num[i]>max)max = num[i];if(num[i]!=0&&num[i]<min)min = num[i];}if(max-min<5)return true;return false;}
};

9. 求1+2+3+…+n

题目

code

class Solution {
public:int Sum_Solution(int n) {bool x = n>1&&(n+=Sum_Solution(n-1));return n;}
};

数组中重复的数字

题目

code

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int duplicate(vector<int>& numbers) {sort(numbers.begin(),numbers.end());for(int i = 1;i<numbers.size();i++){if(numbers[i-1]==numbers[i])//判断是否有相邻的树相等，若是相等，就有重复的数return numbers[i];}return -1;}
};

题解
这个还是比较巧的一种办法，就是简单排个序，然后依靠排序后的性质，通过是否有相同的数字是重复，来知道是否有重复的数字。

构建乘积数组

题目

code

class Solution {
public:vector<int> multiply(const vector<int>& A) {vector<int> B(A.size());for(int i =0;i<A.size();i++){int sum = 1;for(int j = 0;j<A.size();j++){if(j!=i){sum*=A[j];}}B[i] = sum;}return B;}};

题解
这个方法属于比较暴力的方法。