LeetCode 练习 4月

发表于 | 分类于

LeetCode 练习 4月

https://leetcode.com/discuss/general-discussion/551411/30-day-leetcoding-challenge

4月

4.1 日 Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

这道题主要的要求是：程序具有线性复杂度，并且最好不使用额外的内存。

除去这两个要求的话，有如下方法：

  • 第一种：先对序列进行排序，之后遍历一遍序列，如果存在一个数如 array[i] 的左边 array[i-1] 和右边 array[i+1] 均与 array[i] 不同，则这个数为要找的数（i=0以及i=n-1时进行特殊处理）

  • 第二种：使用hashset，这是参考着https://www.cnblogs.com/grandyang/p/4130577.html 看的，我之前对于hashset了解并不多，这里正好也了解一下：https://blog.csdn.net/wds1181977/article/details/51424839 可以看到，其实在java中hashset是通过hashmap实现的，只是在键值对方面hashset 是不同的键对应同一个键值对。根据hashset的思想，可以解决该问题：遍历序列，如果当前值不在hashset中，则放入hashset，否则将同样的值移除hashset。注意：在java中有hashset，在C++中使用的是unordered_set，解决代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            unordered_set<int> st;
            for (int num : nums) {
                if (st.count(num)) st.erase(num);
                else st.insert(num);
            }
            return *st.begin();
        }
    };

但是由于上面条件的限制，不能使用上述两个方法。

开始我也没有想到，想了很长时间，想过通过数学的方法，加加减减得到结果，但是经过测试后不可行。

之后参考了网上的方法，使用*C++的异或操作 ^ * ，比如x=2,y=3 ,z=3.则x ^ y = 5，x^y^z = 2 , y ^ z = 0;

下面是解决方法：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
    int res = 0;
	for (auto num : nums)
	{
		res ^= num;
	}
	return res;
    }
};

4月2日 Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19
Output: true
Explanation: 12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解决代码：

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
class Solution {
public:
    unordered_set<int> st;
bool isHappy(int n) {
	if (n == 1) // 递归终止条件
	{
		return true;
	}
	else if (st.count(n)) // 如果又循环回来了
	{
		return false;
	}
	st.insert(n);
	int sum = getSum(n);//获取到n经过拆分计算后的结果
	return isHappy(sum);
}

int getSum(int n) {
	vector<int> speNum;
	while (n > 0)
	{
		speNum.push_back(n % 10); // 个位数
		n = n / 10; //去掉个位数
	}

	int result = 0;
	for (int num : speNum)
	{
		result += num * num;
	}
	return result;
}
};

代码提交后显示我的代码运行时间是较长的，我看了那些运行时间很短的代码，他们很多用了些技巧，比如：如果1<=n<10的话，如果n=1或者n=7,那么就符合，否则就不符合。但是这样我感觉不好！因为你需要先知道1-10中符合条件的数。

4月3日 Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int left = 0;
		int right = nums.size() - 1;
		int result = maxSum(nums, left, right);
		return result;
	}
	int maxSum(vector<int>& nums, int left, int right) {

		if (left == right)// 递归的基准情况
		{
			return nums[left];
		}

		int mid = (left + right) / 2;
		int maxLeftSum; // 左半部分最大值
		int maxRightSum; // 右半部分最大值
		maxLeftSum = maxSum(nums, left, mid);
		maxRightSum = maxSum(nums, mid + 1, right);

		// 下面开始求中间连接的最大值

		int maxLeftBorderSum;
		int leftTempSum;
		maxLeftBorderSum = leftTempSum = nums[mid];
		for (int i = mid - 1; i >= left; i--) // 从中间边界处向左扩展
		{
			leftTempSum += nums[i];
			if (maxLeftBorderSum < leftTempSum)
			{
				maxLeftBorderSum = leftTempSum;
			}
		}

		int maxRightBorderSum;
		int rightTempSum;
		maxRightBorderSum = rightTempSum = nums[mid + 1];
		for (int i = mid + 2; i <= right; i++)
		{
			rightTempSum += nums[i];
			if (maxRightBorderSum < rightTempSum)
			{
				maxRightBorderSum = rightTempSum;
			}
		}

		// 求左半部分，右半部分，中间部分三者最大值
		return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
	}

	int max3(int a, int b, int c) {
		if (a >= b && a >= c)
		{
			return a;
		}
		else if (b >= a && b >= c)
		{
			return b;
		}
		else
		{
			return c;
		}
	}
};

4月4日 Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.
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
class Solution {
public:
void moveZeroes(vector<int>& nums) {
	int j = 0;
	int i = 0;
	int zerosNum = 0; // 存放0的数量
	while (zerosNum + i < nums.size())
	{
		if (nums[i] == 0) // 如果等于0，那么就将后面的所有数向前移动
		{
			zerosNum++; // 0的数量+1
			j = i + 1;
			// todo 将数组从索引j开始向前移动一个单位
			moveForth(nums,j);
			continue;
		}
		i++;
	}
}
void moveForth(vector<int>& nums, int start) {
	for (int i = start; i < nums.size(); i++) // 向前移动
	{
		nums[i - 1] = nums[i];
	}
	nums[nums.size() - 1] = 0; // 最后一位设置为0
}
};

4月5日 Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

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
class Solution {
public:
 int maxProfit(vector<int>& prices)
{
    if (prices.size() == 0)
	{
		return 0;
	}
	int result = 0;
	int i = 0;
	int tempStart = 0; // 股票开始购买的时间
	int tempEnd = 0; // 股票结束购买时间
	while (i < prices.size() - 1)
	{
		if (prices[i] > prices[i + 1]) // 如果当前股票价格比后一天价格高
		{
			result += prices[tempEnd] - prices[tempStart];
			i++;
			tempStart = i;
			tempEnd = i;
			continue; // 当天的股票不买，进入后一天
		}
		i++;
		tempEnd = i;
	}
	result += prices[tempEnd] - prices[tempStart];
	return result;
}
};