Reversing an Array#
Solution Steps
Place the two pointers (let start and end) at the start and end of the array.
Swap arr[start] and arr[end]
Increment start and decrement end with 1
If start reached to the value length/2 or start ≥ end, then terminate otherwise repeat from step 2.
1from typing import List
2
3
4def reverse_array(arr: List) -> List:
5 start = 0
6 end = len(arr) - 1
7
8 while start < end:
9 arr[start], arr[end] = arr[end], arr[start]
10 start += 1
11 end -= 1
12
13 return arr
14
15
16def reverse_array_pythonic(arr: List) -> List:
17
18 return arr[::-1]
19
20
21if __name__ == "__main__":
22 arr = [1, 2, 3, 4, 5, 6]
23 print(reverse_array(arr))
24 print(arr)
25
26 print(reverse_array_pythonic(arr))
相关练习#
Integer reversion#
https://leetcode.com/problems/reverse-integer/
1def reverse_integer1(x: int) -> int:
2 if x < -(2**31) or x > 2**31 - 1:
3 # if x is out of range,
4 return 0
5 if x < 0: # for negative numbers, -100
6 x = -x # 100
7 x = int(str(x)[::-1]) # '001' -> 1
8 x = -x # -1
9 else: # for positive numbers, 100
10 x = int(str(x)[::-1])
11 return x
12
13
14def reverse_integer2(x: int) -> int:
15
16 if x < -(2**31) or x > 2**31 - 1:
17 # if x is out of range,
18 return 0
19 if x < 0:
20 return -reverse_integer2(-x)
21 else:
22 result = 0
23 while x > 0:
24 result = result * 10 + x % 10
25 x //= 10
26 return result
27
28
29if __name__ == "__main__":
30 print(reverse_integer1(1230))
31 print(reverse_integer1(-1230))
32 print(reverse_integer2(1230))
33 print(reverse_integer2(-1230))
Palindrome Problem#
https://en.wikipedia.org/wiki/Palindrome
1def is_palindrome_pythonic(s):
2 """Return True if the given string is a palindrome."""
3 return s == s[::-1]
4
5
6def is_palindrome(s):
7 """Return True if the given string is a palindrome."""
8 start_index = 0
9 end_index = len(s) - 1
10 while start_index < end_index:
11 if s[start_index] != s[end_index]:
12 return False
13 start_index += 1
14 end_index -= 1
15 return True
16
17
18def leetcode_valid_palindrome(s: str) -> bool:
19
20 # https://leetcode.com/problems/valid-palindrome/
21
22 if len(s) == 0:
23 return True
24 start = 0
25 end = len(s) - 1
26
27 while start < end:
28 while start < end and not s[start].isalnum():
29 start += 1
30 while start < end and not s[end].isalnum():
31 end -= 1
32
33 if s[start].lower() != s[end].lower():
34 return False
35
36 start += 1
37 end -= 1
38
39 return True
40
41
42if __name__ == "__main__":
43 s = "abba"
44 print(is_palindrome(s))
45 s = "1A man, a plan, a canal: Panama1"
46 print(leetcode_valid_palindrome(s))
LeetCode
https://leetcode.com/problems/valid-palindrome/
https://leetcode.com/problems/valid-palindrome-ii/
https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/longest-palindromic-subsequence/
Dutch National Flag Problem#
一个只有0，1，2三种元素的数组，要求把0放在前面，1放在中间，2放在后面。
解题思路总结成一句话就是，把2往后放，把0往前放。
具体思路如下，假如输入的是 [2, 1, 0, 0, 1, 2]
LeetCode
https://leetcode.com/problems/sort-colors/
1def dutch_flag_problem(nums, pivot=1):
2 i = 0
3 j = 0
4 k = len(nums) - 1
5
6 while j <= k:
7
8 if nums[j] < pivot:
9 nums[i], nums[j] = nums[j], nums[i]
10 i += 1
11 j += 1
12 elif nums[j] > pivot:
13 nums[j], nums[k] = nums[k], nums[j]
14 k = k - 1
15
16 else:
17 j += 1
18 return nums
19
20
21if __name__ == "__main__":
22
23 nums = [1, 0, 2, 2, 1, 0, 0, 2, 1]
24 print(dutch_flag_problem(nums, 1))
Trapping Rain Water Problem#
LeetCode
https://leetcode.com/problems/trapping-rain-water/
1# https://leetcode.com/problems/trapping-rain-water/
2
3
4def trap(height):
5 # fill in
6 pass
7
8
9# Trapping Rain Water within given set of bars
10if __name__ == "__main__":
11 heights = [5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0]
12 print("Maximum amount of water that can be trapped is", trap(heights))
13
14
15import unittest
16
17
18class Test(unittest.TestCase):
19 def test_1(self):
20 assert trap([0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0]) == 6
21 print("PASSED: `trap([0,0,1,0,2,1,0,1,3,2,1,2,1,0,0])` should return `6`")
22
23 def test_2(self):
24 assert trap([0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1]) == 14
25 print(
26 "PASSED: `trap([0,0,1,0,2,4,4,4,2,3,1,0,2,4,3,1,0,1])` should return `14`"
27 )
28
29 def test_3(self):
30 assert trap([0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0]) == 0
31 print("PASSED: `trap([0,0,1,2,4,4,4,3,1,0,0,0])` should return `0`")
32
33
34if __name__ == "__main__":
35 unittest.main(verbosity=2)
36 print("Nice job, 3/3 tests passed!")
Anagram Problem#
Anagram问题指的是判断两个字符串中的字符是否完全相同，只是顺序不同。例如，“listen”和“silent”就是一对anagram
https://leetcode.com/problems/valid-anagram/
https://leetcode.com/problems/find-all-anagrams-in-a-string/
https://leetcode.com/problems/group-anagrams/
1"""
2方法1：排序法
3
4首先对两个字符串分别进行排序，如果它们排序后相等，那么这两个字符串就是anagram。
5"""
6
7
8def is_anagram(s1, s2):
9
10 if len(s1) != len(s2):
11 return False
12 s1 = s1.lower()
13 s2 = s2.lower()
14 s1 = sorted(s1)
15 s2 = sorted(s2)
16 return s1 == s2
17
18
19"""
20方法2：哈希表法
21
22可以使用哈希表来记录每个字符在字符串中出现的次数，如果两个字符串中每个字符出现的次数都相同，那么这两个字符串就是anagram。
23"""
24
25from collections import Counter
26
27
28def is_anagram1(s1, s2):
29 return Counter(s1) == Counter(s2)