soapyigu / leetcode-swift Goto Github PK

The link to solution in README.md is off. Currently it's https://github.com/soapyigu/LeetCode_Swift/blob/master/Math/GenerateParentheses.swift, seems that it should be https://github.com/soapyigu/LeetCode_Swift/blob/master/DP/GenerateParentheses.swift instead.

Currently complexity: O((n^2)!)

1. Tiles are switched to 0 once visited, so they cannot be visited again. Although the search can look into 4 directions for each tile, it doesn't keep going.
2. The instructions don't say that the board is a square (although it is in the example).

Suggested complexity: O(mn)

https://github.com/soapyigu/LeetCode-Swift/blob/master/String/ZigZagConversion.swift
Page Not Found 404

When I cloned this project I had to individually select each playground file to view the implementation. I took all your LeetCode_Swift .swift files and neatly put them in one Xcode project folder so it will be easier for anyone cloning it to have it in one place. I also added .playground files to each one. Is that something thats you are willing to consider pulling?

LeetCode-Swift/Array/RemoveDuplicatesFromSortedArray.swift
The solution to the above problem doesn't seems to be correct.

e.g
Input: [1,1,2,2,5,5,6,8,9,9,9]
Program output in Leetcode console: [1,2,5,6,8,9]
Program Output in Xcode Playground : [1, 2, 5, 6, 8, 9, 6, 8, 9, 9, 9]
Expected Output is: [1,2,5,6,8,9]

故胤道长是吧？哈哈

as Apple API Reference say:

Swift Standard Library - AnyBidirectiona - lCollection

reversed()

Instance Method
reversed()
Returns a view presenting the elements of the collection in reverse order.
...
...
If you need a reversed collection of the same type, you may be able to use the collection’s sequence-based or collection-based initializer. For example, to get the reversed version of a string, reverse its characters and initialize a new String instance from the result.

let reversedWord = String(word.characters.reversed())
print(reversedWord)
// Prints "sdrawkcaB"

Complexity: O(1)

@soapyigu , Leetcode has added a new test case ["abc","ab"]. So the solution is failing

I have added this check inside initGraph method, now it's working.

if currentWord.count > nextWord.count && currentWord.starts(with: nextWord){ return ([:], [:]) }

My full solution is https://pastebin.com/f7RzLqfM

The answer for Add Strings links to incorrect question: https://leetcode.com/problems/length-of-last-word/

Add Strings:

Linked to:

/**

• Question Link: https://leetcode.com/problems/range-sum-query-immutable/
• Primary idea: Calculate the sum of the elements of nums between indices left and right
• Time Complexity: O(n), Space Complexity: O(1)

*/

class NumArray {
	var sums: [Int] = []

	init(_ nums: [Int]) {
		var currentSum = 0

		for num in nums {
			currentSum += num
			sums.append(currentSum)
		}
		print(sums)
	}

	func sumRange(_ left: Int, _ right: Int) -> Int {
		if left == 0 {
			return sums[right]
		}
		return sums[right] - sums[left-1]
	}
}

I'm wondering that the time complexity of this solution is O(n) rather than O(n^2) ? Seems that each letter is visited and output for just once.

Also I'm curious why the 2 functions _buildLine and _buildSpecialLine has a "_" prefix? Is it because they are private methods and this is some kind of a coding convention? Thanks a lot:)

Great solution! Although I think the time complexity is more like O(lgn), as n being num?
Not that important anyways, since num is guaranteed to be <= 3999.

use "abcdefghiepoiuq" to test, print 9. but 10 Actually.

My code prints correctly:

    func lengthOfLongestSubstring(_ string: String) -> Int {
        var flags = Array(repeating: -1, count: 128)
        var maxLength = 0
        var startIndex = -1
        
        for (index, char) in string.enumerated() {
            let asciiValue = Int(char.asciiValue ?? 0)
            if flags[asciiValue] > startIndex {
                if index - startIndex > maxLength {
                    maxLength = index - startIndex
                }
                startIndex = flags[asciiValue] + 1
                flags[asciiValue] = index
                continue
            }
            flags[asciiValue] = index
        }
        
        if string.count - startIndex > maxLength {
            maxLength = string.count - startIndex
        }
        return maxLength
    }

