Leetcode算法（二）-探索初级算法-数组

发表于 | 分类于 ，

1. 概述

2. 算法题

2.1 删除排序数组中的重复项

  • 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度
  • 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
  • 主要思想
    • 双指针思想
    • 快指针遍历数组，慢指针在一定条件下移动，条件如下
      • 当遇到重复元素，位置不变
      • 当遇到不同元素时，位置向前移动一位，并将元素赋值给当前位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 1) {
            return 0;
        }
        int i = 0, j = 0;
        while (i < nums.size()) {
            if (nums[i] != nums[j]) {
                j ++;
                nums[j] = nums[i];
            }
            i ++;
        }
        return j + 1;
    }
};

2.2 存在重复元素

  • 给定一个整数数组，判断是否存在重复元素
  • 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false
  • 解题思路
    • 利用set集合，过滤重复元素
    • 如果set集合大小小于原数组大小，则证明有重复元素
1
2
3
4
5
6
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() > unordered_set<int>(nums.begin(), nums.end()).size();
    }
};

2.3 加一

  • 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一
  • 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字
  • 你可以假设除了整数 0 之外，这个整数不会以零开头
  • 主要思想
    • 缝9，置为0，高位加一
    • 最后，如果最高位为9，加一，则需要在首位插入1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> nums;
        bool isLabel = false;
        for (int i = digits.size() - 1 ; i >= 0; i --) {
            if (!isLabel) {
                digits[i] += 1;
            }
            if (digits[i] > 9) {
                digits[i] = 0;
                nums.push_back(digits[i]);
            } else {
                isLabel = true;
                nums.insert(nums.begin(), digits[i]);
            }                   
        }
        if (digits[0] == 0) {
            nums.insert(nums.begin(), 1);
        }
        return nums;
    }
};
  • 优化
    • 不开辟新空间
    • 从低位到高位遍历，遇到9，就置为0；不满9，加一，退出
    • 如果最高位也是9，则置为1，最后压入0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i --) {
            if (i > 0 && digits[i] == 9) {
                digits[i] = 0;
            } else if (i >= 0 && digits[i] < 9) {
                digits[i] += 1;
                break;
            }
            if (i == 0 && digits[i] == 9) {
                digits[i] = 1;
                digits.push_back(0);
            }
            
        }
        return digits;
    }
};

2.4 买卖股票的最佳时机 II

  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格
  • 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）
  • 解题思路
    • 低买高卖
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = 0, sell = 1;
        int price = 0, diff = 0;
        for (int i = 0; i < prices.size(); i ++) {
            if (buy == 0 && sell != 0 && i < prices.size() - 1 && prices[i] < prices[i + 1]) {
                price = prices[i];
                buy = 1;
                sell = 0;
            } else if (buy != 0 && sell == 0 && i < prices.size() - 1 && prices[i] > prices[i - 1] && prices[i] >= prices[i + 1]) {
                diff += prices[i] - price;
                buy = 0;
                sell = 1;
            }
            if (i == prices.size() - 1 && buy != 0) {
                diff += prices[i] - price;
                buy = 0;
                sell = 1;
            }
        }
        return diff;
    }
};

2.5 旋转数组

  • 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
  • 解题思路
    • 使用一个数组保存k位，移动结束后，再将数组内的数据赋值给原数组前k位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.size() <= k) {
            k %= nums.size();
        }
        vector<int> array;
        for(int i = nums.size() - 1; i > nums.size() - k - 1; i --) {
            array.push_back(nums[i]);
        }
        for (int i = nums.size() - k - 1; i >= 0; i --) {
            nums[i + k] = nums[i];
        }
        for (int i = 0; i < k; i ++) {
            nums[i] = array[k - i - 1];
        }
    }
};
  • 循环交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void swap(vector<int> & nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    void rotate(vector<int>& nums, int k) {
        if(k >= nums.size())
            k %= nums.size();
        if(k != 0) {
            int n=nums.size();
            for (int start = 0; start < nums.size() && k != 0; n -= k, start += k, k %= n) {
                for (int i = 0; i < k; i++) {
                    swap(nums, start + i, nums.size() - k + i);
                }
            }
        }
    }
};
  • 库函数
1
2
3
4
5
6
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        std::rotate(nums.begin(), nums.end() - k % nums.size(), nums.end());
    }
};
  • 三次反转
    • 把左部分翻转
    • 把右部分翻转
    • 最后把整体翻转
1
2
3
4
5
6
7
8
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        reverse(nums.begin(), nums.end() - k % nums.size());
        reverse(nums.end() - k % nums.size(), nums.end());
        reverse(nums.begin(), nums.end());
    }
};

