刷题打卡

Wangjingru_1995

Day 9:

Q1. Minimum Absolute Difference in BST 【easy】
题目理解：1）输入：二叉搜索树（root），所有元素为非负整数
            2）输出：整数，表示给定二叉树中任意两元素之差绝对值的最小值

解决方法：递归。对给定的二叉搜索树进行中序遍历。由于二叉树的特性为左子树所有节点的值小于等于根节点值，跟节点值小于右子树的所有节点值，当对二叉搜索树进行中序遍历后，可以得到一个sorted list，记作inOrderList。之后我们对这个inOrderList的两相邻元素求差取绝对值（直接用后一个减去前一个即可，因为是sorted），在寻找最小值即可。为了节省空间，我们也可以不必将所有差值都存下来，可以在遍历inOrderList求差的时候，同时更新最小值。

Q2. Find Smallest Letter Greater Than Target 【easy】
题目理解：1）输入：一个排过序的字符列表letters（仅包含小写字母），和一个目标字符target（小写字母）
            2）输出：字符，表示letters中大于target的最小字符。
            3）所有字符大小按从a至z依次增大a<b<c<…<z，且z<a以此构成闭环

解决方法：1）Brute Force。因为原列表已排序，遍历letters，依次判断是否大于target，输出第一个大于target的字符即可
            2）二分法。因为原列表已排序，因此二分法可行。自定义左、右指针left=0，right = len(letters)，以left<right-1为结束条件进行while循环，在循环中判断letters中mid = left + (right-left)/2 位置的字符和target的大小关系，并对left和right进行更新，循环结束后输出letters[right]即可。具体代码如下（python）：

class Solution(object):
def nextGreatestLetter(self, letters, target):
      if target < letters[0]: return letters[0]
      if target >= letters[-1] or target == "z": return letters[0]
      left = 0
      right = len(letters)
      while left < right-1:
         mid = left + (right - left)/2
         if target >= letters[mid]: left = mid
         elif target < letters[mid]: right = mid
      return letters[right]

注：mid不直接用(left+right)/2定义，是为了防止计算的大小值越界，因为要求取大于target的最小值，所以二分过程采用左闭右开的方式计算边界

Q3: Min Cost Climbing Stairs 【easy】
题目理解：1）输入：整数列表cost，表示经过每个index对应的台阶时的消耗
            2）输出：整数，到顶时需要的最少消耗
            3）cost的长度范围为[2, 1000]，cost中的每个元素cost[i]范围为[0, 999]
            4）可以从index为0或者1的位置开始攀登

解决方法：1）记忆化递归。为了防止超时，采用记忆化递归，自定义一个递归函数dp(cost，i)，表示到达第i个台阶时的消耗，传递关系为dp[cost, i] = min(dp[cost, i-1], dp[cost, i-2]) + cost[i]，并将每个dp[cost, i]存在memory[i]中，最后返回dp[cost, n-1]和dp[cost, n-2]中的最小值即可。
            2）递推：类似之前做的斐波那契数列，先定义起始条件，根据传递函数一步一步计算出，直到算到n即可，过程与方法1）类似，只不过是从前向后直接计算结果。

Q4: Shortest Completing Word 【easy】
题目理解：1）输入：1个string和一个list，分别为licensePlate和words
            2）输出：一个string，表示words列表中，满足条件的第一个出现的最短字符串
            3）条件：要求包含licensePlate中的所有字母（不论是否重复），不计大小写，只记次数
            4）licensePlate的长度范围为[1, 7]，words列表长度[10, 1000]，words中每个word的长度范围为[1, 15]

解决方法： hashtable + 剪枝。先根据licensePlate建立只包含字符的哈希表，keys为字符（全部转换为小写字母），values为相应字符出现的次数。初始化一个字符串长度为15以上的best，对words中每个word循环，若word中出现的任一字符没办法cover我们自己定义的hashtable中的key，就跳过这个word，如果可以包含hashtable中的所有字符且出现次数大于等于每个key对应的value，接着判断该word长度是否小于best，若是，则更新best，否则跳过并继续对下一个word进行循环。具体代码如下（python）：

class Solution(object):
def shortestCompletingWord(self, licensePlate, words):
      Set = {}
      for c in licensePlate:
         if c.isalpha():
            c = c.lower()
            if c in Set: Set[c] += 1
            else: Set[c] = 1
      best = "a"*26
      for word in words:
         found = True
         for key in Set.keys():
            if word.count(key) < Set[key]:
                  found = False
                  break
         if found and len(best)>len(word) :  best = word
      return best


Q5: Best Time to Buy and Sell Stock 【easy】
题目理解：1）输入：整数列表prices
            2）输出：整数，表示可以获得的最大收益

解决方法： 1）Brute Force。直接计算每一天卖出股票时能够获得的最大收益，最后输出最大值即可。整个过程需要更新的就是之前的最低价，和到目前为止的最大收益。具体代码如下（python）：

class Solution(object):
def maxProfit(self, prices):
      n = len(prices)
      if n<2: return 0
      low = prices[0]
      maxprofits = 0
      for i in range(1, n):
         maxprofits = max(prices[i] - low, maxprofits)
         low = min(low, prices[i])
      return maxprofits

