Daily check in - Githubissues

TommyCpp commented 6 years ago

496. Next Greater Element I

https://leetcode.com/problems/next-greater-element-i/description/ 维护一个Map用于存储每个字母对应的结果

TommyCpp commented 6 years ago

500. Keyboard Row

https://leetcode.com/problems/keyboard-row/description/

TommyCpp commented 6 years ago

没有什么难度，但是有一种解决方案使用Stream+正则表达式可以大大减少代码量

TommyCpp commented 6 years ago

412. Fizz Buzz

https://leetcode.com/problems/fizz-buzz/description/

TommyCpp commented 6 years ago

669. Trim a Binary Search Tree

https://leetcode.com/problems/trim-a-binary-search-tree/description/ 经典算法题了

TommyCpp commented 6 years ago

给定一棵二叉搜索树和一个上下界[L,R]，要求筛选出在[L,R]之间的数，分情况讨论递归处理一下就可以得出结论

TommyCpp commented 6 years ago

575. Distribute Candies

https://leetcode.com/problems/distribute-candies/description/

TommyCpp commented 6 years ago

记录下有多少种独特的candy，得出种类数N，令糖果数M，取min(N, M/2) 可以使用Set来实现当种类数N超过糖果数M的一半的时候，就可以直接返回结果了

TommyCpp commented 6 years ago

463. Island Perimeter

https://leetcode.com/problems/island-perimeter/description/

TommyCpp commented 6 years ago

为什么暴力算法可以超过80%的Java提交:confused: 再提交一次竟然超过91%的Java提交:scream:？？？

TommyCpp commented 6 years ago

566. Reshape the Matrix

https://leetcode.com/problems/reshape-the-matrix/description/

注意代码不涉及原始矩阵的行数

TommyCpp commented 6 years ago

766. Toeplitz Matrix

https://leetcode.com/problems/toeplitz-matrix/description/

研究出迭代顺序即可，Repo中代码先按照增加行index，再处理列index

具体来说，

第一轮从第一列中的第一个元素出发，观察M[1][1],M[2][2],...M[N][N]是否和M[0][0]相同
然后从第一列中的第二个元素出发，观察M[2][1],M[3][2],...是否和M[1][0]相同
如此反复，完成对第一列元素的检查
然后对第一行元素进行检查，跳过M[0][0]

TommyCpp commented 6 years ago

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92390/Python-O(n)-time-O(1)-space

题目要求一个O(1)空间复杂度，O(n)时间复杂度的算法

第一个方案，首先排序然后再逐个处理，主要是保证相同的两个元素近邻
第二个方案，利用数组本身做Hash，具体来说，利用数组下标（注意题目中给出了数组元素范围在1到数组长度之间的限制）作为指示量，如果访问过，就把数组下标对应的元素变成负数. 例如如果访问到某个位置的元素是1，则我们把nums[1-1] *= -1，当然访问的时候做一下abs获得原始元素几个

用数组下标做Hash的想法

TommyCpp commented 6 years ago

682. Baseball Game

https://leetcode.com/problems/baseball-game/description/

用栈处理，可以考虑在一轮迭代中同时完成结果累加和压栈步骤

看起来用数组模拟栈操作会快一点，可能是因为不用动态分配空间？

TommyCpp commented 6 years ago

637. Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree/description/

先构建每一层的数组再求平均值

为什么不用递归逐个子树计算平均值？因为每一层的Node数量不确定，不可能在子树级别得出正确答案
感觉用while迭代还快一点

TommyCpp commented 6 years ago

513. Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/description/ 注意题目条件中要求最后一行最左侧的元素，应当从最后一行着手

TommyCpp commented 6 years ago

515. Find Largest Value in Each Tree Row

https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/

注意Python3中如何获得int的最小值使用sys模块

TommyCpp commented 6 years ago

496. Next Greater Element I

https://leetcode.com/problems/next-greater-element-i/description/

可以使用输入值作为返回结果，这样减少空间使用
使用栈结构，
- 如果后一个元素i比栈顶大，则不断出栈，直到栈顶元素大于i，保存结果；后一个元素入栈
- 如果后一个元素比前一个元素小，则入栈

TommyCpp commented 6 years ago

104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 经典算法题了

TommyCpp commented 6 years ago

540. Single Element in a Sorted Array

https://leetcode.com/problems/single-element-in-a-sorted-array/description/

几种思路：

使用异或处理然后reduce一下
- 使用了functools.reduce()进行reduce
- 使用异或来处理重复元素
暴力算法逐个对比
二分搜索（唯一一个应用到了排序特性的方法）

TommyCpp commented 6 years ago

136. Single Number

https://leetcode.com/problems/single-number/description/

用异或处理重复元素，无序的也可以，但是每个重复元素在数组中都只能出现2次

TommyCpp commented 6 years ago

647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/ 动态规划问题，核心是认识到构成回文的充要条件是除去其首尾位置的字符之外的字符串是回文

TommyCpp commented 6 years ago

413. Arithmetic Slices

