#include<iostream> #include<sstream> #include<vector> std::vector<int> split(std::string& str, char delim = ' ') { std::stringstream ss(str); std::string tempStr; std::vector<int> vector; while (getline(ss, tempStr, delim)) { vector.push_back(atoi(tempStr.c_str())); } return vector; } int main() { std::string ret; int ans = 0; while (getline(std::cin, ret, ' ')) { std::vector<int> vector = split(ret); ans = vector[0] + vector[1]; std::cout << ans << std::endl; } return 0; }
3. 无重复字符的最长子串
#include <iostream> #include <unordered_set> class Solution { public: int lengthOfLongestSubstring(std::string s) { int length = s.size(); int maxLength = 0; int lastMaxLength = 0; std::unordered_set<char> unorderedSet; //std::set<int> set; for (int i = 0; i < length; ++i) { unorderedSet.clear(); for (int j = i; j < length; ++j) { if (unorderedSet.find(s[j]) != unorderedSet.end()) { break; } unorderedSet.insert(s[j]); int nowLength = unorderedSet.size(); maxLength = nowLength > lastMaxLength ? nowLength : lastMaxLength; } lastMaxLength = maxLength; } return maxLength; } };
49. 字母异位词分组
#include <iostream> #include <vector> #include <unordered_set> #include <map> #include <algorithm> /* 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] */ class Solution { public: std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) { std::map<std::string, std::vector<std::string>> map; for (auto ss: strs) { std::string value = ss; std::sort(ss.begin(), ss.end()); map[ss].push_back(value); } std::vector<std::vector<std::string>> ret; for (auto it = map.begin(); it != map.end(); it++) { ret.push_back(it->second); } return ret; } };
86. 分隔链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* small = new ListNode(0); ListNode* smallHead = small; ListNode* large = new ListNode(0); ListNode* largeHead = large; while (head != nullptr) { if (head->val < x) { small->next = head; small = small->next; } else { large->next = head; large = large->next; } head = head->next; } large->next = nullptr; small->next = largeHead->next; return smallHead->next; } };
16. 最接近的三数之和
错误代码：这个思路会少算很多可能性！！！
class Solution { public: int threeSumClosest(std::vector<int>& nums, int target) { if (nums.size() < 3) { return 0; } std::sort(nums.begin(), nums.end()); int start = 0; int end = nums.size() - 1; int sum = 0; int ans = nums[0] + nums[1] + nums[2]; while (start < end) { //这里会少算很多可能性，这里只是计算了，s,s+1,e这种可能性，并没有算s+2,s+3,..的可能性，复杂度低了，但是结果就不对了，所以因此应该在外面再加一层循环，确保每一种可能性都被计算到 sum = nums[start] + nums[start + 1] + nums[end]; if(std::abs(target - sum) < std::abs(target - ans)) ans = sum; if (sum < target) { start++; } else if (sum > target) { end--; } else { return ans; } } return ans; }
正确代码：
class Solution { public: int threeSumClosest(std::vector<int>& nums, int target) { std::sort(nums.begin(), nums.end()); int s = 0; int e = nums.size() - 1; int ans = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.size(); ++i) { s = i + 1;//在这里更新s，保证s可以中开始---一直跳到--->结尾 e = nums.size() - 1;//e每次都要更新，因为可能在while循环中更新了e while (s < e) { int sum = nums[i] + nums[s] + nums[e]; if (std::abs(target - ans) > std::abs(target - sum)) ans = sum; if (sum == target) return sum; if (sum < target) s++; if (sum > target) e--; } } return ans; } };
27. 移除元素
#include <vector> class Solution { public: int removeElement(std::vector<int>& nums, int val) { int left = 0; //最终目标：保证(0, left)区间内一个val都没有 for (int right = 0; right < nums.size(); ++right) { if (nums[right] != val) { nums[left] = nums[right]; left++; } } return left; } };
641. 设计循环双端队列
#include <vector> class MyCircularDeque { private: std::vector<int> vector_; int length_{ 0 }; public: /** Initialize your data structure here. Set the size of the deque to be k. */ MyCircularDeque(int k) { length_ = k; //这里要用reserve不要用resize vector_.reserve(k); } /** Adds an item at the front of Deque. Return true if the operation is successful. */ bool insertFront(int value) { if (isFull()) return false; vector_.insert(vector_.begin(), value); return true; } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ bool insertLast(int value) { if (isFull()) return false; vector_.push_back(value); return true; } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ bool deleteFront() { if (isEmpty()) return false; vector_.erase(vector_.begin()); return true; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ bool deleteLast() { if (isEmpty()) return false; //注意，删除最后一个元素的时候，要减1，迭代器（vector_.end()）指向的是最后一个元素的下一个 vector_.erase(vector_.end() - 1); return true; } /** Get the front item from the deque. */ int getFront() { if (isEmpty()) return -1; return vector_.front(); } /** Get the last item from the deque. */ int getRear() { if (isEmpty()) return -1; return vector_.back(); } /** Checks whether the circular deque is empty or not. */ bool isEmpty() { return vector_.empty(); } /** Checks whether the circular deque is full or not. */ bool isFull() { return length_ == vector_.size(); } }; /** * Your MyCircularDeque object will be instantiated and called as such: * MyCircularDeque* obj = new MyCircularDeque(k); * bool param_1 = obj->insertFront(value); * bool param_2 = obj->insertLast(value); * bool param_3 = obj->deleteFront(); * bool param_4 = obj->deleteLast(); * int param_5 = obj->getFront(); * int param_6 = obj->getRear(); * bool param_7 = obj->isEmpty(); * bool param_8 = obj->isFull(); */
406. 根据身高重建队列
#include <vector> #include <algorithm> class Solution { public: std::vector<std::vector<int>> reconstructQueue(std::vector<std::vector<int>>& people) { //1.排序 std::sort(people.begin(), people.end(), [](std::vector<int> a, std::vector<int> b) { if (a[0] != b[0]) return a[0] > b[0]; return a[1] < b[1]; }); //2.插入 std::vector<std::vector<int>> res; for (auto p : people) { if (res.size() < p[1]) res.push_back(p); if (res.size() >= p[1]) res.insert(res.begin() + p[1], p); } return res; } };
946. 验证栈序列
#include <stack> #include <vector> class Solution { private: std::stack<int> *stack_ = new std::stack<int>; public: bool validateStackSequences(std::vector<int>& pushed, std::vector<int>& popped) { int length = pushed.size(); int j = 0; for (int i = 0; i < length; ++i) { stack_->push(pushed[i]); while (!stack_->empty() && stack_->top() == popped[j]) { j++; stack_->pop(); } } //return stack_->empty(); return j == length; } };
笔记：bfs和dfs以及bfs衍生的层序遍历
bfs层次遍历二叉树代码：
#include <vector> #include <queue> //Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { private: std::queue<TreeNode*> *queue_ = new std::queue<TreeNode*>; public: std::vector<std::vector<int>> levelOrder(TreeNode* root) { //bfs queue_->push(root); while (!queue_->empty()) { root = queue_->front(); queue_->pop(); if (root->left != nullptr) { queue_->push(root->left); } if (root->right != nullptr) { queue_->push(root->right); } } } };
102. 二叉树的层序遍历
进一步，bfs衍生出层序遍历：
#include <vector> #include <queue> //Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { private: std::queue<TreeNode*> *queue_ = new std::queue<TreeNode*>; public: std::vector<std::vector<int>> levelOrder(TreeNode* root) { //层序遍历 std::vector<std::vector<int>> ret; if (root != nullptr) queue_->push(root); while (!queue_->empty()) { int nodeNum = queue_->size(); std::vector<int> vector; for (int i = 0; i < nodeNum; ++i) { root = queue_->front(); queue_->pop(); vector.push_back(root->val); if (root->left != nullptr) { queue_->push(root->left); } if (root->right != nullptr) { queue_->push(root->right); } } ret.push_back(vector); } return ret; } };
116. 填充每个节点的下一个右侧节点指针
#include <vector> #include <queue> // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left( nullptr), right( nullptr), next( nullptr) {} Node(int _val) : val(_val), left( nullptr), right( nullptr), next( nullptr) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; class Solution { private: std::queue<Node*> *queue_ = new std::queue<Node*>; public: Node* connect(Node* root) { //层序遍历 if (root != nullptr) queue_->push(root); while (!queue_->empty()) { int nodeNum = queue_->size(); for (int i = 0; i < nodeNum; ++i) { //注意这里的返回值不能是root，因为会更新root，导致结果不对 //只需要更新原二叉树中响应位置的节点即可 Node* temp = queue_->front(); queue_->pop(); //连接，但是每层的最后一个节点不处理 if (i < nodeNum - 1) temp->next = queue_->front(); if (temp->left != nullptr) queue_->push(temp->left); if (temp->right != nullptr) queue_->push(temp->right); } } return root; } };
61. 旋转链表
#include <vector> #include <queue> //Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (head == nullptr || head->next == nullptr || k == 0) return head; //求链表长度 int length = 1; ListNode* tmp = head; while (tmp->next != nullptr) { tmp = tmp->next; length++; } int count = k % length; if (count == 0) return head; tmp->next = head;//链表连接成环 for (int i = 0; i < length - count - 1; ++i) { head = head->next; } ListNode* ret = head->next; head->next = nullptr; return ret; } };
729. 我的日程安排表 I
#include <map> #include <algorithm> class MyCalendar { public: MyCalendar() { } bool book(int start, int end) { if (start >= end) return false; //0.start 已重复 if (map_.find(start) != map_.end()) return false; //1.首先插入 map_.emplace(start, end); //2.返回刚刚插入的迭代器位置 auto pos = map_.find(start); //auto pos = map_.find(start).first; //3.与（有序）map中的前后迭代器进行比较，根据比较结果决定保留或者删除 //3.1 与前一个比较 if (pos != map_.begin()) { --pos;//得到相邻的前一个迭代器 注意：因为map有序，所以这里默认的前一个迭代器的key < start if (pos->second > start) { //删除 map_.erase(start); return false; } ++pos; } //3.2 与后一个比较 ++pos;//得到相邻的后一个迭代器，这里的后一个迭代器默认的key > start if (pos != map_.end()) { if (pos->first < end) { //删除 map_.erase(start); return false; } } return true; } private: std::map<int, int> map_; }; /** * Your MyCalendar object will be instantiated and called as such: * MyCalendar* obj = new MyCalendar(); * bool param_1 = obj.book(start,end); */
105. 从前序与中序遍历序列构造二叉树
#include <vector> #include <unordered_map> //Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) { int length = preorder.size(); for (int i = 0; i < length; ++i) { unorderedMap_[inorder[i]] = i; } return mybuildTree(preorder, 0, length - 1, unorderedMap_, 0, length - 1); } TreeNode* mybuildTree(std::vector<int>& preorder, int preLeft, int preRight, std::unordered_map<int, int>& map, int inLeft, int inRight) { //递归终止条件 if (preLeft > preRight || inLeft > inRight) return nullptr; //0.构建待返回的二叉树 int rootVal = preorder[preLeft]; TreeNode* root = new TreeNode(rootVal); //1.得到根节点 //注意：这里要用全局维护的唯一map！！！！！！！！！！！！！！！！！！！！！ int pIndex = unorderedMap_[rootVal]; //2.构建左子树 root->left = mybuildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, unorderedMap_, inLeft, pIndex -1); //3.构建右子树 root->right = mybuildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, unorderedMap_, pIndex + 1, inRight); return root; } private: std::unordered_map<int, int> unorderedMap_; };
ps：后序和中序也能构造二叉树，代码如下：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ /*这是后序和中序的代码！！！！！！！！！！！！！！！！！！！！！！！！！*/ class Solution { private: std::unordered_map<int, int> map; public: TreeNode* mybuildTree(std::vector<int>& bakorder, int bakLeft, int bakRight, std::unordered_map<int, int>& unorderedMap, int inLeft, int inRight) { //1.递归终止条件 if (bakLeft > bakRight || inLeft > inRight) return nullptr; int rootVal = bakorder[bakRight]; TreeNode* root = new TreeNode(rootVal); int pIndex = map[rootVal]; root->left = mybuildTree(bakorder, bakLeft, pIndex-1-inLeft+bakLeft, map, inLeft, pIndex-1); root->right = mybuildTree(bakorder, pIndex-inLeft+bakLeft, bakRight-1, map, pIndex+1, inRight); return root; } TreeNode* buildTree(std::vector<int>& bakorder, std::vector<int>& inorder) { if (bakorder.size() != inorder.size()) return nullptr; int length = bakorder.size(); for (int i = 0; i < length; ++i) { map[inorder[i]] = i; } return mybuildTree(bakorder, 0, length - 1, map, 0, length - 1); } };
112. 路径总和
//Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) return false; //递归终止条件 if (root->left == nullptr && root->right == nullptr) return targetSum == root->val; return hasPathSum(root->left, targetSum - root->val) or hasPathSum(root->right, targetSum - root->val); } };
98. 验证二叉搜索树
中序遍历方法：https://blog.csdn.net/qq_44179564/article/details/108696548
#include <vector> //Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { private: std::vector<int> vector; public: bool isValidBST(TreeNode* root) { if (root == nullptr) return false; inorder(root); for (int i = 0; i < vector.size() - 1; ++i) { if (vector[i] >= vector[i + 1]) return false; } return true; } void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); vector.push_back(root->val); inorder(root->right); } };
101. 对称二叉树
//Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: bool isSymmetric(TreeNode* root) { return check(root, root); } bool check(TreeNode* r1, TreeNode* r2) { if (r1 == nullptr && r2 == nullptr) return true; if (r1 == nullptr || r2 == nullptr) return false; return r1->val == r2->val && check(r1->left, r2->right) && check(r1->right, r2->left); } };
102. 二叉树的层序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: std::queue<TreeNode*> *queue_ = new std::queue<TreeNode*>; public: std::vector<std::vector<int>> levelOrder(TreeNode* root) { //层序遍历 std::vector<std::vector<int>> ret; if (root != nullptr) queue_->push(root); while (!queue_->empty()) { int nodeNum = queue_->size(); std::vector<int> vector; for (int i = 0; i < nodeNum; ++i) { root = queue_->front(); queue_->pop(); vector.push_back(root->val); if (root->left != nullptr) { queue_->push(root->left); } if (root->right != nullptr) { queue_->push(root->right); } } ret.push_back(vector); } return ret; } };
1047. 删除字符串中的所有相邻重复项
冗余代码思路，用两个栈解决：
#include <string> #include <stack> class Solution { private: std::stack<char> stack_; public: std::string removeDuplicates(std::string S) { std::string ret; for (auto s : S) { if (!stack_.empty() && stack_.top() == s) { stack_.pop(); } else { stack_.push(s); } } std::stack<char> tmp; while (!stack_.empty()) { tmp.push(stack_.top()); stack_.pop(); } while (!tmp.empty()) { ret += tmp.top(); tmp.pop(); } return ret; } };
简洁代码，直接利用std::string本身就有的“栈特性”
#include <string> class Solution { public: std::string removeDuplicates(std::string S) { std::string ret; for (auto s : S) { if (!ret.empty() && ret.back() == s) { ret.pop_back();//弾栈操作 } else { ret += s; } } return ret; } };
1200. 最小绝对差
用stl里面的，可以允许key重复的multimap（注意这个map似乎没有重载[]插入的方式）
对于map：使用insert()插入元素的方式并不能覆盖掉相同key的值（跳过）；而使用[]方式则可以覆盖掉之前的值
#include <string> #include <vector> #include <map> #include <algorithm> class Solution { public: std::vector<std::vector<int>> minimumAbsDifference(std::vector<int>& arr) { std::sort(arr.begin(), arr.end()); for (int i = 0; i < arr.size() - 1; ++i) { std::vector<int> vector; vector.clear(); vector.push_back(arr[i]); vector.push_back(arr[i + 1]); multimap_.insert(std::make_pair(std::abs(arr[i] - arr[i + 1]), vector)); //multimap_[std::abs(arr[i] - arr[i + 1])] = vector; } int flag = multimap_.begin()->first; std::vector<std::vector<int>> ret; for (auto it = multimap_.begin(); it != multimap_.end(); ++it) { if (it->first > flag) { break; } ret.push_back(it->second); } return ret; } private: std::multimap<int, std::vector<int>> multimap_; //std::map<int, std::vector<int>> map_; };
392. 判断子序列
#include <string> class Solution { public: bool isSubsequence(std::string s, std::string t) { int sLength = s.size(); int tLength = t.size(); int i = 0; int j = 0; while (i < sLength && j < tLength) { if (s[i] == t[j]) i++; j++; } return i == sLength; } };
1267. 统计参与通信的服务器
#include <vector> class Solution { public: int countServers(std::vector<std::vector<int>>& grid) { //行 int m = grid.size(); //列 int n = grid[0].size(); //求每一行/列共有多少台服务器 std::vector<int> count_m(m), count_n(n); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { count_m[i]++; count_n[j]++; } } } //第二次遍历，求可通信服务器数量 int ret = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { //判断有效的条件 if (grid[i][j] == 1 && (count_m[i] > 1 || count_n[j] > 1)) { ret++; } } } return ret; } };
剑指 Offer 33. 二叉搜索树的后序遍历序列
#include <vector> class Solution { public: /* * 1.后序遍历： 左、右、根 * 2.二叉搜索树：左子树所有节点的值 < 根节点的值； * 右子树所有节点的值 > 根节点的值*/ bool verifyPostorder(std::vector<int>& postorder) { return help(postorder, 0, postorder.size() - 1); } bool help(std::vector<int>& postorder, int i, int j) { //递归终止条件：整个二叉树遍历完了 if (i >= j) return true; //利用指针p，试图: 任务1.区分左右子树；任务2.遍历完这一次递归的整个树 int p = i; while (postorder[p] < postorder[j]) { p++; } //找到了右子树，任务1完成 int m = p; while (postorder[p] > postorder[j]) { p++; } //遍历完了这一次递归的整个树，任务2完成 //继续递归，分别判断左子树和右子树 return j == p && help(postorder, i, m -1) && help(postorder, m, j-1); } };
300. 最长递增子序列
#include <vector> #include <algorithm> class Solution { public: int lengthOfLIS(std::vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; std::vector<int> dp(n ,1); for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = std::max(dp[i], dp[j] + 1); } } } return *std::max_element(dp.begin(), dp.end()); } };