2020-10-21刷题

将一个链表的值插入vector,用递归实现

#include "util.h" using namespace std; //定义链表的节点 struct Listnode{ int val; Listnode* next; Listnode(int x):val(x),next(nullptr){//列表初始化 } }; void add_to_vector(Listnode* head, vector<int>& vec){ if (!head){ return; } vec.push_back(head->val); add_to_vector(head->next,vec); } int main() { //创建节点 Listnode a(1); Listnode b(2); Listnode c(3); Listnode d(4); Listnode e(5); //连接节点 a.next = &b; b.next = &c; c.next = &d; d.next = &e; vector<int> vec; add_to_vector(&a,vec); int i = 0; //遍历数组 for (;i<vec.size()-1;++i){ cout<< vec[i]<<"->"; } cout<<vec[i]<<endl; }

力扣78求子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路：主要使用回溯法。

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<int> item; vector<vector<int>> result; result.push_back(item); generate(0,nums,item,result); return result; } private: void generate(int i, vector<int>& nums, vector<int>& item, vector<vector<int>>& result){ if(i >= nums.size()){ return; } item.push_back(nums[i]); result.push_back(item); generate(i+1, nums,item,result); item.pop_back(); generate(i+1,nums,item,result); } };

思路;用位运算的方式实现：

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; int all_set = 1<<nums.size(); for(int i = 0;i<all_set;++i){ vector<int> item;//item在这里定义，因为每次都需要清零 for(int j = 0;j<nums.size();++j ){ if(i &(1<<j)){ item.push_back(nums[j]); } } result.push_back(item); } return result; } };

已知nums = [1,2,3],打印子集[1],[1,2][1,2,3]

用循环来实现代码实现如下： #include "util.h" using namespace std; int main() { vector<int> nums={1,2,3}; vector<int> item; vector<vector<int>> result; for (int i = 0; i < nums.size(); ++i) { item.push_back(nums[i]); result.push_back(item); } for (int i = 0; i < result.size(); ++i) { for (int j = 0; j < result[i].size(); ++j) { printf("[%d]",result[i][j]); } printf("\n"); } } 用递归代码来实现如下： #include "util.h" using namespace std; void generate (int i, vector<int>&nums,vector<int>&item,vector<vector<int>>& result){ //递归的出口 if (i >= nums.size()){ return; } item.push_back(nums[i]); result.push_back(item); generate(i+1,nums,item,result);//递归调用 } int main() { vector<int> nums={1,2,3}; vector<int> item; vector<vector<int>> result; generate(0,nums,item,result); for (int i = 0; i < result.size(); ++i) { for (int j = 0; j < result[i].size(); ++j) { printf("[%d]",result[i][j]); } printf("\n"); } }