LeetCode 数组与矩阵(2)

Alex_Shen
2021-02-16 / 0 评论 / 0 点赞 / 84 阅读 / 5,311 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Leetcode 题解 - 数组与矩阵

283. 把数组中的 0 移到末尾

283. Move Zeroes (Easy)

Leetcode / 力扣

思路:第一次遍历获取数组中所有的非零元素总数及其位置,并且重置数组该位置的元素值。然后将cal+1到尾部的元素全部置为0。

    void moveZeroes(vector<int>& nums) {
        int cal = 0;
        for (auto x : nums)
        {
            if (x != 0)
            {
                nums[cal++] = x;
            }
        }
        for (auto it = cal; it != nums.size(); it++)
            nums[it] = 0;
    }

566. 改变矩阵维度

566. Reshape the Matrix (Easy)

Leetcode / 力扣

    vector<vector<int>> matrixReshape(vector<vector<int>> &nums, int r, int c)
    {
        if (nums.size() * nums[0].size() != r * c)
            return nums;
        queue<int> data;
        for (auto x : nums)
            for (auto y : x)
                data.push(y);
        vector<vector<int>> ans;
        for (int i = 0; i < r; i++)
        {
            ans.push_back(vector<int>());
            for (int j = 0; j < c; j++)
            {
                ans[i].push_back(data.front());
                data.pop();
            }
        }
        return ans;
    }

485. 找出数组中最长的连续 1

485. Max Consecutive Ones (Easy)

Leetcode / 力扣

思路1:依次遍历,查询各个连续1串的长度,并且比较出最大值。

    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max=0,cnt=0;
        for(auto x:nums){
            if(x==1){
                cnt++;
                if(max<cnt)
                    max=cnt;
            }
            else
                cnt=0;
        }
        return max;
    }

思路2:动态规划法。如果当前位置是1,则长度为前一位长度+1,如果是0,则设计为0。最后求出dp最大值。

    int findMaxConsecutiveOnes(vector<int> &nums)
    {
        vector<int> dp(nums.size());
        dp[0] = nums[0] == 1 ? 1 : 0;
        for (int i = 1; i < nums.size(); i++)
            dp[i] = nums[i] == 1 ? dp[i - 1] + 1 : 0;
        return *max_element(dp.begin(), dp.end());
    }

240. 有序矩阵查找

240. Search a 2D Matrix II (Medium)

Leetcode / 力扣

思路:类似于二叉树搜索的思路,从左下角开始进行搜索。如果target>matrix[row][col],就向右移动一格,否则向上移动一格。如果落到矩阵外部就搜索结束。
可以从左下角或者右上角开始搜索,但不能从左上角或者右下角开始,因为必须保证大于小于对应不同的移动路径。

    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        int row = m - 1, col = 0;
        while (row >= 0 && col <= n - 1)
        {
            if (target > matrix[row][col])
                col++;
            else if (target < matrix[row][col])
                row--;
            else if (target == matrix[row][col])
                return true;
        }
        return false;
    }

378. 有序矩阵的 Kth Element

378. Kth Smallest Element in a Sorted Matrix ((Medium))

Leetcode / 力扣

暴力解法:

    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        vector<int> rec;
        for (auto &row : matrix)
        {
            for (int it : row)
            {
                rec.push_back(it);
            }
        }
        sort(rec.begin(), rec.end());
        return rec[k - 1];
    }

645. 一个数组元素在 [1, n] 之间,其中一个数被替换为另一个数,找出重复的数和丢失的数

645. Set Mismatch (Easy)

Leetcode / 力扣

思路:利用map,记录每一个元素出现的次数。0次为被替换元素,2次为重复元素。

    vector<int> findErrorNums(vector<int> &nums)
    {
        vector<int> ans;
        int num1 = -1, num2 = -1;

        map<int, int> m;
        for (int i = 0; i < nums.size(); i++)
            m[nums[i]]++;
        for (int i = 1; i <= nums.size(); i++)
        {
            if (m.count(i) == 0)
                num2 = i;
            if (m[i] == 2)
                num1 = i;
            if (num1 != -1 && num2 != -1)
                break;
        }
        ans.push_back(num1);
        ans.push_back(num2);
        return ans;
    }

287. 找出数组中重复的数,数组值在 [1, n] 之间

287. Find the Duplicate Number (Medium)

Leetcode / 力扣

思路:哈希表

    int findDuplicate(vector<int> &nums)
    {
        map<int, int> m;
        for (auto x : nums)
        {
            m[x]++;
            if (m[x] == 2)
                return x;
        }
        return -1;
    }

