191. Number of 1 Bits (Easy)

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0 
        for _ in range(32):
            lastbit = n & 1
            n = n >>1
            res += 1&lastbit
        return res

192. Word Frequency (Medium) BASH

Write a bash script to calculate the frequency of each word in a text file words.txt.

for word in $(cat words.txt);   do echo $word;  done | sort | uniq -c | sort -r | awk '{ print $2 " "$1}'

Just ignore ....

193. Valid Phone Numbers (Easy) BASH

Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers.

grep -e '^[0-9]\{3\}-[0-9]\{3\}-[0-9]\{4\}$' -e '^([0-9]\{3\}) [0-9]\{3\}-[0-9]\{4\}$' file.txt

Just ignore ....

194. Transpose File (Medium) BASH

Given a text file file.txt, transpose its content.

cat file.txt | awk '{for(i=0;++i<=NF;)a[i]=a[i]?a[i] FS $i:$i}END{for(i=0;i++<NF;)print a[i]}'

Just ignore ....

195. Tenth Line (Easy) BASH

Given a text file file.txt, print just the 10th line of the file.

sed -n "10p" file.txt

Just ignore ....

196. Delete Duplicate Emails (Easy) SQL

DELETE p1 FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email AND p1.Id > p2.Id

197. Rising Temperature (Easy) SQL

select w1.id as Id from Weather w1 left join Weather w2 on datediff(w1.RecordDate,w2.RecordDate)=1 where w2.Temperature<w1.Temperature

# answer way of writting
SELECT
    weather.id AS 'Id'
FROM
    weather
        JOIN
    weather w ON DATEDIFF(weather.recordDate, w.recordDate) = 1
        AND weather.Temperature > w.Temperature
;

198. House Robber (Medium)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] = tthe max amount can rob at house i
        # dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        # dp[0] = nums[0]
        # dp[1] = max(nums[0],nums[1])
        if not nums:return 0
        if len(nums)==1: return nums[0]
        if len(nums)==2: return max(nums)
        dp = [float('-inf')]*len(nums)
        dp[0]=nums[0]
        dp[1]=max(nums[:2])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        return dp[-1]

199. Binary Tree Right Side View (Medium)

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return root
        queue = [root]
        res = []
        
        while queue:
            level =[]
            l=len(queue)
            for i in range(l):
                cur = queue.pop(0)
                level.append(cur.val)
                if cur.right:
                    queue.append(cur.right)
                if cur.left:
                    queue.append(cur.left)
            res.append(level[0])
        
        return res

level order tresversal.

200. Number of Islands (Medium)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        
        def dfs(grid,i,j):
            m=len(grid)
            n=len(grid[0])
            if i<0 or j<0 or i>=m or j>=n: return 
            if grid[i][j]=='1':
                grid[i][j]='#'
                dfs(grid,i+1,j)
                dfs(grid,i-1,j)
                dfs(grid,i,j+1)
                dfs(grid,i,j-1)
        r=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    dfs(grid,i,j)
                    r+=1
        
        return r

#UNION FIND
class Solution:
    class UnionFind:
        def __init__(self,grid):
            self.count=0
            self.m=len(grid)
            self.n=len(grid[0])
            self.parent = [None]*(self.m*self.n)
            self.rank = [0]*(self.m*self.n)
            for i in range(self.m):
                for j in range(self.n):
                    if grid[i][j]=='1':
                        self.parent[i*self.n+j]=i*self.n+j
                        self.count+=1
        def find(self,i):
            if self.parent[i]!=i:
                self.parent[i]=self.find(self.parent[i])
            return self.parent[i]
        
        def union(self,x,y):
            rootx=self.find(x)
            rooty=self.find(y)
            if rootx!=rooty:
                if self.rank[rootx]>self.rank[rooty]:
                    self.parent[rooty]=rootx
                elif self.rank[rootx]<self.rank[rooty]:
                    self.parent[rootx]=rooty
                else:
                    self.parent[rooty]=rootx
                    self.rank[rootx]+=1
                
                self.count-=1
        
        def getCount(self):
            return self.count
    
    def numIslands(self, grid: List[List[str]]) -> int:
        nr=len(grid)
        nc=len(grid[0])
        uf = self.UnionFind(grid)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=='1':
                    grid[r][c]='0'
                    if (r-1>=0 and grid[r-1][c]=='1'):
                        uf.union(r*nc+c,(r-1)*nc+c)
                    if (r + 1 < nr and grid[r+1][c] == '1'):
                        uf.union(r * nc + c, (r+1) * nc + c) 
                    if (c - 1 >= 0 and grid[r][c-1] == '1'):
                        uf.union(r * nc + c, r * nc + c - 1) 
                    if   (c + 1 < nc and grid[r][c+1] == '1'):
                        uf.union(r * nc + c, r * nc + c + 1) 
                    
    
        return uf.getCount() 
        

答案玩了个新东西，叫UnionFind， 挺有意思。 就是找爸爸的爸爸，然后谁rank高就作为最终父亲。 这样union时候只是pointer在移动， 刚开始所有1都是自己的爸爸， 然后逐渐union周围的1， 每union一次counter -=1 这样最终counter就是所有独立的岛数目。DFS也很简单， BFS同理。