python練習(五)

Can Place Flowers

題

構想

解答

回答

Best Time to Buy and Sell Stock II

題

構想

解答

回答

Base 7

題

構想

解答

回答

Array Partition I

題

構想

解答

回答

Find All Anagrams in a String

題

構想

解答

回答

書き換え

注意して、答えはただ他人が書いたコードを代表して、正しいですが、テスト(例えばタイムアウト)に合格するとは限らない.列挙するのはただそれらが独特なところを持っているだけで、大部分は確かに私より良いですが.

Can Place Flowers

タイトル

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

構想

1サイクルで解決できるように見える問題は、高速アルゴリズムがあるでしょう.

に答える

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        f=0
        for i in range(len(flowerbed)-1):
            if flowerbed[i] == 0:
                if f == 0 and flowerbed[i+1] == 0:
                    n -=1
                    f =1
                else :
                    f=0
            else:
                f = 1
            if n <= 0:
                return True
        if flowerbed[-1] == 0 and f == 0:
            n -=1
        if n <= 0:
            return True
        else:
            return False

76%で、あまり最適化の余地はないと推定されています

答え

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        for i, x in enumerate(A):
            if (not x and (i == 0 or A[i-1] == 0) 
                and (i == len(A)-1 or A[i+1] == 0)):
                N -= 1
                A[i] = 1
    return N <= 0

f****k、私ははっきりと覚えているのはこの位置で保存するのではありませんて、下の辺の内容はまた双
私は変数fのreturn N<=0を使うべきではないことが好きではありませんか?理解できるが、こんなふうに使えるとは思わなかった.

Best Time to Buy and Sell Stock II

タイトル

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

構想

難しいように見えますが、株を売った後の次の購入ポイントでは、ああ、前のピークを積み重ねるだけでいいのではないでしょうか.[3,5,4,8]のような列では、購入ポイントが確認できません.うーん、現在の価格が前の販売価格より小さいだけでいいですか.

に答える

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        psum = 0
        minprice = prices[0]
        maxprice = 0
        for price in prices:
            if price < maxprice:
                psum += maxprice - minprice
                minprice = maxprice = price
            elif price > maxprice:
                maxprice = price
        if prices[-1] > minprice:
            psum += prices[-1] - minprice
        return psum      

本来、非空判定を加える必要はありませんが、テスト時に判定の末尾がないことに気づき、いくつかの問題が発生したため、末尾検出を追加しましたが、末尾検出の存在により、空表が入ってくるとエラーになるので、また上空表検出を追加します

答え

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_prof = 0
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                max_prof += prices[i+1] - prices[i]
        return max_prof

...どうしてそんなに複雑なことを考えているの?まるでzzのように

Base 7

タイトル

Given an integer, return its base 7 string representation.
Example 1: Input: 100 Output: “202” Example 2: Input: -7 Output: “-10” Note: The input will be in range of [-1e7, 1e7].

構想

10進数から7進数に移行します.

に答える

直接join(l[:-1])はTypeError:sequence item 0:expected string,int foundを誤報するが、l内はstrばかりではないので少しの操作処理が可能である」と述べた.join(map(str,l[:-1]))return 0をreturn‘0’に処理するのを忘れた