思路:二分查找

    int findDuplicate(vector<int> &nums)
    {
        int n = nums.size();
        int l = 1, r = n - 1, ans = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i)
            {
                cnt += nums[i] <= mid;
            }
            if (cnt <= mid)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }

667. 数组相邻差值的个数

667. Beautiful Arrangement II (Medium)

Leetcode / 力扣

思路:先用k+1个数字完成题目要求,排列顺序为1,k+1,2,k,......k/2,k/2+1。这样可以做到前k+1个数字的差为k,k-1......1,之后的数字可以从小到大插入。

    vector<int> constructArray(int n, int k)
    {
        vector<int> ans;
        int i = 1, j = i + k;
        while (j > i)
        {
            ans.push_back(i++);
            ans.push_back(j--);
            if (i == j)
                ans.push_back(i);
        }
        for (int i = k + 2; i <= n; i++)
            ans.push_back(i);
        return ans;
    }

697. 数组的度

697. Degree of an Array (Easy)

Leetcode / 力扣

思路:遍历数组,利用哈希表记录元素出现的位置。然后找到出现最多的元素,并且比较最早出现位置与最晚出现位置的差值,这是某一最大度对应的最小子集的长度,最后与所有相同最大度子集进行比较。

    int findShortestSubArray(vector<int> &nums)
    {
        map<int, vector<int>> mp;
        for (int i = 0; i < nums.size(); i++)
            mp[nums[i]].push_back(i);
        vector<int> ele;
        int max = 0;
        for (auto x : mp)
        {
            if (x.second.size() > max)
                max = x.second.size();
        }
        int ans = 500001;
        for (auto x : mp)
        {
            int min_pos = 50001, max_pos = 0;
            if (x.second.size() == max)
            {
                for (auto pos : x.second)
                {
                    if (pos < min_pos)
                        min_pos = pos;
                    if (pos > max_pos)
                        max_pos = pos;
                }
                if (max_pos - min_pos + 1 < ans)
                    ans = max_pos - min_pos + 1;
            }
        }
        return ans;
    }

766. 对角元素相等的矩阵

766. Toeplitz Matrix (Easy)

Leetcode / 力扣

思路1:分别依次遍历每一条对角线上的元素与首元素进行比较。

    bool isToeplitzMatrix(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        for (int I = 0; I < n; I++)
        {
            //对角线起点在第一行
            int i = 0, j = I, ele = matrix[i][j];
            bool check = true;
            while (i < m && j < n)
            {
                if (matrix[i][j] != ele)
                {
                    check = false;
                    break;
                }
                i++, j++;
            }
            if (!check)
                return check;
        }
        for (int I = 0; I < m; I++)
        {
            //对角线起点在第一列
            int i = I, j = 0, ele = matrix[i][j];
            bool check = true;
            while (i < m && j < n)
            {
                if (matrix[i][j] != ele)
                {
                    check = false;
                    break;
                }
                i++, j++;
            }
            if (!check)
                return check;
        }
        return true;
    }

思路2:遍历整个数组,与左上角元素进行比较。

    bool isToeplitzMatrix(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]!=matrix[i-1][j-1])
                    return false;
            }
        }
        return true;
    }

565. 嵌套数组

565. Array Nesting (Medium)

Leetcode / 力扣

思路:利用visited数组记录每个元素的访问情况。每一次循环都会遍历出一个环,并与max比较环的大小。(因为环的特性,利用一个visited数组就可以记录所有元素的访问情况,并且不会有重叠元素)

    int arrayNesting(vector<int> &nums)
    {
        int n = nums.size();
        vector<bool> visited(n, false);
        int max = 0;
        for (int i = 0; i < n; i++)
        {
            int cnt = 0;
            while (visited[i] == false)
            {
                cnt++;
                visited[i] = true;
                i = nums[i];
            }
            if (max < cnt)
                max = cnt;
        }
        return max;
    }

769. 分隔数组

769. Max Chunks To Make Sorted (Medium)

Leetcode / 力扣

思路:分隔的依据前一个区间的最大值要小于后面的所有数字,方法是当区间的最大值等于区间最右下标时分隔数组。

    int maxChunksToSorted(vector<int> &arr)
    {
        int cnt = 0;
        int Max = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            Max = max(Max, arr[i]);
            if (Max == i)
                cnt++;
        }
        return cnt;
    }

原项目地址:https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%95%B0%E7%BB%84%E4%B8%8E%E7%9F%A9%E9%98%B5.md

0

评论区