5457

1个月前

### 就是在旋转后的数组里用$O(logn)$的时间复杂度做，最坏时间复杂度其实是$O(n)$

class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0,r = nums.size()-1;
while(l <= r){
while(l < r && nums[l] == nums[l+1]) l++;
while(l < r && nums[r] == nums[r-1]) r--;
int mid = l + (r-l) /2;//防止溢出
if(nums[mid]==target) return true;
if(nums[mid]>=nums[l]){
if(target<=nums[mid] && target>=nums[l]) r= mid-1;
else l = mid+1;
}
else {
if(target>=nums[mid] && target<=nums[r]) l=mid+1;//这里的target大于还是大于等于似乎并不影响最终结果，仔细体会。
else r= mid-1;
}
}
return false;
}
};


1个月前

### 思路见代码

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 2) return nums.size();
int index = 2;
for(int i = 2 ; i < nums.size();i++){
if(nums[i] != nums[index-2])
nums[index++] = nums[i];
}
return index;
}
};


1个月前

### 直接把最终结果放在了nums1中，从后往前遍历nums1也不用担心nums1被覆盖

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int last = m + n -1 ;
while(n){
if(m == 0 || nums1[m-1]<=nums2[n-1]){
nums1[last--] = nums2[--n];
}
else{
nums1[last--] = nums1[--m];
}
}
}
};


1个月前

## 思路

### hash表存val值的个数t，如果 t能被 val+1 整除，sum加上t；如果不能被整除，加上(t/(val+1)+1)*(val+1)

class Solution {
public:
int numRabbits(vector<int>& answers) {
map<int,int> mp;
for(auto it : answers){
mp[it] ++ ;
}
int sum = 0 ;
for(auto it : mp){
int val = it.first, t = it.second;
sum+=((t-1)/(val+1)+1)*(val+1);
}
return sum;
}
};


1个月前

## 仔细体会

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length();
int len2 = text2.length();
vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
for(int i = 1 ; i< len1+1;i++){
for(int j = 1;j<len2+1;j++){
if(text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[len1][len2];
}
};


1个月前

### 方法一：按层遍历

class Solution {
public:
int trap(vector<int>& height) {
int Sum = accumulate(height.begin(),height.end(),0);
int volume = 0;
int layer = 1;
int n = height.size();
int left = 0 ;
int right = n-1;
while(left <= right){
while(left <= right && height[left] < layer)
left++;
while(left <= right && height[right] < layer)
right--;
volume += right-left+1;
layer++;
}
return volume - Sum;
}
};


1个月前

## 要用到两个指针遍历，一个是cur遍历老链表，一个是p用来做结果链表不断往里添加。

/**
* 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* deleteDuplicates(ListNode* head) {
if(!head || !head->next) return head;
ListNode* dumpy = new ListNode(-1);
ListNode* cur = head;
dumpy->next = head;
ListNode* p = dumpy;
map<int,int> mp;
while(cur){
if(mp[cur->val] == 0){
mp[cur->val] = 1;
p->next = new ListNode(cur->val);//这里不能写成p->next = cur ;
p = p->next;
}
cur = cur->next;
}
return dumpy->next;
}
};


1个月前
/**
* 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* deleteDuplicates(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
map<int,int> visit;
ListNode* cur = head;
ListNode* dummy = new ListNode(-1);
ListNode* res = dummy;
while(cur){
visit[cur->val]++;
cur = cur->next;
}
cur = head;
while(cur){
if(visit[cur->val] == 1){
res->next = new ListNode(cur->val);
res = res->next;
}
cur =cur->next;
}
return dummy->next;
}
};


1个月前

### 思路：

1. two 记录 132 中的2
2. 单调栈维护当前比 2 大的 3，栈顶为3中的最小值
3. 从后往前遍历，如果当前值比栈顶值大，two更新为栈顶值（之前的two（2）存的是是比栈（3）里小的，更新相当于把two变大），顺便把栈里的小于更新完后的two 的 值全部出栈（栈里全是序列中当前two以后而且比two大的元素）
4. 如果当前值比栈顶值小，说明找到了1（two已被记录的情况下，这里如果只有三个元素123会怎么样，不会怎么样，这样的话two不会被更新，始终是INT_MIN，也就找不到比他小的1了。结果就是false）
5. 一句话总结，two越大，越好找比他小的1
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(n<3) return false;
stack<int> s;
int two = INT_MIN;
for(int i = n-1 ; i >= 0 ; i--){
if(nums[i]< two) return true;
else{
while(!s.empty() && nums[i] > s.top()){
two = s.top();
s.pop();
}
s.push(nums[i]);
}
}
return false;
}
};


1个月前
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = 0 ;
while(n){
n&=n-1;
cnt++;
}
return cnt;
}
};

class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt = 0 ;
while(n){
cnt+= n %2;
n>>=1;
}
return cnt;
}
};