力扣题目训练（1）

2024年1月25日力扣题目训练 2024年1月25日力扣题目训练225. 用队列实现栈257. 二叉树的所有路径258. 各位相加81. 搜索旋转排序数组 II82. 删除排序链表中的重复元素 II30. 串联所有单词的子串

2024年1月25日力扣题目训练

2024年1月25日开始进行编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和苦难题1道。

225. 用队列实现栈

链接: 队列实现栈 难度： 简单 题目： 运行示例： 思路： 栈：先进后出 队列：先进先出 利用两个队列实现栈queue1，queue2，queue1用于存放先存入的数字，queue1与queue2实现栈，queque2先保存新进入的数字，然后再将queue1的数字存入到queue2中，再将queque2与queue1交换即可。 出栈直接从queue1中出栈。 代码：

class MyStack { public: queue<int> queue1; queue<int> queue2; MyStack() { } void push(int x) { queue2.push(x); while(!queue1.empty()){ queue2.push(queue1.front()); queue1.pop(); } swap(queue1,queue2); } int pop() { int r = queue1.front(); queue1.pop(); return r; } int top() { int r = queue1.front(); return r; } bool empty() { return queue1.empty(); } }; 257. 二叉树的所有路径

链接: 二叉树 难度： 简单 题目： 运行示例： 思路： 本质就是二叉树的遍历，用DFS算法即可解决。 代码：

class Solution { public: void dfs(TreeNode* root, string path, vector<string>& paths){ if(root != NULL){ path +=to_string(root->val); if(root->left == NULL && root->right == NULL){ paths.push_back(path); }else{ path += "->"; dfs(root->left,path,paths); dfs(root->right,path,paths); } }else{ return; } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; dfs(root, "", paths); return paths; } }; 258. 各位相加

链接: 各位相加 难度： 简单 题目： 运行示例： 思路： 我主要是利用暴力法解决的，官方是数学方法。

代码： 暴力法

class Solution { public: int addDigits(int num) { if(num >= 0 && num <= 9){ return num; } long sum = 0; while(num){ sum+=num%10; num /= 10; } return addDigits(sum); } };

数学法

class Solution: def addDigits(self, num: int) -> int: if num==0: return 0 if num%9==0: return 9 return num%9 81. 搜索旋转排序数组 II

链接: 旋转排序数组 难度： 中等 题目：

运行示例： 思路： 排序题一般是利用二分法，虽然这个数组是被旋转的但是基本上排序没有变，所以二分法还可以用，这个题中有重复元素，所以应该跳过。 代码：

class Solution { public: bool search(vector<int>& nums, int target) { int n = nums.size(); if (n == 0) { return false; } if (n == 1) { return nums[0] == target; } int begin = 0,end = n - 1; while(begin <= end){ int mid = (begin+end)/2; if(nums[mid] == target) return true; if(nums[begin] == nums[mid] && nums[mid] == nums[end]){ begin++; end--; }else if(nums[begin] <= nums[mid]){ if (nums[begin] <= target && target < nums[mid]) { end = mid - 1; }else{ begin = mid + 1; } }else{ if(nums[mid] < target && target <= nums[n-1]){ begin = mid + 1; }else{ end = mid - 1; } } } return false; } }; 82. 删除排序链表中的重复元素 II

链接: 排序链表 难度： 中等 题目：

运行示例： 思路： 因为链表已经排序，所以重复的数字是连续的，故一次遍历即可。 代码：

class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head){ return head; } ListNode* p= new ListNode(0, head); ListNode*curr = p; while(curr->next && curr->next->next){ if(curr->next->val == curr->next->next->val){ int x = curr->next->val; while(curr->next && curr->next->val == x){ curr->next = curr->next->next; } }else{ curr = curr->next; } } return p->next; } }; 30. 串联所有单词的子串

链接: 单词的子串 难度： 困难 题目： 运行示例：

思路： 哈希表+滑动窗口

代码：

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { int slen = s.size(); int wlen = words[0].size(); int wnum = words.size(); vector<int> ans; //建立哈希表 unordered_map<string ,int> hh; for(int i=0;i<wnum; i++){ hh[words[i]] = i+1; } //初始化答案数组 vector<int> tt(wnum); for(int i=0;i<wnum;i++){ tt[hh[words[i]]-1]++; } //分不同截取方式 for(int i=0;i<wlen;i++){ //记录不同单词数量 vector<int> nn(wnum); //开头位置计算 for(int j=i; j<wlen*wnum+i; j+=wlen){ string st = s.substr(j,wlen); if(hh[st]){ nn[hh[st]-1]++; } } if(nn==tt) ans.push_back(i); //滑动窗口 for(int j=i; j<slen-wlen*wnum; j+=wlen){ string sm = s.substr(j,wlen); string sp = s.substr(j+wlen*wnum, wlen); if(hh[sm]) nn[hh[sm]-1]--; if(hh[sp]) nn[hh[sp]-1]++; if(nn==tt) ans.push_back(j+wlen); } } return ans; } };