概述
每日打卡，比特位计数：
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans(num+1, 0);
for(int i = 1; i <= num; ++i){
ans[i] = ans[i&(i-1)] + 1;
}
return ans;
}
};1.二叉树的最小深度：
给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
/**
* 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:
int minDepth(TreeNode* root) {
return minHight(root);
}
int minHight(TreeNode* n){
if(!n) return 0;
if(n->left && n->right){
return min(minHight(n->left), minHight(n->right)) + 1;
}
if(n->left) return 1+minHight(n->left);
return 1+minHight(n->right);
}
};执行用时: 288ms 超过92% 内存消耗: 141.4MB 超过44%
2.有多少小于当前数字的数字：
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> ans(nums.size(), 0);
for(int i = 0; i < nums.size(); ++i){
swap(nums[i], nums[0]);
for(int j = 1; j < nums.size(); ++j){
if(nums[0] > nums[j]) ans[i]++;
}
}
return ans;
}
};
枚举所有可能 时间复杂度O(n*(n-1)) 在nums[i]没有限制的情况下该算法确保答案是正确的
力扣这道题的限制是 0 <= nums[i] <= 100 所以可以使用叠加的方式 若要知道小于100以内的个数 只需求出小于等于99的个数
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> t(101, 0);
//记录num[i]出现的次数
for(int i = 0; i < nums.size(); ++i){
t[nums[i]] ++;
}
//从1开始统计 <=1的个数
for(int i = 1; i < 101; ++i){
t[i] += t[i-1];
}
vector<int> ans(nums.size(), 0);
for(int i = 0; i < nums.size(); ++i){
ans[i] = nums[i] == 0 ? 0 : t[nums[i]-1];
}
return ans;
}
};执行用时: 52ms 超过38% 内存消耗: 9.7MB 超过100% （n*n的算法运行时间）
3.检查两个字符串数组是否相等：
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。
class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
//stringstream用了空间预分配 效率比string的operator+操作高
stringstream sw1, sw2;
for(int i = 0; i < word1.size(); ++i)
sw1 << word1[i];
for(int i = 0; i < word2.size(); ++i)
sw2 << word2[i];
return sw1.str() == sw2.str();
/* 解法二
int i1 = 0, j1 = 0, i2 = 0, j2 = 0, w1s = word1.size(), w2s = word2.size();
while(i1 < w1s && i2 < w2s){
if(word1[i1][j1] != word2[i2][j2]) return false;
++j1;
++j2;
if(j1 == word1[i1].size()){
++i1;
j1 = 0;
}
if(j2 == word2[i2].size()){
++i2;
j2 = 0;
}
}
return i1 == w1s && i2 == w2s;
*/
}
};
分享两种写法
1.直接用stringstream 组成完整的一个字符串再对比 题意应该并不想要这个解法
空间复杂度高
2.控制好每一个数组的row col 不需要额外内存
空间复杂度O(1)执行用时: 4ms 超过90% 内存消耗:11.5MB 超过64%
4.括号的最大镶嵌深度：
class Solution {
public:
int maxDepth(string s) {
int m = 0, cur = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '('){
++cur;
m = max(m, cur);
}
else if(s[i] == ')') --cur;
}
return m;
}
};执行用时: 0ms 超过100% 内存消耗: 6.1MB 超过77%
5.检查整数及其两倍是否存在：
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
class Solution {
public:
bool checkIfExist(vector<int>& arr) {
unordered_map<int, bool> m;
for(int i = 0; i < arr.size(); ++i){
//不能整除2 所以只判断是否存在arr[i]*2
if(arr[i] % 2){
if(m.count(2*arr[i])) return true;
m[arr[i]] = true;
}
else{
//整除2 需要判断是否存在arr[i]/2或者arr[i]*2
if(m.count(arr[i]*2) || m.count(arr[i]>>1)) return true;
m[arr[i]] = true;
}
}
return false;
}
};执行用时: 8ms 超过90% 内存消耗: 10MB 超过75%
6.跳水板：
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。
编写一个方法，生成跳水板所有可能的长度。返回的长度需要从小到大排列。
class Solution {
public:
vector<int> divingBoard(int shorter, int longer, int k) {
if(!k) return vector<int>();
if(shorter == longer){
return vector<int>(1, shorter*k);
}
vector<int> ans;
int cur = k*shorter;
ans.push_back(cur);
for(int i = k; i > 0; --i){
cur = cur + longer - shorter;
ans.push_back(cur);
}
return ans;
}
}
min+步进7.四数之和：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size() < 4) return vector<vector<int>>();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for(int i = 0; i < nums.size() - 3; ++i){
if(0 != i && nums[i] == nums[i - 1])
continue;
if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)
break;
if(nums[i] + nums[nums.size()-1] + nums[nums.size()-2] + nums[nums.size()-3] < target)
continue;
int t = target - nums[i];
for(int j = i + 1; j < nums.size() - 2; ++j){
if(i + 1 != j && nums[j] == nums[j - 1])
continue;
if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target)
break;
if(nums[i] + nums[j] + nums[nums.size()-1] + nums[nums.size()-2] < target)
continue;
int t2 = t - nums[j];
int left = j + 1, right = nums.size() - 1;
while(left < right){
if(t2 - nums[left] > nums[right])
++left;
else if(t2 - nums[left] < nums[right])
--right;
else{
ans.push_back({nums[i], nums[j], nums[left], nums[right]});
while(left < right && nums[right] == nums[right-1]) --right;
while(left < right && nums[left] == nums[left+1]) ++left;
++left;
--right;
}
}
}
}
return ans;
}
};
//主要加上一些边界条件判断 效率会高很多执行用时: 4ms 超过100% 内存消耗: 12.7MB 超过68%
最后
以上就是儒雅发卡为你收集整理的力扣《六》的全部内容，希望文章能够帮你解决力扣《六》所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复