7月缺米的来刷题/Mock interview活动

今日打卡5题如图

day 7

mock 又是做过的。。。嘿嘿，但是没写出最优解，当初做的时候就没有去写最优解。。以至于我搞了一下午。。
dp的空间通常考虑能不能2d-》1d-》constantFri, Jul 10, 2020, 2:04 PM        Algorithms        
Decode Variations
Find The Duplicates


lc 复习
Maximum Sum of Two Non-Overlapping Subarrays   6 minutes ago
AcceptedjavaMaximum Sum of Two Non-Overlapping Subarrays   7 minutes ago
AcceptedjavaPath with Maximum Gold   12 minutes ago
AcceptedjavaRepeated DNA Sequences   15 minutes ago
AcceptedjavaRepeated DNA Sequences   16 minutes ago
AcceptedjavaNext Closest Time   44 minutes ago
AcceptedjavaPath Sum II   47 minutes ago
AcceptedjavaPath Sum II   1 hour, 2 minutes ago
AcceptedjavaCombinations   1 hour, 12 minutes ago
AcceptedjavaCombinations   1 hour, 16 minutes ago
AcceptedjavaDecode Ways   1 hour, 31 minutes ago
AcceptedjavaDecode Ways   1 hour, 44 minutes ago
Compile ErrorjavaDecode Ways   1 hour, 44 minutes ago
Compile ErrorjavaDecode Ways   1 hour, 44 minutes ago
AcceptedjavaDecode Ways   1 hour, 52 minutes ago
Wrong AnswerjavaDecode Ways   1 hour, 52 minutes ago
Wrong AnswerjavaDecode Ways   1 hour, 56 minutes ago
Wrong AnswerjavaDecode Ways   1 hour, 57 minutes ago
Wrong AnswerjavaDecode Ways   1 hour, 57 minutes ago
Wrong AnswerjavaDecode Ways   2 hours, 2 minutes ago

谢谢各位大佬给分，继续努力 。（周六了，怎么一周又过去了，感觉离动态规划还是很远）
D9：  打卡第9天 (UTC: 11/07/2020)
学习： 数组, 双指针。

数组的题目， index 的 boundary 容易出错；行列的index 也容易出错。

相对于递归，相对简单的题目。
1：merge-sorted-array （88）
  
双指针。
  A：初始化，双指针指向两个数组的末尾。 定义一个index，， 作为当前更新到用于新数组的位置。
  B:比较当前两个数组各指针指向的数字大小，打的存到A index 的位置； index -1; 相应数组指针-1
  C:如果某个数组的指针任然为0，将剩余元素存入A 中index的位置， index -1 ; 相应数组指针-1

2：intersection-of-two-arrays （349）
  很多解法。 还在学习双指针，所以用之。
  A:排序
  B： 双指针，从前往后遍历。 A[i] <B[j]. i 后移。 A[i]> B[j] , j 后移。 相等的时候， 把只加入集合，i,j 后移。
  c: 将集合的元加入结果。

3：sparse-matrix-multiplication （311）
  sparse-matrix:most of the elements are zero.
  
  矩阵相乘： A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][k]*B[k][j] = C[i][j]
  遍历数组的时候，如果是0， continue.

Day 19, solove a problem.

Tips:
LC 78, use backtrack to do it without too much hassle.

打卡第七天 2020.07.11

160 相交链表
315 计算右侧小于当前元素的个数

160 题，这道题要求找到两个单链表值相交的结点，暴力求解的话，算法的时间复杂度就会达到 O(mn)了，题目也提示了可以有 O(n) 的解决方法，然后，想了下，可以用两个指针pA和pB同时遍历两个链表a、b，当pA遍历a链表到尾部时，将pA指针指向链表b的头结点，同理，当pB遍历到b链表尾部时，将pB指针指向链表a的头结点；遍历的终止条件就是pA==pB，最后返回pA；

315 题，这道题看起来比较简单，但是，用普通的暴力法求解，算法的时间复杂度会达到 O(n^2)，应该会超时，最后实在想不出来就看了题解了，插入排序方式的解法能看懂，其他的就有点困难了，后面再研究下。

7.11 day2
217 ，存在重复元素。 简单题
方法1是可对整个list进行两次循环，这样时间复杂度是n的2次方。

方法2是用dict或list来存储已经循环过的元素，循环下一个时，对比是否已经存储过。用dict会更好，dic的查找是O（1）。

打卡第9天
07/11
All Subsets I
All Subsets II (With duplicate)
All Subsets of Size K
All Subsets of Size K II (With duplicate)
Print all valid combination of factors that form an integer
这种题目如果里面有重复的话可以先sort然后如果下个字符和当前不一样的话才继续向下一层走；注意base case

feifeijin 发表于 2020-7-11 22:45
7.11 day2
217 ，存在重复元素。 简单题
方法1是可对整个list进行两次循环，这样时间复杂度是n的2次方。

记得给前面小伙伴加米，谢谢！

day11 #sql 3题
1. 前N项累计和--复表子查询

DAY 6

继续加油⛽️