class Solution(object):
    def convertToBase7(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num > 0:
            f = 0
        elif num == 0:
            return '0'
        else :
            num = -num
            f = 1
        l=[]
        while num > 0:
            l.append(num%7)
            num = num/7
        return ('-' if f else '') + ''.join(map(str,l[::-1]))            

答え

class Solution(object):
    def convertToBase7(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num<0:
            return "-"+self.convertToBase7(-num)

        if num<7:
            return str(num)

        return self.convertToBase7(num//7)+str(num%7)

再帰の方法、とても騒々しくて、すごいです

def convertTo7(self, num):
    if num == 0: return '0'
    n, res = abs(num), ''
    while n:
      res = str(n % 7) + res
      n //= 7
    return res if num > 0 else '-' + res

テーブルではなく文字列を直接使用します.素敵に見える

Array Partition I

タイトル

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1: Input: [1,4,3,2]
Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

構想

長い間理解してやっと大体理解して、異なる1対1対に分けて、最大の対数を求めますか?試してみると、いいえ、テーマさえ分からないので毛糸を作ってみましょう.ペアごとにmin(a,b)を計算し、すべての最小値を加算して、最大の和がほしいです.つまり、最大値を削除し、現在の最大値を取得し、最大値を削除し、現在の最大値を取得し、listをソートして1、3、5、7...ビットを繰り返すだけでいいのです

に答える

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])

私も1行書くことができます(ただテーマが簡単すぎるからでしょう)python機能が強いとしか言えません

答え

私と同じように、もっと良いことはありませんハハ

Find All Anagrams in a String

タイトル

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

構想

問題は確かに分かりやすいです.どうすればいいですか.そして、提供されたpの長さは小さくありませんが、pythonはinがありますか.

に答える

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        p = sorted(p)
        l=[]
        for i in range(len(s)-len(p)+1):
            if sorted(''.join(s[i:i+len(p)])) == p:
                l.append(i)
        return l

自分の考えにほれぼれしていたのに、テストの時にタイムアウトして1万個も与えられたように見えたaという入力はタイヤを転がすほうがいいようだが、タイヤを転がすのは書きにくい.
位置エラー、重複エラーなど、さまざまなエラー

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        p = sorted(p)
        l=[]
        x=y=-1
        pl =len(p)
        for i in range(len(s)):
            if i < x:      
                continue
            elif i == x:
                if s[i] == s[x-pl]:
                    if x-pl+1 not in l:
                        l.append(x-pl+1)
                    x=i+1
                    y=x
                elif s[i] in p:
                    y=i+1
                elif i > len(s)-len(p):
                    break
            if sorted(''.join(s[i:i+pl])) == p :
                if i not in l:
                    l.append(i)
                if x < i:
                    x=i+pl
            if i == y:
                if sorted(''.join(s[i-pl+1:i+1])) == p:
                    if i-pl+1 not in l:
                        l.append(i-pl+1)
                    x=i+1
        return sorted(l)

半日変更したが,またダブルタイムアウトになった
思いつかず、

答え

def findAnagrams(self, s, p):
    """
    :type s: str
    :type p: str
    :rtype: List[int]
    """
    d = defaultdict(int)
    ns, np = len(s), len(p)
    ans = []

    for c in p: d[c] -= 1

    for i in xrange(ns):
        if i < np:
            d[s[i]] += 1
            if not d[s[i]]: del d[s[i]]

        else:
            if not d: ans.append(i-np)

            d[s[i-np]] -= 1
            if not d[s[i-np]] : del d[s[i-np]]

            d[s[i]] += 1
            if not d[s[i]]: del d[s[i]]
    if not d: ans.append(i-np+1)

    return ans

defaultdict(int)は、デフォルトの初期値がカッコ内の量の辞書を生成します.私はまだ辞書をあまり使ったことがありません.辞書について...辞書はif判断を直接行うことができます.key値はp内の各文字で、value値は出現回数によって決定され、対応する負数です.次に文字列sの値を少しずつ入力し、対応value値が0の場合、対応keyを削除します.len(p)が満たされた場合、dが空であるか否か(pと同じ値である場合、dが空であるべき)を判断し、空である場合、対応するi値を解答表に記入する.その後、ウィンドウがスライドし始め(つまりタイヤを転がす......)、頭の値を外し、最後の値(キュー?)を加えます.そして比較を繰り返し、移動します.

   from collections import Counter

    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        pCounter = Counter(p)
        sCounter = Counter(s[:len(p)-1])
        for i in range(len(p)-1,len(s)):
            sCounter[s[i]] += 1   # include a new char in the window
            if sCounter == pCounter:    # This step is O(1), since there are at most 26 English letters 
                res.append(i-len(p)+1)   # append the starting index
            sCounter[s[i-len(p)+1]] -= 1   # decrease the count of oldest char in the window
            if sCounter[s[i-len(p)+1]] == 0:
                del sCounter[s[i-len(p)+1]]   # remove the count if it is 0
        return res

Counter(p)を使って、前の方法のdに似ていますが、最初の方法ほど巧みではありません.

書き換える

うーん、この方法では逆に私の前の論理を再現することはできません.そして、前にimportの一言も必要ありません.

from collections import defaultdict
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        d = defaultdict(int)
        for i in p: 
            d[i] -= 1
        l=[]
        pl =len(p)
        for i in range(len(s)):
            if i < pl:
                d[s[i]] += 1
                if not d[s[i]]:
                    del d[s[i]]
            else:
                if not d:
                    l.append(i)
                d[s[i]] += 1
                if not d[s[i]]:
                    del d[s[i]]
                d[s[i-pl]] -= 1
                if not d[s[i-pl]]:
                    del d[s[i-pl]]
        if not d:
            l.append(len(s)-pl)
        return l