Skip to content

Commit 4127f48

Browse files
programming086programming086
authored
Merge pull request #1 from soapyigu/master
pull
2 parents 27e5b66 + eb35598 commit 4127f48

File tree

6 files changed

+169
-40
lines changed

6 files changed

+169
-40
lines changed

‎Array/MissingRanges.swift

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/missing-ranges/
3+
* Primary idea: Scan the array and compare each element with previous one and generate corresponding ranges
4+
*
5+
* Time Complexity: O(n), Space Complexity: O(1)
6+
*
7+
*/
8+
9+
class MissingRanges {
10+
func findMissingRanges(_ nums: [Int], _ lower: Int, _ upper: Int) -> [String] {
11+
if nums.isEmpty {
12+
return [getRange(lower - 1, upper + 1)]
13+
}
14+
15+
var res = [String]()
16+
17+
for (i, num) in nums.enumerated() {
18+
if i == 0 {
19+
if lower < num {
20+
res.append(getRange(lower - 1, num))
21+
}
22+
} else {
23+
if nums[i - 1] + 1 < num {
24+
res.append(getRange(nums[i - 1], num))
25+
}
26+
}
27+
}
28+
29+
if nums.last! + 1 < upper + 1 {
30+
res.append(getRange(nums.last!, upper + 1))
31+
}
32+
33+
return res
34+
}
35+
36+
private func getRange(_ numPrev: Int, _ numPost: Int) -> String {
37+
if numPrev + 2 == numPost {
38+
return "\(numPrev + 1)"
39+
} else {
40+
return "\(numPrev + 1)->\(numPost - 1)"
41+
}
42+
}
43+
}

‎Array/SortArrayByParity.swift

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,9 @@
88

