摘要：此篇文章最先發(fā)布在我的博客上記錄上的一些題，基本上是上的題，其他的我會(huì)標(biāo)注出來(lái)，用的語(yǔ)言目前是寫(xiě)的代碼很庸俗，請(qǐng)大神不要見(jiàn)笑題目羅馬數(shù)字的規(guī)則如下羅馬數(shù)字共有個(gè)，即和。在較大的羅馬數(shù)字的左邊記上較小的羅馬數(shù)字，表示大數(shù)字減小數(shù)字。

此篇文章最先發(fā)布在我的博客mbinary上
? ?
記錄OJ上的一些題，基本上是leetcode上的題，其他的我會(huì)標(biāo)注出來(lái)，用的語(yǔ)言目前是python,寫(xiě)的代碼很庸俗，請(qǐng)大神不要見(jiàn)笑(>_<)

# 2017-8-20

Integer to Roman

??題目

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
羅馬數(shù)字的規(guī)則如下：

羅馬數(shù)字共有7個(gè)，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、?（50）、?（100）、?（500）和?（1000）。按照下述的規(guī)則可以表示任意正整數(shù)。需要注意的是羅馬數(shù)字中沒(méi)有“0”，與進(jìn)位制無(wú)關(guān)。一般認(rèn)為羅馬數(shù)字只用來(lái)記數(shù)，而不作演算。


重復(fù)數(shù)次：一個(gè)羅馬數(shù)字重復(fù)幾次，就表示這個(gè)數(shù)的幾倍。

右加左減：

在較大的羅馬數(shù)字的右邊記上較小的羅馬數(shù)字，表示大數(shù)字加小數(shù)字。
在較大的羅馬數(shù)字的左邊記上較小的羅馬數(shù)字，表示大數(shù)字減小數(shù)字。
左減的數(shù)字有限制，僅限于I、X、C。比如45不可以寫(xiě)成VL，只能是XLV
左減時(shí)不可跨越一個(gè)位值。比如，99不可以用IC（ 100-1）表示，而是用XCIX（[100-10]+[10-1]）表示。（等同于阿拉伯?dāng)?shù)字每位數(shù)字分別表示。）
左減數(shù)字必須為一位，比如8寫(xiě)成VIII，而非IIX。
右加數(shù)字不可連續(xù)超過(guò)三位，比如14寫(xiě)成XIV，而非XIIII。（見(jiàn)下方“數(shù)碼限制”一項(xiàng)。）



加線乘千：
在羅馬數(shù)字的上方加上一條橫線或者加上下標(biāo)的?，表示將這個(gè)數(shù)乘以1000，即是原數(shù)的1000倍。同理，如果上方有兩條橫線，即是原數(shù)的1000000（ {displaystyle 1000^{2}} 1000^{{2}}）倍。

數(shù)碼限制：
同一數(shù)碼最多只能連續(xù)出現(xiàn)三次，如40不可表示為XXXX，而要表示為XL。例外：由于IV是古羅馬神話主神朱庇特（即IVPITER，古羅馬字母里沒(méi)有J和U）的首字，因此有時(shí)用IIII代替IV。

?? ??思路
這道題還是蠻有意思的，同樣用遞歸的方法，在了解拼寫(xiě)規(guī)則后，要從數(shù)值范圍來(lái)判斷羅馬數(shù)字的結(jié)構(gòu)，即取哪個(gè)字母？哪種組合？左或是右？
孿生題是Roman to Interger比較簡(jiǎn)單
??代碼

