Skip to content

Commit df8accb

Browse files
author
Yi Gu
committed
Merge branch 'master' into String
2 parents 9d61dc8 + 53e6521 commit df8accb

File tree

8 files changed

+310
-2
lines changed

8 files changed

+310
-2
lines changed

‎Array/ThreeSum.swift

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/3sum/
3+
* Primary idea: Sort the array, and traverse it, increment left or decrease right
4+
* predicated on their sum is greater or not than the target
5+
* Time Complexity: O(n^2), Space Complexity: O(n)
6+
*/
7+
8+
class ThreeSum {
9+
func threeSum(nums: [Int]) -> [[Int]] {
10+
var nums = nums.sort({$0 < $1})
11+
var res = [[Int]]()
12+
13+
if nums.count <= 2 {
14+
return res
15+
}
16+
17+
for i in 0...nums.count - 3 {
18+
if i == 0 || nums[i] != nums[i - 1] {
19+
var remain = -nums[i]
20+
var left = i + 1
21+
var right = nums.count - 1
22+
while left < right {
23+
if nums[left] + nums[right] == remain {
24+
var temp = [Int]()
25+
temp.append(nums[i])
26+
temp.append(nums[left])
27+
temp.append(nums[right])
28+
29+
res.append(temp)
30+
repeat {
31+
left += 1
32+
} while (left < right && nums[left] == nums[left - 1])
33+
repeat {
34+
right -= 1
35+
} while (left < right && nums[right] == nums[right + 1])
36+
} else if nums[left] + nums[right] < remain {
37+
repeat {
38+
left += 1
39+
} while (left < right && nums[left] == nums[left - 1])
40+
} else {
41+
repeat {
42+
right -= 1
43+
} while (left < right && nums[right] == nums[right + 1])
44+
}
45+
}
46+
}
47+
}
48+
49+
return res
50+
}
51+
}

‎Math/AddBinary.swift

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/add-binary/
3+
* Primary idea: use Carry and iterate from last to start
4+
*
5+
* Note: Swift does not have a way to access a character in a string with O(1),
6+
* thus we have to first transfer the string to a character array
7+
* Time Complexity: O(n), Space Complexity: O(n)
8+
*
9+
*/
10+
11+
class AddBinary {
12+
func addBinary(a: String, _ b: String) -> String {
13+
var res = ""
14+
var aChars = [Character](a.characters)
15+
var bChars = [Character](b.characters)
16+
17+
var i = aChars.count - 1
18+
var j = bChars.count - 1
19+
var carry = 0
20+
var num = 0
21+
22+
while i >= 0 || j >= 0 || carry > 0 {
23+
num = carry
24+
25+
if i >= 0 {
26+
num += Int(String(aChars[i]))!
27+
i -= 1
28+
}
29+
if j >= 0 {
30+
num += Int(String(bChars[j]))!
31+
j -= 1
32+
}
33+
34+
carry = num / 2
35+
num = num % 2
36+
37+
res = String(num) + res
38+
}
39+
40+
return res
41+
}
42+
}

‎Math/AddTwoNumbers.swift

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/add-two-numbers/
3+
* Primary idea: use carry and iterate through both linked lists
4+
* Time Complexity: O(n), Space Complexity: O(1)
5+
*
6+
* Definition for singly-linked list.
7+
* public class ListNode {
8+
* public var val: Int
9+
* public var next: ListNode?
10+
* public init(_ val: Int) {
11+
* self.val = val
12+
* self.next = nil
13+
* }
14+
* }
15+
*/
16+
17+
class AddTwoNumbers {
18+
func addTwoNumbers(l1: ListNode?, _ l2: ListNode?) -> ListNode? {
19+
var carry = 0
20+
var sum = 0
21+
let dummy = ListNode(0)
22+
var node = dummy
23+
var l1 = l1
24+
var l2 = l2
25+
26+
while l1 != nil || l2 != nil || carry != 0 {
27+
sum = carry
28+
29+
if l1 != nil {
30+
sum += l1!.val
31+
l1 = l1!.next
32+
}
33+
if l2 != nil {
34+
sum += l2!.val
35+
l2 = l2!.next
36+
}
37+
38+
carry = sum / 10
39+
sum = sum % 10
40+
41+
node.next = ListNode(sum)
42+
node = node.next!
43+
}
44+
45+
return dummy.next
46+
47+
}
48+
}

