• 时间:
  • 分类: 数组
  • 访问: 1,302 次

一、题目列表

题目1、构建乘积数组

题目2、调整数组顺序使奇数位于偶数前面(一)

题目3、把数组排成最小的数 JZ45

题目4、丑数 JZ49

题目5、数组中重复的数字 JZ3

题目6、旋转数组的最小数字 JZ11

题目7、打印从1到最大的n位数JZ17

题目8、两数之和 leetcode1 :给定一个整数数组 nums 和一个整数目标值 target

数组基本操作-python

1.数组反转

array = [1,2,3,4]
result = array[::-1]
print(result)

二、题目

题目1、构建乘积数组

JZ66 构建乘积数组

描述
给定一个数组 A[0,1,...,n-1] ,请构建一个数组 B[0,1,...,n-1] ,其中 B 的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]）
对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

示例1
输入：
[1,2,3,4,5]
返回值：
[120,60,40,30,24]
1.思路

方法一：暴力求解

方法二：通过两次循环
第一次左边连续相乘
第二次右边连续相乘

时间复杂度：O(n)，其中nnn为数组A的长度，遍历两次数组
空间复杂度：O(1)，数组B为返回必要空间，不属于额外空间

2.代码
(1)方法一:暴力求解
class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        # write code here
        ans=[1] *len(A)
        for i in range(len(A)):
            mark = A[:i]+A[i+1:]
            for item in mark:
                ans[i]*=item
        return ans

(2)方法二：通过两次循环
class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        #初始化数组B
        B = [1 for i in range(len(A))]
        #先乘左边，从左到右
        for i in range(1, len(A)):
            #每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1]
        temp = 1
        #再乘右边，从右到左
        for i in reversed(range(len(A))):
            #temp为右边的累乘
            B[i] *= temp
            temp *= A[i]
        return B

题目2、 调整数组顺序使奇数位于偶数前面(一)

JZ21 调整数组顺序使奇数位于偶数前面(一)

描述
输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
1.思路

比较简单，先抽出奇数，在抽出偶数

2.代码
#
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        # write code here
        res = []
        for each in array:
            if each % 2: res.append(each)
        for each in array:
            if not each % 2: res.append(each)
        return res

题目3、JZ45 把数组排成最小的数

描述
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
1.思路
2.代码
import functools
class Solution:
    
    def mycmp(x,y):
        x ,y = str(x), str(y) 
        if x + y < y+x :
            return 1
        elif x+y > y+x :
            return -1
        else:
            return 0
    
    def PrintMinNumber(self , numbers: List[int]) -> str:
        # write code here
        
            numbers.sort(key=functools.cmp_to_key(mycmp),reverse = True)
            
            return "".join(numbers)

题目4、丑数

描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数
1.思路

step 1：第一个丑数1加入数组。
step 2：使用i、j、k三个索引表示该数字有无被乘2、乘3、乘5的指针
step 3：后续继续找n−1n-1n−1个丑数，每次取当前丑数索引乘2、乘3、乘5的最小值加入数组，并计数。
step 4：若是该丑数为相应索引乘上某个数字，则对应的索引往后一位。
参考：https://blog.csdn.net/slove3366/article/details/106724597

2.代码
class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        #排除0
        if index == 0:
            return 0
        #按顺序记录丑数
        num = []
        num.append(1)
        #记录这是第几个丑数
        count = 1; 
        #分别代表要乘上2 3 5的下标，定义三个指针
        i = 0
        j = 0 
        k = 0 
        while count < index:
            #找到三个数中最小的丑数
            num.append(min(num[i] * 2,num[j] * 3, num[k] * 5)); 
            count += 1
            #判断刚才插入数组是哪个指针，需要指针向前移动一个
            if num[count - 1] == num[i] * 2:
                i += 1
            #由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if num[count - 1] == num[j] * 3:
                j += 1 
            #由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
            if num[count - 1] == num[k] * 5:
                k += 1 
        return num[count - 1]

题目5、数组中重复的数字 JZ3

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
返回描述：
如果数组中有重复的数字，函数返回true，否则返回false。
如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）
1.思路
2.代码
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        tmp = []
        for i in numbers:
            if i in tmp:
                duplication[0] = i 
                return True
            else:
                tmp.append(i)
        return False

题目6、旋转数组的最小数字 JZ11

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1 le n le 100001≤n≤10000，数组中任意元素的值: 0 le val le 100000≤val≤10000
要求：空间复杂度：O(1)O(1) ，时间复杂度：O(logn)O(logn)

1.思路

二分法实现，先取得中间的数，和最右边对比，判断中间到最右是否升序数组

2.代码
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , r: List[int]) -> int:
        # write code here
        left, right = 0, len(r)-1
        while left < right:
            mid = (left+right-1)//2
            if r[mid] < r[right]:
                right = mid
            elif r[mid] > r[right]:
                left = mid+1
            else:
                right -= 1
        return r[left]

题目7、打印从1到最大的n位数JZ17

1.思路
2.代码
class Solution:
    def printNumbers(self , n: int) -> List[int]:
        # write code here
        seq = []
        for i in range(1, 10**n):
            seq.append(i)
        return seq

题目8、 两数之和

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

1.思路
2.代码

标签: none

添加新评论