99
class SortArrayByParity {
1010
func sortArrayByParity(_ A: [Int]) -> [Int] {
11-
var outputArray = [Int]()
12-
for (_,value) in A.enumerated(){
13-
outputArray.insert(value, at: value % 2 == 0 ? 0 : outputArray.count)
11+
return A.enumerated().reduce(into: [Int]()) { (acc, arg) in
12+
let (_, value) = arg
13+
acc.insert(value, at: value.isMultiple(of: 2) ? 0 : acc.count)
1414
}
15-
16-
return outputArray
1715
}
1816
}

‎Array/ThreeSum.swift

Lines changed: 27 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -6,42 +6,38 @@
66
*/
77

88
class ThreeSum {
9-
func threeSum(nums: [Int]) -> [[Int]] {
10-
var nums = nums.sorted(by: <)
9+
func threeSum(_ nums: [Int]) -> [[Int]] {
1110
var res = [[Int]]()
1211

13-
if nums.count <= 2 {
12+
guard nums.count >= 3 else {
1413
return res
1514
}
1615

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-
}
16+
let nums = nums.sorted()
17+
18+
for i in 0..<nums.count - 2 {
19+
if i > 0 && nums[i] == nums[i - 1] {
20+
continue
21+
}
22+
23+
let firstNum = nums[i], remainingSum = -firstNum
24+
var m = i + 1, n = nums.count - 1
25+
26+
while m < n {
27+
if nums[m] + nums[n] == remainingSum {
28+
res.append([firstNum, nums[m], nums[n]])
29+
30+
repeat {
31+
m += 1
32+
} while nums[m] == nums[m - 1] && m < n
33+
34+
repeat {
35+
n -= 1
36+
} while nums[n] == nums[n + 1] && m < n
37+
} else if nums[m] + nums[n] < remainingSum {
38+
m += 1
39+
} else {
40+
n -= 1
4541
}
4642
}
4743
}

‎Math/PermutationSequence.swift

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/permutation-sequence/
3+
* Primary idea: Iterate and change the array from last to the first
4+
*
5+
* Time Complexity: O(n^2), Space Complexity: O(1)
6+
*/
7+
8+
class PermutationSequence {
9+
func getPermutation(_ n: Int, _ k: Int) -> String {
10+
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
11+
12+
var factorial = 1
13+
for i in 1 ..< n {
14+
factorial *= i
15+
}
16+
17+
var result = ""
18+
var k = k
19+
var divisor = n - 1
20+
21+
for i in 0 ..< n {
22+
for (index, number) in numbers.enumerated() {
23+
if k > factorial {
24+
k -= factorial
25+
} else {
26+
result += "\(number)"
27+
numbers.remove(at: index)
28+
break
29+
}
30+
}
31+
if divisor > 1 {
32+
factorial /= divisor
33+
divisor -= 1
34+
}
35+
}
36+
37+
return result
38+
}
39+
}

‎Queue/ImplementQueueUsingStacks.swift

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/**
2+
* Question Link: https://leetcode.com/problems/implement-queue-using-stacks/
3+
* Primary idea: queue
4+
* Time Complexity: O(n), Space Complexity: O(n)
5+
*
6+
* Copyright © 2019 Ilyar Mnazhdin. All rights reserved.
7+
8+
* Your MyQueue object will be instantiated and called as such:
9+
* let obj = MyQueue()
10+
* obj.push(x)
11+
* let ret_2: Int = obj.pop()
12+
* let ret_3: Int = obj.peek()
13+
* let ret_4: Bool = obj.empty()
14+
*/
15+
16+
import Foundation
17+
18+
class MyQueue {
19+
var storage = [Int]()
20+
21+
/** Initialize your data structure here. */
22+
init() {
23+
24+
}
25+
26+
/** Push element x to the back of queue. */
27+
func push(_ x: Int) {
28+
storage.append(x)
29+
}
30+
31+
/** Removes the element from in front of queue and returns that element. */
32+
func pop() -> Int {
33+
return storage.removeFirst()
34+
}
35+
36+
/** Get the front element. */
37+
func peek() -> Int {
38+
guard let first = storage.first else { return 0}
39+
return first
40+
}
41+
42+
/** Returns whether the queue is empty. */
43+
func empty() -> Bool {
44+
return storage.isEmpty
45+
}
46+
}

‎README.md

Lines changed: 11 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
![Leetcode](./logo.png?style=centerme)
55

66
## Progress
7-
[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 282 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
7+
[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 284 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
88

99
## Contributors
1010

@@ -17,6 +17,7 @@
1717
* [String](#string)
1818
* [Linked List](#linked-list)
1919
* [Stack](#stack)
20+
* [Queue](#queue)
2021
* [Tree](#tree)
2122
* [Dynamic programming](#dynamic-programming)
2223
* [Depth-first search](#depth-first-search)
@@ -65,6 +66,7 @@
6566
[4Sum](https://leetcode.com/problems/4sum/)| [Swift](./Array/FourSum.swift)| Medium| O(n^3)| O(nC4)|
6667
[Summary Ranges](https://leetcode.com/problems/summary-ranges/)| [Swift](./Array/SummaryRanges.swift)| Medium| O(n)| O(n)|
6768
[Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)| [Swift](./Array/NumMatrix.swift)| Medium| O(mn)| O(mn)|
69+
[Missing Ranges](https://leetcode.com/problems/missing-ranges/)| [Swift](./Array/MissingRanges.swift)| Medium| O(n)| O(1)|
6870
[Asteroid Collision](https://leetcode.com/problems/asteroid-collision/)| [Swift](./Array/AsteroidCollision.swift)| Medium| O(n)| O(n)|
6971
[Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/)| [Swift](./Array/MaximizeDistanceToClosestPerson.swift)| Easy| O(n)| O(1)|
7072
[Exam Room](https://leetcode.com/problems/exam-room/)| [Swift](./Array/ExamRoom.swift)| Medium| O(n)| O(n)|
@@ -162,6 +164,10 @@
162164
[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)| [Swift](./Stack/PostorderTraversal.swift)| Hard| O(n)| O(n)|
163165
[Decode String](https://leetcode.com/problems/decode-string/)| [Swift](./Stack/DecodeString.swift)| Medium| O(n)| O(n)|
164166

167+
## Queue
168+
| Title | Solution | Difficulty | Time | Space |
169+
| ----- | -------- | ---------- | ---- | ----- |
170+
[Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks)| [Swift](./Queue/ImplementQueueUsingStacks.swift)| Easy| O(n)| O(n)|
165171

166172
## Tree
167173
| Title | Solution | Difficulty | Time | Space |
@@ -314,6 +320,7 @@
314320
[Counting Bits](https://leetcode.com/problems/counting-bits/)| [Swift](./Math/CountingBits.swift)| Medium| O(n)| O(n)|
315321
[K-th Smallest in Lexicographical Order](https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/)| [Swift](./Math/KthSmallestLexicographicalOrder.swift)| Hard| O(n)| O(1)|
316322
[Gary Code](https://leetcode.com/problems/gray-code/)| [Swift](./Math/GaryCode.swift)| Medium| O(n)| O(2^n)|
323+
[Permutation Sequence](https://leetcode.com/problems/permutation-sequence/)| [Swift](./Math/PermutationSequence.swift)| Medium| O(n^2)| O(1)|
317324

318325
## Search
319326
| Title | Solution | Difficulty | Time | Space |
@@ -639,7 +646,7 @@
639646
| | 235 | [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) | Easy |
640647
| [Swift](./LinkedList/PalindromeLinkedList.swift) | 234 | [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/) | Easy |
641648
| | 233 | [Number of Digit One](https://leetcode.com/problems/number-of-digit-one/) | Hard |
642-
| | 232 | [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) | Easy |
649+
| [Swift](./Queue/ImplementQueueUsingStacks.swift) | 232 | [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) | Easy |
643650
| [Swift](./Math/PowerTwo.swift) | 231 | [Power of Two](https://leetcode.com/problems/power-of-two/) | Easy |
644651
| [Swift](./Tree/KthSmallestElementBST.swift) | 230 | [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) | Medium |
645652
| [Swift](./Array/MajorityElementII.swift) | 229 | [Majority Element II](https://leetcode.com/problems/majority-element-ii/) | Medium |
@@ -692,7 +699,7 @@
692699
| | 166 | [Fraction to Recurring Decimal](https://oj.leetcode.com/problems/fraction-to-recurring-decimal/) | Medium |
693700
| | 165 | [Compare Version Numbers](https://oj.leetcode.com/problems/compare-version-numbers/) | Easy |
694701
| | 164 | [Maximum Gap](https://oj.leetcode.com/problems/maximum-gap/) | Hard |
695-
| | 163 | [Missing Ranges](https://oj.leetcode.com/problems/missing-ranges/) &hearts; | Medium |
702+
| [Swift](./Array/MissingRanges.swift) | 163 | [Missing Ranges](https://oj.leetcode.com/problems/missing-ranges/) &hearts; | Medium |
696703
| [Swift](./Search/FindPeakElement.swift) | 162 | [Find Peak Element](https://oj.leetcode.com/problems/find-peak-element/) | Medium |
697704
| [Swift](./String/OneEditDistance.swift) | 161 | [One Edit Distance](https://oj.leetcode.com/problems/one-edit-distance/)&hearts; | Medium |
698705
| | 160 | [Intersection of Two Linked Lists](https://oj.leetcode.com/problems/intersection-of-two-linked-lists/) | Easy |
@@ -795,7 +802,7 @@
795802
| [Swift](./DP/UniquePathsII.swift) | 63 | [Unique Paths II](https://oj.leetcode.com/problems/unique-paths-ii/) | Medium |
796803
| [Swift](./DP/UniquePaths.swift) | 62 | [Unique Paths](https://oj.leetcode.com/problems/unique-paths/) | Medium |
797804
| [Swift](./LinkedList/RotateList.swift) | 61 | [Rotate List](https://oj.leetcode.com/problems/rotate-list/) | Medium |
798-
| | 60 | [Permutation Sequence](https://oj.leetcode.com/problems/permutation-sequence/) | Medium |
805+
| [Swift](./Math/PermutationSequence.swift) | 60 | [Permutation Sequence](https://oj.leetcode.com/problems/permutation-sequence/) | Medium |
799806
| [Swift](./Array/SpiralMatrixII.swift) | 59 | [Spiral Matrix II](https://oj.leetcode.com/problems/spiral-matrix-ii/) | Medium |
800807
| [Swift](./String/LengthLastWord.swift) | 58 | [Length of Last Word](https://oj.leetcode.com/problems/length-of-last-word/) | Easy |
801808
| [Swift](./Sort/InsertInterval.swift) | 57 | [Insert Interval](https://oj.leetcode.com/problems/insert-interval/) | Hard |

0 commit comments

Comments
 (0)