数组训练营1(leetcode)

1.多数元素

 题目描述:

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

数组训练营1(leetcode)

思路:

数组训练营1(leetcode)

数组训练营1(leetcode)数组训练营1(leetcode)数组训练营1(leetcode)

代码:

    //时复O(N)空复O(1)
    int majorityElement(vector<int>& nums){
        int thinkAns=nums[0],count=0;//thinkAns随便赋值
        for(int x:nums){
            if(x==thinkAns)
                count++;
            else if(--count<0){
                thinkAns=x;
                count=1;
            }
        }
        return thinkAns;      
    }

    //此处为垃圾代码
    //时复O(N^2)空复O(N)
    int majorityElement1(vector<int>& nums) {
        int n=nums.size();
        map<int,int> m;//<数字,次数>
        for(int x:nums){
            if(m.find(x)==m.end())
                m[x]=1;
            else
                m[x]++;
        }
        //找次数最大的
        int maxTime=0;
        int ans;
        for(pair<int,int> p:m){
            if(p.second>maxTime){
                maxTime=p.second;
                ans=p.first;
            }
        }
        return ans;
    }

2.找到字符串中的所有字母异位词

题目描述: 

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

数组训练营1(leetcode)

思路: 

根据题目要求,我们需要在字符串 ss 寻找字符串 pp 的异位词。因为字符串 pp 的异位词的长度一定与字符串 pp 的长度相同,所以我们可以在字符串 ss 中构造一个长度为与字符串 pp 的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串 pp 中每种字母的数量相同时,则说明当前窗口为字符串 pp 的异位词。

算法:

在算法的实现中,我们可以使用数组来存储字符串 pp 和滑动窗口中每种字母的数量。

细节:

当字符串 ss 的长度小于字符串 pp 的长度时,字符串 ss 中一定不存在字符串 pp 的异位词。但是因为字符串 ss 中无法构造长度与字符串 pp 的长度相同的窗口,所以这种情况需要单独处理。

代码实现:

    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int n1=s.size(),n2=p.size();
        if(n1<n2)
            return ans;
        vector<int> sCount(26),pCount(26);
        for(int i=0;i<n2;i++){
            sCount[s[i]-'a']++;
            pCount[p[i]-'a']++;
        }
        if(sCount==pCount)
            ans.emplace_back(0);
        for(int i=0;i<n1-n2;i++){
            --sCount[s[i]-'a'];
            ++sCount[s[i+n2]-'a'];
            if(sCount==pCount)
                ans.emplace_back(i+1);
        }
        return ans;
    }

3.乘积小于K的连续子数组的个数

 题目描述:

给定一个正整数数组 nums和整数 k 。

请找出该数组内乘积小于 k 的连续的子数组的个数。

 数组训练营1(leetcode)

方法一(二分查找):

数组训练营1(leetcode)

 代码实现:

//为了计算过程中不超出范围,取对数 log(x*y)=logx+logy  所以用prefix存储前缀和
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k == 0)
        return 0;
    int n = nums.size();
    vector<double> prefix(n+1);//prefix[i]表示【0,i-1]的前缀和
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + log(nums[i - 1]);//profix[i]-profix[j]表示[j,i-1]的和
    }
    double logk = log(k);
    int ans = 0;
    int N = prefix.size();
    int low = 0, high = N - 1,mid=low+((high-low)>>1);
    for (int i = 0; i < N; i++) {
        //二分
        low = i + 1; high = N;
        while (low < high) {
            mid = low + ((high - low) >> 1);
            if (prefix[mid] < prefix[i] + logk - 1e-9)
                low = mid + 1;
            else
                high = mid;
        }
        ans += low-1 - i;
    }
    return ans;
}

方法二:(双指针)
数组训练营1(leetcode)

代码实现:

//双指针
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <=1)
        return 0;
    int n = nums.size();
    int prod = 1, ans = 0, left = 0;
    for (int right = 0; right < n; right++) {
        prod *= nums[right];
        while (prod >= k)
            prod /= nums[left++];
        ans += right - left + 1;
    }
    return ans;
}

4.最大子数组和

题目描述: 

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

 数组训练营1(leetcode)
算法和思路:  

数组训练营1(leetcode)代码实现:

    //动态规划
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = max(pre + x, x);//小就跟更新
            maxAns = max(maxAns, pre);//同时记录最大的
        }
        return maxAns;
    }

5.和为K的子数组

 题目描述:

给你一个整数数组 nums 和一个整数 k ,请你统计并返回该数组中和为 k 的连续子数组的个数。 

数组训练营1(leetcode) 

思路:前缀和+哈希优化 

数组训练营1(leetcode)

代码: 

    //时复O(n) 空复O(n)
    int subarraySum(vector<int>& nums, int k){
        int count=0,pre=0;
        unordered_map<int,int> mp;
        mp[0]=1;
        for(int x:nums){
            pre+=x;
            if(mp.find(pre-k)!=mp.end())
                count+=mp[pre-k];
            mp[pre]++;
        }
        return count;
    }

 

上一篇:Java实现二叉搜索树的插入、删除


下一篇:Windows下安装Redis服务(zip)