2）递归。先将原问题稍作转化。这道题中，将原数组进行newElement[i] = prices[i+1] – prices[i]的操作后，问题就变成了之前做过一道题Maximum Subarray，是求所有连续子序列和的最大值。利用递归解决即可。

Wangjingru_1995

Day 9:

Q1. Minimum Absolute Difference in BST 【easy】
题目理解：1）输入：二叉搜索树（root），所有元素为非负整数
            2）输出：整数，表示给定二叉树中任意两元素之差绝对值的最小值

解决方法：递归。对给定的二叉搜索树进行中序遍历。由于二叉树的特性为左子树所有节点的值小于等于根节点值，跟节点值小于右子树的所有节点值，当对二叉搜索树进行中序遍历后，可以得到一个sorted list，记作inOrderList。之后我们对这个inOrderList的两相邻元素求差取绝对值（直接用后一个减去前一个即可，因为是sorted），在寻找最小值即可。为了节省空间，我们也可以不必将所有差值都存下来，可以在遍历inOrderList求差的时候，同时更新最小值。

Q2. Find Smallest Letter Greater Than Target 【easy】
题目理解：1）输入：一个排过序的字符列表letters（仅包含小写字母），和一个目标字符target（小写字母）
            2）输出：字符，表示letters中大于target的最小字符。
            3）所有字符大小按从a至z依次增大a<b<c<…<z，且z<a以此构成闭环

解决方法：1）Brute Force。因为原列表已排序，遍历letters，依次判断是否大于target，输出第一个大于target的字符即可
            2）二分法。因为原列表已排序，因此二分法可行。自定义左、右指针left=0，right = len(letters)，以left<right-1为结束条件进行while循环，在循环中判断letters中mid = left + (right-left)/2 位置的字符和target的大小关系，并对left和right进行更新，循环结束后输出letters[right]即可。具体代码如下（python）：

class Solution(object):
def nextGreatestLetter(self, letters, target):
      if target < letters[0]: return letters[0]
      if target >= letters[-1] or target == "z": return letters[0]
      left = 0
      right = len(letters)
      while left < right-1:
         mid = left + (right - left)/2
         if target >= letters[mid]: left = mid
         elif target < letters[mid]: right = mid
      return letters[right]

注：mid不直接用(left+right)/2定义，是为了防止计算的大小值越界，因为要求取大于target的最小值，所以二分过程采用左闭右开的方式计算边界

Q3: Min Cost Climbing Stairs 【easy】
题目理解：1）输入：整数列表cost，表示经过每个index对应的台阶时的消耗
            2）输出：整数，到顶时需要的最少消耗
            3）cost的长度范围为[2, 1000]，cost中的每个元素cost[i]范围为[0, 999]
            4）可以从index为0或者1的位置开始攀登

解决方法：1）记忆化递归。为了防止超时，采用记忆化递归，自定义一个递归函数dp(cost，i)，表示到达第i个台阶时的消耗，传递关系为dp[cost, i] = min(dp[cost, i-1], dp[cost, i-2]) + cost[i]，并将每个dp[cost, i]存在memory[i]中，最后返回dp[cost, n-1]和dp[cost, n-2]中的最小值即可。
            2）递推：类似之前做的斐波那契数列，先定义起始条件，根据传递函数一步一步计算出，直到算到n即可，过程与方法1）类似，只不过是从前向后直接计算结果。

Q4: Shortest Completing Word 【easy】
题目理解：1）输入：1个string和一个list，分别为licensePlate和words
            2）输出：一个string，表示words列表中，满足条件的第一个出现的最短字符串
            3）条件：要求包含licensePlate中的所有字母（不论是否重复），不计大小写，只记次数
            4）licensePlate的长度范围为[1, 7]，words列表长度[10, 1000]，words中每个word的长度范围为[1, 15]

解决方法： hashtable + 剪枝。先根据licensePlate建立只包含字符的哈希表，keys为字符（全部转换为小写字母），values为相应字符出现的次数。初始化一个字符串长度为15以上的best，对words中每个word循环，若word中出现的任一字符没办法cover我们自己定义的hashtable中的key，就跳过这个word，如果可以包含hashtable中的所有字符且出现次数大于等于每个key对应的value，接着判断该word长度是否小于best，若是，则更新best，否则跳过并继续对下一个word进行循环。具体代码如下（python）：

class Solution(object):
def shortestCompletingWord(self, licensePlate, words):
      Set = {}
      for c in licensePlate:
         if c.isalpha():
            c = c.lower()
            if c in Set: Set[c] += 1
            else: Set[c] = 1
      best = "a"*26
      for word in words:
         found = True
         for key in Set.keys():
            if word.count(key) < Set[key]:
                  found = False
                  break
         if found and len(best)>len(word) :  best = word
      return best


Q5: Best Time to Buy and Sell Stock 【easy】
题目理解：1）输入：整数列表prices
            2）输出：整数，表示可以获得的最大收益

解决方法： 1）Brute Force。直接计算每一天卖出股票时能够获得的最大收益，最后输出最大值即可。整个过程需要更新的就是之前的最低价，和到目前为止的最大收益。具体代码如下（python）：

