大三后，就开始折腾各种项目开发，再也没有搞算法了，到现在，毕业后工作都快一年了，感觉自己脑子有时候反而变得不太灵活了，闲来无聊，想到杭电刷两道题，结果死活记不起曾经的号，算了，从头开始，在LeetCode上注册个账号，有空刷上一两道题，顺便记录下对题目的理解。
2. Add Two Numbers
图片.png
这题目是最简单的链表值相加，基础算法题目，要注意的是，最后一位数是否要进位的问题，直接上代码：
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var number = 0
var list: ListNode!
var list1 = l1;
var list2 = l2;
var list3: ListNode!
while list1 != nil && list2 != nil {
let a = (list1?.val)!
let b = (list2?.val)!
if list == nil {
list = ListNode((a + b + number) % 10)
list3 = list
} else {
list3.next = ListNode((a + b + number) % 10)
list3 = list3?.next
}
number = (a + b + number) / 10
list1 = list1?.next
list2 = list2?.next
}
var li: ListNode!
if list1 != nil || list2 != nil {
li = list1 != nil ? list1 : list2
while li != nil {
let a = li?.val
if list == nil {
list = ListNode((a! + number) % 10)
list3 = list
} else {
list3.next = ListNode((a! + number) % 10)
list3 = list3?.next
}
number = (a! + number) / 10
li = li.next
}
}
if number != 0 {
list3.next = ListNode(number)
list3 = list3?.next
}
return list
}
7. Reverse Integer
图片.png
数字的反转问题，需要注意，反转后的值如果大于int32的最大值， 则返回0，水题，上代码：
func reverse(_ x: Int) -> Int {
let max_int = (1<<31)-1
let min_int = -1<<31
var flag = false
var num = x
var arr: [Int] = []
if x == 0 {
return x
}
if x < 0 {
num = -num
flag = true
}
while num != 0 {
arr.append(num % 10)
num /= 10
}
func power(_ a: Int, _ b: Int) -> Int {
if b == 0 {
return 1
}
var num = a
for _ in 1..<b {
num *= a
}
return num
}
var reverseNum = 0
for index in 0..<arr.count {
reverseNum += arr[arr.count - index - 1] * power(10, index)
}
if flag {
reverseNum = -reverseNum
}
if reverseNum < min_int || reverseNum > max_int {
return 0
}
return reverseNum
}
19. Remove Nth Node From End of List
64A63B0D-1C8A-4EBF-9D91-DD222F2A1526.png
删除链表中的指定值，水题，不解释，直接上代码：
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
var list: ListNode!
var list1 = head
var list2: ListNode!
var arr: [Int] = []
while list1 != nil {
let a = list1?.val
arr.append(a!)
list1 = list1?.next
}
if arr.count <= 0 {
return head
}
for index in 0..<arr.count {
if index == arr.count - n {
continue
}
if list == nil {
list = ListNode(arr[index])
list2 = list
} else {
list2.next = ListNode(arr[index])
list2 = list2?.next
}
}
return list
}
25. Reverse Nodes in k-Group
69F7E7A0-CC8A-413F-9A33-E1C53C3D279C.png
链接的反转，思路是每隔k个就进行反转一次，把链表转成数组就很好处理了，这题目是hard类的，好像感觉挻水的，不过一开始我也错了两次，主要是没有注意读题目，没看清楚，以为只反转前面k个，原来每k个就进行反转一次，这里直接上代码了：
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
var list: ListNode!
var list1 = head
var list2: ListNode!
var arr: [Int] = []
while list1 != nil {
let a = list1?.val
arr.append(a!)
list1 = list1?.next
}
if k == 0 || arr.count <= 0 || k > arr.count {
return head
}
let count = arr.count / k
var reverseArr: [Int] = []
for index in 1...count {
for ind in 1...k {
reverseArr.append(arr[k * index - ind])
}
}
if arr.count % k != 0 {
for index in k*count..<arr.count {
reverseArr.append(arr[index])
}
}
for index in 0..<reverseArr.count {
if list == nil {
list = ListNode(reverseArr[index])
list2 = list
} else {
list2.next = ListNode(reverseArr[index])
list2 = list2?.next
}
}
return list
}
41. First Missing Positive
图片.png
刷了些题目后，发现自己看英（装）文（逼）水平又提高的节奏，这题目的大意是求数组中没有的最小正整数，这题目是看林总简书上算法题目分享，然后自己也去做了他分享的第一题，也就是这题目，在公车上和回家路上思考了20分钟，回家后开电脑，提交了4次才ac，好吧，水平有待提高。
思路：这题目的难点是空间复杂度是常数级别，所以说，不能开数组！！！不能开，不能开数组，只能用重复利用原来的数组了，因为求数组中没有的最小正整数，所以答案的范围就是 1~n+1（n是数组的大小），理解这个，整个问题应该很好理解，就是如果存在k(1-n+1范围内)，就把nums[k-1]标记为存在，再将nums[k-1]原来的值递归执行这个操作，当遍历整个数组时，没有被标记的下标就是答案了，如果都被标志了，那就是n+1了。
不懂或者没看明白，看下下面的ac代码：
func firstMissingPositive(_ nums: [Int]) -> Int {
var arr = nums
if nums.count <= 0 {
return 1
}
// 这里其实就是避免出现-1， 然后将-1当成标识
for index in 0..<nums.count {
if arr[index] < 0 {
arr[index] -= 1
}
}
// 递归思想
for index in 0..<nums.count {
var flag = nums[index]
while flag > 0 && flag <= nums.count {
let f = flag
flag = arr[flag - 1]
arr[f - 1] = -1
}
}
for index in 0..<arr.count {
if arr[index] != -1 {
return index + 1
}
}
return nums.count + 1
}
这里好像可以少一个for循环的，现在思路不太清晰，回头想下的。
53. Maximum Subarray
图片.png
一看，求最大值的连续序列，其实这题，暴力解决，很是容易，直接多重循环就好，但这不是我们这种优美的程序员所做的事情，我们来寻求最优解决，时间复杂度O(n)。
思路：当前连续的子串的值如果为负时，就不可能成为最大连续子串的前缀或者后缀
这句话有点绕，要自己慢慢体会，直接看代码应该就能明白，如果还是不太懂，拿起笔来，比画下就更加容易明白了：
func maxSubArray(_ nums: [Int]) -> Int {
var sum = 0
var maxsum = 0
var max = 0
for index in 0..<nums.count {
if index == 0 {
max = nums[index]
}
if nums[index] > max {
max = nums[index]
}
sum += nums[index]
if sum > maxsum {
maxsum = sum
} else if sum < 0 {
sum = 0
}
}
if max <= 0 {
return max
}
return maxsum
}
349. Intersection of Two Arrays
56E69F31-BF8E-47CC-91F8-48D736A37DCB.png
求集合的交集，但交集中无重复的值，如上面给出来的例子，重复的2只保留一个。
比较水的题目，代码实现:
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var set: Set<Int> = []
var arr: [Int] = []
for index in 0..<nums1.count {
if !set.contains(nums1[index]) {
set.insert(nums1[index])
}
}
for index in 0..<nums2.count {
if set.contains(nums2[index]) {
arr.append(nums2[index])
set.remove(nums2[index])
}
}
return arr;
}
做这题目的时候，一共快刷了6道了，虽然都是比较简单的问题，但是都是通过自己思考，没有看ac答案，比起以前总喜欢看别人的解决方案，已经有所进步。算法题目可以让自己的头脑更加清晰，有空的时候还是可以多做过，结合自己的一些工作经验，比起以前只为刷题而刷题收获得更多。
350. Intersection of Two Arrays II
998C4DF0-4FA1-4057-9AC0-4485875E91A3.png
这题目求的是两个数组的交集，暴力点的解决方法是一个个枚举，但也可以通过快排来提高效率，但要明确的一点，快排的最坏情况也是O(n*n)。
- 方法一：快排
func quickSort(data: [Int]) -> [Int] {
if data.count <= 1 {
return data;
}
var left: [Int] = []
var right: [Int] = []
let midpoint = data[data.count - 1]
for index in 0..<data.count - 1 {
if data[index] < midpoint {
left.append(data[index])
} else {
right.append(data[index])
}
}
var result = quickSort(data: left)
result.append(midpoint)
let rightResult = quickSort(data: right)
result.append(contentsOf: rightResult)
return result
}
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
let n1 = quickSort(data: nums1)
let n2 = quickSort(data: nums2)
var i = 0
var j = 0
var arr: [Int] = []
while i < n1.count {
while j < n2.count {
if n1[i] < n2[j] {
break
} else if n1[i] > n2[j] {
j += 1
continue
} else {
arr.append(n1[i])
j += 1
break
}
}
i += 1
}
return arr
}
这里看下所有人的运行效率图：
图片.png
这里明显有更加效率的方法，可以自己思考下，有没有办法将时间复杂度降到O(n)呢。
- hashMap 方式：
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var dict1 = Dictionary<Int, Int>()
var dict2 = Dictionary<Int, Int>()
var arr: [Int] = []
for index in 0..<nums1.count {
if dict1[nums1[index]] == nil {
dict1[nums1[index]] = 1;
} else {
dict1[nums1[index]] = dict1[nums1[index]]! + 1;
}
}
for index in 0..<nums2.count {
if dict2[nums2[index]] == nil {
dict2[nums2[index]] = 1;
} else {
dict2[nums2[index]] = dict2[nums2[index]]! + 1;
}
}
for key in dict1.keys {
if dict2[key] != nil && dict1[key] != nil {
let count = dict2[key]! > dict1[key]! ? dict1[key]! : dict2[key]!
for _ in 0..<count {
arr.append(key)
}
}
}
return arr
}
这里通过hashMap的方式实现的，上面的时间复杂度应该是O(n)，但在leetcode上面运行的时间却比第一种的方式慢，是不是写入速度慢呢，这个再研究下才知道结论。
414. Third Maximum Number
图片.png
这个问题就是求数组里面的第n大的值，上面要求时间最长是O(n)， 所以暴力排序的方法肯定是过不了的。
思路:
- 从数组里读取三个不一样的值进行排序；
- 然后遍历数组中的其它值，分别和前面取出来的三个数值进行比较，去掉值最少的那个，并且所有数值不能重复；
这个问题类似于求数组中第k大值的问题，直接上传码：
func thirdMax(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums[0]
}
if nums.count == 2 {
return nums[0] > nums[1] ? nums[0] : nums[1]
}
var dict = Dictionary<Int, Int>()
var flag = false;
var arr: [Int] = []
for index in 0..<nums.count {
if !flag {
if dict[nums[index]] == nil {
dict[nums[index]] = nums[index]
}
if dict.keys.count >= 3 {
flag = true
for item in dict.values {
arr.append(item)
}
if arr[0] < arr[1] {
let flag = arr[0]
arr[0] = arr[1]
arr[1] = flag
}
if arr[0] < arr[2] {
let flag = arr[0]
arr[0] = arr[2]
arr[2] = flag
}
if arr[1] < arr[2] {
let flag = arr[1]
arr[1] = arr[2]
arr[2] = flag
}
}
} else {
if nums[index] < arr[2] {
continue
}
if nums[index] > arr[0] {
arr[2] = arr[1]
arr[1] = arr[0]
arr[0] = nums[index];
} else if nums[index] > arr[1] {
arr[2] = arr[1]
arr[1] = nums[index];
} else if nums[index] > arr[2] {
arr[2] = nums[index]
}
}
}
if arr.count >= 3 {
return arr[2]
} else {
return arr[0]
}
}
看下运行的时间分布图：
图片.png
最快的是22ms，上面的代码是25ms，相对来说，算是比较快的速度，后面有时间再来想想怎样才能达到最优。
442. Find All Duplicates in an Array
图片.png
因为数组的值只会出现一次或者2次，这样直接用字典来保存的同时判断下是否重复就可以了，时间复杂度n，代码：
func findDuplicates(_ nums: [Int]) -> [Int] {
var dict = Dictionary<Int, Int>()
var arr: [Int] = []
for index in 0..<nums.count {
if dict[nums[index]] != nil {
arr.append(nums[index])
}
dict[nums[index]] = nums[index]
}
return arr;
}
448. Find All Numbers Disappeared in an Array
图片.png
水题，该注意的地方也标出来了，思维路是用hashMap来实现，实际时间复杂度是 2 * n，直接上代码：
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var dict = Dictionary<Int, Int>()
for index in 0..<nums.count {
dict[nums[index]] = nums[index]
}
var arr: [Int] = []
if nums.count > 0 {
for index in 1...nums.count {
if dict[index] == nil {
arr.append(index)
}
}
}
return arr;
}
468. Validate IP Address
图片.png
字符串的判断，把各种情况考虑上就可以了，代码：
func validIPAddress(_ IP: String) -> String {
if IP.contains(".") {
let arr = IP.components(separatedBy: ".")
if arr.count != 4 {
return "Neither"
}
for item in arr {
if (item.hasPrefix("0") && item.characters.count > 1) || item.hasPrefix("-") {
return "Neither"
} else {
let a = Int(item)
if a == nil || a! < 0 || a! > 255 {
return "Neither"
}
}
}
return "IPv4"
} else if IP.contains(":") {
let arr = IP.components(separatedBy: ":")
if arr.count != 8 {
return "Neither"
}
for item in arr {
if item.characters.count > 4 || item.characters.count <= 0 {
return "Neither"
}
for ite in item.characters {
let value = UnicodeScalar(String(ite))?.value
if value! < 48 || (value! > 57 && value! < 65) || (value! > 70 && value! < 97) || value! > 102 {
return "Neither"
}
}
}
return "IPv6"
} else {
return "Neither"
}
}
485. Max Consecutive Ones
86DBE1FF-73B7-47BE-8A72-D8A2BE27C99A.png
这道是水题，求连续最长的1的长度，直接帖代码：
func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
var max = 0
var sum = 0
for index in 0..<nums.count {
if nums[index] == 0 {
if sum > max {
max = sum
}
sum = 0
} else {
sum += 1
if sum > max {
max = sum
}
}
}
return max
}
495. Teemo Attacking
图片.png
这题目，又想起曾经超鬼的经历，哈哈，好像已经有一年没有玩过了，这题目就是要求TM队长攻击敌人的中毒时长，数组内传的是攻击的时候，第二个参数是中毒的时长。
比如：[1, 2], 3，1秒的时候攻击了敌人，中毒时间是3秒，在第2秒的时候又攻击了敌人，因为已经中毒了，就不会重复中毒，但中毒时间会重复计算。所以中毒时间是， 1、2、3、4、5， 一共5秒。
这样的话，就很好理解了，可以分为两种情况：
1. 如果前后两个攻击时差大于5秒时，那么中毒的时间就增加5秒；
2. 如果两次攻击的时间少于或等于5秒时，那就中毒的时间就会在增加两次攻击的时间差；
理解了逻辑，就很容易写出代码了：
func findPoisonedDuration(_ timeSeries: [Int], _ duration: Int) -> Int {
var count = duration
if timeSeries.count == 0 {
return duration
}
if timeSeries.count < 2 {
return count
}
for index in 0..<timeSeries.count - 1 {
if timeSeries[index] + duration - 1 < timeSeries[index + 1] {
count += duration
} else {
count = count + timeSeries[index + 1] - timeSeries[index];
}
}
return count
}
这里需要注意的两处就是数组为空和只有一次攻击的时候，这两种情况需要另外的处理，然后然后就AC了~~~
待续~~~