#python
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        dic = {0:"",1:"I",5:"V",10:"X",50:"L",100:"C",500:"D",1000:"M"}
        ks = [1,5,10,50,100,500,1000]
        
        def convert(num):
            if num in dic.keys():
                return dic[num]
            if num > 1000:
                n = int(num/1000)
                num -= n * 1000
                return  "M"*n + convert(num)
            n = 1000
            for i in ks:
                if i > num :
                    n = i
                    break
            exp = 1
            flag = False
            while exp <= n:   # judge if n is 10 exp k
                if exp == n:
                    flag = True
                    break
                exp *= 10
            if flag:
                small = n / 10
                if num >= 9 * small:
                    return dic[small] + dic[n] + convert(small -(n-num)) 
                else:
                    return dic[n/2] + convert(num - n/2)
            else:
                small = n / 5
                if n - small <= num :
                    return dic[small] + dic[n] + convert(small - (n-num))
                else:
                    n2 = int(num / small)
                    num -= n2 * small
                    return dic[small] * n2 + convert(num)
        return convert(num)             

word search

??題目

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

? ???思路
這道題可以用遞歸函數(shù)來(lái)解決，注意到，eg從“a” 中判斷是否有“aa” ，如果直接遞歸是返回true的，這不對(duì)，要就是說(shuō)在一次判斷中，已判斷過(guò)的字母不能再判斷，所以參數(shù)應(yīng)該還有一個(gè)board，記錄當(dāng)前的字母狀態(tài)，考慮到python是用的引用，傳遞參數(shù)時(shí)沒(méi)有復(fù)制，我又不想額外再去復(fù)制board，就在函數(shù)中記下當(dāng)前位置的字母，在函數(shù)調(diào)用結(jié)束再改回來(lái)的。哈哈！
??代碼

#python
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        row = len(board)
        col = len(board[0])
        num = len(word)
        def find(r,c,n):
            if n == num-1 and board[r][c] == word[n]:
                return True
            if board[r][c] != word[n] or n == num-1:
                return  False
            tmp = board[r][c]    #save  the  val
            board[r][c] = 0
            if r < row-1 and find(r+1,c,n+1):
                return True
            if r > 0 and find(r-1,c,n+1):
                return True
            if c  0 and find(r,c-1,n+1):
                return True
            board[r][c] = tmp
            return False
        for i in range(row):
            for j in range(col):
                if find(i,j,0):
                    return True
        return False

# 2017-8-19

3 sum

??題目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

????思路
最開(kāi)始我想的就直接3重循環(huán)，再加判重的循環(huán)，暴力求解，當(dāng)然超時(shí)了，要高于O(n3)。后來(lái)想到可以將正負(fù)數(shù)，0，分成三組來(lái)組合，然而最后兩個(gè)數(shù)據(jù)過(guò)不了，在網(wǎng)上搜了一下，可以固定一個(gè)數(shù)，頭尾雙指針來(lái)移動(dòng)，這是O(n2)。哎，折騰了一晚上，我好菜啊。 這是前幾次的結(jié)果[站外圖片上傳中……(1)]

? ???代碼 (分成正負(fù)0三組，寫(xiě)了很多判斷語(yǔ)句，唉，庸俗的代碼。 )

#python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        rst = []
        zero = []   #zeros
        neg = []    #negative
        pos = []    #positive
        for i in (nums):
            if i < 0:
                neg.append(i)
            elif i > 0:
                pos.append(i)
            else:
                zero.append(i)
        if len(zero) > 2:
            rst.append([0,0,0])
        if neg == []  or  pos == []:
            return rst
        if zero != []:
            if len(neg) > len(pos):
                for i in pos:
                    if -i in neg:
                        rst.append([-i,0,i])
            else:
                for i in neg:
                    if -i in pos:
                        rst.append([i,0,-i])
        pos.sort()
        neg.sort()
        if len(pos) == 1 and len(neg) == 1:
            return rst
        elif len(pos) == 1 :
            tmp = len(neg) - 1
            while tmp > 0:
                sum = neg[tmp] + neg[tmp-1]
                if sum == - pos[0]:
                    rst.append([neg[tmp-1],neg[tmp],pos[0]])
                    break
                elif sum < - pos[0]:
                    break
                tmp -= 1
        elif len(neg) == 1:
            tmp = 0
            while tmp < len(pos) - 1 :
                sum = pos[tmp] + pos[tmp+1]
                if sum == - neg[0]:
                    rst.append([neg[0],pos[tmp],pos[tmp+1]])
                    break
                elif sum > - neg[0]:
                    break
                tmp -= 1
        sameI = []     #avoid test several same num
        for i in range(len(pos)-1):
            if i in sameI:
                continue
            sameI.append(i)
            sameJ=[]
            for j in range(i+1,len(pos)):
                if j in sameJ:
                    continue
                sameJ.append(j)
                sum = pos[i] + pos[j]
                for k in neg:
                    if   sum > -k:
                        break
                    elif sum == -k:
                        rst.append([k,pos[i],pos[j]])
        sameI = []
        for i in range(len(neg)-1):
            if i in sameI:
                continue
            sameI.append(i)
            sameJ=[]
            for j in range(i+1,len(neg)):
                if j in sameJ:
                    continue
                sameJ.append(j)
                sum = neg[i] + neg[j]
                for k in pos:
                    if   sum > -k:
                        break
                    elif sum == -k:
                        rst.append([neg[i],neg[j],k])
        fnl = []   
        for i in rst:
            if i not in fnl:
                fnl.append(i)
        return fnl 

