leetcode刷题记录3-7

发表于   |   分类于

介绍3

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

思路3

显然不能死板操作，只能找找规律了

代码3

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num==0:
            return 0
        if num%9==0:
            return 9
        else:return num%9

介绍4

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

思路4

利用python列表的特性取巧了，直接删掉0，删一个就在列表末尾补一个，避免对列表整体的移动操作

代码4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        l=len(nums)
        n=0
        for i in range(l):
            if i==l-n-1:
                break
            for j in range(l):
                if nums[i]==0:
                    del nums[i]
                    nums.append(0)
                    n=n+1
                else:
                    break

介绍5

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

思路5

没啥好说的，错了很多次，有各种意外情况，写的代码还能再优化

代码5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        nums=[]
        if len(nums1)==1:
            for i in range(len(nums2)):
                if nums1[0]==nums2[i]:
                    nums.append(nums1[0])
                    break
        else:
            for i in range(len(nums1)):
               if nums==[]:
                  for j in range(len(nums2)):
                     if nums1[i]==nums2[j]:
                        nums.append(nums1[i])
                        break 
               else:
                   if nums1[i]==nums[-1]:
                       pass
                   else:
                       for j in range(len(nums2)):
                            if nums1[i]==nums2[j]:
                                 nums.append(nums1[i])
                                 break 
   
                             
        return nums

介绍6

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

思路6

先全部乘起来再分别除以各个元素就行了，不过得考虑出现0的情况

代码6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        p=1
        n=0
        t=0
        for i in range(len(nums)):
           if nums[i]==0:
                n=n+1
                t=i
           else:
                p=p*nums[i]
        if n>=2:
            output=[0 for i in range(len(nums))]
        elif n==1:
            output=[0 for i in range(len(nums))]
            output[t]=p
        else:
            output=[p/nums[i] for i in range(len(nums))]
        return output

介绍7

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

思路7

利用位操作

代码7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n1=0
        n2=0
        q=0
        p=1
        t=0
        for i in nums:
            q=q^i
        while True:
            if q%2==1:
                break
            else:
                q=q>>1
                t=t+1
        for i in nums:
            if (i>>t)%2==1:
                n1=n1^i
            else:
                n2=n2^i
        return [n1,n2]