数组OJ题

2024-02-02 08:27:10

数组OJ训练

1. 剑指offer3—数组中重复的数字

链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
数组OJ题
①先排序，然后双指针法来找是否有相同的数字

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int prev = 0,cur = 1;
        while(cur < nums.size())
        {
            if(nums[prev] != nums[cur])
            {
                prev++;
                cur++;
            }
            else
            {
                return nums[prev];
            }
        }
        //因为压根就不应该走到这里，如果走到了就说明出现大问题了，返回-1
        return -1;
    }
};

②使用hash表

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> Countmap;
        for(auto& e: nums)
        {
            Countmap[e]++;
        }
        for(auto& e:Countmap)
        {
            if(e.second > 1)
                return e.first;
        }
        return 0;
    }
};

2. LeetCode1题—两数之和

链接:https://leetcode-cn.com/problems/two-sum/
数组OJ题
①这题其实有点像9 * 9乘法表那种感觉

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0;i<nums.size();++i)
        {
            for(int j = i+1;j<nums.size();++j)
            {
                if(nums[i] + nums[j] == target)
                    return {i,j};
            }
        }
        return {0,0};
    }
};

②Hash映射，构建数组中的元素和对应的数组下标的对应关系，然后在找是否是有相同的元素

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        //我需要的是数和下标的一种映射的关系
        for(int i = 0;i<nums.size();++i)
        {
            m[nums[i]] = i;
        }
        //还不能有重复的下标
        for(int j = 0;j<nums.size();++j)
        {
            auto it = m.find(target-nums[j]);
            if(it != m.end() && it->second != j)
            {
                //说明找到了
                return {j,it->second};
            }
        }
        return {0,0};
    }
};

3. 删除有序数组中的重复项（前后指针法）

3.1 LeetCode26题—删除有序数组中的重复项I

链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
数组OJ题
双指针法，如果不相同就同时走，相同的时候就只让fast走，直到不相同

class Solution {
public:
   //最明显的方式就是使用双指针法，来解这道题
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        //题目已经说明是一个有序数组了
        int slow = 0,fast = 1;
        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                nums[slow + 1] = nums[fast];
                slow++;
            }
            else
            {
                fast++;
            }
        }
       return slow+1;
    }
};

3.2 LeetCode26题—删除有序数组中的重复项II

链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
数组OJ题
检查fast的位置是否和他前两个位置的值相同

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //通过题目的提示可以看出来，数组是不可能为空的
        int n = nums.size();
        if(n <=2)
            return n;
        int slow = 2,fast = 2;
        while(fast < n)
        {
            if(nums[slow-2] != nums[fast])
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

4. LeetCode217题—存在重复的元素

链接:https://leetcode-cn.com/problems/contains-duplicate/
数组OJ题

class Solution {
public:
    //这道题其实没有必要使用unordered_set 和 unordered_map
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i = 0;i<nums.size()-1;++i)
        {
            if(nums[i] == nums[i+1])
                return true;
        }
        return false;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() == 0)
            return false;
        unordered_map<int,int> HashMap;
        for(auto& e:nums)
        {
            HashMap[e]++;
        }

        for(auto& e:HashMap)
        {
            if(e.second > 1)
                return true;
        }
        return false;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> us;
        for(auto& e:nums)
        {
            us.insert(e);
        }

        //此时在unordered_set中就已经对重复的数进行了剔除
        if(us.size() == nums.size())
            return false;
        else
            return true;
    }
};

5. LeetCode215题—数组中的第K个最大元素

链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
数组OJ题

①但是这道题这种解法我并不觉得好，因为并没能真正的考察出实力，所以选择换一个解法

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),greater());
        //此时排序是按照降序进行的
        return nums[k-1];
    }
};

②我们可以使用优先级队列，也就是借助堆的思想，来求解这道题，如果自己写堆是不是过于麻烦，但是优先级队列的底层使用的就是堆，但是默认的情况下使用的是构建大堆，但是我们想要拿数组的前k个数构建一个降序，所以要修改比较器

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> KMinHeap(nums.begin(),nums.begin()+k);
        for(size_t i = k;i<nums.size();++i)
        {
            if(nums[i] > KMinHeap.top())
            {
                KMinHeap.pop();
                KMinHeap.push(nums[i]);
            }
        }
        return KMinHeap.top();
    }
};

