当前位置：网站首页>Question brushing record: easy array (continuously updated)
Question brushing record: easy array (continuously updated)
2022-06-27 19:58:00 【Lao Yan is trying】
1. Subscript 、 Iterators and other basic operations
1： Sum of two numbers ： Power button
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>m;
int n=nums.size();
for(int i=0;i<n;++i){
if(m.count(target-nums[i])){
return {i,m[target-nums[i]]};
}
m[nums[i]]=i;
}
return {};
}
};26： Remove duplicate items from an ordered array - Power button
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n=nums.size();
for(auto it=nums.begin();it!=nums.end();){
if(it!=nums.begin() && *it==*(it-1)){
nums.erase(it);
}else{
++it;
}
}
return nums.size();
}
};27： Remove elements - Power button
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for(auto it=nums.begin();it!=nums.end();){
if(*it==val){
nums.erase(it);
}else{
++it;
}
}
return nums.size();
}
};283. Move zero - Power button （LeetCode）
You can also use double pointers , Similar to bubbling thoughts
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i=0;
for(auto it=nums.begin();it!=nums.end(),i<nums.size();++i){
if(*it==0){
nums.erase(it);
nums.emplace_back(0);
}else{
++it;
}
}
}
};2. Dynamic programming （Easy）
53. Maximum subarray and - Power button
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre=0;
int maxAns=nums[0];
for(auto &i:nums){
pre=max(pre+i,i);
maxAns=max(maxAns,pre);
}
return maxAns;
}
};746. Use the minimum cost to climb the stairs - Power button （LeetCode）
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int>dp(n+1);
dp[0]=dp[1]=0;
for(int i=2;i<=n;++i){
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
3. Two points search
704. Two points search - Power button （LeetCode）
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
return -1;
}
};The finger of the sword Offer 11. Minimum number of rotation array - Power button （LeetCode）
This question can also be used deque To do it
class Solution {
public:
int minArray(vector<int>& numbers) {
if(numbers.size()==0)return 0;
int left=0,right=numbers.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(numbers[mid]>numbers[right]){
left=mid+1;
}else if(numbers[mid]==numbers[right]){
--right;
}else{
right=mid;
}
}
return numbers[left];
}
};
4. Hashtable (unordered_map,unordered_set)
217. There are duplicate elements - Power button （LeetCode）
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int>m;
for(auto &i:nums){
if(m.count(i)){
return true;
}
m[i]++;
}
return false;
}
};219. There are duplicate elements II - Power button （LeetCode）
Similar to the previous question , Just added some constraints
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n=nums.size();
unordered_map<int,int>m;
for(int i=0;i<n;++i){
int t=nums[i];
if(m.count(t) && i-m[t]<=k){
return true;
}
m[t]=i;
}
return false;
}
};5. mathematics
136. A number that appears only once - Power button （LeetCode）
Exclusive or
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(auto &i:nums){
ans^=i;
}
return ans;
}
};169. Most elements - Power button （LeetCode）
Moore voting （ The curtain ）
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count=0;
int target=nums[0];
for(auto &i:nums){
if(count==0){
target=i;
}
if(i==target){
++count;
}else{
--count;
}
}
return target;
}
};The finger of the sword Offer 53 - II. 0～n-1 Missing numbers in - Power button （LeetCode）
Exclusive or
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res=0;
int n=nums.size();
for(int i=0;i<n;++i){
res^=nums[i];
}
for(int i=0;i<=n;++i){
res^=i;
}
return res;
}
};6. Double pointer
977. The square of an ordered array - Power button （LeetCode）
Make good use of the property of ascending array , Determine the positive and negative boundaries , Double pointer operation is similar to merge sort
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int pivot=-1;
for(int i=0;i<nums.size();++i){
if(nums[i]<0){
pivot=i;
}else{
break;
}
}
vector<int>ans;
int p1=pivot,p2=pivot+1;
while(p1>=0 && p2<nums.size()){
int pow1=nums[p1]*nums[p1];
int pow2=nums[p2]*nums[p2];
if(pow1<pow2){
ans.emplace_back(pow1);
--p1;
}else{
ans.emplace_back(pow2);
++p2;
}
}
while(p1>=0){
ans.emplace_back(nums[p1]*nums[p1]);
--p1;
}
while(p2<nums.size()){
ans.emplace_back(nums[p2]*nums[p2]);
++p2;
}
return ans;
}
};283. Move zero - Power button （LeetCode）
A bubbling thought
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int left=0,right=0;
while(right<nums.size()){
if(nums[right]!=0){
swap(nums[left],nums[right]);
left++;
}
right++;
}
}
};350. Intersection of two arrays II - Power button （LeetCode）
It's very clever here , It must be a short array that goes to the end first , End of cycle ,&& instead of ||
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int p1=0,p2=0;
//4 5 9
//4 4 8 9 9
vector<int>ans;
while(p1<nums1.size() && p2<nums2.size()){
if(nums1[p1]<nums2[p2]){
p1++;
}else if(nums1[p1]>nums2[p2]){
p2++;
}else{
ans.emplace_back(nums1[p1]);
p1++;
p2++;
}
}
return ans;
}
};
7. The sliding window
219. There are duplicate elements II - Power button （LeetCode）
A sliding window implementation , It is worth learning
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int>s;
for(int i=0;i<nums.size();++i){
if(i>k){
s.erase(nums[i-k-1]);
}
if(s.count(nums[i])){
return true;
}
s.emplace(nums[i]);
}
return false;
}
};
. Some template questions
The finger of the sword Offer 29. Print matrix clockwise - Power button （LeetCode）
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.empty())return {};
int left=0,right=matrix[0].size()-1;
int top=0,bottom=matrix.size()-1;
vector<int>ans;
while(true){
for(int i=left;i<=right;++i){
ans.emplace_back(matrix[top][i]);
}
if(++top>bottom)break;
for(int i=top;i<=bottom;++i){
ans.emplace_back(matrix[i][right]);
}
if(--right<left)break;
for(int i=right;i>=left;--i){
ans.emplace_back(matrix[bottom][i]);
}
if(--bottom<top)break;
for(int i=bottom;i>=top;--i){
ans.emplace_back(matrix[i][left]);
}
if(++left>right)break;
}
return ans;
}
};The finger of the sword Offer 40. The smallest k Number - Power button （LeetCode）
TopK problem , Priority queue （ Heap sort ）
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
priority_queue<int,vector<int>,greater<>>q;
vector<int>ans;
for(auto &i:arr){
q.push(i);
}
for(int i=0;i<k;++i){
ans.emplace_back(q.top());
q.pop();
}
return ans;
}
};1984. The minimum difference in student scores - Power button （LeetCode）
Maximum and minimum , Sorting is often the solution
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int MIN=INT_MAX;
for(int i=0;i+k-1<nums.size();++i){
MIN=min(MIN,nums[i+k-1]-nums[i]);
}
return MIN;
}
};
边栏推荐
猜你喜欢
华大单片机KEIL报错_WEAK的解决方案
【debug】平台工程接口调试
Embracing cloud Nativity: Practice of Jiangsu Mobile order center
SQL Server - window function - solve the problem of filtering consecutive n records
海底电缆探测技术总结
Redis集群
从感知机到前馈神经网络的数学推导
Oracle 获取月初、月末时间，获取上一月月初、月末时间
Buzzer experiment based on stm32f103zet6 library function
MySQL表的增删改查（基础）
随机推荐
Online text batch inversion by line tool
刷题记录：Easy 数组(持续更新)
Pointers and structs
带你认识图数据库性能和场景测试利器LDBC SNB
What is ssr/ssg/isr? How do I host them on AWS?
OpenSSL client programming: SSL session failure caused by an obscure function
Labelimg usage guide
【bug】联想小新出现问题，你的PIN不可用。
308. 二维区域和检索 - 可变 线段树/哈希
《第五项修炼》(The Fifth Discipline):学习型组织的艺术与实践
Rust 中的枚举和控制流运算
Manage rust project through cargo
1024 Palindromic Number
Character interception triplets of data warehouse: substrb, substr, substring
刷题笔记-树（Easy）-更新中
shell脚本常用命令(四)
Rust 所有权进阶 -- 内存管理
运算符的基础知识
（LC）46. Full Permutation
海底电缆探测技术总结