从这篇文章开始，我将会将我在算法练习中的所想和收获记录下来。

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
题目输出案例

1.1 思路1

思路1是最简单的思路，就是遍历数组，对于每个元素，都去数组中查找是否有目标值减去当前值的元素。
时间复杂度为O(n^2)，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      for i in nums:
          j = target - i
          start_index = nums.index(i)
          next_index = start_index + 1 
          nums_new = nums[next_index:]#对原数组进行切片，去掉当前元素之前的元素
          if j in nums_new:
              return [start_index,next_index+nums_new.index(j)]

1.2 思路2(哈希表)

思路2是利用哈希表来解决问题。我们遍历数组，对于每个元素，都去哈希表中查找是否有目标值减去当前值的元素。
如果有，就返回当前元素的下标和哈希表中目标值减去当前值的元素的下标。
如果没有，就将当前元素和下标加入哈希表中。
时间复杂度为O(n)，空间复杂度为O(n)。用空间换时间

1
2
3
4
5
6
7
8
class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      dir={}
      for i in range(len(nums)): #遍历数组
          if target-nums[i] not in dir: #如果目标值减去当前值不在字典中
              dir[nums[i]] = i
          else :
              return [dir[target-nums[i]],i]

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。(负数不是回文数)

9.1 思路1

思路1是将整数%10，得到最后一位数，然后将整数//10，去掉最后一位数，重复这个过程，直到整数变成0。
每次得到的数都乘以10，最后得到的数就是整数的倒序。
时间复杂度为O(logn)，空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
if (x<0):
          return False
      else :
          a = x
          num = 0
          while(a!=0):
              num =10 * num + a % 10
              a = a // 10
          if (x == num):
              return True
          else:
              return False