6. LeetCode88题—合并两个有序数组

链接:https://leetcode-cn.com/problems/merge-sorted-array/
数组OJ题

class Solution {
public:
    //怎么想办法把数组二中的元素都放到数组1中
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0;i<n;++i)
        {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    //end1:nums1的末尾
    //end2:nums2的末尾
    //end:合并之后整个数组的末尾
        int end1 = m-1;
        int end2 = n-1;
        int end = m+n-1;
        
        while(end1 >= 0 && end2 >= 0)
        {   //选出尾最大的元素，存放到整个数组的末尾
            //每存放一个元素，尾向前移动一个位置
            if(nums1[end1] > nums2[end2])
            {
                nums1[end--] = nums1[end1--]; 
            }
            else
            {
                nums1[end--] = nums2[end2--];
            }
        }
        //剩余元素依次向末尾存放 
        while(end2 >= 0)
        {
            nums1[end--] = nums2[end2--];
        }
    }
};

7. LeetCode189题—旋转数组

链接:https://leetcode-cn.com/problems/rotate-array/
数组OJ题

对于这种翻转k的，就要想到有可能K是超过数组或者链表长度的

class Solution {
public:
    void Reverse(vector<int>& nums,int begin,int end)
    {
        while(begin<end)
        {
            int tmp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = tmp;
            begin++;
            end--;
        }
    }
    //还有一种可能就是旋转的数是大于数组的长度的
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        Reverse(nums,0,nums.size()-1);
        Reverse(nums,0,k-1);
        Reverse(nums,k,nums.size()-1);
    }
};

8. 数组中数字的次数

8.1 剑指offer56题—数组中数字的次数I

链接: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
数组OJ题

class Solution {
public:
    //这道题可以使用异或的思想
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        for(int i = 0;i<nums.size();++i)
        {
            ret ^= nums[i];
        }
        //此时就可以得到最终哪两个不同的数异或的值，然后在想办法将他们分开
        int m = 0;
        while(m < 32)
        {
            if(ret & (1<<m))
                break;
            else
                ++m;
        }

        //最终一定会跳出循环
        int x1 = 0,x2 = 0;
        for(int j = 0;j<nums.size();++j)
        {
            if(nums[j] & (1<<m))
            {
                x1 ^= nums[j];
            }
            else
            {
                x2 ^= nums[j];
            }
        }
        return {x1,x2};
    }
};

8.2 剑指offer56题—数组中数字的次数II

链接: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
数组OJ题

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> m;
        for(auto& ch : nums)
        {
            m[ch]++;
        }

        for(auto& e : m)
        {
            if(e.second == 1)
                return e.first;
        }
        return 0;
    }
};

9. LeetCode989题—数组形式的整数加法（重要）

链接:https://leetcode-cn.com/problems/add-to-array-form-of-integer/
数组OJ题

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        //这是我最后一次今天在做一次这个题
        vector<int> v;
        for(int i = num.size()-1;i>=0;--i)
        {
            int ret = num[i] + k % 10;
            k /= 10;
            if(ret > 9)
            {
                k++;
                ret -= 10;
            }
            v.push_back(ret);
        }
        //上面的这段代码对于正常的逻辑还可以，但是有几点是没有考虑到的
        //比如测试用例所提到的  215 + 806 这个数值最终的进位也需要插入到v中
        //还有之中可能就是数组中[0] + 23 ....的情况
        while(k != 0)
        {
            v.push_back(k%10);
            k /= 10;
        }
        reverse(v.begin(),v.end());
        return v;
    }
};

10. 顺序表和链表的对比

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。（可以理解为在物理和逻辑层面上都是开辟的连续空间）

  1. 开辟的空间连续，支持随机的访问（优点）
  2. 中间/头部的插入删除，时间复杂度为O(N)，这里还有就是顺序表尾插效率很高
  3. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  4. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。（只有逻辑上认为是连续的）

  1. 以节点为单位存储，不支持随机访问（缺点）
  2. 任意位置插入删除时间复杂度为O(1)
  3. 没有增容问题，插入一个开辟一个空间。
上一篇：nowcoder-oj【面试高频TOP榜单-入门难度】


下一篇：[游记]在SSL的集训生活