704.二分查找
https://leetcode.cn/problems/binary-search/description/
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
int mid = left + (right - left)/2; //除二相当于左移1 ， 也可以left + right / 2
if(nums[mid] > target)
right = mid -1;
else if(nums[mid] < target)
left = mid + 1;
else return mid;
}
return -1;
}
};
35.搜索插入位置
https://leetcode.cn/problems/search-insert-position/description/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
int mid = (left + right)/2;
if(nums[mid] > target)
right = mid - 1;
else if(nums[mid] < target)
left = mid + 1;
else return mid;
}
return right + 1;
}
};
34.在排序数组中寻找目标值的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = searchBoder(nums, target, "start");
int end = searchBoder(nums, target, "end");
vector<int> ans = {start,end};
return ans;
}
private:
int searchBoder(vector<int>& nums, int target, string s) {
//要找的不是target，而是target(可能不止一个)的两侧位置！！！！
int left = 0;
int right = nums.size() - 1;
int start = -1; int end = -1;
while(left <= right)
{
int mid = (left + right) / 2;
if(nums[mid] > target) //说明target的最后一个元素(比如133345678的第三个3)必定在中值(4)左侧
right = mid - 1; //所有的3在【left,mid-1】内，注意是所有的3！！！
else if(nums[mid] < target)
left = mid + 1; //同理
else //中值刚好是target.此时要找左右边界，先找左边界start
{
//找到了某个3，第一个3就至少是这个位置，接着把搜索范围的右侧(right)更新到这个3左边的位置，再次二分
//注意：已经找到了某个3，现在要找第一个3，left肯定在这个3左边了，是把right也放到它左边来找第一个3！！！！
if(s == "start")
{
start = mid;
right = mid - 1;
}
if(s == "end")
{
//找最后一个3，同理
end = mid;
left = mid + 1;
}
}
}
if(s == "start") return start;
else return end;
}
};
69.x的平方根
https://leetcode.cn/problems/sqrtx/description/
class Solution {
public:
int mySqrt(int x) {
//二分查找，根号x <= x/2 + 1，一般小于x/2即可，x = 1的时候取等号，可以特殊讨论
if(x == 1 || x == 0) return x;
int left = 0;
int right = x/2;
while(left <= right)
{
int mid = (left + right)/2;
if((long)mid*mid < x)
{
if((mid+1)*(mid+1) > x) //比如说找8的平方根，当前mid = 2,mid + 1 = 3,就可以直接返回2了
return mid;
else
left = mid + 1;
}
else if((long)mid*mid > x)
{
if((long)(mid-1)*(mid-1) < x) //同理
return mid-1;
else
right = mid - 1;
}
else //mid刚好就是平方根
return mid;
}
return -1;
}
};
367.有效的完全平方数
https://leetcode.cn/problems/valid-perfect-square/description/
class Solution {
public:
bool isPerfectSquare(int x) {
if(x == 1 || x == 0) return true;
int left = 0;
int right = x/2;
while(left <= right)
{
int mid = (left + right)/2;
if((long)mid*mid < x)
{
left = mid + 1;
}
else if((long)mid*mid > x)
{
right = mid - 1;
}
else //mid刚好就是平方根
return true;
}
return false;
}
};
27.移除元素
https://leetcode.cn/problems/remove-element/description/
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++)
{
if(val != nums[fast])
nums[slow++] = nums[fast];
}
return slow;
}
};
26.删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 1) return 1;
int slow = 0;
for(int fast = 1; fast < nums.size(); fast++)
{
if(nums[slow] != nums[fast])
{
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
};
283.移动零
https://leetcode.cn/problems/move-zeroes/description/
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++)
{
if(nums[fast] != 0)
nums[slow++] = nums[fast];
}
cout<<slow;
while(slow < nums.size())
{
nums[slow++] = 0;
}
}
};
844.比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare/description/
class Solution {
public:
bool backspaceCompare(string s, string t) {
fun(s);
fun(t);
return s==t;
}
void fun(string &s){
int slow = 0;
for(int fast = 0; fast < s.size(); fast++)
{
if(s[fast] != '#')
s[slow++] = s[fast];
else if(slow > 0)
slow--;
}
s.resize(slow);
}
};
977.有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/description/
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int size = nums.size();
int k = size - 1;
int forward = 0;
int back = size-1;
vector<int> result(size,0);
while(forward <= back)
{
int a = nums[forward]*nums[forward];
int b = nums[back]*nums[back];
if(a < b)
{
result[k--] = b;
back--;
}
else
{
result[k--] = a;
forward++;
}
}
return result;
}
};
209.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int start = 0;
int sum = 0;
int len = 0;
int res = INT32_MAX;
for(int end = 0; end < nums.size(); end++)
{
sum += nums[end];
while(sum >= target)
{
len = end - start + 1;
res = res > len ? len : res;
sum -= nums[start];
start++;
}
}
return res == INT32_MAX ? 0 : res;
}
};
904.水果成栏
https://leetcode.cn/problems/fruit-into-baskets/description/
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int num = fruits.size();
if(num <= 2)
return num;
unordered_map<int,int> type_count;
int types = 0;
int res = 0;
for(int start = 0, end = 0; end < num; end++)
{
if(type_count[fruits[end]] == 0) //如果当前的水果种类之前没有，就加一个种类
types++;
type_count[fruits[end]]++; //不管以前有没有这种水果，他的数量++
while(types > 2) //如果种类数超过2了，考虑后移start,
{
type_count[fruits[start]]--;
if(type_count[fruits[start]] == 0) //直到消失这个种类
types--;
start++; //每次都要后移一个
}
res = max(res, end - start + 1);
}
return res;
}
};
76.最小覆盖字符串
https://leetcode.cn/problems/minimum-window-substring/description/
class Solution {
public:
string minWindow(string s, string t) {
if(s.size() < t.size())
return "";
unordered_map<char,int> hs,ht; //用于记录s t的每个字符有几个
int cnt = 0;
string ans = "";
for(auto& ch :t)
ht[ch]++;
//不管怎么样, end都要向后扩，但只有多余了 start 才会收缩（向后）以找到最短
//比如abcde第四次循环完成，就找到abcd最接近的答案，可能刚好就是abcd，也可能是bcd 还可能不够，但start一定是最靠后的位置
for(int start = 0, end = 0; end < s.size(); end++)
{
hs[s[end]]++; //不管怎么样end都要后扩，让s[end]的个数加一
if(hs[s[end]] <= ht[s[end]]) //是否是有效添加？无效添加就是比如目前已经有3个a，但是t只有两个a，多了一个
{
cnt++;
}
while(hs[s[start]] > ht[s[start]]) //移完后面移前面，尽可能保证start靠后，啥时候保证不了？缩的该有的都没了的时候
{
hs[s[start++]]--; //start可以后移，s[start]个数减少一个
//cout<<s[start]<<endl;
}
int curLen = end - start + 1;
if(cnt == t.size())
{
if (ans.empty() || ans.size() > curLen)
//这里很重要，ans.empty()保证第一次ans可以填入，ans比当前len长保证把ans更新为更短答案
ans = s.substr(start, curLen);
}
}
return ans;
}
};
59.螺旋矩阵Ⅱ
https://leetcode.cn/problems/spiral-matrix-ii/description/
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
//分为奇数偶数，奇数比如5就一共有两圈加中心一个25，偶数比如4就正好两圈
//上 -- 右 -- 下 -- 左 最外圈每次填n-1次，左闭右开。每往里一圈，起点右下移一个，右边往前移一个
vector<vector<int>> matrix(n,vector<int>(n,0));
int startx = 0, starty = 0;
int end = n - 1;
int loop = n/2;
int count = 1;
while(loop--)
{
//上
for(int i = starty; i < end; i++)
{
matrix[startx][i] = count++;
}
//右
for(int i = startx; i < end; i++)
{
matrix[i][end] = count++;
}
// //下
for(int i = end; i > startx; i--)
{
matrix[end][i] = count++;
}
// //左
for(int i = end; i > starty; i--)
{
matrix[i][startx] = count++;
}
startx++;
starty++;
end--;
}
if(n%2 != 0)
matrix[n/2][n/2] = n*n;
return matrix;
}
};
54.螺旋矩阵
https://leetcode.cn/problems/spiral-matrix/
https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array) {
vector<int> res;
//分别表示left right bottom top, 左上角为(0,0)
if(array.size() == 0) return res;
int l = 0, r = array[0].size() - 1, t = 0, b = array.size() - 1;
while(1)
{
for(int i = l; i <= r; i++)
res.push_back(array[t][i]);
if(++t > b) //跑完顶行，下移一行
break;
for(int i = t; i <= b; i++)
res.push_back(array[i][r]);
if(--r < l) //跑完右行，左移一行
break;
for(int i = r; i >= l; i--)
res.push_back(array[b][i]);
if(--b < t) //跑完底行，上移一行
break;
for(int i = b; i >= t; i--)
res.push_back(array[i][l]);
if(++l > r) //跑完左行，右移一行
break;
}
return res;
}
};