soapyigu / leetcode-swift Goto Github PK
View Code? Open in Web Editor NEWSolutions to LeetCode by Swift
License: MIT License
Solutions to LeetCode by Swift
License: MIT License
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)!)
Suggested complexity: O(mn)
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/
/**
*/
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?
testcase: [ 2, 3, 4, 2, 6, 2, 5, 1 ]
expected: [4, 4, 6, 6, 6, 5]
errorResult: [4, 4, 6, 6, 5, 5]
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
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.