https://leetcode.com/problems/arithmetic-slices/description/

动态规划问题
- 子问题：A[i]是否是Arithmetic？
- 状态转移方程：dp[i+1] = 1 + dp[i] if A[i] - A[i-1] == A[i-1] - A[i-2]
观察，如果Slice长度为3时候能找到多少个，当长度为4的时候能找到多少个？
- 可以得出规律，针对长度为n的Arithmetic Slices，其数量是num(n-1)*num(n-2) / 2

TommyCpp commented 6 years ago

406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/description/

题目中有一个隐含条件，假设给定一系列[i,j]，那么一定存在[i_max,0]，其中i_max是最大的i
所以从大到小排列，如果i相等，则按照j从小到大排列
- 为什么这么做？因为这样每一步完成之后数组中的所有值都比下一步要插入的大或者等于，这个时候按照j直接插入就好了
- 但同时下一步插入的值都比上一步小，不影响上一步值的相对位置

TommyCpp commented 6 years ago

485. Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/description/ 暴力算法即可

TommyCpp commented 6 years ago

226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/description/ 官方吐槽，最为致命

TommyCpp commented 6 years ago

508. Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum/description/ 使用Python Counter API处理

TommyCpp commented 6 years ago

260. Single Number III

https://leetcode.com/problems/single-number-iii/description/ 同样适用Counter API处理，但是应当有一个使用bit操作处理的方法

TommyCpp commented 6 years ago

526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/ 回溯法解决具体来说

首先定义用于递归的函数

def backtracking(length, nums): # length表示正在选择的位置
        res = []
        if len(nums) == 1: # 边界条件
            if nums[0] % length == 0 or length % nums[0] == 0:
                return [[nums[0]]]
            else:
                return []
        else:
            for num in nums: 
                if num % length == 0 or length % num == 0: # 如果num符合条件
                    for lst in backtracking(length + 1,[j for j in nums if j != num]):  # 迭代
                        lst.insert(0, num)
                        res.append(lst)
            return res

然后设置初始条件
```
backtracking(1, range(1, N + 1))
```

TommyCpp commented 6 years ago

784. Letter Case Permutation

https://leetcode.com/problems/letter-case-permutation/description/ 回溯法解决

TommyCpp commented 6 years ago

739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/ 用Stack处理

TommyCpp commented 6 years ago

553. Optimal Division

https://leetcode.com/problems/optimal-division/description/ 推导出固定式，即永远用第一项除以其他所有项的余数...

TommyCpp commented 6 years ago

748. Shortest Completing Word

https://leetcode.com/problems/shortest-completing-word/description/ 为了提高效率，当word长度大于等于目前最短的符合条件的word的时候直接不判断

TommyCpp commented 6 years ago

451. Sort Characters By Frequency

https://leetcode.com/problems/sort-characters-by-frequency/description/ Counter API是真的好用

TommyCpp commented 6 years ago

693. Binary Number with Alternating Bits

https://leetcode.com/problems/binary-number-with-alternating-bits/description/ 注意右移的语法，本题利用右移和1不断取出最右侧bit

A >>=1 //右移一位

TommyCpp commented 6 years ago

762. Prime Number of Set Bits in Binary Representation

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/

Integer.bitCount(Integer i); //统计bit数量

TommyCpp commented 6 years ago

609. Find Duplicate File in System

https://leetcode.com/problems/find-duplicate-file-in-system/description/ 分解String后用HashTable处理

关于几个Follow Up Question 相关讨论 https://leetcode.com/problems/find-duplicate-file-in-system/discuss/104120/Follow-up-questions-discussion

Imagine you are given a real file system, how will you search files? DFS or BFS?

DFS
If the file content is very large (GB level), how will you modify your solution?

用 Hash 函数来处理内容
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution?
What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

TommyCpp commented 6 years ago

520. Detect Capital

https://leetcode.com/problems/detect-capital/description/

TommyCpp commented 6 years ago

796. Rotate String

https://leetcode.com/problems/rotate-string/description/

TommyCpp commented 6 years ago

606. Construct String from Binary Tree

https://leetcode.com/problems/construct-string-from-binary-tree/description/ 分情况讨论，

如果只有右子树，则左子树应当以()呈现
如果只有左子树，则右子树为""

TommyCpp commented 6 years ago

198. House Robber

https://leetcode.com/problems/house-robber/description/ 动态规划问题子问题：dp[i]表示nums[:i]的最大偷窃值状态转移方程：dp[i+1] = max(dp[i-1]+nums[i+1], dp[i])

为什么在这里子问题中不需要区分偷窃的房子中包不包括最后一个?

如果没有偷窃最后一个房子，容易证明dp[i] = dp[i-1]，这个时候按照转移方程我们可以通过dp[i-1]+nums[i+1]这条路径获得正确的值
如果有偷窃最后一个房子，那么则不能偷窃i+1个房子
所以在任何情况下，我们都不需要判断dp[i]+nums[i+1]

TommyCpp commented 6 years ago

389. Find the Difference