2.6 只出现一次的数字

  • 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
  • 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗
  • 解题思路
    • 如果没有时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种
      • 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字
      • 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字
      • 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字
    • 上述三种解法都需要额外使用 O(n)的空间，其中 n是数组长度。如果要求使用线性时间复杂度和常数空间复杂度
    • 位运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i ++) {
            if (i == 0) {
                if (nums[i] != nums[i + 1]) {
                    return nums[i];
                }
            } else if (i == nums.size() - 1) {
                if (nums[i] != nums[i - 1]) {
                    return nums[i];
                }
            } else {
                if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        int ret = nums[0];
        for (int i = 1; i < nums.size(); i ++) {
            ret ^= nums[i];
        }
        return ret;
    }
};

2.7 两个数组的交集 II

  • 给定两个数组，编写一个函数来计算它们的交集
  • 解题思路
    • 使用map，第一轮循环让map中的value值存储nums1中对应key值的元素数量，第二轮循环遍历num2中的元素，如果map中此时key为i对应的value大于等于1,即为交集元素，加入存储答案的vector中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        unordered_map<int, int> m;
        
        for (auto num : nums1) {
            ++m[num];
        }
        
        for (auto num : nums2) {
            if (m.find(num) != m.end() && --m[num] >= 0) {
                ret.push_back(num);
            }
        }
        return ret;
        
    }
};

2.8 移动零

  • 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
  • 解题思路
    • 双指针，第一个指针正常向后移动，第二个指针一直保持指向第一个零；如果，第一个指针指向非零元素，则交换两个指针的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if (nums.size() <= 1) {
            return;
        }
        int j = -1;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] != 0 && j >= 0) {
                swap(nums[i], nums[j]);
                j ++;
            } else if (nums[i] == 0 && j == -1) {
                j = i;
            }
            
        }
    }
};
1
2
3
4
5
6
7
void moveZeroes(vector<int>& nums) {
    for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[lastNonZeroFoundAt++], nums[cur]);
        }
    }
}

2.9 两数之和

  • 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标
  • 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍
  • 解题思路
    • 查找问题想到哈希表来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> results;
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i ++) {
            if (m.find(target - nums[i]) != m.end()) {
                results.push_back(m[target - nums[i]]);
                results.push_back(i);
                return results;
            }
            m[nums[i]] = i;
        }
        return results;
    }
};

2.10 有效的数独

  • 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可
    • 数字 1-9 在每一行只能出现一次
    • 数字 1-9 在每一列只能出现一次
    • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
  • 解题思路
    • 遍历到每个数的时候，例如boar[i][j]，我们判断其是否满足三个条件
      • 在第 i 个行中是否出现过
      • 在第 j 个列中是否出现过
      • 第 j/3 + (i/3)*3个box中是否出现过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0};// 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
        // 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
        int col[9][10] = {0};// 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
        int box[9][10] = {0};// 存储每一个box的每个数是否出现过，默认初始情况下，在每个box中，每个数都没有出现过。整个board有9个box。
        for(int i=0; i<9; i++){
            for(int j = 0; j<9; j++){
                // 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过，
                // 同时判断这个数在其所在的列有没有出现过
                // 同时判断这个数在其所在的box中有没有出现过
                if(board[i][j] == '.') continue;
                int curNumber = board[i][j]-'0';
                if(row[i][curNumber]) return false; 
                if(col[j][curNumber]) return false;
                if(box[j/3 + (i/3)*3][curNumber]) return false;

                row[i][curNumber] = 1;// 之前都没出现过，现在出现了，就给它置为1，下次再遇见就能够直接返回false了。
                col[j][curNumber] = 1;
                box[j/3 + (i/3)*3][curNumber] = 1;
            }
        }
        return true;
    }
};

（以上代码参考：https://leetcode-cn.com/problems/valid-sudoku/solution/36-jiu-an-zhao-cong-zuo-wang-you-cong-shang-wang-x/）

2.11 旋转图像

  • 给定一个 n × n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度
  • 解题思路
    • 转置加翻转
    • 先转置矩阵，然后翻转每一行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix[0])        
        # transpose matrix
        for i in range(n):
            for j in range(i, n):
                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i] 
        
        # reverse each row
        for i in range(n):
            matrix[i].reverse()
1
2
3
4
5
6
7
8
9
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for (int i=0; i<matrix.size(); i++)
            for (int j=0; j<i; j++) swap(matrix[i][j], matrix[j][i]);
        
        for (auto& row: matrix) reverse(row.begin(), row.end());
    }
};