2024年2月5日力扣题目训练
2024年2月5日第十二天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的。
476. 数字的补数
链接: 数字的补数
难度： 简单
题目：
运行示例：
思路：
由题目可知，我们可以将 num二进制表示的每一位取反。因此我们需要首先找到 num二进制表示最高位的那个 1，再将这个 1以及更低的位进行取反。
如果 num 二进制表示最高位的 1 是第 i (0≤i≤30)位，那么一定有：2i≤num<2i+1
因此我们可以使用一次遍历，在 [0,30]中找出 i的值。在这之后，我们就可以遍历 num的第 0∼i个二进制位，将它们依次进行取反。
代码：
class Solution {
public:
int findComplement(int num) {
int highbit = 0;
for(int i = 1; i < 31; i++){
if(num >= (1 << i)){
highbit = i;
}else{
break;
}
}
int mask = (highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1);
return num ^ mask;
}
};
482. 密钥格式化
链接: 密钥格式化
难度： 简单
题目：
运行示例：
思路：
这道题本质就是对原来字符串进行分组，将’ - '分配到每组，主要是遍历。
代码：
class Solution {
public:
string licenseKeyFormatting(string s, int k) {
string res,ans;
for(int i = 0; i < s.size(); i++){
if(s[i] != '-'){
if(s[i] >= 'a' && s[i] <= 'z'){
res += s[i]-'a'+'A';
}else{
res+= s[i];
}
}
}
int count = 0;
for(int i = res.size()-1; i >= 0; i--){
if(count % k == 0 && count != 0){
ans+='-';
}
ans+=res[i];
count++;
}
reverse(ans.begin(),ans.end());
return ans;
}
};
485. 最大连续 1 的个数
链接: 连续 1 的个数
难度： 简单
题目：
运行示例：
思路：
这道题是一道比较简单问题,只需遍历一次记录连续1的个数即可。
代码：
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
vector<int> dp(nums.size()+1,0);
int ans = 0;
for(int i = 1 ; i <= nums.size(); i++){
if(nums[i-1] == 1){
dp[i] = dp[i-1] + 1;
ans = (ans > dp[i])? ans:dp[i];
}else{
dp[i] = 0;
}
}
return ans;
}
};
148. 排序链表
链接: 排序链表
难度： 中等
题目：
运行示例：
思路：
这道题其实跟147. 对链表进行插入排序类似，我采用了相同方法解决,但很容易超时，所以官方的方法是归并排序完成。
代码：
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == NULL) return head;
ListNode* newhead = new ListNode(0);
newhead->next = head;
ListNode* p = head;
ListNode* curr = head->next;
while(curr != NULL){
if(p->val <= curr->val){
p = p->next;
}else{
ListNode* pre = newhead;
while(pre->next->val <= curr->val) pre = pre->next;
p->next = curr->next;
curr->next = pre->next;
pre->next = curr;
}
curr = p->next;
}
return newhead->next;
}
};
164. 最大间距
链接: 最大间距
难度： 中等
题目：
运行示例：
思路：
这道题就是利用自带的排序函数，之后算差值，不过官方的方法是基数排序，没有利用自带的函数。
代码：
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.size() < 2) return 0;
sort(nums.begin(),nums.end());
vector<int> res(nums.size());
int count = 0;
for(int i = 1; i < nums.size(); i++){
count = (nums[i]-nums[i-1]) > count ?(nums[i]-nums[i-1]):count;
}
return count;
}
};
运行示例：
运行示例
思路：
这道题我知道是找一根柱子的左侧且最近的小于其高度的柱子，但我不太懂如何利用栈完成这道题。
官方解法
代码：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if(n == 0) return 0;
vector<int> left(n),right(n);
stack<int> st;
for(int i = 0; i < n; i++){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
left[i] = (st.empty()? -1:st.top());
st.push(i);
}
st = stack<int>();
for(int i = n -1; i >= 0; i--){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
right[i] = (st.empty()? n:st.top());
st.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