simple problem:

class Solution {
    func containsDuplicate(nums: [Int]) -> Bool {
        return nums.count > Set(nums).count
    }
}

I think it would be cool if there was an option for each contributor to be able to explain in a REAME file their thought process and how they came up with their solutions. I think it would help people understand someone else's logic. It will also help it read better on github. I can add additional changes to the Architect branch. What do you think?

Here I just tried to improve the space complexity.

your Solution ->

https://github.com/soapyigu/LeetCode-Swift/blob/master/Math/TrappingRainWater.swift

Mine with -> O(n) TC and O(1) SC

`
class Solution {
func trap(_ height: [Int]) -> Int {
var waterContainerResult = 0
var left = 0, right = height.count - 1, leftMax = 0, rightMax = 0

    while left < right{
        if height[left] < height[right]{
            if height[left] >= leftMax{
                leftMax = height[left]
            }else{
                waterContainerResult = waterContainerResult + leftMax - height[left]
            }
            left += 1
        }else{
            if height[right] >= rightMax{
                rightMax = height[right]
            }else{
                waterContainerResult = waterContainerResult + rightMax - height[right]
            }
            right -= 1
        }
    }

    return waterContainerResult
}

}
`

Runtime: 28 ms, faster than 93.62% of Swift online submissions for Trapping Rain Water.
Memory Usage: 20.9 MB, less than 5.01% of Swift online submissions for Trapping Rain Water.

If it looks fine, I will raise a PR for this.

Hi there,

Can u give a bit explanation of the following lines:

      for i in 0..<arr.count {
            searchPalindrome(arr,i,i,&start,&maxLength)
            searchPalindrome(arr,i,i+1,&start,&maxLength)
        }

and:

      if maxLength < r - l - 1 {
            start = l + 1
            maxLength = r - l - 1
        }

Best Regards

Multiple lines for func verticalOrder(_ root: TreeNode?) -> [[Int]] { . Please remove one.

https://github.com/soapyigu/LeetCode-Swift/blob/master/Tree/BinaryTreeVerticalOrderTraversal.swift

Just wanted to know, would you be able to submit the solution in Leetcode? For me, it's failing.

The current algorithm will always return the last integer to displace the major as the new majority element. Take var array = [1,1,1,2,2,3] for example. The answer should be 1 but the algorithm returns 3.

Also, majority element must appear more than number of elements/2 times. The algorithm doesn't take this in to account.

Thanks for all your hard work!

Slight Correction..

`func isPalindrome(_ s: String) -> Bool {
// Make String into an array of lowercase Characters
let characters = s.lowercased()

// Only keep alphanumeric characters.
let cleanedCharacter = characters.filter { character in
    return character.description.rangeOfCharacter(from: CharacterSet.alphanumerics) != nil
}

// Making array of cleaned characters
let cleaned = Array(cleanedCharacter)

// Compare values at mirroring indices.
let total = cleaned.count
for i in 0 ..< total/2 {
    if cleaned[i] != cleaned[total - 1 - i] {
        return false
    }
}
return true

}
`

The space complexity was specified as O(1) in the solution, however because of recursion, considering the stack, should it be O(n) instead?

https://github.com/soapyigu/LeetCode-Swift/blob/master/Array/SlidingWindowMaximum.swift

testcase: [ 2, 3, 4, 2, 6, 2, 5, 1 ]
expected: [4, 4, 6, 6, 6, 5]
errorResult: [4, 4, 6, 6, 5, 5]

Modify

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        guard k > 0 && k <= nums.count else {
            return []
        }

        var maxIdx = [Int]()
        var res = [Int]()

        for i in 0..<nums.count {
            while maxIdx.count > 0 && nums[maxIdx.last!] <= nums[i] {
                maxIdx.removeLast()
            }
            maxIdx.append(i)
            if i >= k - 1 {
                if maxIdx.first! + k == i {
                    maxIdx.removeFirst()
                }
                res.append(nums[maxIdx.first!])
            }
        }

        return res
    }