https://leetcode.com/problems/find-the-difference/description/ Counter API

注意Counter是dict的子类

Counter常见操作

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

对Counter的加减操作

c = Counter(a=3, b=1)
d = Counter(a=1, b=2)
c - d # 逐个相减，保留正数
c + d #逐个相加
c & d #min(c[x], d[x]) 
c | d  # max(c[x],d[x])

TommyCpp commented 6 years ago

462. Minimum Moves to Equal Array Elements II

https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/description/

注意不需要判断数组长度是否是奇数，因为即便是偶数，用len(nums)//2和用len(nums)//2-1位置的元素作为中位数不存在区别

TommyCpp commented 6 years ago

448. Find All Numbers Disappeared in an Array

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/ 与#442相似，用数组下标做Hash的想法，妙啊！

TommyCpp commented 6 years ago

819. Most Common Word

https://leetcode.com/problems/most-common-word/description/ 注意首先要对paragraph进行一些处理（全部变成最小化，去除标点符号）

TommyCpp commented 6 years ago

717. 1-bit and 2-bit Characters

https://leetcode.com/problems/1-bit-and-2-bit-characters/description/ 感觉类似哈夫曼编码的思想如果出现1，则后一位不管是0或1都无所谓，所以跳过

TommyCpp commented 6 years ago

347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/ 不说了，Counter API

TommyCpp commented 6 years ago

781. Rabbits in Forest

https://leetcode.com/problems/rabbits-in-forest/description/ 从森林里所有的兔子中抽样一部分（也有可能是全部），询问有多少兔子和他们一个颜色，得出answers 因此，answers中每个元素加一就可以形成一个集合。例如[0,0,1,2,2]对应集合[1,1,2,3,3] 因为要求最小值，所以直观上来说我们将相同数量的集合**尽可能***认为是同一集合，上例中包含三种不同大小的集合. 但是又观察到[1,1]不可能是一个集合，因为每个兔子只可能有一种颜色因此，对于n个大小为1的集合，至少对应n个兔子又因为， [3,3]肯定凑不成一个大小为3的集合，因此肯定有一个隐藏的兔子，[3,3]对应3个兔子 [2]肯定凑不成一个大小为2的集合，因此肯定还有一个隐藏的兔子，[2]对应2个兔子

又考虑这样一种情况[0,0,1,1,1] 后半部分，对应[2,2,2]集合，这个集合可以凑成一个包含两个元素的集合，但是还多一个元素。因此必须凑成两个集合，最终需要4个元素。

TommyCpp commented 6 years ago

817. Linked List Components

https://leetcode.com/problems/linked-list-components/description/

注意题意是让我们从G中找出list中的联通部分首先考虑极端情况，如果G中每个元素之间都不联通，则返回G的长度

考虑从表头开始遍历，每遍历到一个节点就去G中找，找到了则继续，如果没有找到，说明联通部分断开了，结果加一，继续寻找（注意此时不需要再检测当前节点是否在G内部，因为题目中给定了G中元素均取自list）。

TommyCpp commented 6 years ago

171. Excel Sheet Column Number

https://leetcode.com/problems/excel-sheet-column-number/description/

没啥好说的Easy题

TommyCpp commented 6 years ago

238. Product of Array Except Self

https://leetcode.com/submissions/detail/157501055/ 创建两个数组before和after，分别记录nums[i]前的所有数之积和nums[i]后所有数之积，然后把每个i对应的before[i]和after[i]相乘就可以得到结果

TommyCpp / AhaMoment

Daily check in #3

496. Next Greater Element I

500. Keyboard Row

412. Fizz Buzz

669. Trim a Binary Search Tree

575. Distribute Candies

463. Island Perimeter

566. Reshape the Matrix

766. Toeplitz Matrix

442. Find All Duplicates in an Array

682. Baseball Game

637. Average of Levels in Binary Tree

513. Find Bottom Left Tree Value

515. Find Largest Value in Each Tree Row

496. Next Greater Element I

104. Maximum Depth of Binary Tree

540. Single Element in a Sorted Array

136. Single Number

647. Palindromic Substrings

413. Arithmetic Slices

406. Queue Reconstruction by Height

485. Max Consecutive Ones

226. Invert Binary Tree

508. Most Frequent Subtree Sum

260. Single Number III

526. Beautiful Arrangement

784. Letter Case Permutation

739. Daily Temperatures

553. Optimal Division

748. Shortest Completing Word

451. Sort Characters By Frequency

693. Binary Number with Alternating Bits

762. Prime Number of Set Bits in Binary Representation

609. Find Duplicate File in System

520. Detect Capital

796. Rotate String

606. Construct String from Binary Tree

198. House Robber

389. Find the Difference

462. Minimum Moves to Equal Array Elements II

448. Find All Numbers Disappeared in an Array

819. Most Common Word

717. 1-bit and 2-bit Characters

347. Top K Frequent Elements

781. Rabbits in Forest

817. Linked List Components

171. Excel Sheet Column Number

238. Product of Array Except Self