LeetCode初级算法数组类——算法总结

LeetCode初级算法数组类——算法总结

PS：算法并非原创，总结的本意在于温故知新、巩固知识。

1、删除排序数组中的重复项
使用C++进行答题。
代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int numsSize =  nums.size();
        if(numsSize == 0)
            return 0;
        int i = 0;//i用来记录数组中不同数字的个数，同时在第一次for循环中来代表数组的0号元素
        for (int j = 1; j < numsSize; j++) {
            if(nums[j] != nums[i]){//如果i号元素和j号元素不相同，则i增加一位
                i++;
                nums[i]=nums[j];//此时用nums[i]记录nums[j]的数值，然后进行循环
            }
        }
        return i+1;//返回值+1，即代表数值不同的个数       
    }
};

算法解析：
用一个变量i记录数组中非重复的数据数量，同时，i也用来指示数组中的存储位置变化。在排序数组中，用j遍历数组，i初始值为0，如果nums[j]和nums[i]不相等，将这个不相等的数据写入nums[i+1]的位置，如果二者相等，j继续遍历。
最后得到的将是一个长度为i+1的数组，且元素均不相同。

算法占用时空间资源：

2、买卖股票的最佳时机 II
使用C++进行答题。
代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) 
return 0;
        int peak = prices[0];   // 峰 极大值
        int valley = prices[0]; // 谷 极小值
        int ret = 0;
        int i = 0;
        // 累加每一对紧邻着的波峰-波谷差值
        while (i < prices.size()-1){
            // 找波谷
while (i+1 < prices.size() && prices[i] >= prices[i+1])
 ++ i;   
            valley = prices[i];
// 找波峰
            while (i+1 < prices.size() && prices[i] <= prices[i+1]) 
++ i; 
            peak = prices[i];
            if (peak - valley > 0)
                ret += peak - valley;
        }
        return ret;
    }
};

算法解析：
进行波峰和波谷的寻找。i遍历到某一个点，之后进行二次遍历，寻找到波峰或者波谷。当峰谷均找到之后，进行求差累计。

算法占用时空间资源：


3、旋转数组
使用C++进行答题。
代码如下：

class Solution {
public:
    //数组反转函数
    void reverseArray(vector<int>& array, int begin, int end)
    {
        int temp, tmp_end = end;
        for (int i = begin; i <= (begin + end)/2; i++)
        {
            temp = array[i];
            array[i] = array[tmp_end];
            array[tmp_end] = temp;
            tmp_end--;
        }
    }
    
    void rotate(vector<int>& nums, int k) {
       int len = nums.size();
        k %= len; 
        if(k == 0)
            return; 
        //使用自定义的反转函数
        reverseArray(nums, 0, len - k - 1);
        reverseArray(nums, len - k, len - 1);
        reverseArray(nums, 0, len - 1);
 
        //使用C++自带的反转函数
	    /*reverse(nums.begin(), nums.end() - k);
	    reverse(nums.end() - k, nums.end());
	    reverse(nums.begin(), nums.end());*/
	}
};

算法解析：
使用反转函数，主要是观察得出数组元素移动前后的顺序变化。反转函数可以使用自带的函数，也可以使用自定义的反转函数。反转函数使用三次可达到最终结果。
反转过程：【例子：1 2 3 4 5 6 7移动4位】
1 2 3 4 5 6 7 --> 3 2 1 4 5 6 7–> 3 2 1 7 6 5 4 --> 4 5 6 7 1 2 3
很巧妙的一种算法，佩服大神思维！
补充：C++自带的reverse算法说明：
reverse函数功能是逆序（或反转），多用于字符串、数组、容器。
头文件是#include <algorithm>
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值
reverse(nums.begin(), nums.end() - k);————移动前端元素，长度为nums.size() - k(例如7-4 = 3)
reverse(nums.end() - k, nums.end());————移动后端元素，长度为k(例如4 )
reverse(nums.begin(), nums.end());————移动全部元素，长度为nums.size()(例如7 )

算法占用时空间资源：

