Lei's Blog

数组

买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

1
2
3
4
5
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  • C语言实现
1
2
3
4
5
6
7
8
9
10
11
int maxProfit(int* prices, int pricesSize) {
if (pricesSize > 0) {
int total = 0;
for (int i = 0; i < pricesSize - 1; i++) {
if (prices[i] < prices[i + 1])
total += prices[i + 1] - prices[i];
}
return total;
}
return 0;
}
  • Swift 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
if prices.count > 0 {
var total = 0
for i in 0..<(prices.count - 1) {
if prices[i] < prices[i + 1] {
total += prices[i + 1] - prices[i]
}
}
return total
}
return 0
}
}

存在重复

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

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

示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
  • C语言实现
1
2
3
4
5
6
7
8
9
10
11
12
bool containsDuplicate(int* nums, int numsSize) {
if (numsSize > 0) {
for (int i = 0; i < numsSize; i ++) {
for (int j = i + 1; j < numsSize; j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
}
return false;
}
  • Swift 实现1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
if nums.count > 0 {
let numSet = NSSet.init(array: nums)
if numSet.count < nums.count {
return true
} else {
return false
}
}
return false
}
}
  • Swift 实现2
1
2
3
4
5
6
7
8
9
func containsDuplicate(_ nums: [Int]) -> Bool {
nums.sorted()
for i in (0..<nums.count - 1 ) {
if nums[i] == nums[i + 1] {
return true;
}
}
return false
}

只出现一次的数字

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

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4
  • C语言实现

使用异或的思想解决

异或运算符∧也称XOR运算符。它的规则是若参加运算的两个二进位同号,则结果为0(假);异号则为1(真)。即0∧0=0,0∧1=1,1∧1=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int singleNumber(int* nums, int numsSize);
int main() {
int nums[3] = {2,2,1};
printf("打印的结果是 %d\n", singleNumber(nums, 3));
return 0;
}
int singleNumber(int* nums, int numsSize) {
int num = 0;
for (int i = 0; i < numsSize; i ++) {
num = num ^ nums[i];
}
return num;
}
  • Swift 实现

采用NSMutableSet去重发来解决
先判断元素在不在集合中,如果在就删除这个元素,如果不在就加入到元素中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var arr = [2,2,1]
func singleNumber(_ nums: [Int]) -> Int {
let numSet = NSMutableSet.init()
for i in 0..<nums.count {
if numSet.contains(nums[i]) {
numSet.remove(nums[i])
} else {
numSet.add(nums[i]);
}
}
print(numSet)
return numSet.allObjects.first as! Int
}
print(singleNumber(arr))

两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
  • Swift 实现

    原理 先排序 然后用定义两个下标分别指向两个数组的首元素, 如果num1[0] < num2[0] 则num2[0] 原地不动 num1[0]下标加1 反之 num1[0]下标不动, num2[0]下标加1 如果相等 下标都加1

Playground 实现

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
import UIKit
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var recods:[Int] = []
nums1.sorted()
nums2.sorted()
var i: Int = 0
var j: Int = 0
while i < nums1.count && j < nums2.count {
if nums1[i] < nums2[j] {
i+=1
} else if nums1[i] > nums2[j] {
j+=1
} else {
recods.append(nums1[i])
i+=1
j+=1
}
}
return recods
}
var nums1 = [1,2,1,2], nums2 = [2,2]
print(intersect(nums1, nums2))

加一

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

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

你可以假设除了整数 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。

解决此题的关键问题在于进位同时用C语言解答的话要理解第三个参数的意义returnSize 这个参数代表返回数组的长度,有没有进位,笔者在本地测试正确,提交leetcode总是报空数组,就是因为没有修改returnSize的值

算法思想 初始化一个进位变量为carry = 1,当个位数加进位变量之后对个位数字除以10取整,如果为1说明需要进位,如果为0。对当前位置上的值除以10去余即可。 依次类推, 如果遍历完成之后进位变量还为1,说明需要增加数组长度,重新初始化一个数组,首地址为1,然后把之前数组上的值依次赋到新数组之后即可。

  • C语言实现
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
#include <stdio.h>
#include <stdlib.h>
int* plusOne(int* digits, int digitsSize, int* returnSize);
int main() {
int nums[] = {9,9,8};
int count = 0;
int *r = plusOne(nums, 3, &count);
for (int i = 0; i < count; i ++) {
printf("打印结果是 %d\n", r[i]);
}
return 0;
}
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize) {
int carry = 1;
for (int i = digitsSize - 1; i >= 0 && carry > 0; i --) {
int temp = digits[i] + carry;
carry = temp / 10;
digits[i] = temp % 10;
}
if (carry == 0) {
*returnSize = digitsSize;
return digits;
}
// int *newSize = (int *)realloc(*returnSize, (digitsSize + 1) * sizeof(int));
int *newSize = (int *)malloc(sizeof(int) * (digitsSize + 1));
newSize[0] = 1;
for (int i = 0; i < digitsSize; i++) {
newSize[i + 1] = digits[i];
}
*returnSize = digitsSize + 1;
return newSize;
}

移动零

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

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。

  • C实现

解题思想
首先题目要求
1不能创建新的存贮单元
2移动之后顺序不能变
我们维护两个下标i,j i用于遍历数组中的每一个元素,j用来记录不为0的元素, 将所有不为0的元素移动到数组最前端,从j开始之后的元素全部赋值为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
30
31
#include <stdio.h>
void moveZeroes(int* nums, int numsSize);
int main() {
int nums[5] = {0,1,0,3,12};
moveZeroes(nums, 5);
for (int n = 0; n < 5; n ++) {
printf(" 打印结果是 %d\n", nums[n]);
}
return 0;
}
void moveZeroes(int* nums, int numsSize) {
int i = 0, j = 0;
while (i < numsSize) {
if (nums[i] != 0)
{
nums[j] = nums[i];
j++;
}
i++;
}
for (int k = j; k < numsSize; k++)
{
nums[k] = 0;
}
}

###