Skip to content

Commit 31f304a

Browse files
javadevjavadev
committed
Improved tasks
1 parent ffe71ad commit 31f304a

File tree

11 files changed

+741
-552
lines changed

11 files changed

+741
-552
lines changed

‎README.md

+620-435
Large diffs are not rendered by default.

‎src/main/scala/g0001_0100/s0001_two_sum/readme.md

+9-8
Original file line numberDiff line numberDiff line change
@@ -45,15 +45,16 @@ You can return the answer in any order.
4545
```scala
4646
object Solution {
4747
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
48-
val lookup = scala.collection.mutable.Map[Int, Int]()
49-
for (idx <- nums.indices) {
50-
if (lookup.contains(target - nums(idx))) {
51-
return Array(lookup(target - nums(idx)), idx)
52-
} else {
53-
lookup.addOne(nums(idx) -> idx)
54-
}
48+
val indiced = nums.zipWithIndex
49+
val sortedStruct = indiced.sortBy(_._1)
50+
var i = 0
51+
var j = nums.length - 1
52+
while (i < j && j > 0) {
53+
if sortedStruct(j)._1 + sortedStruct(i)._1 > target then j = j - 1
54+
else if sortedStruct(j)._1 + sortedStruct(i)._1 < target then i = i + 1
55+
else return Array(sortedStruct(i)._2, sortedStruct(j)._2)
5556
}
56-
Array(-1, -1)
57+
return Array(-1, -1)
5758
}
5859
}
5960
```

‎src/main/scala/g0001_0100/s0020_valid_parentheses/readme.md

+19-14
Original file line numberDiff line numberDiff line change
@@ -51,27 +51,32 @@ An input string is valid if:
5151

5252
```scala
5353
import scala.collection.mutable.Stack
54+
import scala.util.control.Breaks._
5455

5556
object Solution {
5657
def isValid(s: String): Boolean = {
5758
val stack = Stack[Char]()
58-
59-
for (i <- 0 until s.length) {
60-
val c = s.charAt(i)
61-
if (c == '(' || c == '[' || c == '{') {
62-
stack.push(c)
63-
} else if (c == ')' && stack.nonEmpty && stack.top == '(') {
64-
stack.pop()
65-
} else if (c == '}' && stack.nonEmpty && stack.top == '{') {
66-
stack.pop()
67-
} else if (c == ']' && stack.nonEmpty && stack.top == '[') {
68-
stack.pop()
69-
} else {
70-
return false
59+
var result = true
60+
61+
breakable {
62+
for (i <- 0 until s.length) {
63+
val c = s.charAt(i)
64+
if (c == '(' || c == '[' || c == '{') {
65+
stack.push(c)
66+
} else if (c == ')' && stack.nonEmpty && stack.top == '(') {
67+
stack.pop()
68+
} else if (c == '}' && stack.nonEmpty && stack.top == '{') {
69+
stack.pop()
70+
} else if (c == ']' && stack.nonEmpty && stack.top == '[') {
71+
stack.pop()
72+
} else {
73+
result = false
74+
break()
75+
}
7176
}
7277
}
7378

74-
stack.isEmpty
79+
result && stack.isEmpty
7580
}
7681
}
7782
```

‎src/main/scala/g0001_0100/s0041_first_missing_positive/readme.md