? ? 代碼 (頭尾雙指針，過(guò)了，注意判重的方法，前一個(gè)用的if，后面在找到答案時(shí)用while)

#python
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst=[]
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            head = i+1
            tail = len(nums) - 1
            while head < tail:
                if nums[i] + nums[head] + nums[tail]  == 0:
                    rst.append([nums[i],nums[head],nums[tail]])
                    head += 1
                    tail -= 1
                    while head< tail and nums[head] == nums[head -1]:
            head = i+1
            tail = len(nums) - 1
            while head < tail:
                if nums[i] + nums[head] + nums[tail]  == 0:
                    rst.append([nums[i],nums[head],nums[tail]])
                    head += 1
                    tail -= 1
                    while head< tail and nums[head] == nums[head -1]:
                        head += 1
                    while head
2017-8-17

jump game
??題目    


Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.  
For example:

A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.      
????思路
由于只有非負(fù)數(shù)，不能成功的點(diǎn)一定是當(dāng)前位置為0，所以可以將列表中所以的0找出來(lái)，并記下位置（下標(biāo)），然后從這個(gè)位置開(kāi)始往前搜索，若存在能跳過(guò)此位置的點(diǎn)，則能跳過(guò)，去除這個(gè)0，一直跳過(guò)所有0
????代碼
#python
    class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        if len(nums) == 1:
            return True
        zeros = []
        for i,j in enumerate(nums):
            if j == 0:
                zeros.append(i)
        while zeros != []:
            i = zeros[0]
            tmp = i - 1
            flag = 0
            while tmp >= 0:
                if nums[tmp] > i-tmp  or nums[tmp]+tmp+1 >=len(nums):
                    flag = 1
                    break
                tmp -= 1
            if flag == 0 :
                return False
            del zeros[0]
            
        return True


super pow
??題目

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
 a = 2

b = [3]
 Result: 8
Example2:
a = 2
b = [1,0]
Result: 1024
??思路
這道題顯然不能直接計(jì)算，可以用歐拉定理
對(duì)任意正整數(shù)a,正整數(shù)m,(a,m) = 1,?(m) 為比m小的與m互質(zhì)的(注意不一定是質(zhì)數(shù))正整數(shù)的個(gè)數(shù)，
則 a?(m)  ≡ 1 (mod m) 。
再利用性質(zhì)： a ≡ b (mod m) ,c ≡ d (mod m) ,則ac ≡ bd (mod m)  
證明就不寫(xiě)了，打數(shù)學(xué)符號(hào)太累了（T^T）,給個(gè)傳送門吧--> 歐拉定理)
??代碼
    #python
    class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        m = 1337
        if a % m == 0:
            return 0
        sum = 0
        for i in b:
            sum = 10 * sum + i    
        phi = 0
        for i in range(1,m):
            if (i % 7 != 0) and (i % 191 != 0):
                phi += 1
        sum = sum % phi
        return (a**sum) % 1337
        # if m a prime num ,use the small law of Fermat
        # else use the law of Euler