161. One Edit Distance (Medium)

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        #
        #      ''  a  b
        #   '' 0   1  2
        #    a 1   0  1  
        #    c 2   1  1
        #    b 3   2  1
        #
        #    dp[i][j] is s[:i]  t[:j]'s editdistance
        #    dp[i][j] =   min(dp[i][j-1] ,  dp[i-1][j] ,  dp[i-1][j-1]) +1 if s[i]!=t[j]        
        m = len(s)
        n = len(t)
        
        dp = [[0]*(n+1) for _ in range(m+1)]
      
        for i in range(n+1):
            dp[0][i]=i
        for i in range(m+1):
            dp[i][0]=i
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s[i-1]!=t[j-1]:
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
                else:
                    dp[i][j] = dp[i-1][j-1]
        return dp[-1][-1]==1

 #second way of writting
 class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        
        # s->t    insert
        
        if len(t)-len(s)==1 and len(set(t))-len(set(s))<=1:
            #s insert
            # ssss sss
            # tttttttt
           
            while s and s[0]==t[0]:
                s=s[1:]
                t=t[1:]
            while s and s[-1]==t[-1]:
                s=s[:len(s)-1]
                t=t[:len(t)-1]
            if len(t)==1:
                return True
            
        elif len(s)-len(t)==1 and len(set(s))-len(set(t))<=1:
            #s del
            # sssssss
            # ttt ttt
            while t and s[0]==t[0]:
                s=s[1:]
                t=t[1:]
            while t and s[-1]==t[-1]:
                s=s[:len(s)-1]
                t=t[:len(t)-1]
            if len(s)==1:
                return True
            
            
        elif len(s)==len(t)  and len(set(s))-len(set(t))<=1:
            # replace
            while t and s[0]==t[0]:
                s=s[1:]
                t=t[1:]
            while t and s[-1]==t[-1]:
                s=s[:len(s)-1]
                t=t[:len(t)-1]
            
            if len(t)==1 and len(s)==1 and t!=s:
                return True

        return False

#MY ANSWER WAY OF WRITING
class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        #insert
        #A B D C
        #A B C
        
        if abs(len(s)-len(t))==1:
            ss = s
            tt = t
            while ss and tt and ss[0]==tt[0]:
                ss = ss[1:]
                tt = tt[1:]
            while ss and tt and ss[-1]==tt[-1]:
                ss = ss[:-1]
                tt = tt[:-1]
            if not ss:
                if tt and len(tt)==1:
                    return  True
            if not tt:
                if ss and len(ss)==1:
                    return  True
                

        #delete
        # is same as insert

        #replace
        if len(s)==len(t):
            ss = s
            tt = t
            while ss and tt and ss[0]==tt[0]:
                ss = ss[1:]
                tt = tt[1:]
            while ss and tt and ss[-1]==tt[-1]:
                ss = ss[:-1]
                tt = tt[:-1]
            if ss  and tt and len(ss)==len(tt) and len(tt)==1 and ss!=tt:
                return True         
        

        return False
        

               

用dp方法，time limit exceeded。dp是n*n的。所以用定义做。 分3种情况， insert ，del， replace。 头尾之间去除相同的，剩下长度为1 就是可以的。

162. Find Peak Element （Medium）

A peak element is an element that is strictly greater than its neighbors.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        
#         for i in range(len(nums)-1):
#             if nums[i] > nums[i+1]:
#                 return i
        
#         return len(nums)-1
        
        
        return self.search(nums,0,len(nums)-1)
    
    def search(self, nums,l,r):
        if l==r:
            return l
        
        m = (l+r)//2
        
        if nums[m] > nums[m+1]:
            return self.search(nums,l,m)
        else:
            return self.search(nums,m+1,r)

#
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:

        l = 0
        r = len(nums)-1
        while l< r:
            m = (l+r)//2
            if nums[m]>nums[m+1]:
                r=m
            else:
                l=m+1
        
        return l

一定是考binary search的，但木有思路，答案很精彩。 就是比较 m 和 m+1就搞定了。
做出来了， 但是不是标准的Binary Search， m可以和m+1比较而不越界因为 m=(l+r)//2,m+1也不会很大而越界， 要点在while l小于r， 要退出时候l==r。

