2018-07-08

はいれつ
問題1.並べ替え配列から重複を削除
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:
与えられた配列nums=[1,1,2],
関数は新しい長さ2を返し、元の配列numsの最初の2つの要素は1,2に変更されます.
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.例2:
与えられたnums=[0,0,1,1,2,2,3,4],
関数は新しい長さ5を返し、元の配列numsの最初の5つの要素は0,1,2,3,4に変更されます.
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.説明:
なぜ返される数値は整数ですが、出力される答えは配列ですか?
入力配列は「参照」で渡されます.これは、関数で入力配列を変更することが呼び出し元に表示されることを意味します.
内部操作は次のように想像できます.

// nums   “  ”     。    ，         
int len = removeDuplicates(nums);

//                    。
//            ,                    。

for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解題構想:配列は並べ替えられているので、1つの下付きiで要素が配列を繰り返さない最後の要素の位置を維持するだけで、iは0に初期化され、それから最初の要素から配列を遍歴し、要素がiの位置の要素と同じであれば繰り返し要素であり、スキップすることができ、そうでなければこの要素をi + 1の位置に置く.下付きの更新はi + 1を指す、遍歴終了後の重複しない配列の長さはi + 1であり、同時に遮断配列は最後の重複しない要素の位置iまでしか保持する.

Time:  O(n)
Space: O(1)
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        i = 0
        for j in xrange(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        nums = nums[:i + 1]
        return i + 1
        

問題2.株式売買のベストタイミングII
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:
入力:[7,1,5,3,6,4]出力:7解釈:2日目(株価=1)に購入し、3日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.その後、4日目(株価=3)に購入し、5日目に購入する(株価=6)のときに売り、この取引所で利益を得る=6-3=3.例2:
入力:[1,2,3,4,5]出力:4解釈:1日目(株価=1)に購入し、5日目に(株価=5)のときに売ると、この取引所は利益=5-1=4になります.1日目と2日目に株を相次いで購入してから売ることはできないことに注意してください.これは複数の取引に同時に関与しているので、再購入前に前の株を売却する必要があります.例3:
入力:[7,6,4,3,1]出力:0解釈:この場合、取引が完了しないため、最大利益は0である.
问题の考え方:株が储かる条件は安く买って高く売ることで、ここの制限条件は同时に1笔の取引しかできないので、それでは最大の利益は売买の最大の差額の和で、横座標で时间の日を考えて、縦座標は毎日の株価で、1本の株価の线を描きますでは、最大の利益を得る戦略は、取引ごとに曲線の低点(左右の両方が当日の株価より高い)から購入し、高点(左右の両方が当日の株価より低い)で売り、高点の株価から低点の株価を差し引くと、この取引の利益であり、低点座標(x 1,y 1)、中間点座標(x 2,y 2)、高点座標(x 3,y 3)と仮定し、ではprofit=y 3-y 1=(y 3-y 2)+(y 2-y 1)となり、検索低点と高点を隣接2日間の株価の差の和に変換することができ、隣接2日間の株価の差がマイナスになると損失をもたらす場合は、この取引をしないことを選択します.

Time:  O(n)
Space: O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        return sum(map(lambda x: max(prices[x + 1] - prices[x], 0), xrange(len(prices[:-1]))))

問題3.かいてんはいれつ
配列を指定し、配列内の要素をk個の位置に右に移動します.ここで、kは負ではありません.
例1:入力:[1,2,3,4,5,6,7]およびk=3出力:[5,6,7,1,2,3,4]解釈:右回転1ステップ:[7,1,2,3,4,5]右回転2ステップ:[6,7,1,2,3,4,5]右回転3ステップ:[5,6,7,1,2,3,4]
例2:入力:[-1,-100,3,99]およびk=2出力:[3,99,-1,-100]解釈:右へ1ステップ回転:[99,-1,-100,3]右へ2ステップ回転:[3,99,-1,-100]説明:

はできるだけ多くの解決策を考え出し、少なくとも3つの異なる方法でこの問題を解決することができる.

は、空間的複雑度がO(1)のその場アルゴリズムの使用を要求する.

解題構想:新しい配列で結果を保存できれば,単純に二つの部分に分けて新しい配列を入れるだけでよい,時間責任度はO(n)であるが,問題は空間複雑度がO(1)であることを要求し,元の配列でしか変換できない,最も直接的な考え方はk回の平行移動を行い,平行移動のたびにO(1)の空間しか必要としない,しかし時間責任はO(n*k)となるので、O(n)の時間的複雑さを見つけることができるかどうかを考え続けるしかない.すなわち、定数回数の平行シフト変換(kに関係なく)をするだけで、出力結果と入力の対比をよく見ると、最後の辺のk個数を左に置き、元のn-k個数を右に移動するだけで、reverseの操作でこのような効果が得られると考えられ,次にreverseが発見された後の左右の2つの部分の要素の順序を比較するとさらにreverseが必要となり,これで最後の効果が得られる.

Time:  O(n)
Space: O(1)
class Solution(object):
    
    def reverse_array(self, arr, begin, end):
        b, e = begin, end
        while b < e:
            arr[b], arr[e] = arr[e], arr[b]
            b += 1
            e -= 1
    
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        k = k % len(nums)
        self.reverse_array(nums, len(nums) - k, len(nums) - 1)
        self.reverse_array(nums, 0, len(nums) - 1 - k)
        self.reverse_array(nums, 0, len(nums) - 1)