アルゴリズム(3)--leetcode-explore-learn-データ構造-配列1

leetcode-explore-learn-データ構造-配列1

1.概要

2.例題

2.1配列の中心インデックスを探す

2.2少なくとも他の数字の2倍の最大数

2.3プラス

このシリーズのブログはleetcode-explore-learnサブ欄の学習ノートです.不明な点があれば、leetcode公式サイトを参照してください.https://leetcode-cn.com/explore/learn/card/array-and-string/198/introduction-to-array/768/
1.簡単に述べる
配列は、データを順番に格納するための最も基本的なデータ構造です.配列内の要素はインデックスによって読み書き操作を実現します.配列には1つ以上の次元があり、本稿では主に1次元配列とその関連例題を記録する.
一般的なプログラミング言語では,配列には固定容量があり,初期化時に配列サイズを決定する必要があり,その後はその長さを変更することはできない.操作が非常に便利ではないため、多くのプログラミング言語は動的配列のデータ構造を提供し、そのサイズは可変である.
ButはPythonではそれほど複雑ではなく、リストデータ構造は配列や動的配列を含む多くのニーズを満たすことができます.
2.例題
2.1配列の中心インデックスを探す
整数タイプの配列を指定し、プログラミングは配列の中心インデックスを返します.中心インデックスの定義:中心インデックスの左側のすべての要素の和が右側のすべての要素の和より大きい.特殊な場合:中心インデックスが存在しない場合は、-1を返します.複数の中心がある場合は、一番左の考え方を返します.2つの配列を定義します.l e f t_s u m [ i ] = ∑ j = 0 i − 1 n u m s [ j ] ,    i = 1 , 2 , 3 , . . . , n − 1 left\_sum[i]=\sum_{j=0}^{i-1}nums[j],\\i=1,2,3,...,n-1 left_sum[i]=j=0∑i−1​nums[j],  i=1,2,3,...,n−1
r i g h t _ s u m [ i ] = ∑ j = i + 1 n − 1 n u m s [ j ] ,    i = n − 2 , n − 3 , . . . , 0 right\_sum[i]=\sum_{j=i+1}^{n-1}nums[j],\\i=n-2,n-3,...,0 right_sum[i]=j=i+1∑n−1​nums[j],  i=n−2,n−3,...,0
個々の比較left_sumとright_sumの要素は、同じ場合は対応するインデックスを返し、遍歴が完了しても同じでない場合は-1を返します.
例:nums=[1,7,3,6,5,6][0,1,27][1,7,20][8,3,17][11,6,11][17,5,6][22,6,0]left_sum=[0,1,8,11,17,22] right_sum=[27,20,17,11,6,0]

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n==0:
            return -1
        left_sum=[0]*(n)
        right_sum=[0]*(n)
        for i in range(1,n):
            left_sum[i]=left_sum[i-1]+nums[i-1]
        for i in range(n-2,-1,-1):
            right_sum[i]=right_sum[i+1]+nums[i+1]
        print (left_sum,right_sum)
        for i  in range(n):
            if left_sum[i]==right_sum[i]:
                return i
        return -1

2.2少なくとも他の数字の2倍の最大数
与えられた配列numsには、常に最大要素が存在する.配列内の最大要素が、配列内の他の各数値の少なくとも2倍であるかどうかを検索します.もしそうであれば、最大要素のインデックスが返されます.そうでなければ、-1が返されます.
考え方:一回の検索、最大値の二回の検索を探して、2倍の条件を満たすかどうかを判断します

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        max_num=float("-INF")
        max_ind=-1
        for i in range(n):
            if nums[i]>max_num:
                max_num=nums[i]
                max_ind=i

        for i in range(n):
            if i ==max_ind:
                continue
            #      nums[i]   
            if max_num<nums[i]*2:
                
                return -1
        return max_ind
            

2.3プラス1
整数からなる非空配列で表される非負の整数を与え、その数に1を加える.最上位の数値は配列の先頭に格納され、配列内の各要素には単一の数値のみが格納されます.整数0を除いて、この整数はゼロで始まると仮定できます.
コアの難点:キャリーがある場合はどのように処理すればいいのか、操作を追加するため、キャリーの難易度を大幅に簡素化した.
構想1 :配列上で直接操作し、配列の各位置の数字がキャリーを発生するかどうかを判断する.

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        n=len(digits)
        digits[n-1]+=1
        #     ,        。
        flag=0
        for i in range(n-1,-1,-1):
            if flag==1:
                digits[i]+=1
                flag=0
            if digits[i]==10:
                digits[i]=0
                flag=1
        if flag!=0:
            res=[flag]
            for i in range(n):
                res.append(digits[i])
            return res
        return digits
            

構想2:配列回転数,数字+1処理,再回転配列.

    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        #      ，        
        n=len(digits)
        nums=0
        e=0
        for i in range(n-1,-1,-1):
            nums+=digits[i]*10**e
            e+=1
        nums+=1
        res=[]
        while(nums>0):
            digit=nums%10
            res.append(digit)
            nums=(nums-digit)/10
        res.reverse()
        return res