Jayce's Blog

PROBLEM剑指 Offer 48. 最长不含重复字符的子字符串 难度 中等 MY ANSWER基本滑动窗口，维护窗口内不能有重复字符，记录窗口最大值返回。遍历字符串，若新字符不重复，则窗口右边缘向右扩展一位；若重复，则左边缘向右收缩直到窗口左边第一个是之前窗口的重复字符。因调用字符串的find函数，时间复杂度O(n^2)，空间复杂度O(1)。 class Solution {public: int lengthOfLongestSubstring(string s) { if(s.empty()) { return 0; } int max = 1; int end = 1; int start = 0; for(int i = 1; i < s.size(); i++) { size_t fpos = s.substr(start, end).find(s[i]); if ...

PROBLEM剑指 Offer 47. 礼物的最大价值 难度 中等 MY ANSWER典型的动态规划，不能使用贪心时，就看能否使用动态规划。转移方程为： 时间复杂度O(mn)，空间复杂度O(mn)。 class Solution {public: int maxValue(vector<vector<int>>& grid) { if(grid.empty()) { return 0; } vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0)); dp[0][0] = grid[0][0]; for(int i = 1; i < dp[0].size(); i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } ...

PROBLEM剑指 Offer 46. 把数字翻译成字符串 难度 中等 MY ANSWER将数字转换为字符串，使用动态规划。时间复杂度O(logn)，空间复杂度O(logn)。代码还可继续优化：因为只需用到i - 2和i - 1的结果，所以可以不使用数组存储每位的结果，只使用两个变量储存前两位的结果。 class Solution {public: int translateNum(int num) { vector<int> res; res.push_back(1); res.push_back(1); string str = to_string(num); for(int i = 1; i < str.size(); i++) { int tmp = res[i]; if(str.substr(i - 1, 2) <= "25" && str.substr(i - 1, ...

PROBLEM剑指 Offer 45. 把数组排成最小的数 难度 中等 MY ANSWER无。 BETTER SOLUTION本质上是排序问题，排序规则为（字符串比较）： 拼接字符串x + y > y + x，则x > y 反之x + y < y + x，则x < y 将数组按规则从小到大排序再连接即为答案。时间复杂度O(nlogn)，空间复杂度O(n)。 两种实现方法： 手写快排class Solution {public: string minNumber(vector<int>& nums) { vector<string> strs; for(int i = 0; i < nums.size(); i++) strs.push_back(to_string(nums[i])); quickSort(strs, 0, strs.size() - 1); string res; for(string ...

PROBLEM剑指 Offer 43. 1～n 整数中 1 出现的次数 难度 困难 MY ANSWER无。 BETTER SOLUTION逐位计算1出现的次数，类似滚动密码锁，固定住一位1，计算有多少个数与这个1组合。时间复杂度O(logn)，空间复杂度O(1)。每位分3种情况： cur = 0 cur = 1 cur > 1 class Solution {public: int countDigitOne(int n) { int cur = n % 10; int low = 0; int high = n / 10; long long digit = 1; int res = 0; while(cur != 0 || high != 0) { if(cur == 0) { res += high * digit; } else if(cur ...

PROBLEM剑指 Offer 41. 数据流中的中位数 难度 困难 MY ANSWER一个大顶堆一个小顶堆，分别存放比中位数小和大的数。addnum时间复杂度O(logn)，空间复杂度O(n)，findmedian时间复杂度O(1)，空间复杂度O(1)。 class MedianFinder {public: priority_queue<int> small; priority_queue<int, vector<int>, greater<int>> big; double median = INT_MIN; MedianFinder() { } void addNum(int num) { if(median == INT_MIN) { median = num; } if(num <= median) { if(small.s ...

PROBLEM剑指 Offer 40. 最小的k个数 难度 简单 MY ANSWER使用大顶堆，遍历到比堆顶小的元素时，出堆并将元素插入。priority_queue默认就为大顶堆，若构造小顶堆取相反数即可。时间复杂度为O(nlogk)，空间复杂度O(k)。 class Solution {public: vector<int> getLeastNumbers(vector<int>& arr, int k) { priority_queue<int> heap; vector<int> res; if(arr.empty() || !k) { return res; } for(int i = 0; i < k; i++) { heap.push(arr[i]); } for(int i = k; i < arr ...

PROBLEM剑指 Offer 39. 数组中出现次数超过一半的数字 难度 简单 MY ANSWER哈希表储存元素个数，超过一半时返回。时间空间复杂度都为O(n)。 class Solution {public: int majorityElement(vector<int>& nums) { unordered_map<int, int> ht; for(int i = 0; i < nums.size(); i++) { if(ht.find(nums[i]) != ht.end()) { ht[nums[i]]++; if(ht[nums[i]] > nums.size() / 2) { return nums[i]; } } else
...

PROBLEM剑指 Offer 38. 字符串的排列 难度 中等 MY ANSWER使用回溯，vis标记访问过的字符，使用set记录得到的结果，若重复则不保存到最终结果中。时间空间复杂度都很高，因为没有剪枝。 class Solution {public: vector<string> res; string s; vector<int> vis; set<string> ans; void select(string str) { if(str.length() == s.length()) { if(ans.insert(str).second) { res.push_back(str); } return; } else { for(int i = 0; i < v ...

PROBLEM剑指 Offer 37. 序列化二叉树 难度 困难 MY ANSWER 队列实现bfs，使用to_string来实现int到string的转换，从而实现二叉树的序列化。 首先使用循环与substr对字符串进行分割，储存到string向量中。同样使用队列实现二叉树的构建，从队头中取节点添加儿子节点，将儿子节点入队。同时遍历string向量，index指示当前节点对应的儿子节点的值，构建节点使用stoi将字符串转换为int。 时间复杂度O(n)，空间复杂度O(n)。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Codec {public: // Encodes a tree to a ...