初级算法 数组

1.从排序数组中删除重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。

思路

拿到题目，看到重复项目，第一时间想到的是set。直接遍历插进去就可以了。但是题目说空间复杂度是O(1)，所以是用滑动小标进行实现

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())return 0;
        int n = 0;
        for(int i = 1;i<nums.size();i++){
            if(nums[i]!=nums[n])nums[++n]=nums[i];
        }
        return n+1;
    }
};

2.买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: [7,1,5,3,6,4]输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:输入: [1,2,3,4,5]输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:输入: [7,6,4,3,1]输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0

思路：计算相邻两天的差值，只买赚的

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        auto n = prices.size();
        if(n == 1)
            return 0;
        auto earn=0;
        for(auto i = 1;i<n;i++){
            if(prices[i]-prices[i-1]>0)earn+=prices[i]-prices[i-1];
        }
        return earn;
    }
};

3.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。

思路

1. 做K次右移就完事儿了

class Solution {
public:
    void rotate(vector<int> & nums,int k){
        if (nums.empty() || (k %= nums.size()) == 0) return;
        k %= nums.size();
        for(int i = 0 ;i<k;i++)rotateOnce(nums);
        return;
    }
    
    void rotateOnce(vector<int>& nums){
        int lastVal = nums.front();
        for(int i = 1;i<nums.size();i++){
            int temp = lastVal;
            lastVal = nums[i];
            nums[i] = temp;
        }
        nums[0] = lastVal;
        return;
    }
};

但是nums.size()大了之后就会出现超时，所以得换个方法

2.利用vector::push_back(),vector::erase()模拟左移

右移k次(k<n)，相当于左移n-k次

class Solution {
public:
    void rotate(vector<int> & nums,int k){
        if (nums.empty() || (k %= nums.size()) == 0) return;
        k %= nums.size();
        k = nums.size()-k;
        for(int i = 0 ;i<k;i++){
            nums.push_back(nums.front());
            nums.erase(nums.begin());
        }
        return;
    }
    
};

还是超时？？？ wtf

3.思路是先把前n-k个数字翻转一下，再把后k个数字翻转一下，最后再把整个数组翻转一下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

4.存在重复

给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:
输入: [1,2,3,1]
输出: true

示例 2:
输入: [1,2,3,4]
输出: false

示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

思路：排序，遍历一遍看到相同返回false

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int i;
        if(nums.size() <= 1) return false;
        sort(nums.begin(),nums.end());
        for(i = 1;i < nums.size();i++){
            if(nums[i] == nums[i-1])return true;
        }
        return false;
    }
};

4.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

思路：异或操作，相同的将会抵消成0

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return accumulate(nums.begin(),nums.end(),0,bit_xor<int>());// begin end initialVal operator
    }
};

5.两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
• 我们可以不考虑输出结果的顺序。

进阶:

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路： 遍历较小的一个数组，在较大的当中找相同的，找完从较大的数组中删除这个元素

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        if(nums1.size()<nums2.size()){
            for(int i1 = 0;i1<nums1.size();i1++){
                for(int i2 = 0;i2<nums2.size();i2++){
                    if(nums1[i1]==nums2[i2]){
                        result.push_back(nums1[i1]);
                        nums2.erase(nums2.begin()+i2);
                        break;
                    }
                }
            }
        } else{
            for(int i2 = 0;i2<nums2.size();i2++){
                for(int i1 = 0;i1<nums1.size();i1++){
                    if(nums1[i1]==nums2[i2]){
                        result.push_back(nums1[i1]);
                        nums1.erase(nums1.begin()+i1);
                        break;
                    }
                }
            }
        }
        return  result;
    }
};

6.加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

思路，很简单，从后往前遍历就可以

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        bool c_flag = false;
        int i = (int)digits.size()-1;
        do{
            digits[i] = digits[i]+1;
            if(digits[i]>=10){
                digits[i]=digits[i]-10;
                c_flag = true;
            } else c_flag= false;
            i = i-1;
        }while (c_flag&&i>=0);
        if(i<0&&c_flag)digits.insert(digits.begin(),1);
        return digits;
    }
};

7.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

思路，还是和之前的去除重复一样，利用滑动下标的方法

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size()<2)return;
        int n = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i]!=0){
                nums[n++] = nums[i];
            }
        }
        for(int i = n;;i<nums.size();i++)nums[i]=0;
        return;
    }
};

8.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路，两个for循环嵌套遍历

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

9.有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

思路，直接挨个检查行，列，方块就好

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i = 0;i<9;i++){
            if(!ValidSudoRow(board,i))return false;
            if(!ValidSudoColum(board,i))return false;
        }
        for(int i =0;i<3;i++)
            for(int j = 0;j<3;j++){
                if(!ValidSudoCell(board,i,j))return false;
            }
        return true;
    }

    bool ValidSudoRow(vector<vector<char>>& board,int row){
        set<int> test;
        for(int i = 0;i<9;i++){
            if(board[row][i]=='.')continue;
            if(!board[row][i]>='1' && board[row][i]<='9')return false;
            if(test.find(board[row][i]-'0')==test.end()){
                test.insert(board[row][i]-'0');
            } else return false;
        }
        return true;
    }

    bool ValidSudoColum(vector<vector<char>>& board,int colum){
        set<int> test;
        for(int i = 0;i<9;i++){
            if(board[i][colum]=='.')continue;
            if(!board[i][colum]>='1' && board[i][colum]<='9')return false;
            if(test.find(board[i][colum]-'0')==test.end()){
                test.insert(board[i][colum]-'0');
            } else return false;
        }
        return true;
    }
    
    bool ValidSudoCell(vector<vector<char>>& board,int row_i,int col_i){
        set<int> test;
        for(int i = 0;i<3;i++)
            for(int j = 0;j<3;j++){
                if(board[i+row_i*3][j+col_i*3]=='.')continue;
                if(!board[i+row_i*3][j+col_i*3]>='1' && board[i+row_i*3][j+col_i*3]<='9')return false;
                if(test.find(board[i+row_i*3][j+col_i*3]-'1')==test.end()){
                    test.insert(board[i+row_i*3][j+col_i*3]-'1');
                } else return false;
            }
        return true;
    }
};

10.旋转图像

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

思路

首先以从对角线为轴翻转，然后再以x轴中线上下翻转即可得到结果

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - i; ++j) {
                swap(matrix[i][j], matrix[n - 1- j][n - 1 - i]);
            }
        }
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }
    }
};

这种方法首先对原数组取其转置矩阵，然后把每行的数字翻转可得到结果

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};