刷题心得
- python的list默认支持栈的方法pop()和append()（和push同一个功能）
- “in-place”的题，想到指针
- 物理层调制器作用：将数字信号转换成模拟信号
- leetcode 53：maxSubArray
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int max = nums[0];
for(int i=1; i<n; i++){
if(dp[i-1] > 0)
dp[i] = dp[i-1] + nums[i];
else
dp[i] = nums[i];
max = Math.max(max, dp[i]);
}
return max;
}
}
-
-
A * "1+1+1+1+1+1+1+1 =？" * A : "上面等式的值是多少" B : *计算* "8!" A *在上面等式的左边写上 "1+" * A : "此时等式的值为多少" B : *quickly* "9!" A : "你怎么这么快就知道答案了" A : "只要在8的基础上加1就行了" A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过 的解来节省时间'" - 动态规划算法的核心:记住已经解决过的子问题的解。
并查集
-
用于解决动态连通性问题的逻辑数据结构
-
包含两种操作：union()和connect()
-
union(x,y)给x,y之间添加一条connection
-
find(x,y)返回x和y之间是否连通，True/False
-
quickFind：
-
quickUnion：
- 想一想为什么每一次union都用是连通分量的根指向联通分量的根，这个步骤是提升效率的关键
-
quick-union和quick-find都不行
-
改进：
-
每个连通分量引入权重（每个分量上的节点数），以此避免树线性化
-
每一个union操作，都将权重小的连通分量连在另一颗树上
-
复杂度分析：
-
再改进一下？？：引入路径压缩
- 加入一行代码，每次让节点指向他的祖父节点，基本就能将整棵树展平
-
-
- 最近生活过的不太规律，该学习的时候一定得找一个没地方躺的地方不然一趟就是大半天..
-
之后的计划：两周内把leetcode100题刷完，Princeton算法课跟上，最后，小程序要急工赶完。
-
Python的五个标准数据类型：
- Numbers：包含int,long,float,short. int溢出会自动转化为long
- String：*是重复操作，+号是连接操作
- List：list[1:5:2] 返回list[1],list[3]和list[5]。第三个参数指定步长
- Tuple：只读列表，用tuple = ()创建
- Dict
- 在 python 中，strings, tuples, 和 numbers 是不可更改的对象，而 list,dict 等则是可以修改的对象。
- python 中一切都是对象，严格意义我们不能说值传递还是引用传递，我们应该说传不可变对象和传可变对象。
-
运算符：
- $$取幂运算：24 = 16
- //除法向下取整：7//3 = 2
-
id()函数获取对象内存地址，类似java hashcode()
-
is 与 == 区别：
is 用于判断两个变量引用对象是否为同一个(同一块内存空间)， == 用于判断引用变量的值是否相等。
==用于判断值，is 判断内存地址
a=[1,2] b= a a==b(True) a is b(True)
a= [1,2] b= a[:] a==b(True) a is b(False)
-
python list转string: string = ‘‘.join(list)
-
python sorted函数，返回所有可迭代对象的有序list形式
- leetcode 55 Jump Game: Greedy and Dynamic Programming
- leetcode 56 Merge Intervals：没吃透，复杂度太高（主要是memory copy操作太伤了），明天再来
- OpenStack还是作为备选把，明天还是继续跟一下普林的算法课
8.09
-
Leetcode 64. Minimum Path Sum:看到这道题两眼放光：“哇这可以用dijkstra最短路径来写”。心情激动地写下了第一次dijkstra的实现..然后运行时间被DP暴捶…
-
def dijkstra(self,grid): result = 0 m = len(grid) n = len(grid[0]) if m==0 or n ==0: return 0 traversed = {} untraversed = {} traversed[(0,0)] = [grid[0][0],False] for i in range(m): for j in range(n): untraversed[(i,j)] = float("inf") del untraversed[(0,0)] i,j=0,0 while len(untraversed)>0: for key,value in traversed.items(): if not value[1]: if key[0] <m-1: if (key[0]+1,key[1]) not in traversed: traversed[(key[0]+1,key[1])]= [grid[key[0]+1][key[1]]+traversed[key][0],False] del untraversed[(key[0]+1,key[1])] elif traversed[(key[0]+1,key[1])][0] > grid[key[0]+1][key[1]]+traversed[key][0]: traversed[(key[0]+1,key[1])][0]= grid[key[0]+1][key[1]]+traversed[key][0] if key[1] <n-1: if (key[0],key[1]+1) not in traversed: traversed[(key[0],key[1]+1)]= [grid[key[0]][key[1]+1]+traversed[key][0],False] del untraversed[(key[0],key[1]+1)] elif traversed[(key[0],key[1]+1)][0] > grid[key[0]][key[1]+1]+traversed[key][0]: traversed[(key[0],key[1]+1)][0]= grid[key[0]][key[1]+1]+traversed[key][0] traversed[key][1] = True return traversed[(m-1,n-1)][0] -
def dp(self,grid): m = len(grid) n = len(grid[0]) for i in range(1, n): grid[0][i] += grid[0][i-1] for i in range(1, m): grid[i][0] += grid[i-1][0] for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]
-
其实说到底对于这个题，这两种写法思想是一致的。但是显然DP看到了问题本质，每一个点的值只与←和↑两个值有关。第一种dijkstra的实现并没有抓到这个本质，又加上过多访存和字典增删的开销，导致时间大大超出DP
- 经典题：通过二叉树的前序和中序遍历，画出二叉树
- 思路：
- 前序序列队首值，总是一颗树/子树的根
- 在中序序列中，找到这个队首值的位置。
- 位于这个位置左边的，就是属于这个根的左子树；右边的，就是右子树
- 递归，直到inorder为空就返回（inorder为空说明当前节点没有子树了）
- LC141: Find cycle in a linked list
- 题目本身很简单，自然的想法是遍历+哈希表
- 时间复杂度：O(n)
- 空间复杂度: O(n)
- 一种空间复杂度为O(1)的方法：两根指针
- 两根指针同时遍历
- 一根指针步长设为1
- 另一根步长设为2
- 每一次判断两根指针是否指向同一个node
- 题目本身很简单，自然的想法是遍历+哈希表
