preface

Why swipe Leetcode with Swift? Because I have two ideas: one is to learn Swift and have the opportunity to practice; the other is to finish brushing Leetcode. So the two ideas came together, and now I’m doing it at a rate of about one a day.

Is Swift suitable for swiping Leetcode? Now I have done more than 20 questions, my personal opinion is not suitable. Probably easier to write than pure C, but not as easy to write as Java or Python.

First of all, Swift is not very efficient. Some algorithms will time out if they are ok with other languages (although it is related to case, Swift is really not efficient). Second, Swift has a lot of problems, especially with string handling. It can’t even access random characters somewhere in the string… It has to be converted to an array of characters first, which means that any problem with strings can be at least O(n) in time and space. There are some string-related apis that can be inefficient and time out if you want to keep your code concise… In short, if it is a practice algorithm, it is best not to consider these factors. From this point of view, Swift is not the most suitable language for brushing Leet code. But of course it’s possible, so if you’re interested, do it.

I posted my solution on my Github and updated it gradually. There is also a very complete solution on Github, for which I have contributed a little bit of code.

Notes for each problem

Here are my simple answers to questions 1-20 that you can look at when you get stuck:

  1. Two Sum (Easy) solve a simple hash. A trick is to check for each number to see if the desired number and target is already in the dict, and return it if it is, before putting itself in the dict. Instead of building the hash and iterating over it again, loop twice. Time complexity: O(n) Space complexity: O(n)

  2. Add Two Numbers (Medium) Problem solving simple single – linked list processing. Consider several cases: 1. Two digits are equal, and the highest digit does not carry. 2. The two digits are not equal. Some people write dummy at the head of the result, with dummy val inserted directly after any real head. Finally return dummy -> next. Time complexity: O(n) Space complexity: O(1)

  3. For Longest Substring Without Repeating Characters (Medium), the method I use is to use a hash to record the index for each letter appearing, and then scan the string. You fill in the hash table when there’s no repetition. When a duplicate occurs, the previousIndex of the letter is extracted from the hash and all letters from the beginning of the current string to previousIndex are removed from the hash. A better way to do this is not to store the index where the letter appears, but to simply clear the hash from the beginning of the string to where the letter appears. In this case, you don’t need a Dictionary to hash, you just need a Set. The extra space needed to hash is small, but swift must save a copy of the character array to iterate through the string. So the space complexity is order n. Time complexity: O(n) Space complexity: O(n)

  4. Median of Two Sorted Arrays (Hard) The idea is to approach the median from both sides, take the midpoint of two sequences, and it can be proved that there is always one that cannot satisfy the condition of the KTH largest. And then we adjust the sequence. The problem is that some things can go too far. In addition, there is a case where the array has reached its end and cannot be adjusted, and another array needs to be adjusted. It’s still log of m plus N, but the code is very long, and the principles aren’t very clear. Solution1 looks at a solution where two numbers are cut off at k/2 each time. Why is Solution1 so concise? The main problem is that Solution1 approaches the problem from one side, getting closer to the solution with each iteration. Solution2 approaches from both sides to the middle, whereas binary search is not as good as binary search. It is possible for both Pointers to be on the same side of the solution and to look back. In addition, Solution1 uses a trick to ensure that NUMS1 is shorter with each iteration, instead of switching. You can avoid a lot of symmetric duplicate code. In language, we can see if(…) in Swift. {return … } This is mostly used instead of guard. Time complexity: log(m+n) Space complexity: O(m+n)

  5. For Longest palindromic Substring (Medium), the solution is O(n^2). DP, search for length 1, 2… To n. It’s not very neat, it has a lot of temporary variables, it’s all swift. Remember the nature of the Swift string, which cannot be accessed randomly because each character is not necessarily the same length. That is, if you don’t store temporary variables, take a certain bit of character, take the length of the string, cut the substring, all at level N… So time runs out again and again. IsPalidromeMatrix [startIndex][endIndex] =… This will time out, and if (…) {isPalidromeMatrix[startIndex][endIndex] = true} this does not. It just assigns more false… And if isPalidrome is changed to if isPalidromeMatrix[startIndex][endIndex], the time is twice as long. It feels like the swift performance problem is really serious with a slightly larger amount of data. Time complexity: O(n^2) Space complexity: O(n^2) This problem has an O(n) algorithm. First of all, there is the idea of violent search, which is to expand outward with any one as the center. O(n) algorithm is based on this, using the property of palindrome string, there is a substring so that the center point is symmetric on both sides, and on this basis you can search out. See this article for details

  6. ZigZag Conversion (Easy) problem solving very simple problem, the only difficulty is the problem itself is not very clear description. You need to consider the boundary cases for row = 1, 2. Swift has a stride function to handle the for step case. Time complexity: O(n) Space complexity: O(n)

  7. Reverse Integer (Easy) The Reverse Integer (Easy) is an Easy question in itself, but it feels like a good interview question. You can test whether the interviewer considers various boundary cases and has a concept of overflow. The test case is not given to Swift properly, so only int32.max can be used. I am to unify negative numbers into positive numbers to calculate, so that the judgment of the overflow statement can be simple. Time complexity: O(LGN) Space complexity: O(1)

  8. String to Integer (Easy) String to Integer (Easy) A pile of cases, really a little lazy can not steal it. Time complexity: O(n) Space complexity: O(n)

  9. Palindrome Number (Easy) Palindrome Number (Easy) There is a case 1000021 that was made wrong at the beginning. The other one wrote a recursion at first, but later found it unnecessary… Time complexity: O(n) Space complexity: O(1)

  10. Regular Expression Matching (Hard) 答 案 是 : Regular Expression Matching (Hard) When it comes to *, it can be divided into two situations: use up the token or use the token in the next round. One problem is that direct recursion times out. We need to deal with the re formula first:

    1. aaCombined into a *
    2. a.bFor the merger.(is it.All the x’s before and afterRemove all).

      Time complexity: O(n) Space complexity: O(n)

  11. The Container With Most Water (Medium) Container With Most Water (Medium) Worst case O(n^2), and then two sets of data (worst case) can’t get through, timeout. If you look in the problem, if you look in the middle, you get order n. Want to change to memory search, find it difficult. Search order is really important! A lot of things from back to front, from the middle to both sides, from both sides to the middle, much worse… Time complexity: O(n) Space complexity: O(1)

  12. Integer to Roman (Medium) Problem solving is very simple recursion, nothing to say. Just be careful. If you look at some of the problems where you save 1000, 900, 500, that’s a lot faster, because you don’t have to worry about adding to the left. It’s also non-recursive because you don’t have to go to the 10th power and it’s probably a little bit faster. Time complexity: O(LGN) Space complexity: O(1)

  13. Roman to Integer (Easy) Roman to Integer (Easy) Roman to Integer (Easy) It’s a case of simple recursion (why do I like recursion so much…). See a solution of the idea is very clever, backward sweep forward, bigger than the previous one to add, not the previous one to reduce. It’s taking advantage of a nice feature of Roman numerals. But on second thought, there seems to be no need to reverse it… The same is true for scanning directly from front to back O O Time complexity: O(n) Space complexity: O(n)

  14. Longest Common Prefix (Easy) the simplest string handling, there is nothing to say. Time complexity: O(nm) Space complexity: O(nm)

  15. I’m still using the hash method to find the first number and then the second number… The way to get rid of the weight is to ask for the order of the three numbers so that they don’t get heavier. If you see a problem, you sort it, and then you fix the first number, the second number on the left, and the third number on the right. Then big move small, small move big… Like this. That’s another way of thinking about it. Time complexity: O(n^2) Space complexity: O(n)

  16. Closest (Medium) At this point use the same sort of thinking as the last problem. Then specify that the first term is left to right, the second term is to the right of the first term (the leftmost of the remaining interval), and the third term is to the right. Then when they are small, they move the left one to the right, and when they are big, they move the right one to the left… Time complexity: O(n^2) Space complexity: O(n)

  17. Letter Combinations of a Phone Number (Medium). Clearly a wide search problem, and write “recursive”, just because I am too lazy to open two arrays…… Is it impossible to save the O O ok, back to the honest repair of a normal version. And found that the “recursive” version was much faster… For no reason at all, the “recursive” version unnecessarily builds suffix strings, but copying arrays is slow? Time: O(3^n) Space: O(3^n)

  18. 4Sum (Medium) = 3Sum (Medium) = 3Sum (Medium) I heard it goes over time? It didn’t. It was still around the median. Some simple pruning, such as squeezing the smallest two numbers are not small enough, the largest two numbers are not large enough, then there is no need to continue. With the pruning, the code is much, much longer, but whoosh, at only 52 ms. Each node is linked to the linked list. Time: O(n^3) Space: O(n)

  19. Remove Nth Node From End of List (Easy) Just two Pointers, the first to the head and the second to the NTH node; And then we move both Pointers backwards, and when the second pointer comes to the tail, the first pointer points to the NTH node from the bottom, and we just drop it. Time complexity: O(n) Space complexity: O(n)

  20. The Valid Parentheses (Easy) solution is probably the easiest one on the stack. If it’s an open bracket, push; It’s close parenthesis, pop, and returns false if it doesn’t match. Return true if the stack is empty, false otherwise. Time complexity: O(n) Space complexity: O(n)