‎Math/IntegerBreak.swift

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/integer-break/
3+
* Primary idea: Final Result must be split as 2^m * 3^n. Lets say p = p1 + p2 + ... + pn,
4+
* if p1 could be split as 2(p1 - 2), than it would be greater than p1 if p1 > 4.
5+
* same thing for 3(p1 - 3). Thus we spilt the original number to multiple 3s and 2s to
6+
* get the final result
7+
* Time Complexity: O(logn), Space Complexity: O(1)
8+
*/
9+
10+
class IntegerBreak {
11+
func integerBreak(n: Int) -> Int {
12+
var num = n
13+
var res = 1
14+
15+
if num == 2 {
16+
return 1
17+
}
18+
if num == 3 {
19+
return 2
20+
}
21+
22+
while num > 4 {
23+
res *= 3
24+
num -= 3
25+
}
26+
res *= num
27+
28+
return res
29+
}
30+
}

‎README.md

Lines changed: 34 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,13 @@
11
# LeetCode by Swift
2-
[LeetCode Online Judge] (https://leetcode.com/) is a website containing many **algorithm questions**. Most of them are real interview questions of **Google, Facebook, LinkedIn, Apple**, etc. This repo shows my solutions by Swift and the code style is strictly follow [RayWenderlich Swift Style Guide](https://github.com/raywenderlich/swift-style-guide). Please feel free to reference and STAR to support this repo, thank you!
2+
[LeetCode Online Judge] (https://leetcode.com/) is a website containing many **algorithm questions**. Most of them are real interview questions of **Google, Facebook, LinkedIn, Apple**, etc. This repo shows my solutions by Swift and the code style is strictly follow [RayWenderlich Swift Style Guide](https://github.com/raywenderlich/swift-style-guide). Please feel free to reference and **STAR** to support this repo, thank you!
33

4-
## Contents
4+
## Data Structures
55
* [Array](#array)
6+
* [String](#string)
67
* [Tree](#tree)
8+
* [Math](#math)
9+
* [Search](#search)
10+
* [Sort](#sort)
711

812
## Array
913
| Title | Solution | Difficulty |
@@ -15,6 +19,13 @@
1519
[Move Zeroes](https://leetcode.com/problems/move-zeroes/)| [Swift](./Array/MoveZeroes.swift)| Easy|
1620
[Remove Element](https://leetcode.com/problems/remove-element/)| [Swift](./Array/RemoveElement.swift)| Easy|
1721
[Rotate Array](https://leetcode.com/problems/rotate-array/)| [Swift](./Array/RotateArray.swift)| Easy|
22+
[Two Sum](https://leetcode.com/problems/two-sum/)| [Swift](./Array/TwoSum.swift)| Easy|
23+
[3Sum](https://leetcode.com/problems/3sum/)| [Swift](./Array/ThreeSum.swift)| Medium|
24+
25+
## String
26+
| Title | Solution | Difficulty |
27+
| ----- | -------- | ---------- |
28+
[Count and Say](https://leetcode.com/problems/count-and-say/)| [Swift](./Array/CountAndSay.swift)| Easy|
1829

1930
## Tree
2031
| Title | Solution | Difficulty |
@@ -31,4 +42,25 @@
3142
[Path Sum](https://leetcode.com/problems/path-sum/)| [Swift](./Tree/PathSum.swift)| Easy|
3243
[Path Sum II](https://leetcode.com/problems/path-sum-ii/)| [Swift](./Tree/PathSumII.swift)| Medium|
3344

45+
## Math
46+
| Title | Solution | Difficulty |
47+
| ----- | -------- | ---------- |
48+
[Add Binary](https://leetcode.com/problems/add-binary/)| [Swift](./Math/AddBinary.swift)| Easy|
49+
[Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)| [Swift](./Math/AddTwoNumbers.swift)| Medium|
50+
[Integer Break](https://leetcode.com/problems/integer-break/)| [Swift](./Math/IntegerBreak.swift)| Medium|
51+
52+
## Search
53+
| Title | Solution | Difficulty |
54+
| ----- | -------- | ---------- |
55+
[Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)| [Swift](./Search/ClosestBinarySearchTreeValue.swift)| Easy|
56+
[Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)| [Swift](./Search/SearchInRotatedSortedArray.swift)| Hard|
57+
[Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)| [Swift](./Search/SearchInRotatedSortedArrayII.swift)| Medium|
58+
[Sqrt(x)](https://leetcode.com/problems/sqrtx/)| [Swift](./Search/Sqrtx.swift)| Medium|
3459

60+
## Sort
61+
| Title | Solution | Difficulty |
62+
| ----- | -------- | ---------- |
63+
[Valid Anagram](https://leetcode.com/problems/valid-anagram/)| [Swift](./Sort/ValidAnagram.swift)| Easy|
64+
[Meeting Rooms](https://leetcode.com/problems/meeting-rooms/)| [Swift](./Sort/MeetingRooms.swift)| Easy|
65+
[Sort Colors](https://leetcode.com/problems/sort-colors/)| [Swift](./Sort/SortColors.swift)| Medium|
66+
[Merge Intervals](https://leetcode.com/problems/merge-intervals/)| [Swift](./Sort/MergeIntervals.swift)| Hard|

‎Sort/MergeIntervals.swift

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/merge-intervals/
3+
* Primary idea: Sort the original intervals and then append them one by one
4+
* Time Complexity: O(nlogn), Space Complexity: O(n)
5+
*
6+
* Definition for an interval.
7+
* public class Interval {
8+
* public var start: Int
9+
* public var end: Int
10+
* public init(_ start: Int, _ end: Int) {
11+
* self.start = start
12+
* self.end = end
13+
* }
14+
* }
15+
*/
16+
17+
class MergeIntervals {
18+
func merge(intervals: [Interval]) -> [Interval] {
19+
if intervals.count <= 1 {
20+
return intervals
21+
}
22+
23+
var intervals = intervals.sort(sortIntervals)
24+
25+
var res = [Interval]()
26+
res.append(intervals[0])
27+
28+
for i in 1..<intervals.count {
29+
var last = res[res.count - 1]
30+
var current = intervals[i]
31+
if current.start > last.end {
32+
res.append(current)
33+
} else {
34+
last.end = max(last.end, current.end)
35+
}
36+
}
37+
38+
return res
39+
}
40+
41+
private func sortIntervals(p: Interval, q: Interval) -> Bool {
42+
if p.start != q.start {
43+
return p.start < q.start
44+
} else {
45+
return p.end < q.end
46+
}
47+
}
48+
}

‎Sort/SortColors.swift

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/sort-colors/
3+
* Primary idea: Bucket sort
4+
* Time Complexity: O(n), Space Complexity: O(1)
5+
*/
6+
7+
class SortColors {
8+
func sortColors(inout nums: [Int]) {
9+
guard nums.count > 1 else {
10+
return
11+
}
12+
13+
var red = 0
14+
var blue = nums.count - 1
15+
var i = 0
16+
17+
while i <= blue {
18+
if nums[i] == 0 {
19+
_swap(&nums, i, red)
20+
red += 1
21+
i += 1
22+
} else if nums[i] == 1 {
23+
i += 1
24+
} else {
25+
_swap(&nums, i, blue)
26+
blue -= 1
27+
}
28+
}
29+
}
30+
31+
private func _swap(inout nums: [Int], _ p: Int, _ q: Int) {
32+
let temp = nums[p]
33+
nums[p] = nums[q]
34+
nums[q] = temp
35+
}
36+
}

‎Sort/ValidAnagram.swift

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/valid-anagram/
3+
* Primary idea: Transfer string to char array and sort, compare the sort one
4+
* Time Complexity: O(nlogn), Space Complexity: O(1)
5+
*/
6+
7+
class ValidAnagram {
8+
func isAnagram(s: String, _ t: String) -> Bool {
9+
guard s.characters.count == t.characters.count else {
10+
return false
11+
}
12+
13+
return sortStr(s) == sortStr(t)
14+
}
15+
16+
private func sortStr(s: String) -> [Character] {
17+
var sChars = [Character](s.characters)
18+
sChars.sortInPlace({$0 < $1})
19+
return sChars
20+
}
21+
}

0 commit comments

Comments
 (0)