class Solution(object):
def maxProfit(self, prices):
      n = len(prices)
      if n<2: return 0
      low = prices[0]
      maxprofits = 0
      for i in range(1, n):
         maxprofits = max(prices[i] - low, maxprofits)
         low = min(low, prices[i])
      return maxprofits

2）递归。先将原问题稍作转化。这道题中，将原数组进行newElement[i] = prices[i+1] – prices[i]的操作后，问题就变成了之前做过一道题Maximum Subarray，是求所有连续子序列和的最大值。利用递归解决即可。

Wangjingru_1995

Wangjingru_1995 发表于 2019-3-2 07:50
Day 9:

Q1. Minimum Absolute Difference in BST 【easy】

emmm，，，没想到不知不觉都已经更新到第二页了，还以为没发表成功，，发重了hh

Wangjingru_1995

Day 10:

Q1. Ugly Number 【easy】
题目理解：1）输入：整数num
            2）输出：bool结果，表示输入整数是否为“丑数”
            3）丑数：仅包含2，3，5三个质因数的正整数。特别地，1为特殊的“丑数”
            4）输入的整数范围为[−2^31, 2^31− 1].

解决方法： Brute Force。这是一道比较基础的数学问题，每个正整数都可以表示为质因数的幂的乘积。因为丑数都是正整数，因此先判断输入是否为正数，若不是则直接返回False。之后对num进行三次while循环，分别将原数中的2，3，5质因子降幂至0，最后判断剩下的因子是否为1，若是则返回True，否则返回False。

Q2. Sqrt(x) 【easy】
题目理解：1）输入：整数x
            2）输出：整数，表示x的平方根的整数部分

解决方法：二分法。因为输出为x平方根的整数部分，所以结果一定是小于或者等于sqrt(x)，所以在这里我们依然使用左闭右开的方式定义左右指针left = 0，right = x+1，用while循环进行二分操作，以left<right-1作为循环进行的条件，每次计算mid = left +(right – left)/2的平方和x的关系，并更新left，right指针。当循环结束时，直接返回left即可。【Time：o(log n)】

Q3: Prime Number of Set Bits in Binary 【easy】
题目理解：1）输入：两个整数L、R，表示上下限
            2）输出：整数，表示从L开始到R之间的数中“二进制形式形式下1的个数为质数”的总个数
            3）L<=R，L、R的范围为[1, 10^6]，R – L<=10000

解决方法：brute force + hashtable。因为所有数不大于10^6（约为2^20），也就是说，二进制下1的个数不大于20，所以可以直接制作一个质数表，dict = {2, 3, 5, 7, 11, 13, 17, 19}。之后用暴力方式直接遍历L到R之间的每个数，判断其二进制中1的数量是否在dict中即可。

