LeetCode — (1)

要約:
Nim Game、WordPattern、Move zeros、First Bad version、Ugly Numberの5つのアルゴリズムのpython実装.
　
一ヶ月余り更新されていないのは、調子がずっと悪いせいか、何度か開いたのに何から書いたのか分からない.この1ヶ月余りをまとめます:いくつかのアルゴリズムを見ました;ハドopに触れたのはまだできないが;linuxが使えます.HTMLを見て、JS;二つの省賞を取ったが、その中の一つは本当にずっと夢だった.チームに参加しても自分の夢に一歩近づくことができます.自分の好きなところに行ったことがあります.食べたり遊んだりします.自分の好きなことをいくつもしました.多くの人を助けた.今突然大学院受験か仕事か迷っています......実はブログを書くのが本当に素晴らしいと思って、それでは今日からよく書き続けました.何を書くか分からないので、LeetCodeの中で自分が最近見たアルゴリズムを書きましょう~もちろん、一番簡単なことから始めます:
1.Nim Game
　　You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
　　For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
タイトル:
あなたと友达はnimゲームをしています:交代で石の山の中から1-3粒行って、最後の石の勝を取って、その中で、あなたとあなたの相手は毎回最高の策略を見つけることができます(これはあの宝石のゲームと似ていますか).解決すべき問題は、石の山の個数nを与えて、あなたの勝負(Falseに負けて、Trueに勝って)を判断して、その中で、ゲームはあなたから始めます.
分析:
毎回最良の戦略を見つけることができるので、nが[1,3]の場合、あなたは必ず勝つことができます.nが4のとき、あなたが初めていくつかの石を取っても、あなたの友达が取った石の数は[1,3]で、あなたはきっと負けます.同じように、nが[5,7]のとき、あなたはきっと相応の石を取ってnを4に変換して、それではあなたはきっと勝つことができます;n=8のとき、初めていくら取っても、相手に残した石の数は[5,7]で、あなたは必ず負けます....このように、nが4の倍数になると、あなたは必ず負けます.
python実装:
C、C++を習ったことがありますが、pyhtonを使いたいです.コードは次のとおりです.

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

 
2. wordpattern
Given a  pattern  and a string  str , find if  str  follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in  pattern  and a non-empty word in  str .
Examples:

pattern =  "abba" , str =  "dog cat cat dog"  should return true.

pattern =  "abba" , str =  "dog cat cat fish"  should return false.

pattern =  "aaaa" , str =  "dog cat cat dog"  should return false.

pattern =  "abba" , str =  "dog dog dog dog"  should return false. 

タイトル:
簡単な理解は、パターン(pattern)とstrのセットを与え、文字列がパターンと一致しているかどうかを確認することです.モードは小文字のみで構成され、文字列は単一のスペース文字で区切られ、文字列の各単語は小文字で構成されていることに注意してください.パターンと文字列の前後に余分なスペースは含まれません.パターン内の各アルファベットは、1つの文字列の少なくとも1の単語に一致する必要があります.
pythonコード:

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        words = str.split()
        if len(pattern) == len(words):
            return len(set(zip(pattern,words))) == len(set(pattern)) == len(set(words))
        else:
            return False

3.Move Zeros
　　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.

タイトル:
1つの配列について、1つの関数を作成して、すべての配列の0を配列の末尾に配置し、他の非0配列の相対位置を維持し、新しい配列を確立しないことを保証し、演算量をできるだけ減らす.
pythonコード:

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count = len(nums)
        p = 0
        for i in range(0,count):
            if nums[i] != 0:
                nums[p] = nums[i]
                p = p + 1
        for j in range(p,count):
            nums[j] = 0

4. First bad version
　　You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have  n  versions  [1, 2, ..., n]  and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API  bool isBadVersion(version)  which will return whether  version  is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
タイトル:
最初の破損したバージョンが整列したバージョンで見つかり、最初の破損したバージョン以降のバージョンが破損していると理解できます.
分析:
検索、前にCで似たようなプログラムを作成し、二分法を選択します.
pythonコード:

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left,right = 1,n
        while(left <= right):
            mid = (left + right) / 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

5. Ugly number
　　Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include  2, 3, 5 . For example,  6, 8  are ugly while  14  is not ugly since it includes another prime factor  7 .
Note that  1  is typically treated as an ugly number.
タイトル:
プログラムを作成して、1つの数が醜いかどうかを判断します.このうち,ブス数とは因子2,3,5のみを含む数であり,1が最初のブス数と見なされる.
分析:
2,3,5でしか除算できない数は,2,3,5で除算された後が1であり,これにより実現可能となる.まず思いついたのはCの中の質数を判断するプログラムで、以下の通りです.

#include
#include

void main(void)
{
    int n,i;
    printf("please input a number:
");
    scanf("%d",&n);

    for(i = 2;i < n && n % i;i++)
        ;
    if (i >= n)
        printf("  ");
    else
        printf("   ");
    getch();
}

素数は1とそれ自体でしか割り切れない数であり,もちろん上記の手順とは一定の差がある.
python実装:

class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """        
        while(num >= 2 and num % 2 == 0):
            num /= 2;
        while(num >= 3 and num % 3 == 0):
            num /= 3;
        while(num >= 5 and num % 5 == 0):
            num /= 5;
        if(num == 1):
            return True
        else:
            return False

 
これが私がここ数日見た5つのアルゴリズムの実現であり,もちろん各種バージョンを修正してもここでは後述しない.アルゴリズムがよりよく実現される友达には教えてほしい.