LeetCode

数组

26. 删除排序数组中的重复项

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        int count = 0;
        int index = 0;

        if((nums.empty())|| (nums.size() == 0))
        {
            std::cout << "nums is empty or NULL!" << std::endl;
            return 0;
        }

        for(int i = 1; i < nums.size(); i++ )
        {
           if(nums[i] == nums[index])
           {
               count++;
           }
           else
           {
               nums[i-count] = nums[i];
               index++;
           }

        }

        return nums.size() - count;
    }
};

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
顺时针旋转90°：
[1,2],[3,4]
=>[3,1],[4,2];
其中可以看出：

(i,j)顺时针旋转90°为(j,row-1-i);
若继续旋转90°为(row-1-i,col-1-j);
再顺时针旋转90°为(col-1-j,i);
可以知道将矩阵中的一个数给顺时针旋转90°，也就是将四个数互相交换位置

    //其中row为行,col为列
    swap(matrix[i][j],matrix[col-1-j][i]);
	swap(matrix[col-1-j][i],matrix[row-1-i][col-1-j]);
	swap(matrix[row-1-i][col-1-j],matrix[j][row-1-i]);
    ```
```cpp
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
         for(size_t i = 0;i<(matrix.size()+1)/2;++i)
        {
            for(size_t j =i;j<matrix.size()-i-1;++j)
            {
                swap(matrix[i][j],
                matrix[matrix.size()-1-j][i]);

                swap(matrix[matrix.size()-1-j][i],
                matrix[matrix.size()-1-i][matrix.size()-1-j]);

                swap(matrix[matrix.size()-1-i][matrix.size()-1-j]
                ,matrix[j][matrix.size()-1-i]);
            }    
        }

    }
};

66.加一

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int length = digits.size();

        for(int i=length-1; i>=0; --i)
        {
            digits[i] +=1;
            //digits[i] =digits[i]%10;
            if(digits[i] == 10)
            {
                digits[i] = 0;
            }
            else
            {
                return digits;
            }
        }
        //if all digits are num 9, then the loop will not return the NUM,so The highest digit carries 1
        digits.insert(digits.begin(),1);
        return digits;

    }
};

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

贪心算法

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int profit = 0;
        int data = prices.size();
        if(prices.empty() || (data== 0)){
            std::cout << "Parameters Invalid" << std::endl;
        }

        for(int i=1; i < data; ++i)
        {
            profit += max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }
};

** "i++" 与“++i”的区别**
i++ 与 ++i 的主要区别有两个：根本区别是语义上的区别
a.) i++ 返回原来的值，++i 返回加1后的值。
**b.) ** i++ 不能作为左值，而++i 可以。

如果没有用到返回值的话，区别在于效率。

若i是内置的数值类型，两者完全一样
若i是一些自定义的类，如iterator，++i的效率 > = i++的效率

136.只出现一次的数字

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

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int repeat = 0;

        for(int i = 0; i< nums.size(); ++i)
        {
            repeat ^= nums[i];
        }
        return repeat;
    }
};

189.旋转数组

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

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length = nums.size();
        vector<int> temp(length);
        k = k % length; // Determine whether *k* exceeds the length of array
        
        if(nums.empty() || (nums.size()==0)){
            std::cout << "Invalid Parameter" << std::endl;
        }
        for (int i = 0; i < nums.size(); i++) {
            temp[i] = nums[i];
        }
        for(int i = 0; i < k; ++i)
        {
            nums[i] = temp [length-k+i];
        }
        for(int j= k; j < nums.size(); ++j)
        {
            nums[j] = temp[j-k];
        }
    }
};

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {


        if(nums.empty() || (nums.size()==0)){
            std::cout << "Invalid Parameter" << std::endl;
        }
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size()-1; ++i)
        {
            if (nums[i] == nums[i+1]){
                return true;
            }
        }

        return false;

    }
};

283. 移动零

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

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int length = nums.size();
       // vector<int> nums2(length);
        int index = 0;
        for(int i=0; i<=length-1; i++)
        {
            if(nums[i] != 0)
            {
                nums[index] = nums[i];
                index++;
            }
        }

        if((length -index) > 0)
        {
            for(int i = index; i <= length -1; i++)
            {
                nums[i] = 0;
            }
        }
        //nums = nums2;

    }
};

350. 两个数组的交集 II

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());  // Sort
        vector<int>target;

        for(vector<int>::iterator it1=nums1.begin(),it2=nums2.begin();it1!=nums1.end()&&it2!=nums2.end();)
        {
            if(*it1<*it2 ) it1++;
            else if(*it1==*it2)
            {
                target.push_back(*it1);
                 it1++;
                 it2++;
            }
            else if(*it1>*it2 ) it2++;
        }
        return target;
    }
};

字符串

344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

对称交换

class Solution {
public:
    void reverseString(vector<char>& s) {
        int length = s.size();
        for (int i = 0; i < (length+1)/2; ++i)
        {
            swap(s[i],s[length-1-i]);
        }
        

    }
};

7.整数反转

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while(x != 0)
        {
            int pop = x %10;
            x /=10;
            if((rev > INT_MAX/10))
            {
                return 0;
            }
            if((rev < INT_MIN/10))
            {
                return 0;

            }
            rev = rev*10 +pop;
        }
        return rev;

    }
};

Algorithms

数组