4、存在重复元素
使用python3解答，
代码如下：

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        
        """
        dic=collections.Counter(nums)
        for value in dic.values():
            if value>=2:
                return True
        return False

算法解析：
主要用到了python中的功能函数，是一种很巧妙的方法。
先介绍一下collections.Counter(nums)的含义。collections模块是python的标准库，collections.Counter()是字典的子类，实现了可哈希对象的计数功能，返回一个字典，key是元素，value是出现的次数。这里使用collections.Counter(nums)即可实现相同数字的自动计数。dic是一个字典，格式为{1：2，3：5，7：10}（1出现2次，3出现5次，7出现10次）
之后如果出现大于1的value值，即说明存在重复元素。
关于counter的使用，详见博客：
counter()使用技巧

算法占用时空间资源：

5、只出现一次的数字
使用C++解答；
代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num = 0;
        for (int i = 0; i < nums.size(); i++) {
            num = num ^ nums[i];
        }
        return num;
    }
};

算法解析：
一种想法是和第四题类似，使用数据结构存储元素和出现次数，然后进行计数。但是这种做法没有利用到题目中的一个特殊条件——“有且只有一个元素出现一次，其他元素均出现两次”。有一种想法相当巧妙，即使用异或运算进行处理。当两个相同的元素进行异或时，仍然得出0，只有遇到那个特殊的“孤单数”（我瞎起的），才会出现非零值。
比如：2 2 3 4 5 4 3【结果应当为5】
num=0 --> num=2 --> num=0 --> num=3 --> num=3⊕4 --> num=3⊕4⊕5 --> num=3⊕(4⊕5⊕4) = 3⊕5 -->num=3⊕5⊕3 = 5。
最终返回num,值为5。

算法占用时空间资源：

6、两个数组的交集 II
使用java进行解答，
代码如下：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
		Arrays.sort(nums2);
		int len1=nums1.length;
		int len2=nums2.length;
		ArrayList<Integer> al=new ArrayList<Integer>();
		for(int i=0,j=0;i<len1 && j<len2;) {
			if(nums1[i] == nums2[j]) {
				al.add(nums1[i]);
				i++;
				j++;
			}
			else if(nums1[i] > nums2[j]) {
				j++;
			}
			else {
				i++;
			}	
		}
 
		int[] in = new int[al.size()];
		int e=0;
		for(int i:al)
			in[e++] = i;
		return in;
    }
}

算法解析：
此算法采用的是排序插入的合并方式，先把两个数组进行排序，然后根据大小顺序把两个数组合并为一个列表al。然后将al转为一个int型数组。
int[] in 类似于C中的int in[];
for(int i:al) 含义是遍历列表al，然后用i接受每个元素。

算法占用时空间资源：

7、加一
使用JAVA进行解答。
代码如下：

class Solution {
    public int[] plusOne(int[] digits) {
        int len=digits.length;
        for(int i=len-1;i>=0;i--){
            if(digits[i]==9){
                digits[i]=0;
            }
else{
                digits[i]+=1;
            	return digits;
            }
        }
        int[] new_digits=new int[digits.length+1];
        new_digits[0]=1;
        return new_digits;
    }
}

算法解析：
digits数组内采用十进制加法，遍历数组，先看最后一位数，如果不为9，则直接加一然后返回结果即可，此时直接结束函数。如果不为9，需要进位为0；然后检验倒数第二位，同样分情况讨论……
如果循环结束之后算法还没有结束，表示此时数组元素全部为9，那么结果一定是10……0开辟一个新的数组，比原数组多一位，然后0号元素为1，其余元素为0，返回这个结果。
主要就是分类讨论，以及十进制进位的处理，算法相对简单。

算法占用时空间资源：

8、移动零
采用JAVA进行解答。
代码如下：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0){
            return;
        }
        //记录非0元素开始位置
        int k = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] != 0) {
                nums[k++] = nums[i];
            }
        }
        while(k < nums.length) {
            nums[k] = 0;
            k++;
        }
    }
}

算法解析：
主要算法是将非零元素存入原数组，并且使用k记录非零元素的个数，经过一轮遍历之后，原数组的前k位均为原顺序的非零元素。之后比较k和数组长度（JAVA中采用nums.length），将最后（nums.length -k）位填充0。算法相对好理解。

算法占用时空间资源：

9、两数之和
使用C++进行解答。
代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;//提供一对一的hash
        vector<int> b(2,-1);//用来承载结果，初始化一个大小为2，值为-1的容器b
        for(int i=0;i<nums.size();i++){
            if(a.count(target-nums[i])>0){
                b[0]=a[target-nums[i]];
                b[1]=i;
                break;
            }
            a[nums[i]]=i;//反过来放入map中，用来获取结果下标
        } 
        return b;
    };
};

算法解析：
map<int,int> a表示设置一个hash类型的数据结构a，一开始为空表。
if(a.count(target-nums[i])>0)用来判断hash表a中是否存在关键字target-nums[i]；如果存在，那么a[target-nums[i]]和i为最终需要返回的元素，将其存入一个整形数组。
如果不存在,那么将a[nums[i]]中存入i。
通过具体例子来理解算法过程：给定 nums = [2, 7, 11, 15], target = 9
i = 0时，a[2] = 0;
i = 1时，target-nums[1] = 9 -7 =2,由于a[2] = 0,因此存在关键字2。返回的下标为a[2] = 0和1.
直接返回。
另例：给定 nums = [2, 7, 11, 15], target = 26
i = 0，a[2] = 0，
i = 1，a[7] = 1，
i = 2，a[11] = 2,
i = 3，返回下标a[26-15] = 2和3。
通过hash表，在两个下标中，存储第一个下标，然后当找到第二个下标之后，两个下标都提出。

算法占用时空间资源：

10、有效的数独
使用JAVA进行解答，
代码如下：

class Solution {
    public boolean isValidSudoku(char[][] board) {
         //最外层循环，每次循环并非只是处理第i行，而是处理第i行、第i列以及第i个3x3的九宫格
        for(int i = 0; i < 9; i++){
            HashSet<Character> line = new HashSet<>();
            HashSet<Character> col = new HashSet<>();
            HashSet<Character> cube = new HashSet<>();
            for(int j = 0; j < 9; j++){
                if('.' != board[i][j] && !line.add(board[i][j]))
                    return false;
                if('.' != board[j][i] && !col.add(board[j][i]))
                    return false;
                int m = i/3*3+j/3;
                int n = i%3*3+j%3;
                if('.' != board[m][n] && !cube.add(board[m][n]))
                    return false;
            }
        }
        return true;
    }
}

算法解析：
题目中对数独的规则如下：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
算法对于字符矩阵进行二次遍历。如果某一个元素不是空格，在行列块的哈希表中出现重复元素，那么将不符合要求。
HashSet.add(key)应该是一个操作，表中出现重复数据，那么返回值为0。
int m = i/33+j/3,；int n = i%33+j%3;操作实现了块的定位。可以通过列举数据进行检测，在每一个i确定而j变化的二层循环中，行数在3行之间移动，列数在3列之间移动。而对于i变化的一层循环，0_{2维持同样的三行，3}5维持同样的三行，6~8维持同样的三行。
算法中每遍历一行元素，都构建了全新的哈希集合，目的是为了保证每一次的add()操作不受到上一次的影响。

算法占用时空间资源：

11、旋转图像
使用C++进行解答，
代码如下：

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());
        }   
    }
};

算法解析：
首先理解matrix.size()的含义。对于矩阵来说：求矩阵vec的行数使用vec.size()；求矩阵vec列数使用vec[0].size()；求矩阵内元素总数使用vec.size()*vec[0].size()。此处n得到矩阵的行数。由于矩阵为N×N的，因此行数和列数相同。
之后遍历矩阵，左上-右下的对角线两侧两个元素进行交换，使用C++自带的swap()函数。
每一列通过reverse反转函数进行反转，将对角线移动为左下-右上。
例如：
0 0 1 0 2 4 4 2 0
2 3 4 —swap—> 0 3 3 —reverse—> 3 3 0
4 3 1 1 4 1 1 4 1
翻转完成！
和之前那题旋转数组类似，需要对数据进行观察。

算法占用时空间资源：