163. Missing Ranges （Easy)

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        res=[]
        
        def helper(x,y):
            if y-x==2:
                # y=3 x=1
                res.append(str(x+1))
            elif y-x>2:
                res.append(str(x + 1) + '->' + str(y - 1))
            
        
        pre = lower-1
        for num in nums:
            helper(pre,num)
            pre=num
        
        helper(pre,upper+1)
            
        return res


class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:      
        if not nums: return [[lower, upper]]
        res = []
        pre  = None
        if nums[0]!=lower-1:
            nums  = [lower-1]+nums
        if nums[-1]!=upper+1:
            nums  = nums+[upper+1]

        for n in nums:
            if pre is not None and pre+1!=n:
                res.append([pre+1,n-1])
            pre = n
        return res

if else 判断太繁杂， 答案很简单，这个是个easy题目？？？ 为了统一 x 到 y之间判断， lower =lower-1，这样lower就包括进去了， upper=upper+1，这样upper就包括进去了。

164. Maximum Gap （Hard）

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        
        if not nums or len(nums)<2: return 0
        
        maxval = max(nums)
        exp=1 # 1,10,100,...
        radix=10 #base 10 system
        aux = [0]*len(nums)
        while maxval//exp>0:
            count = [0]*radix
            
            for i,n in enumerate(nums):
                count[(n//exp)%10] +=1
            
            for i,n in enumerate(count):
                if i==0: continue
                count[i] += count[i-1]
            
            for i in range(len(nums)-1,-1,-1):
                count[(nums[i]//exp)%10] -= 1
                aux[ count[(nums[i]//exp)%10] ] = nums[i]
                
            nums= aux[:]
            
            exp*=10
        
        print(nums)
        
        maxGap = 0 
        for   i  in range(len(nums)-1): 
            maxGap = max(nums[i + 1] - nums[i], maxGap)

        return maxGap

# answer way of writting
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        ## RC ##
        ## APPROACH : BUCKET SORT ##
        ## LOGIC ##
        ## 1. lets say we have number from 1 to 10 like, 1,1.1,1.2,2.4,3.5,3.7,4,....10 (not in the same order)
        ## 2. we create n - 1 buckets, why n-1 ? (b1 -> [1-2] b2-> [2-3] b3->[3-4] ...so on 9 buckets)
        ## 3. we can say size of each bucket will be (10 - 1) // 9 i.e 1 ==> (maximum - mimimum) // (length - 1)
        ## 3. Instead of storing all the elements in the buckets, we store minvalue of that bucket and maximum value of that bucket
        ## 4. Maximum Gap can be Case 1: gap between min and max in the bucket itself (or) Case 2: Gap between bucket1 max and bucket2 and so on..
        
		## TIME COMPLEXITY : O(N) ##
		## SPACE COMPLEXITY : O(N) ##
        
        if len(nums) < 2 or min(nums) == max(nums):
            return 0
        minimum, maximum = min(nums), max(nums)
        size = ( maximum - minimum )//(len(nums)-1) or 1
        buckets = [[None, None] for _ in range(( maximum - minimum )//size+1)]
        for num in nums:
            # getting the bucket number in which it falls into
            bucket = buckets[ ( num - minimum )//size ]
            bucket[0] = num if bucket[0] is None else min(bucket[0], num)
            bucket[1] = num if bucket[1] is None else max(bucket[1], num)
        buckets = [bucket for bucket in buckets if bucket[0] is not None]
        return max(buckets[i][0]-buckets[i-1][1] for i in range(1, len(buckets)))        

要求O（n）for space and time没思路。答案思路1） Radix Sort 听过，但写不出来。。。2）Buckets 这个思路很好。

知识点 Radix Sort

     def count_sort(arr,exp):
           #辅助数组用于返回
           aux = [0]*len(nums)
           #0到9是个数字的计数器
           count=[0]*10
           #计数
           for i,n in enumerate(arr):
               ind= (n//exp)%10
               count[ind]+=1
           #计算位置  count【i】 就是 i 这个位，属于的数字所在的位置
           for i in range(1,10):
               count[i] += count[i-1]
            #从后向前遍历数组
           for i in range(len(arr)-1,-1,-1):
               #找到index
               ind = (arr[i]//exp)%10
               #找到位置 因为位置从0开始所以要-1
               count[ind] -= 1
               #赋值
               aux[count[ind]] = arr[i]
           return aux 


       def Radix_Sort(arr):
           maxval=max(arr)
           exp=1
           while maxval//exp>0:
               #print('#',exp)
               arr = count_sort(arr,exp)
               exp*=10
           return arr
       
       nums = Radix_Sort(nums)

165. Compare Version Numbers （Medium）

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        while version1 or version2:
            v1=0
            v2=0
            while version1 and version1[0]!='.':
                v1 = v1*10+int(version1[0])
                version1=version1[1:]
            while version2 and version2[0]!='.':
                v2 = v2*10+int(version2[0])
                version2=version2[1:]
            
            if v1>v2: return 1
            if v1<v2: return -1
            
            version1 = version1[1:] if version1 else ''
            version2 = version2[1:] if version2 else ''
    
        return  0
        
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:

        v1=list(map(int,version1.split('.')))
        v2=list(map(int,version2.split('.')))

        while v1 or v2:
            c1 = v1.pop(0) if v1 else 0
            c2 = v2.pop(0) if v2 else 0

            if c1<c2: return -1
            if c1>c2: return 1
        
        return 0

166. Fraction to Recurring Decimal （Medium）

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        negsign = (numerator>0) ^ (denominator>0)
        numerator= abs(numerator)
        denominator=abs(denominator)
        if numerator==0: negsign=False
        
        integer = numerator//denominator
        if integer*denominator==numerator:
            return str(integer) if not negsign else  '-'+str(integer)
        res_int = str(integer)
        
        numerator -= integer*denominator
        
        def loop(res_dec,denominator_len):
            l=len(res_dec)
            if l>=2:
                for lookback in range(1,l//2+1):     
                    if lookback>=denominator_len and res_dec[l-lookback:l] == res_dec[l-2*lookback :l-lookback] :
                        return True, l-2*lookback, lookback
            return False, 0,0
        res_dec = []
        while True:
            numerator *= 10
            val =numerator//denominator
            res_dec.append(val)
            #print(res_dec)
            flag, start,length =  loop(res_dec,len(str(denominator)))
            if flag:
                l=len(res_dec)
                part1 = res_dec[:start]
                recur = res_dec[start:start+length]
                part1=''.join([str(e) for e in part1])
                recur = '('+''.join([str(e) for e in recur]) +')' if recur else ''
                decpart=part1+recur
                result= res_int+'.'+decpart if decpart else res_int
                return result if not negsign else '-'+result
            numerator=numerator-val*denominator
            if numerator==0:
                break
        
        decpart=''.join([str(e) for e in res_dec])
        result=res_int+'.'+decpart if decpart else res_int
        return result if not negsign else '-'+result

#answer way of writting
class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
       
        if not numerator: return "0";
        res=""
        if  (numerator < 0) ^ (denominator < 0):
            res += '-'
        
        numer = numerator * (-1) if numerator < 0 else numerator
            
        denom =  denominator * (-1) if denominator < 0 else denominator;
        integral = numer // denom;
        res += str(integral);
        rmd = numer % denom;
        if  rmd==0: return res
        res += '.';
        rmd *= 10
        mp=dict() 
        while rmd:
            quotient = rmd / denom
            if rmd in mp:
                #res.insert(mp[rmd], 1, '(');
                res=res[:mp[rmd]]+'('+res[mp[rmd]:]
                res += ')'
                break
            
            mp[rmd] = len(res)
            res += str(quotient);
            rmd = (rmd % denom) * 10
        
        return res;


#MY ANSWER
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        sign = (numerator>0 and denominator>0) or (numerator<0 and denominator<0)
        if numerator==0: sign = True
        numerator=abs(numerator)
        denominator = abs(denominator)
        dic = dict()
        res =  str(int(numerator//denominator))
        if numerator % denominator == 0: 
            return res if sign else '-'+res
        else:
            res+='.'
        
        numerator = (numerator%denominator)*10
        while numerator % denominator:
            val = numerator//denominator
            key = (numerator,denominator)
            if key in dic:
                res =  res[:dic[key]]+'('+res[dic[key]:]+')'
                return res if sign else '-'+res
            dic[key] = len(res)
            res+=str(val)
            numerator = (numerator%denominator)*10
          
        res+=str(numerator//denominator)
        return res if sign else '-'+res

判断recurring，lookback需要长度大于被除数。不难但细节太多，垃圾题。答案写的很优雅。用了dict去存reminder，如果重复出现reminder说明存在重复。 我的方法是之间判断数组是否循环。答案更优雅。

167. Two Sum II - Input Array Is Sorted （Easy）

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        length = len(numbers)
        l=0
        r=length-1
        while l<r:
            if numbers[l]+numbers[r]==target:
                return [l+1,r+1]
            elif  numbers[l]+numbers[r]<target:
                l+=1
            else:
                r-=1

sorterd 直接上two pointer了。

168. Excel Sheet Column Title （Easy）

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        # 26 进制数
        
      
        
        
        chars = 'ZABCDEFGHIJKLMNOPQRSTUVWXY'
        dic = dict()
        for i in range(26):
            dic[i]=chars[i]
        
        res = []
        while columnNumber:
            
            reminder = columnNumber%26
            #print(columnNumber,reminder)
            res.append(dic[reminder])
            columnNumber = columnNumber //26
            if reminder==0:
                columnNumber-=1
             
        return ''.join(res[::-1])
             

就是个26进制数转换问题，这个也能卡。。。 卡在的点为 if reminder==0: columnNumber-=1
如果没有余数恰巧除干净了，说明需要上一位减去一。

169. Majority Element （Easy）

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        maj = nums[0]
        c = 0
        for n in nums:
            if n==maj:
                c+=1
            else:
                c-=1
            
            if c==0:
                maj=n
                c=1
       
        
        return  maj

这个是个经典算法 摩尔投票算法，需要记住。 思路：遍历过程中不同元素之间两两抵消，由于一个数组中，出现次数超过n/2最多只有一个，那么遍历结束时，未被抵消掉的即是出现次数超过n/2的元素。在数组中maj元素出现一次，count就自加一次，如果出现了和maj不同的元素，说明maj可被抵消一次，count就自减一次，如果count减为0，也就说明maj元素已经被抵消完了， 更新maj。
如果找超过1/3元素。 最多只有两个元素符合要求。需要设置maj1和count1、maj2和count2来分别记录这两个元素的抵消情况。如果出现了和maj1或maj2相同的元素，那么对应的count1和count2就自加1，如果元素与maj1和maj2都不相同，那么count1和count2就都应当自减1，如果maj1或maj2抵消掉后，就应当更新对应的maj1或maj2。NOTE 注意： 初始值 maj1和maj2、count1和count2相同，所以在判断二者与当前值是否相同时应当使用if else语句，而不是分开的两个if。此外，考虑到可能出现maj1和maj2都同时出现抵消掉的情况，所以也不能同时进行count自减和判断count1或count2是否为0，如果同时判断的话，那么maj1和maj2又会都同时成为当前元素了。

maj1=nums[0]
maj2=nums[0]
c1=0
c2=0

for n in nums:
   if n==maj1:
       c1+=1
   elif n==maj2:
       c2+=1
   elif c1==0:
       c1=1
       maj1=n
   elif c2==0:
       c2=1
       maj2=n
   else:
       c1-=1
       c2-=1
#recalce make sure        
c1=c2=0
for n in nums:
   if n==maj1:c1+=1
   if n==maj2:c2+=1
res=[]
if c1>len(nums)//3:
   res.append(maj1)
if c2>len(nums//3) and maj1!=maj2:
   res.append(maj2)
return res

170. Two Sum III - Data structure design (Easy)

class TwoSum:

    def __init__(self):
        self.stack = []
        

    def add(self, number: int) -> None:
        self.stack.append(number)
        

    def find(self, value: int) -> bool:
        dic= dict()
        for i,n in enumerate(self.stack):
            if value-n in dic:
                return True
            dic[n]=i
        return False
        


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)

class TwoSum:

    def __init__(self):
        self.dic = collections.defaultdict(list)
        self.c = 0
        

    def add(self, number: int) -> None:
        self.dic[number].append(self.c)
        self.c+=1
        

    def find(self, value: int) -> bool:
        res = False
        for key in self.dic.keys():
            if value-key == key:
                res = res or len(self.dic[key])>1   
            else:
                if value-key in self.dic:
                    res = res or True
        
        return res