Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int len = nums.size();
        for(int i=0; i<len; i++) {
            int m = abs(nums[i])-1;  // index start from 0
            nums[m] = nums[m]>0 ? -nums[m] : nums[m];
        }
        vector<int> res;
        for(int i = 0; i<len; i++) {
            if(nums[i] > 0) res.push_back(i+1);
        }
        return res;
    }
};

该题用了一个特殊的方法，取负法。

含义是：将元素对应的位置取负。简单一句话可能不好理解，我们举个例子。假设在位置k放了元素i，则在取负的过程中i的取值有两种可能：为正，表示当前尚未遇到元素k将该位置取负；为负，表示当前已经有元素k出现，并将元素取负。但是我们不关心k，我们关心元素i。元素i既然出现，我们就看一下位置i：为正，表示这是元素i第一次出现，我们将位置i取负；为负，表示元素i已经出现过一次，我们不做任何操作。不管一个元素出现一次还是两次，只要出现它对应的位置就会被取负。当某个元素不出现的时候，该元素对应的位置始终访问不到，所以还是正值，通过这种方法我们就可以找到哪些元素没有出现。

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

class Solution {
public:
    int areaNum(vector<vector<int>>& grid, int m ,int n){
        if (m<grid.size()&&m>=0&&n<grid[0].size()&&n>=0&&grid[m][n]==1) {
            //将经过的位置标记为0，避免循环检验
            grid[m][n] = 0;
            return 1+ areaNum(grid, m+1, n)+areaNum(grid, m, n+1)+areaNum(grid, m-1, n)+areaNum(grid, m, n-1);
        }
        return 0;
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int result = 0;
        for (int i =0; i<grid.size(); i++) {
            for (int j=0; j<grid[0].size(); j++) {
                if (grid[i][j]==1) {
                    result = max(result, areaNum(grid, i, j));
                }
            }
        }
        return result;
    }
};

Given a binary array, find the maximum number of consecutive 1s in this array.

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int sum1 = 0;
        int tmp = 0;
        for (int i=0; i<nums.size(); i++) {
        if (nums[i]==1) {
            tmp++;
        }else{
            tmp = 0;
        }
            sum1 = max(tmp, sum1);
        }
    
        return sum1;
    }
};

In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.

You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int sumNum = nums.size() * nums[0].size();
        int r1 = nums.size();
        int c1 = nums[0].size();
        if (sumNum != r*c) {
            return nums;
        }
        vector<vector<int>> result = vector<vector<int>>(r,vector<int>(c,0));
        int j = 0;
        for (int i =0; i<r*c; i++) {
            result[i/c][i%c] = nums[i/c1][i%c1];
        }
        
        return result;
    }
};

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        
        if (nums.size()<2) {
            return nums.size();
        }
        unordered_map<int, int>startIndex , number;
        int len = nums.size();
        int fre = 0;
        for (int i=0; i<nums.size(); i++) {
            if (startIndex.count(nums[i])==0) {
                startIndex[nums[i]]=i;
            }
            number[nums[i]]++;
            if (number[nums[i]]==fre) {
                len = min(i-startIndex[nums[i]]+1, len);
            }
            if (number[nums[i]]>fre) {
                len = i - startIndex[nums[i]] + 1;
                fre = number[nums[i]];
            }
        }
        
        return len;
    }
};

该算法主要使用了两个hash_map:
一个来记录数字所出现的次数，另一个记录数字最开始出现的位置。一旦有一个数字的频数超过了当前的len，则更新len，若两个数字出现的频率相等则取长度最小的。