+7-6
Original file line numberDiff line numberDiff line change
@@ -40,20 +40,21 @@ import scala.annotation.tailrec
4040
object Solution {
4141
def firstMissingPositive(nums: Array[Int]): Int = {
4242
for (i <- nums.indices) {
43-
if (nums(i) <= 0 || nums(i) > nums.length || nums(i) == i + 1) {
44-
// Continue the loop
45-
} else {
43+
if (nums(i) > 0 && nums(i) < nums.length && nums(i) != i + 1) {
4644
dfs(nums, nums(i))
4745
}
4846
}
4947

50-
for (i <- nums.indices) {
48+
var result = nums.length + 1
49+
var found = false
50+
for (i <- nums.indices if !found) {
5151
if (nums(i) != i + 1) {
52-
return i + 1
52+
result = i + 1
53+
found = true
5354
}
5455
}
5556

56-
nums.length + 1
57+
result
5758
}
5859

5960
@tailrec

‎src/main/scala/g0001_0100/s0045_jump_game_ii/readme.md

+4-3
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,8 @@ object Solution {
4141
var maxLength = 0
4242
var minJump = 0
4343

44-
for (i <- 0 until nums.length - 1) {
44+
var result = -1
45+
for (i <- 0 until nums.length - 1 if result == -1) {
4546
length -= 1
4647
maxLength -= 1
4748
maxLength = math.max(maxLength, nums(i))
@@ -52,11 +53,11 @@ object Solution {
5253
}
5354

5455
if (length >= nums.length - i - 1) {
55-
return minJump
56+
result = minJump
5657
}
5758
}
5859

59-
minJump
60+
if (result == -1) minJump else result
6061
}
6162
}
6263
```

‎src/main/scala/g0001_0100/s0055_jump_game/readme.md

+17-18
Original file line numberDiff line numberDiff line change
@@ -38,32 +38,31 @@ object Solution {
3838
val sz = nums.length
3939
// We set tmp to 1 so it won't break on the first iteration
4040
var tmp = 1
41+
var result = true // Variable to store the result
4142

42-
for (i <- 0 until sz) {
43+
for (i <- 0 until sz if result) {
4344
// We always deduct tmp for every iteration
4445
tmp -= 1
4546
if (tmp < 0) {
4647
// If from the previous iteration tmp is already 0, it will be < 0 here,
4748
// leading to a false value
48-
return false
49-
}
50-
// We get the maximum value because this value is supposed to be our iterator. If both values are 0,
51-
// then the next iteration will return false.
52-
// We can stop the whole iteration with this condition. Without this condition, the code runs in 2ms (79.6%).
53-
// Adding this condition improves the performance to 1ms (100%)
54-
// because if the test case jump value is quite large, instead of just iterating, we can
55-
// just check using this condition.
56-
// Example: [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> we can just jump to the end without iterating the whole array.
57-
tmp = math.max(tmp, nums(i))
58-
if (i + tmp >= sz - 1) {
59-
return true
49+
result = false
50+
} else {
51+
// We get the maximum value because this value is supposed to be our iterator. If both values are 0,
52+
// then the next iteration will return false.
53+
// We can stop the whole iteration with this condition. Without this condition, the code runs in 2ms (79.6%).
54+
// Adding this condition improves the performance to 1ms (100%)
55+
// because if the test case jump value is quite large, instead of just iterating, we can
56+
// just check using this condition.
57+
// Example: [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> we can just jump to the end without iterating the whole array.
58+
tmp = math.max(tmp, nums(i))
59+
if (i + tmp >= sz - 1) {
60+
result = true
61+
}
6062
}
6163
}
62-
// We can just return true at the end because if tmp is 0 on the previous
63-
// iteration,
64-
// even though the next iteration's index is the last one, it will return false under the
65-
// tmp < 0 condition.
66-
true
64+
65+
result
6766
}
6867
}
6968
```

‎src/main/scala/g0001_0100/s0079_word_search/readme.md

+3-5
Original file line numberDiff line numberDiff line change
@@ -56,11 +56,10 @@ object Solution {
5656
numRows = board.length
5757
numCols = board(0).length
5858
var result = false
59-
for (row <- 0 until numRows) {
60-
for (col <- 0 until numCols) {
59+
for (row <- 0 until numRows if !result) {
60+
for (col <- 0 until numCols if !result) {
6161
if (board(row)(col) == word(0)) {
6262
result = backTracking(board, row, col, word, 0)
63-
if (result) return true
6463
}
6564
}
6665
}
@@ -75,11 +74,10 @@ object Solution {
7574
val originalValue = board(row)(col)
7675
board(row)(col) = '0'
7776
var output = false
78-
for (dir <- directions) {
77+
for (dir <- directions if !output) {
7978
val newRow = row + dir(0)
8079
val newCol = col + dir(1)
8180
output = backTracking(board, newRow, newCol, word, index + 1)
82-
if (output) return true
8381
}
8482
board(row)(col) = originalValue
8583
output

‎src/main/scala/g0001_0100/s0084_largest_rectangle_in_histogram/readme.md

+10-4
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,8 @@ Given an array of integers `heights` representing the histogram's bar height whe
3333
## Solution
3434

3535
```scala
36+
import scala.util.control.Breaks.{break, breakable}
37+
3638
object Solution {
3739
def largestRectangleArea(heights: Array[Int]): Int = {
3840
largestArea(heights, 0, heights.length)
@@ -84,12 +86,16 @@ object Solution {
8486
}
8587

8688
private def checkIfSorted(a: Array[Int], start: Int, limit: Int): Boolean = {
87-
for (i <- start + 1 until limit) {
88-
if (a(i) < a(i - 1)) {
89-
return false
89+
var sorted = true
90+
breakable {
91+
for (i <- start + 1 until limit) {
92+
if (a(i) < a(i - 1)) {
93+
sorted = false
94+
break
95+
}
9096
}
9197
}
92-
true
98+
sorted
9399
}
94100

95101
private def maxOfThreeNums(a: Int, b: Int, c: Int): Int = {

‎src/main/scala/g0201_0300/s0207_course_schedule/readme.md

+20-30
Original file line numberDiff line numberDiff line change
@@ -38,41 +38,31 @@ Return `true` if you can finish all courses. Otherwise, return `false`.
3838
## Solution
3939

4040
```scala
41-
import scala.collection.mutable.ArrayBuffer
42-
4341
object Solution {
44-
val WHITE = 0
45-
val GRAY = 1
46-
val BLACK = 2
47-
4842
def canFinish(numCourses: Int, prerequisites: Array[Array[Int]]): Boolean = {
49-
val adj = Array.fill(numCourses)(new ArrayBuffer[Int]())
50-
prerequisites.foreach { pre =>
51-
adj(pre(1)).append(pre(0))
52-
}
53-
54-
val colors = Array.fill(numCourses)(WHITE)
55-
(0 until numCourses).forall { i =>
56-
if (colors(i) == WHITE && adj(i).nonEmpty && hasCycle(adj, i, colors)) {
57-
false
58-
} else {
59-
true
60-
}
43+
import scala.collection.mutable.{Queue, ListBuffer}
44+
val indegree = Array.fill(numCourses)(0)
45+
val graph = Array.fill(numCourses)(new ListBuffer[Int])
46+
for (data <- prerequisites) {
47+
val course = data.head
48+
val prerequisiteCourse = data.last
49+
indegree(course) = indegree(course) + 1
50+
graph(prerequisiteCourse) += course
6151
}
62-
}
63-
64-
private def hasCycle(adj: Array[ArrayBuffer[Int]], node: Int, colors: Array[Int]): Boolean = {
65-
colors(node) = GRAY
66-
adj(node).foreach { nei =>
67-
if (colors(nei) == GRAY) {
68-
return true
69-
}
70-
if (colors(nei) == WHITE && hasCycle(adj, nei, colors)) {
71-
return true
52+
val startingCourses = indegree.zipWithIndex.filter(_._1.equals(0)).map(_._2)
53+
val queue = Queue[Int](startingCourses: _*)
54+
var courseTaken = 0
55+
while (queue.nonEmpty) {
56+
val current = queue.dequeue
57+
courseTaken = courseTaken + 1
58+
for (neighbor <- graph(current)) {
59+
indegree(neighbor) = indegree(neighbor) - 1
60+
if (indegree(neighbor).equals(0)) {
61+
queue.enqueue(neighbor)
62+
}
7263
}
7364
}
74-
colors(node) = BLACK
75-
false
65+
courseTaken == numCourses
7666
}
7767
}
7868
```

‎src/main/scala/g0201_0300/s0234_palindrome_linked_list/readme.md

+29-27
Original file line numberDiff line numberDiff line change
@@ -44,40 +44,42 @@ import com_github_leetcode.ListNode
4444
*/
4545
object Solution {
4646
def isPalindrome(head: ListNode): Boolean = {
47-
var len = 0
48-
var right = head
49-
50-
// Calculate the length
51-
while (right != null) {
52-
right = right.next
53-
len += 1
47+
if (head == null || head.next == null) {
48+
return true
5449
}
55-
56-
// Reverse the right half of the list
57-
len = len / 2
58-
right = head
59-
for (_ <- 0 until len) {
60-
right = right.next
50+
def reverseList(node: ListNode): ListNode = {
51+
var prev: ListNode = null
52+
var current: ListNode = node
53+
while (current != null) {
54+
val nextNode = current.next
55+
current.next = prev
56+
prev = current
57+
current = nextNode
58+
}
59+
prev
6160
}
6261

63-
var prev: ListNode = null
64-
while (right != null) {
65-
val next = right.next
66-
right.next = prev
67-
prev = right
68-
right = next
62+
def findMiddle(node: ListNode): ListNode = {
63+
var slow = node
64+
var fast = node
65+
while (fast != null && fast.next != null) {
66+
slow = slow.next
67+
fast = fast.next.next
68+
}
69+
slow
6970
}
70-
var head2 = head
71-
// Compare left half and right half
72-
for (_ <- 0 until len) {
73-
if (prev != null && head2.x == prev.x) {
74-
head2 = head2.next
75-
prev = prev.next
76-
} else {
71+
72+
val middle = findMiddle(head)
73+
var secondHalf = reverseList(middle)
74+
75+
var firstHalf = head
76+
while (secondHalf != null) {
77+
if (firstHalf.x != secondHalf.x) {
7778
return false
7879
}
80+
firstHalf = firstHalf.next
81+
secondHalf = secondHalf.next
7982
}
80-
8183
true
8284
}
8385
}

‎src/main/scala/g0201_0300/s0287_find_the_duplicate_number/readme.md

+3-2
Original file line numberDiff line numberDiff line change
@@ -53,13 +53,14 @@ You must solve the problem **without** modifying the array `nums` and uses only
5353
object Solution {
5454
def findDuplicate(nums: Array[Int]): Int = {
5555
val arr = new Array[Int](nums.length + 1)
56+
var duplicate = 0
5657
for (num <- nums) {
5758
arr(num) += 1
5859
if (arr(num) == 2) {
59-
return num
60+
duplicate = num
6061
}
6162
}
62-
0
63+
duplicate
6364
}
6465
}
6566
```

0 commit comments

Comments
 (0)