461. Hamming Distance (Easy)

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        res=x^y
        c=0
        for i in range(32):
            if res >>i & 1:
                c+=1
        return c
#
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        xor = x ^ y
        distance = 0
        while xor:
            # mask out the rest bits
            if xor & 1:
                distance += 1
            xor = xor >> 1
        return distance

#
class Solution:
    def hammingDistance(self, x, y):
        xor = x ^ y
        distance = 0
        while xor:
            distance += 1
            # remove the rightmost bit of '1'
            xor = xor & (xor - 1)
        return distance

462. Minimum Moves to Equal Array Elements II (Medium)

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
In one move, you can increment or decrement an element of the array by 1.
Test cases are designed so that the answer will fit in a 32-bit integer.

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        # nums[i]-mid
        nums.sort()
        mid= nums[len(nums)//2]
        return sum([abs(val-mid) for val in nums])

#O（n） use quickselect
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        n = len(nums)
        
        def partition(idx,left,right):
            pval = nums[idx]
            nums[idx],nums[right] = nums[right],nums[idx]
            store_idx  = left
            for i in range(left,right):
                if nums[i]<pval:
                    nums[store_idx],nums[i] = nums[i],nums[store_idx]
                    store_idx+=1
            
            nums[right],nums[store_idx] = nums[store_idx],nums[right]

            return store_idx
        
        def select(l,r,k):
            
            idx = random.randint(l,r)
            idx = partition(idx,l,r)
            
            if idx==k:
                return nums[k]
            elif idx<k:
                return select(idx+1,r,k)
            else:
                return select(l,idx-1,k)
        
        mid = select(0,n-1,n//2)
        res =0 
        for n in nums:
            res+=abs(n-mid)
        return res
#JAVA ANSWER good to know
public class Solution {
    public int minMoves2(int[] nums) {
        int l = 0, r = nums.length - 1, sum = 0;
        Arrays.sort(nums);
        while (l < r) {
            sum += nums[r] - nums[l];
            l++;
            r--;
        }
        return sum;
    }
}

463. Island Perimeter (Easy)

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        # find a neighor + neighbor4 but contact need to -contact number.
        visited=set()
        def nei(i,j):
            neis=[]
            for ii,jj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if ii<0 or ii>=len(grid) or jj<0 or jj>=len(grid[0]) or grid[ii][jj]==0: 
                        continue
                neis.append((ii,jj))
            return neis
        
        self.res = 0
        
        def dfs(i,j):
            if (i,j) in visited: return
            visited.add((i,j))
            self.res+=4
            neis = nei(i,j)
            self.res-=len(neis)
            for ne in neis:
                if ne not in visited:
                    dfs(*ne)
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    dfs(i,j)
                    break
        return self.res

#MY ANSWER
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        matrix = []
        ncols = len(grid[0])
        row0 = [0]*(ncols+2)
        matrix.append(row0)
        for row in grid:
            matrix.append([0]+row+[0])
        matrix.append(row0[:])
        
        m,n = len(matrix),len(matrix[0])
        res = 0

        for i in range(1,m):
            for j in range(1,n):
                if  matrix[i][j]==1 and matrix[i][j-1]==0 and matrix[i-1][j]==0:
                    res+=2
                elif matrix[i][j]==0 and matrix[i][j-1]==1 and matrix[i-1][j]==0:
                    res+=1

                elif matrix[i][j]==1 and matrix[i][j-1]==0 and matrix[i-1][j]==1:
                    res+=1
                elif matrix[i][j]==0 and matrix[i][j-1]==1 and matrix[i-1][j]==1:
                    res+=2
                
                elif matrix[i][j]==0 and matrix[i][j-1]==0 and matrix[i-1][j]==1:
                    res+=1
                elif matrix[i][j]==0 and matrix[i][j-1]==0 and matrix[i-1][j]==0:
                    res+=0
                
                elif matrix[i][j]==1 and matrix[i][j-1]==1 and matrix[i-1][j]==1:
                    res+=0
                elif matrix[i][j]==1 and matrix[i][j-1]==1 and matrix[i-1][j]==0:
                    res+=1


        return res
            

464. Can I Win (Medium)

In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.
Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= 0: return True
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False
        memo = {}

        def helper(nums, desiredTotal):
            hash = str(nums)
            if hash in memo:
                return memo[hash]
            #if nums[-1] >= desiredTotal:
            #    return True
            if desiredTotal<=0: return False
            for i in range(len(nums) - 1, -1, -1):
                if not helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
                    memo[hash] = True
                    return True
            memo[hash] = False
            return False
         

        return helper(list(range(1, maxChoosableInteger + 1)), desiredTotal)
 
 #ANSWER
 class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        total_sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2
        if total_sum < desiredTotal:
            return False
        if desiredTotal <= 0:
            return True

        self.map = {}
        self.used = [False] * (maxChoosableInteger + 1)
        return self.helper(desiredTotal)

    def helper(self, desiredTotal):
        if desiredTotal <= 0:
            return False
        key = self.format(self.used)
        if key not in self.map:
            # try every unchosen number as the next step
            for i in range(1, len(self.used)):
                if not self.used[i]:
                    self.used[i] = True
                    # check whether this leads to a win (i.e. the other player loses)
                    if not self.helper(desiredTotal - i):
                        self.map[key] = True
                        self.used[i] = False
                        return True
                    self.used[i] = False
            self.map[key] = False
        return self.map[key]

    # transfer boolean[] to an Integer
    def format(self, used):
        num = 0
        for b in used:
            num <<= 1
            if b:
                num |= 1
        return num

can not reuse integer， Force Win return True.

465. Optimal Account Balancing （Hard）

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.
Return the minimum number of transactions required to settle the debt.

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        dic = defaultdict(int)
        for a,b,val in transactions:
            dic[a]-=val
            dic[b]+=val
    
        debt = [d for d in dic.values() ]
    
        def dfs(i):
            if i==len(debt): return 0 
            if debt[i]==0: return dfs(i+1)
            r = float('inf')
            for j in range(i+1,len(debt)):
                if debt[i]*debt[j]<0:
                    #j will be total responsable for i's debt
                    debt[j]+=debt[i]
                    r = min(r,1+dfs(i+1))
                    debt[j]-=debt[i]
            return r 
        return dfs(0)

idea is tricky... person index i have debt[i] for other person j , if other person have neg sign then person s. update debt[i] with debt[j] (so person j will take full responsiblity of person i). r=min(r,1+dfs(i+1))

466. Count The Repetitions (Hard)

We define str = [s, n] as the string str which consists of the string s concatenated n times.
For example, str == ["abc", 3] =="abcabcabc".
We define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1.
For example, s1 = "abc" can be obtained from s2 = "abdbec" based on our definition by removing the bolded underlined characters.
You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].
Return the maximum integer m such that str = [str2, m] can be obtained from str1.

class Solution:
    def getMaxRepetitions(self, s1, n1, s2, n2):
        d, l1, l2, i1, i2 = {}, len(s1), len(s2), 0, 0
        tot = l1 * n1

        while i1 < tot:
            if s1[i1 % l1] == s2[i2 % l2]:
                if (i1 % l1, i2 % l2) in d:
                    prev1, prev2 = d[(i1 % l1, i2 % l2)]
                    cir1, cir2 = i1 - prev1, i2 - prev2
                    count_cir1 = (tot - i1) // cir1
                    i1 += count_cir1 * cir1
                    i2 += count_cir1 * cir2
                    if i1 >= tot: break
                else:
                    d[(i1 % l1, i2 % l2)] = (i1, i2)
                i2 += 1
            i1 += 1
        return i2 // l2 // n2

#TLE BINARY SEARCH
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # s1 acbacbacbacb s2 = abab
        l=1
        r=len(s1)*n1//len(s2)//n2+1

        def GCD(a,b):
            while b:
                a, b = b, a%b
            return a

        def s2ins1(s2,s1):
            ls2 = len(s2)
            ls1 = len(s1)
            start = 0
            for i in range(ls1):
                if s1[i] == s2[start]:
                    start+=1
                    if start==ls2:
                        break
            return start == ls2

        while l<=r:
            m = (l+r)//2
            tmp = GCD(m*n2,n1)
            #print(tmp,m*n2,n1)
            if s2ins1(s2*(m*n2//tmp) , s1*(n1//tmp)):
                # m is large:
                l = m+1
            else:
                r = m-1
        
        return l-1 

直接数出现的次数算重复不行，因为还有字母出现次序问题。。。 得找重复pattern。 答案厉害。BINARY SEARCH TLE

467. Unique Substrings in Wraparound String (Medium)

We define the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this:
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Given a string p, return the number of unique non-empty substrings of p are present in s.

def findSubstringInWraproundString(self, p):
        res = {i: 1 for i in p}
        l = 1
        for i, j in zip(p, p[1:]):
            l = l + 1 if (ord(j) - ord(i)) % 26 == 1 else 1
            res[j] = max(res[j], l)
        return sum(res.values())

#ANSWER DP 思路：若字符连续，当前可形成的substring个数+1，若不连续substring个数=1，更新count 为防止重复字符overwrite，更新时候取max。 
class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        count=[0]*26
        cur_maxlen=0
        for i in range(len(p)):
            if i>0 and (ord(p[i])-ord(p[i-1]))%26==1:
                cur_maxlen+=1
            else:
                cur_maxlen=1
            
            index=ord(p[i])-ord('a')
            count[index]=max(count[index],cur_maxlen)
        
        return sum(count)

#
class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
         
        dp = [0]*26
        cur_maxlen = 0

    
        for i,n in enumerate(s):
            if i>0 and (ord(n) - ord(s[i-1])) % 26==1:
                cur_maxlen+=1
            else:
                cur_maxlen = 1
            
            idx = ord(n)-ord('a')
            dp[idx] = max(dp[idx],cur_maxlen)
             
        return sum(dp)

DP[i] 意思是以s【i】为结尾的substring的个数。 注意取max
Each single charecter contribution is initialized to 1
if the order is continued, the contribution is increased by 1 from previous character contribution

example string zabce

Values got incremented in the following way

z -> 1
a -> 1 + 1 (or) z + 1 -> 2
b -> 1 + 1 + 1 (or) a + 1 -> 3
c -> 1 + 1 + 1 + 1 (or) b + 1 -> 4
e -> 1 (ord(j) - ord(i)) % 26 != 1 here

So the final answer is contribution from z + a + b + c + e (1 + 2 + 3 + 4 + 1 = 11)

max(res[j], l) is required to handle cases where the character is repeated.

For example in zaba, since each each unique character is assigned as key to res, the 2nd a contribution should not replace the 1st a contribution until it exceeds the 1st a contribution

468. Validate IP Address （Medium）

Given a string queryIP, return "IPv4" if IP is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.
A valid IPv4 address is an IP in the form "x1.x2.x3.x4" where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses but "192.168.01.1", while "192.168.1.00" and "192.168@1.1" are invalid IPv4 addresses.
A valid IPv6 address is an IP in the form "x1:x2:x3:x4:x5:x6:x7:x8" where:
1 <= xi.length <= 4
xi is a hexadecimal string which may contain digits, lower-case English letter ('a' to 'f') and upper-case English letters ('A' to 'F').
Leading zeros are allowed in xi.
For example, "2001:0db8:85a3:0000:0000:8a2e:0370:7334" and "2001:db8:85a3:0:0:8A2E:0370:7334" are valid IPv6 addresses, while "2001:0db8:85a3::8A2E:037j:7334" and "02001:0db8:85a3:0000:0000:8a2e:0370:7334" are invalid IPv6 addresses.

class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        
        def convert4(string):
            # in range 0~255
            # cannot leading zeros
            # number only
            if not string: return False
            if len(string)>1 and string[0]=='0': return False
            val=0
            for s in string:
                if s not in '0123456789':
                    return False
                val=val*10+int(s)
            
            #return True if success, else False
            if val>=0 and val<=255:
                return True
            return False
        
        def convert6(string):
            if not string: return False
            #length 1~4
            # hexadecial string 0~9 a~f A~F
            if len(string)>4: return False
            for s in string:
                if s not in '0123456789abcdefABCDEF':
                    return False
            return True
        
        if '.' in queryIP:
            data = queryIP.split('.')
            if len(data)==4 and all([convert4(string) for string in data]):
                return 'IPv4'        
            
        elif ':' in queryIP:
            data = queryIP.split(':')
            if len(data)==8 and all([convert6(string) for string in data]):
                return 'IPv6'
        
        return 'Neither'

只需要细心的题目

469. Convex Polygon （Medium）

You are given an array of points on the X-Y plane points where points[i] = [xi, yi]. The points form a polygon when joined sequentially.
Return true if this polygon is convex and false otherwise.
You may assume the polygon formed by given points is always a simple polygon. In other words, we ensure that exactly two edges intersect at each vertex and that edges otherwise don't intersect each other.

def isConvex(self, p: List[List[int]]) -> bool:
    def ccw(a, b, c):
        # (b-a) X (c-a)
        return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) 
    res = [ccw(p[i-2], p[i-1], p[i]) for i in range(len(p))]
    return abs(sum(res)) == sum(abs(i) for i in res)

#MY ANSWER
class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        #  x X y = ad-bc  
        #  i j k
        #  a b 0 
        #  c d 0

        vects = []
        for i in range(len(points)):
            a = points[i]
            b = points[i-1]
            vects.append([a[0]-b[0],a[1]-b[1]])
        
        aXb = []
        for i in range(len(vects)):
            a = vects[i]
            b = vects[i-1]
            aXb.append(a[0]*b[1]-a[1]*b[0])
        print(aXb)
        return all(map(lambda x:x>=0 ,aXb)) or  all(map(lambda x:x<=0 ,aXb)) 

convex...beyond my knowledge CCW算法。。。Note: |Σxi| = Σ|xi| is only true when all xi are the same sign.

470. Implement Rand10() Using Rand7() (Medium)

Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.
Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        # rand1  1~7   取1~6  奇偶决定生成左区间1~5 还是右区间6~10
        # rand2        取1~5  
        rand1=rand7()
        while rand1==7:
            rand1=rand7()
        flag = rand1%2==1
        rand2=rand7()
        while rand2>5:
            rand2=rand7()
        return 5+rand2 if flag else rand2

#ANSWER
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        n1=rand7()
        n2=rand7()
        while n1+(n2-1)*7 >40:
            n1=rand7()
            n2=rand7()
        return (n1+(n2-1)*7)%10 +1

(n2-1)乘7+n1
"(randN - 1)*N + randN" is the uniform random variable rand{N^2}.