摘要：此篇文章最先發布在我的博客上記錄上的一些題，基本上是上的題，其他的我會標注出來，用的語言目前是寫的代碼很庸俗，請大神不要見笑題目羅馬數字的規則如下羅馬數字共有個，即和。在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字減小數字。

此篇文章最先發布在我的博客mbinary上
? ?
記錄OJ上的一些題，基本上是leetcode上的題，其他的我會標注出來，用的語言目前是python,寫的代碼很庸俗，請大神不要見笑(>_<)

# 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.
羅馬數字的規則如下：

羅馬數字共有7個，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、?（50）、?（100）、?（500）和?（1000）。按照下述的規則可以表示任意正整數。需要注意的是羅馬數字中沒有“0”，與進位制無關。一般認為羅馬數字只用來記數，而不作演算。


重復數次：一個羅馬數字重復幾次，就表示這個數的幾倍。

右加左減：

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



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

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

?? ??思路
這道題還是蠻有意思的，同樣用遞歸的方法，在了解拼寫規則后，要從數值范圍來判斷羅馬數字的結構，即取哪個字母？哪種組合？左或是右？
孿生題是Roman to Interger比較簡單
??代碼

#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.

? ???思路
這道題可以用遞歸函數來解決，注意到，eg從“a” 中判斷是否有“aa” ，如果直接遞歸是返回true的，這不對，要就是說在一次判斷中，已判斷過的字母不能再判斷，所以參數應該還有一個board，記錄當前的字母狀態，考慮到python是用的引用，傳遞參數時沒有復制，我又不想額外再去復制board，就在函數中記下當前位置的字母，在函數調用結束再改回來的。哈哈！
??代碼

#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]
]

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

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

#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 

? ? 代碼 (頭尾雙指針，過了，注意判重的方法，前一個用的if，后面在找到答案時用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.      
????思路
由于只有非負數，不能成功的點一定是當前位置為0，所以可以將列表中所以的0找出來，并記下位置（下標），然后從這個位置開始往前搜索，若存在能跳過此位置的點，則能跳過，去除這個0，一直跳過所有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
??思路
這道題顯然不能直接計算，可以用歐拉定理
對任意正整數a,正整數m,(a,m) = 1,?(m) 為比m小的與m互質的(注意不一定是質數)正整數的個數，
則 a?(m)  ≡ 1 (mod m) 。
再利用性質： a ≡ b (mod m) ,c ≡ d (mod m) ,則ac ≡ bd (mod m)  
證明就不寫了，打數學符號太累了（T^T）,給個傳送門吧--> 歐拉定理)
??代碼
    #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