Q4: Letter Case Permutation【easy】
题目理解：1）输入：1个string（S），里面包含字母或者数字
            2）输出：list of string，包含将S中每个字母大写和小写转化后的所有结果
            3）eg：S = ‘a1b2’，则输出[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

解决方法：递归。自定义一个递归函数，设定好保护条件，之后对每个S，将S[-1]拎出判断是否为字母，若是来行大小写转换操作并ans中插入所有情况；若不是，则S[-1]保留，只需更新ans。具体代码如下（python）：

class Solution(object):
def letterCasePermutation(self, S):
      return self.dfs(S)

def dfs(self, S):
      if S == "":
         return ['']
      left = self.dfs(S[:-1])
      ans = []
      for l in left:
         if S[-1].isalpha():
            ans.append(l + S[-1].upper())
            ans.append(l + S[-1].lower())
         else:
            ans. append(l + S[-1])
      return ans

Q5: Find All Anagrams in a String【easy】
题目理解：1）输入：两个string，s和p
            2）输出： list of int，表示s中的所有满足条件的substring的起始index
            3）条件：s的substring包含p中出现的所有元素且个数全部相同。

解决方法： 1）Brute Force。直接对s进行循环，每次分别判断s的子字符串和p中各个字母出现次数是否相同。具体代码如下（python）：

class Solution(object):
def findAnagrams(self, s, p):
      n = len(s)
      m = len(p)
      if n < m: return []
      ans = []
      alphabeta = 'abcdefghijklmnopqrstuvwxyz'
      for i in range(0,n-m+1):
         curr = s[i:i+m]
         valid = True
         for c in alphabeta:
            if curr.count(c)!=p.count(c):
                  valid = False
                  break
         if valid: ans.append(i)
      return ans

            2）Sliding window。整体思路与1）类似，只是在对s中长度为m = len(p)的子字符串循环时，由于每次都是向后移一位，所以不需要每次重新建立curr，只需要每次减去前一位字母，并加上后一位字母，之后判断curr和org是否相等即可。具体代码如下（python）：

class Solution(object):
def findAnagrams(self, s, p):
      n = len(s)
      m = len(p)
      if n < 1 or n < m or m < 1: return []
      org = [0]*26
      for l in p:
         org[ord(l) - ord('a')]+=1
      left = 0
      right = m
      currSet = [0]*26
      ans = []
      for c in s[0:m]:
         currSet[ord(c) - ord('a')]+=1
      if currSet == org: ans.append(0)
      for i in range(1, n-m+1):
         currSet[ord(s[i-1]) - ord('a')] -=1
         currSet[ord(s[i+m-1]) - ord('a')] +=1
         if currSet == org:
            ans.append(i)
      return ans

Wangjingru_1995

今天身体不适，没来及刷完题写总结，明天补上～

Wangjingru_1995

Day 11:

Q1. K Closest Points to Origin 【easy】
题目理解：1）输入：一个列表points（里面是某平面的一些坐标）和一个整数K
            2）输出：所有满足条件的坐标，表示points里到原点距离第K近的所有点
         3）输出的序列可以是任何顺序，但结果唯一

解决方法：排序。因为题目中不限定输出的顺序，所以我们直接按照坐标的平方和作为排序标准，从小到大进行排序，然后直接返回第K近的所有坐标即可。

Q2. Print Binary Tree 【Medium】
题目理解：1）输入：二叉树（root）
            2）输出：满足条件的2维矩阵（m*n）
            3）要求：m等于二叉树的高度；n为奇数。节点的值以字符串的形式打印，根节点在第一行的正中间，且之后的每个子树的根节点都在相应的起始行的正中间

解决方法：递归。借助两个辅助函数，一个用来计算二叉树的高度getHeight（root），一个用来将根节点的值填入所要输出的矩阵中fillMatrix（root，height，ans，left，right）。在定义getHeight函数时，利用递归的方式，返回左右子树高度的最大值加一，当root为空时返回0作为递归的终止条件。在定义fillMatrix时，因为根节点要在正中间，所以左右子树分别在一根节点为中心分开的左右两部分，并分别占据各部分的正中，left和right就是用来限制对相应root要填写其节点值时的左右边界，mid = ( left + right ) / 2为root在height行的位置。两个函数都定义完之后，在主函数中初始化ans矩阵，并call一下fill函数并填入初始值即可。具体代码实现如下（python）：

class Solution(object):
def printTree(self, root):
      h = self.getHeight(root)
      w = 2**h - 1
      ans = [[""]*w for row in range(0,h)]
      self.fillMatrix(root, 0, ans, 0, w-1)
      return ans

def getHeight(self, root):
      if not root: return 0
      return max(self.getHeight(root.left), self.getHeight(root.right)) + 1

def fillMatrix(self, root, h, ans, l, r):
      if not root: return
      mid = (l+r)/2
      ans[h][mid] = str(root.val)
      self.fillMatrix(root.left, h+1, ans, l, mid-1)
      self.fillMatrix(root.right, h+1, ans, mid+1, r)

Q3: Path Sum II 【Medium】
题目理解：1）输入：二叉树（root），整数sum
            2）输出：所有满足条件的path，要求从root开始到任意叶子的path上所有节点值之和等于sum

解决方法：递归。需要写一个辅助函数helper(root, sum, curr, ans)，其中root和sum为input，curr表示当前分支，ans表示将要返回的结果。每次进入helper时先将当前节点传入curr，之后将所有情况分为三种来讨论，当root为叶子时，直接判断当前root.val和当前sum是否相同，若相同将当前支路curr中的所有元素的list传入ans，否则将curr的最后一个元素pop掉完成当前分支的回溯。接下来root一定存在左或右分支，分别对左右分支递归调用原函数，此时root变为root.left（或root.right），sum需要减去root.val作为new_sum，在左右分支分别结束后，不论结果如何都需要pop掉curr的最后一个元素完成回溯。Helper函数定义完成后只需在主函数中初始化curr和ans，并call一下helper 函数，最后返回ans即可。具体实现过程如下（python）：

class Solution(object):
def pathSum(self, root, sum):
      if not root:
         return []
      ans = []
      curr = []
      self.helper(root, sum, curr, ans)
      return ans

def helper(self, root, sum, curr, ans):
      curr.append(root.val)
      if not root.left and not root.right:
         if root.val == sum:
            ans.append(curr[:])
#注：为了在ans中引用curr里当前的所有元素（curr相当于一个指针）需要用curr[:]来实现，而不是直接append curr，否则ans中插入的就是输入时curr代表的内容
         curr.pop() #回溯
         return #递归的终止条件

      if root.left:
self.helper(root.left, sum - root.val, curr, ans)
#传递关系体现在sum的变化，new_sum = sum – root.val
      if root.right:
         self.helper(root.right, sum - root.val, curr, ans)
      curr.pop() #回溯

Q4: Triangle 【Medium】
题目理解：1）输入：1个下三角矩阵
            2）输出：整数，表示从第一行到最后一行的minimum path对应的最小值
            3）行进规则：从上到下的path只能向正下方或者右下方前进

解决方法：递推。将所有path从上到下求和，找到以每个位置结束的path 能够得到的最小值，最后返回最后一行的最小值即可。在计算所有最小值时，利用行进规则建立传递函数，以保证每个点得到的值最小。具体代码如下（python）：

class Solution(object):
def minimumTotal(self, triangle):
      n = len(triangle)
      miniSum = triangle
      for i in range(1,n):
         for j in range(0, i+1):
            if j == 0:
                  miniSum[i][j] = miniSum[i-1][j] + triangle[i][j]
            elif j == i:
                  miniSum[i][j] = miniSum[i-1][j-1] + triangle[i][j]
            else:
                  miniSum[i][j] = min(miniSum[i-1][j], miniSum[i-1][j-1]) + triangle[i][j]
      return min(miniSum[-1])

Q5: Word Break【Medium】
题目理解：1）输入：非空字符串s，字符串列表wordDict（所有元素非空）
            2）输出：bool结果，表示输入的s可否分割成几个子字符串满足所有子字符串都在wordDict中出现
            3）wordDict中的单词可以重复利用，假设列表中单词不重复

解决方法：递推。首先我们需要遍历s的所有分割情况，n = len(s)，我们在s开头加一个空格使得我们可以在从1到n的所有位置都可以进行分割。定义和1个长度为n+1的memory并初始化为0，用来记录在前index位置的子字符串可否实现分割，若可以则memory[index] = 1。一开始先初始化memory[0] = 1，表示什么都没有时满足。之后进行for循环遍历从index=1到n的所有子字符串，并通过在套用一个for循环来判断和更新memory，当循环进行完毕，输出memory[n]即可。具体代码如下（python）：

class Solution(object):
def wordBreak(self, s, wordDict):
      n = len(s)
      f = [0] * (n+1)
      s = " "+s
      f[0]=1
      for i in range(1, n+1):
         for j in range(0, i):
            if f[j] == 1:
                  new_s = s[j+1:i+1]
                  if wordDict.count(new_s):
                     f[i] = 1
                     break
      return f[-1]==1

Wangjingru_1995

Day 12:

Q1. Different Ways to Add Parenthesis 【Medium】
题目理解：1）输入：一个字符串input，包含数字和操作符
            2）输出：整数列表，表示在input 中任意加入括号后能得到的所有整数解
         3）有效操作符包括：’+’、‘-’、‘*’。
            4）输出的结果唯一，不计顺序

解决方法：递归。和昨天的Word Break类似，将整个输入从每个操作符分别分成左右两部分，并分别进行递归调用原函数计算，之后将左右两部分结果保留后进行笛卡尔积操作，并将循环的所有结果保存在ans中一起输出即可。一开始想的时候觉得较为复杂，但想明白并进行实际操作之后，会发现实现起来还比较简单，代码也比较简洁。具体代码实现过程如下（python）：

class Solution(object):
def diffWaysToCompute(self, input):
      ans = []
      n = len(input)
      for i in range(0, n):
         op = input[i]
         if op in {'+', '-', '*'}:
            left = input[:i]
            right = input[i+1:]
            L = self.diffWaysToCompute(left)
            R = self.diffWaysToCompute(right)

            for l in L:
                  for r in R:
                     ans.append(self.f(l,r,op))
      if len(ans) == 0:
         ans.append(int(input))
      return ans

def f(self, l, r, op):
      if op == '+':
         return l+r
      if op == '-':
         return l-r
      if op == '*':
         return l*r

Q2. Binary Tree Level Order Traversal 【Medium】
题目理解：1）输入：二叉树（root）
            2）输出：List[List[int]]，表示给定二叉数按照每一层进行打印的结果
            3）输出中每个整数表示原二叉树中每个节点的值，打印顺序为从上到下，从左到右，中间的空节点全部省略。

解决方法：1）BFS。利用宽度优先搜索的方式跟题目的描述最为接近。利用两个辅助list分别记录当前层currL和下一层nextL的节点（先进先出相当于queue），按照逐层遍历的方式，进行逐层打印即可。具体实现方式如下（python）：

class Solution(object):
def levelOrder(self, root):
      currL = []
      nextL = []
      if not root:
         return []
      ans = []
      currL.append(root)
      while currL:
         ans.append([])
         for c in currL:
            ans[-1].append(c.val)
            if c.left:
                  nextL.append(c.left)
            if c.right:
                  nextL.append(c.right)
         currL = nextL
         nextL = []
      return ans

            2）DFS。和之前遇到的二叉树问题类似，因为需要对整棵树进行遍历，因此除了BFS之外同样可以利用DFS进行深度优先搜索。利用递归的方式进行先序遍历，同时需要引入一个辅助变量level或者height进行层与层之间的传递。这道题中DFS和BFS的运行时间差不多都是24ms，BFS更易理解，DFS的代码更加简洁。具体实现过程如下（python）：

class Solution(object):
def levelOrder(self, root):
      ans = []
      self.dfs(root, 0, ans)
      return ans

def dfs(self, root, level, ans):
      if not root:
         return []
      if len(ans) <= level:
         ans.append([])
      ans[level].append(root.val)

      self.dfs(root.left, level+1, ans)
      self.dfs(root.right, level+1, ans)

相似题目：Leetcode 637. Average of Levels in Binary Tree。前几天的简单题目中出现过。

Q3. Maximum Binary Tree 【Medium】
题目理解：1）输入：整数列表nums
            2）输出：二叉数（root）
            3）题目给出了一种将list转变为二叉树的规则：list中的最大值为根节点，最大值左边的元素为左子树，右边为右子树，其左右子树的构成规则同上。

解决方法：递归。根据题目描述，比较容易想到递归，因为每个子树的构成规则和整个列表相同，因此只要一开始先找到最大值构建根节点，之后对list的左半部分和右半部分分别递归调用解函数返回作为左右子树即可。注意要考虑corner case进行必要的保护操作。具体实现如下（python）：

class Solution(object):
def constructMaximumBinaryTree(self, nums):
      if not nums:
         return

      root = TreeNode(0)
      rootIndex = nums.index(max(nums))
      root.val = max(nums)

      left = nums[:rootIndex]
      right = nums[rootIndex+1:]
      root.left = self.constructMaximumBinaryTree(left)
      root.right = self.constructMaximumBinaryTree(right)

      return root

Q4. Word Search 【Medium】
题目理解：1）输入：二维字符矩阵board，和一个字符串word
            2）输出：bool结果，表示是否可以在board中找到word
            3）规则：用board中的字母构成单词时，每个字符只能向上下左右四个方向的相邻元素前进，且同一个位置的字符不能重复使用。起始位置未指定

解决方法： DFS。因为题目需要找整个word是否出现，相当于深度确定，且扩展方向为上下左右四个方向，较为复杂，因此我们采用DFS进行递归。我们需要两个大的步骤，一是要定义辅助函数search，进行递归条件的描述并完成递归过程；而是要通过对board进行直接循环寻找可能的起始位置，再call自定义的search函数。需要注意的是，这道题目的边界情况较多，且由于同一个位置不能多次使用，因此在search中需要进行回溯。具体实现过程如下（python）：

class Solution(object):
def exist(self, board, word):
      m = len(board)
      if m == 0:
         return False
      n = len(board[0])
      l = len(word)
      for j in range(0, m):
         for k in range(0, n):
            if self.search(j, k, board, 0, word):
                  return True
      return False

def search(self, x, y, board, i, word):
      m = len(board)
      if m == 0:
         return False
      n = len(board[0])
      l = len(word)
      if l > m*n: return False
      if x<0 or x>m-1 or y<0 or y>n-1:
         return False
      if word[i] != board[x][y]:
         return False
      if i == l-1:
         return True
      curr = board[x][y]
      board[x][y] = '0'
      ans = self.search(x+1, y, board, i+1, word) or self.search(x-1, y, board, i+1, word) or self.search(x, y+1, board, i+1, word) or self.search(x, y-1, board, i+1, word)
      board[x][y] = curr
      return ans

Q5. Find Minimum in Rotated Sorted Array 【Medium】
题目理解：1）输入：整数列表nums，满足进行rotate操作后会变成一个排好序的列表，且nums中无重复元素
            2）输出：整数，表示nums中的最小值
            3）输入的例子：nums = [4, 5, 6, 7, 1, 2, 3][1, 2, 3, 4, 5, 6, 7]

解决方法：1）直接排序找第一个元素/直接返回最小值。运行时间较长
            2）for 循环直接遍历nums，找到第一个nums[i] < nums[i-1]输出nums[i]，若循环结束也没找到，说明nums为排好序的列表，直接返回nums[0]
            3）二分法。最小值一定出现在非连续上升序列的一半中，或者就是第一个元素。因此每次循环中只需要对mid和right进行比较即可。具体实现如下（python）：
class Solution(object):
def findMin(self, nums):
      n = len(nums)
      if n<1: return []
      left = 0
      right = n-1
      while left < right -1:
         mid = left+(right-left)/2
         if nums[mid] < nums[right]:
            right = mid
            continue
         else:
            left = mid
      return min(nums[left], nums[right])

Wangjingru_1995

Wangjingru_1995 发表于 2019-3-6 11:45
Day 12:

Q1. Different Ways to Add Parenthesis 【Medium】

最近开始做Medium题目，有些题目上还是能明显感觉到难易程度的差别的，尤其是在coding中，整体篇幅有变长hh，但是思路上其实还是有很多类似的地方，相信只要能够坚持下去，以后会越来越好的，加油！！不要被medium的label吓到hh

Wangjingru_1995

Day 13:

Q1. Valid Triangle Number【Medium】
题目理解：1）输入：整数列表nums（list of int）
            2）输出：整数，nums中的元素能够构成
         3）nums的长度不超过1000，nums中的元素范围[0, 1000]

解决方法：双指针。网上的视频教程中提到了贪心算法，但是我从个人的角度，看到这道题我首先想到的是在一个for 循环中套用双指针，来实现3条边的遍历，来判断三角形三边满足的条件。根据题目给出的数据规模可以知道如果直接对3条边进行三重遍历，时间复杂度在n^3，一定会超时。我是先将nums排序，之后根据三角形三边特点如果a<b<c，那么a+b>c，所以我们可以从最大值开始作为c进行遍历，左右指针分别代表a、b，双指针在while循环中实现，a<b作为循环条件。b从c前一位开始，当a满足条件时，则a右边一直到b之前所有的元素都满足。虽然描述起来听着有点复杂，但是代码实现却很简单具体代码实现过程如下（python）：

class Solution(object):
def triangleNumber(self, nums):
      n = len(nums)
      if n < 3: return 0
      nums.sort()
      ans = 0
      for c in range(1, n-1):
         a = 0
         b = n-c-1
         while a < b:
            if nums[a] + nums[b] > nums[-c]:
                  ans += b-a
                  b-=1
            else:
                  a+=1
      return ans

Q2. Unique Path 【Medium】
题目理解：1）输入：整数m、n，分别表示机器人的行走矩阵范围m*n，机器人从左上角开始走向右下角，机器人每次走一步，且只能向下或右前进
            2）输出：整数，表示机器人从起点到终点的不同走法数量

解决方法：1）递推。先确定起始条件，x或y小于等于0时，行走方式为0种，x、y都为1时为1，递推关系为之后每个位置都等于左边的行走方式加上面的行走方式：memo[i][j] = memo[i-1][j] + memo[i][j-1]，最后返回右下角的值即可。具体实现方式如下（python）：

class Solution(object):
def uniquePaths(self, m, n):
      if m <= 0 or n <= 0:
         memo[m][n] = 0

      memo = [[0]*(n+1) for row in range(0, m+1)]

      for i in range(1, m+1):
         for j in range(1, n+1):
            if i == 1 and j == 1:
                  memo[i][j] = 1
            else:
                  memo[i][j] = memo[i-1][j] + memo[i][j-1]
      return memo[m][n]

            2）记忆化递归。和以前遇到的所有递推递归类型的题目类似，都可以正反两种方式实现，记忆化递归和递推思路的递推关系完全相同，只是计算方向相反。我自己也做了递归，但是不知道为什么总是显示超时，自己觉得没问题，具体实现过程po在下面了，欢迎指正（python）：

class Solution(object):
def uniquePaths(self, m, n):
      if m<=0 or n<=0:
         return 0
      if m == 1 and n == 1:
         return 1
      memo = [[0]*(n+1) for row in range(0, m+1)]
      if memo[m][n] > 0:
         return memo[m][n]
      else:
         memo[m][n] = self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
      return memo[m][n]

Q3. Unique Path II 【Medium】
题目理解：1）输入：整数矩阵，仅包含0和1，这道题为上一题的follow up，其他设定都相同，只是输入有所出入，这里的矩阵规模m、n对应上一题的输入，这里矩阵中若为0，一切正常，若为1，表示当前位置有障碍物，不能通过
            2）输出：整数，依然表示机器人从起点到终点的不同走法的数量

解决方法：和上一题一样都是递推和递归两种方法。唯一的不同在于，我们要将障碍物处的方法设置为0，同时要考虑一些特殊的起始条件（corner case），例如障碍物在起点等。和上一题一样，我自己用记忆化递归还是超时，就很怪，Anyway，这里列出了递推的具体实现（python），和上一题几乎一样：

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
      m = len(obstacleGrid)
      if m == 0:
         return 0
      n = len(obstacleGrid[0])
      memo = [[0]*(n+1) for row in range(0,m+1)]
      for i in range(0, m):
         for j in range(0,n):
            if i == 0 and j == 0:
                  if obstacleGrid[i][j] == 1:
                     memo[i+1][j+1] = 0
                  else:
                     memo[i+1][j+1] = 1
                  continue
            if obstacleGrid[i][j] == 1:
                  memo[i+1][j+1] = 0
            else:
                  memo[i+1][j+1] = memo[i][j+1] + memo[i+1][j]
      return memo[m][n]

Q4. Longest Increasing Subsequence 【Medium】
题目理解：1）输入：整数list（未排序）nums
            2）输出：整数，表示nums中最长的递增子序列的长度

注：之前做过类似的题，不过是要寻找最长连续递增子序列长度，虽然两题相似，而且这题的代码也不长，但是这道题思考起来还是有很大不同的，稍微难一些的，计算也更复杂一些

解决方法：递推/记忆化递归。以递推为例。这道题需要对数量进行双层循环进行，因为这道题的递增序列并不一定连续，所有在每次计算第i个位置的结果时，需要对i之前的元素和其计算过的结果进行遍历辅助计算，计算时间比较长。具体实现过程如下（python）：

class Solution(object):
def lengthOfLIS(self, nums):
      n = len(nums)
      if n < 1:
         return 0
      ans = [0] * n
      memo = [1] * n
      for i in range(0, n):
         for j in range(0, i):
            if nums[i]>nums[j]:
                  memo[i] = max(memo[j]+1, memo[i])
return max(memo)

Q5. Implement Magic Dictionary 【Medium】
题目理解：这道题是设计数据结构，需要实现一些交互，要实现的功能包括：
            1）buildDict：【输入】字符串，【输出】Null
            2）search：【输入】字符串，【输出】bool结果，表示输入字符串更改一个字符后可否在dict中找到。

解决方法：我个人认为没有什么特殊的算法，题目的主要目的是通过学习答案来掌握一些以前不知道的知识，进行知识的积累和补充就行了。具体实现如下（python）：
class MagicDictionary(object):

def __init__(self):
      """
      Initialize your data structure here.
      """
      self.myDict = collections.defaultdict(list)

def buildDict(self, dict):
      """
      Build a dictionary through a list of words
      :type dict: List[str]
      :rtype: None
      """
      for word in dict:
         self.myDict[len(word)].append(word)

def search(self, word):
      """
      Returns if there is any word in the trie that equals to the given word after modifying exactly one character
      :type word: str
      :rtype: bool
      """
      return any(sum(a!=b for a,b in zip(word, candidate)) == 1
               for candidate in self.myDict[len(word)])
注：整个答案中并没有特别复杂的地方，通过这道题，我自己是新学会了python的内置函数zip（）的使用，也了解了class的书写方法。之前见到过一道类似的题目，我记得是Leetcode 707，是设计Linked List的，好像是一道【easy】的题目，之前跳过了，等再做一段时间算法题之后，以后在分类刷题的时候可以留心一下，做做类似的设计题

Q6. Sort Characters By Frequency 【Medium】
题目理解：1）输入：字符串s
            2）输出：字符串，将s中的元素按照出现频率进行排序后输出的结果
            3）出现频率相同的字符顺序任意，且s中仅含小写字母

解决方法：1）直接对原字符串进行自定义排序规则进行排序
            2）hashtable。利用哈希表对s中的字符进行计数，之后按数量排序后生成相应new_s

Wangjingru_1995

Day 14:

Q1. Sort Characters By Frequency 【Medium】
题目理解：1）输入：字符串s
            2）输出：字符串，将s中的元素按照出现频率进行排序后输出的结果
            3）出现频率相同的字符顺序任意，且s中仅含小写字母

解决方法：1）直接对原字符串进行自定义排序规则进行排序。需要注意的是，如果直接排序输出会产生一个list of string/char，所以若想要返回一个string需要进行join

class Solution(object):
def frequencySort(self, s):
      l = sorted(list(collections.Counter(s).items()), key = lambda x: -x[1])
      ans = ""
      for c,a in l:
         ans+=c*a
      return ans

2）hashtable。利用哈希表对s中的字符进行计数，之后按数量排序后生成相应new_s

Q2. Number of Longest Increasing Subsequence 【Medium】
题目理解：1）输入：整数list（未排序）nums
            2）输出：整数，表示能组成的最长子序列的个数

注：感觉像是昨天第4题的变形，但是在实现上略有不同，个人感觉这道题比昨天的要难一些，思考方式也要进行调整

解决方法：递推/记忆化递归。这里依然以递推为例。和昨天的第4题类似，这道题依然需要对数量进行双层循环进行，不同点在于除了需要对最长子序列的构成进行记忆和递推计算，还需要另外一个extra space对以每个元素结尾生成相应位置最长子序列的个数，同时递推关系也略有不同。具体实现过程如下（python）：

class Solution(object):
def findNumberOfLIS(self, nums):
      n = len(nums)
      if n < 1:
         return 0
      memo = [1] * n #记录以每个位置结尾的最长子序列的长度
      memoN = [1] * n #记录以每个位置结尾的最长子序列能有几个
      for i in range(0,n):
         for j in range(0,i):
            if nums[i] > nums[j]:
                  if memo[j]+1 > memo[i]:
                     memo[i] = memo[j]+1
                     memoN[i] = memoN[j]
                  elif memo[j]+1 == memo[i]:
                     memoN[i] += memoN[j]
      ans = 0
      for i in range(0,n):
         if memo[i] == max(memo):
            ans += memoN[i]

      return ans

Q3. Insert Delete GetRandom O(1) 【Medium】
题目理解：好巧不巧今天又遇到了一道数据结构设计题，需要实现一些交互，且对每个具体操作的时间要求为o(1)。要实现的功能包括：
            1）insert(val)：【输入】整数val【输出】bool变量，若val不在set中则插入val并输出True表示操作成功，若已经存在则输出False表示不能操作
            2）remove(val)：【输入】整数val，【输出】bool结果，若val不在set中则输出False表示无法操作，若存在则删除所有val并输出True表示操作成功
            3）getRandom：随机返回set中的一个元素，要求每个元素有相同的出现概率（和元素个数成正比）

解决方法：因为我个人对数据结构设计的语法了解较少，所以和之前一样还是主要通过看别人分享的结果一步一步的摸索学习，因为代码不是自己design的，所以具体代码就不po了，感兴趣的朋友可以在leetcode的discussion中借鉴各位大神的结果。

Q4. Map Sum Pairs 【Medium】
题目理解：这道题和上一题一样也是数据结构设计，具体理解就不写了，详见leetcode 677。之后第二阶段按类别刷题的时候在进行进一步的总结。

Q5. Reconstruct Itinerary【Medium】
今天最大的问题大概就在这里了，不知道是因为昨天晚上没睡够还是心理问题，有点太明白。看网上的视频讲解，觉得讲的方法非常高大上，巧妙但是没完全理解。至少听完之后自己还是不太明白如何实现。所以明天会继续学习这道题，想办法跟着别人的解法走一遍，再自己试着解决。废话不多说啦，主要还是今天在外面跑得有点久外加马上搬家需要收拾东西外加跟朋友约饭打羽毛球，所以学习的时间没够hh～明天继续加油啦！

刷题打卡

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

浏览过的版块