数组

杨辉三角

加一

删除排序数组中的重复项

四数之和

杨辉三角

118. 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:

1
2
3
4
5
6
7
8
9
输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
     
        vector<vector<int>> res;
        for(int i = 0; i < numRows; i++)
        {   
            vector<int> row;
            row.resize(i+1);
            row[0] = 1;
            row[i] = 1;
            for(int j = 1; j <= i-1; j++)
            {
               row[j] = res[i-1][j-1]+res[i-1][j];
            }
            res.push_back(row);
        }
        return res;
      
    }
};

加一

66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

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

示例 2:

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i = digits.size()-1;i>=0;i--)
        {
            digits[i]++;
            if(digits[i]==10) digits[i]=0;
            else return digits;
        }
        digits.insert(digits.begin(),1);
        return digits;
    }
};

删除排序数组中的重复项

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

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

1
2
3
4
5
给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:
1
2
3
4
5
给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.size(); j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;

    }
};

四树之和

18. 四数之和

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        	sort(nums.begin(), nums.end());
	vector<vector<int>> ret;
	int length = nums.size();
	for (int i = 0; i < length; i++)
	{
		if (i > 0 && nums[i] == nums[i - 1]) continue;

		for (int first = i + 1; first < length - 2; first++)
		{
			if (first > i + 1 && nums[first] == nums[first - 1]) continue;
			int second = first + 1;
			int third = length - 1;

			while (second < third)
			{
				int sum = nums[first] + nums[second] + nums[third] + nums[i];
				cout << "sum:" << sum << ':';
				cout << nums[i] << " " << nums[first] << " " << nums[second] << " " << nums[third] << endl;
				if (sum == target)
				{
					ret.push_back({ nums[i] , nums[first] , nums[second] , nums[third] });
					while (second < third && nums[second] == nums[second + 1]) ++second;   //注意去重
					while (second < third && nums[third] == nums[third - 1]) --third;
					third--;
					second++;
				}
				else if (sum < target)
					second++;
				else
					third--;
			}
		}

	}
	return ret;

    }
};