<
查看: 657|回复: 17
收起左侧

刷题打卡记录

|只看干货
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
如题,
希望能在明年六月前刷完400道题。 每天都会更新进度和总结。

上一篇:金融学生强行转码实录 女人也要顶起半边天
下一篇:找同學一起開zoom刷題,寫代碼
 楼主| Liumiuniuniuniu 2020-12-27 05:22:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
day 1 - 12/26/2020

bubble sort
参考了 https://stackabuse.com/bubble-sort-in-python/

Bubble Sort is one of the worst-performing sorting algorithms in every case except checking whether the array is already sorted, where it often outperforms more efficient sorting algorithms like Quick Sort.
In the most inefficient approach, Bubble Sort goes through n-1 iterations, looking at n-1 pairs of adjacent elements. This gives it the time complexity of O(n2), in both best-case and average-case situations. O(n2) is considered pretty horrible for a sorting algorithm.
It does have an O(1) space complexity, but that isn't enough to compensate for its shortcomings in other fields.

最简单的达到 O(n^2) 的implementation:
[Python] 纯文本查看 复制代码
def bubbleSort(array):
    for i in range(len(array) - 1):
		for j in range(0, len(array) - 1):
			if array[j + 1] < array[j]:
				array[j + 1], array[j] = array[j], array[j + 1]
	return array

注意到 在任意一次iteration内, 假如 当j > swapEnd时, 所有的j,j+1都不需要交换, 则swapEnd之后都是有序排列的, 但是swapEnd之前的数组还可能是乱序。
例如 5, 2, 1, 6, 7
一次iteration之后变成 2,1,5, 6, 7. 这里swapEnd 的index是 1.

经过optimization 的版本, optimize了 loop i 的终止条件 和 loop j的终止条件
[Python] 纯文本查看 复制代码
def bubbleSort(array):
	hasSwapped = True
    swapEnd = len(array) - 1
	while(hasSwapped):
		hasSwapped = False
		for j in range(swapEnd):
			if array[j] > array[j + 1]:
				array[j], array[j + 1] = array[j + 1], array[j]
				hasSwapped = True
				swapEnd = j
	return array
回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-27 05:39:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
本帖最后由 Liumiuniuniuniu 于 2020-12-27 05:42 编辑

day 1 - 12/26/2020
selection sorting

Time Complexity: O(n^2) in best/average/worst scenarios as there are two nested loops.
Auxiliary Space: O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

this sorting method is not stable.
[Python] 纯文本查看 复制代码
def selectionSort(array):
    for i in range(len(array)):
                minIdx = i
                for j in range(i + 1, len(array)):                        
                        if array[j] < array[minIdx]:
                                minIdx = j
                if minIdx != i:
                        array[i], array[minIdx] = array[minIdx], array[i]
        return array

回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-27 10:12:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
day 1 - 12/26/2020
insertion sort

insertion sort is stable
best time complexity O(n), space complexity O(1)
average time complexity O(n^2), space complexity O(1)
worst time complexity O(n^2), space complexity O(1)

[Python] 纯文本查看 复制代码
def insertionSort(array):
    for i in range(1, len(array)):
		current = array[i]
		j = i - 1
		while j >= 0 and array[j] > current:
			array[j + 1] = array[j]
			j -= 1
		array[j + 1] = current
	return array
回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-27 14:40:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
day1 - 12/26/2020

sorting
bubble sort
insertion sort
selection sort
three number sort
quick sort
heap sort
marge sort

pending item:
implementation of heap
回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-28 10:41:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
本帖最后由 Liumiuniuniuniu 于 2020-12-28 11:27 编辑

day2 - 12/27/2020

今日主题 stack
刷题有:
Find the n largest number
Sunset Views
Min Max stack construction
Balanced Brackets
Shorten path  注意 tokens = str.split()    "/".join(my_list)

顺便刷的简单题:two sum number
validate subsequence
binary search
palindrome check
caesar cipher encryptor 注意 chr 和 ord function的用法
run-length encoding


pending items:comparison of sorting algorithm
implementation of heap
implementation of stack and queue, (python 中list的api)
python中string的api


回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-29 13:57:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
本帖最后由 Liumiuniuniuniu 于 2020-12-29 14:20 编辑

day3 - 12/28/2020
刷题
branch sum  分治 和 递归
Find Closest in BST  递归 和  遍历
Node Depths 递归 和 BST
product sum 注意 type(item) is list 的用法

pending items:
comparisonofsortingalgorithm
implementationofheap
implementationofstackandqueue(python中list的api)
python中string的api



回复

使用道具 举报

 楼主| Liumiuniuniuniu 2020-12-30 12:47:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
本帖最后由 Liumiuniuniuniu 于 2020-12-30 12:49 编辑

day 3 - 12/29/2020

今日刷题
nth Fibonacci 注意这道题可以用decorator来做memoize
depth first search
Three number sum 加强版的two sum
smallest difference
move element to end
monotonic array
array of products
first duplicate value 注意把 number 当idx的用法basic calculator 这道题有点难 肯定要重刷的

pending item
还是那些 哎 没啥心情做 希望周末可以做完

今天把naive的都清掉了 希望可以早日把easy清掉 坚持哇

回复

使用道具 举报

 楼主| Liumiuniuniuniu 2021-1-4 13:08:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
day5 - 1/4/2021

没想到一晃过去了那么多天。。。 目前只坚持了leetcode的每日一题。没有再额外刷题了 要加强时间管理啊
回复

使用道具 举报

 楼主| Liumiuniuniuniu 2021-1-6 13:37:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
DAY6 - 1/6/2020

做了每日一题 每天效率好低 明天加油哇
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表