algorithm-programming/algorithmPublic

NotificationsYou must be signed in to change notification settings
Fork0
Star1

Commit3a21bea

ssjssh

committed

1,完成leecode的第三题，第四题还有bug

2,把所有的代码放在ssj包下，因为一些包的命名跟python自带库明名重复，可能会出现一些意想不到的问题。

1 parent36d8774 commit3a21beaCopy full SHA for 3a21bea

File tree

94 files changed

+154

-2079

lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

94 files changed

+154

-2079

lines changed

`‎src/leecode/init.pyrenamed to‎src/ssj/init.py`

File renamed without changes.

`‎src/clrs/9/9-2(b).pyrenamed to‎src/ssj/clrs/9/9-2(b).py`

File renamed without changes.

`‎src/clrs/9/9-2(c).pyrenamed to‎src/ssj/clrs/9/9-2(c).py`

File renamed without changes.

`‎src/clrs/9/init.pyrenamed to‎src/ssj/clrs/9/init.py`

File renamed without changes.

`‎src/clrs/init.pyrenamed to‎src/ssj/clrs/init.py`

File renamed without changes.

`‎src/divide_conquer/init.pyrenamed to‎src/ssj/divide_conquer/init.py`

File renamed without changes.

`‎src/divide_conquer/find_max_sublist.pyrenamed to‎src/ssj/divide_conquer/find_max_sublist.py`

Lines changed: 5 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -13,17 +13,17 @@`
`13`	`13`	`deffind_max_sublist(li):`
`14`	`14`	`li_len=len(li)`
`15`	`15`	`ifli_len<2:`
`16`		`-return(0,0,sum(li))`
	`16`	`+return0,0,sum(li)`
`17`	`17`	`middle=li_len/2`
`18`	`18`	`m_x,m_y,m_sum=find_max_in_middle(li,middle)`
`19`	`19`	`l_x,l_y,l_sum=find_max_sublist(li[:middle])`
`20`	`20`	`r_x,r_y,r_sum=find_max_sublist(li[middle+1:])`
`21`	`21`	`ifm_sum>=l_sumandm_sum>=r_sum:`
`22`		`-return(m_x,m_y,m_sum)`
	`22`	`+returnm_x,m_y,m_sum`
`23`	`23`	`elifl_sum>=m_sumandl_sum>=r_sum:`
`24`		`-return(l_x,l_y,l_sum)`
	`24`	`+returnl_x,l_y,l_sum`
`25`	`25`	`else:`
`26`		`-return(r_x,r_y,r_sum)`
	`26`	`+returnr_x,r_y,r_sum`
`27`	`27`
`28`	`28`
`29`	`29`	`"""`
`@@ -53,7 +53,7 @@ def find_max_in_middle(li, middle):`
`53`	`53`	`right_max_sum=cur_sum`
`54`	`54`	`right_max_index=x`
`55`	`55`	`# 这里并没有判断一端结果为负的情况，因为这个时候可以在其中一端的列表中得到最大子数列`
`56`		`-return(left_max_index,right_max_index,right_max_sum+left_max_sum)`
	`56`	`+returnleft_max_index,right_max_index,right_max_sum+left_max_sum`
`57`	`57`
`58`	`58`
`59`	`59`	`defmain():`

`‎src/divide_conquer/find_max_sublist_without_ recursion.pyrenamed to‎src/ssj/divide_conquer/find_max_sublist_without_ recursion.py`

File renamed without changes.

`‎src/divide_conquer/power.pyrenamed to‎src/ssj/divide_conquer/power.py`

File renamed without changes.

`‎src/divide_conquer/yong_matrix.pyrenamed to‎src/ssj/divide_conquer/yong_matrix.py`

File renamed without changes.

`‎src/dynamic/init.pyrenamed to‎src/ssj/dynamic/init.py`

File renamed without changes.

`‎src/dynamic/fabo/init.pyrenamed to‎src/ssj/dynamic/fabo/init.py`

File renamed without changes.

`‎src/dynamic/fabo/fabo_loop.pyrenamed to‎src/ssj/dynamic/fabo/fabo_loop.py`

File renamed without changes.

`‎src/dynamic/fabo/fabo_math.pyrenamed to‎src/ssj/dynamic/fabo/fabo_math.py`

File renamed without changes.

`‎src/dynamic/fabo/fabo_up_down.pyrenamed to‎src/ssj/dynamic/fabo/fabo_up_down.py`

File renamed without changes.

`‎src/dynamic/lcs/init.pyrenamed to‎src/ssj/dynamic/lcs/init.py`

File renamed without changes.

`‎src/dynamic/lcs/down_up.pyrenamed to‎src/ssj/dynamic/lcs/down_up.py`

File renamed without changes.

`‎src/dynamic/lcs/up_down.pyrenamed to‎src/ssj/dynamic/lcs/up_down.py`

File renamed without changes.

`‎src/dynamic/lps/init.pyrenamed to‎src/ssj/dynamic/lps/init.py`

File renamed without changes.

`‎src/dynamic/lps/down_up.pyrenamed to‎src/ssj/dynamic/lps/down_up.py`

File renamed without changes.

`‎src/dynamic/lps/up_down.pyrenamed to‎src/ssj/dynamic/lps/up_down.py`

File renamed without changes.

`‎src/dynamic/task/init.pyrenamed to‎src/ssj/dynamic/task/init.py`

File renamed without changes.

`‎src/dynamic/task/max_weighted_action.pyrenamed to‎src/ssj/dynamic/task/max_weighted_action.py`

File renamed without changes.

`‎src/graph/init.pyrenamed to‎src/ssj/graph/init.py`

File renamed without changes.

`‎src/graph/general_graph.pyrenamed to‎src/ssj/graph/general_graph.py`

Lines changed: 2 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -6,8 +6,8 @@`
`6`	`6`	`reload(sys)`
`7`	`7`	`sys.setdefaultencoding('UTF-8')`
`8`	`8`
`9`		`-fromlibimportqueue`
`10`		`-fromlib.stackimportStack`
	`9`	`+fromssj.libimportqueue`
	`10`	`+fromssj.libimportStack`
`11`	`11`
`12`	`12`	`__author__='shenshijun'`
`13`	`13`

`‎src/graph/weighted_graph.pyrenamed to‎src/ssj/graph/weighted_graph.py`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,6 @@`
`1`	`1`	`#!/usr/bin/env python`
`2`	`2`	`# -*- coding:UTF-8`
`3`		`-fromlib.queueimportQueue`
	`3`	`+fromssj.libimportQueue`
`4`	`4`
`5`	`5`	`__author__='shenshijun'`
`6`	`6`	`"""`

`‎src/greedy/init.pyrenamed to‎src/ssj/greedy/init.py`

File renamed without changes.

`‎src/greedy/max_task_count.pyrenamed to‎src/ssj/greedy/max_task_count.py`

File renamed without changes.

`‎src/heap/init.pyrenamed to‎src/ssj/heap/init.py`

File renamed without changes.

`‎src/heap/max_heap.pyrenamed to‎src/ssj/heap/max_heap.py`

File renamed without changes.

`‎src/heap/max_queue.pyrenamed to‎src/ssj/heap/max_queue.py`

File renamed without changes.

`‎src/string/init.pyrenamed to‎src/ssj/leecode/init.py`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,3 @@`
`1`	`1`	`#!/usr/bin/env python`
`2`		`-#-*- coding:UTF-8`
	`2`	`+#-*- coding:UTF-8`
`3`	`3`	`__author__='shenshijun'`

`‎src/leecode/add_two_numbers.pyrenamed to‎src/ssj/leecode/add_two_numbers.py`

File renamed without changes.

`‎src/ssj/leecode/find_median_sorted_arrays.py`

Lines changed: 86 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,86 @@`
	`1`	`+#!/usr/bin/env python`
	`2`	`+# -*- coding:UTF-8`
	`3`	`+__author__='shenshijun'`
	`4`	`+"""`
	`5`	`+There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).`
	`6`	`+"""`
	`7`	`+"""`
	`8`	`+思路一:遍历一遍就可以把两个数组排序,然后取中点的值就可以了,这样的复杂度是O(m+n)`
	`9`	`+思路二:排序显然做了许多无用功,因为只需要一个中间数就可以了`
	`10`	`+参考:http://www.cnblogs.com/lichen782/p/leetcode_Median_of_Two_Sorted_Arrays.html`
	`11`	`+可以分成四种情况考虑`
	`12`	`+1,两个列表都没有数据,那么返回0`
	`13`	`+2,两个列表中只有一个列表有数据,那么返回其中一个列表的中间点`
	`14`	`+3,两个列表中的一个列表整体大于另一个列表,那么可以在逻辑上把这两个列表合并起来求出合并后的中点`
	`15`	`+4,问题可以简化成从两个排序列表中求出第k个数,也就是从两个数组的开头取出k个数字,这k个数字比留在数组中的数字要小`
	`16`	`+那么可以开始从两个数组中取出k/2的数字(这样做每次可以把问题的规模减小一半,整体的复杂度也就是指数级的),`
	`17`	`+比较k/2位置处数字的大小,小的那一部分一定是在k小的数字之内(可以假设法证明),这样剩下的问题就是从剩下的列表中找`
	`18`	`+第k/2位数了.等到这个数为1,那么就好计算了.`
	`19`	`+`
	`20`	`+"""`
	`21`	`+`
	`22`	`+`
	`23`	`+classSolution(object):`
	`24`	`+deffindMedianSortedArrays(self,nums1,nums2):`
	`25`	`+"""`
	`26`	`+ :type nums1: List[int]`
	`27`	`+ :type nums2: List[int]`
	`28`	`+ :rtype: float`
	`29`	`+ """`
	`30`	`+ifnotnums1:`
	`31`	`+returnself.__findMedian(nums2)`
	`32`	`+elifnotnums2:`
	`33`	`+returnself.__findMedian(nums1)`
	`34`	`+elifnotnums1andnotnums2:`
	`35`	`+return0`
	`36`	`+`
	`37`	`+len1=len(nums1)`
	`38`	`+len2=len(nums2)`
	`39`	`+`
	`40`	`+if (len1+len2)%2is0:`
	`41`	`+return (self.__findKth((len1+len2)/2+1,nums1,nums2)+self.__findKth((len1+len2)/2,nums1,`
	`42`	`+nums2))/2.0`
	`43`	`+else:`
	`44`	`+returnself.__findKth((len1+len2)/2+1,nums1,nums2)`
	`45`	`+`
	`46`	`+@staticmethod`
	`47`	`+def__findMedian(li):`
	`48`	`+median=len(li)/2`
	`49`	`+iflen(li)%2is0:`
	`50`	`+return (li[median]+li[median-1])/2.0`
	`51`	`+else:`
	`52`	`+returnli[median]`
	`53`	`+`
	`54`	`+@staticmethod`
	`55`	`+def__findKth(k,l1,l2):`
	`56`	`+l1_start=0`
	`57`	`+l2_start=0`
	`58`	`+k-=1`
	`59`	`+while (len(l1)+len(l2)-l1_start-l2_start-1)>=k:`
	`60`	`+ifkis0:`
	`61`	`+returnmin(l1[l1_start],l2[l2_start])`
	`62`	`+iflen(l1)-l1_start<len(l2)-l2_start:`
	`63`	`+l1_comp_start=l1_start+min(len(l1),k/2)`
	`64`	`+l2_comp_start=k-min(len(l1),k/2)+l2_start`
	`65`	`+else:`
	`66`	`+l2_comp_start=min(len(l2),k/2)+l2_start`
	`67`	`+l1_comp_start=k-min(len(l2),k/2)+l1_start`
	`68`	`+`
	`69`	`+ifl1[l1_comp_start]>l2[l2_comp_start]:`
	`70`	`+k-= (l2_comp_start-l2_start)`
	`71`	`+l2_start=l2_comp_start+1`
	`72`	`+elifl1[l1_comp_start]<l2[l2_comp_start]:`
	`73`	`+k-= (l1_comp_start-l1_start)`
	`74`	`+l1_start=l1_comp_start+1`
	`75`	`+else:`
	`76`	`+returnl1[l1_comp_start]`
	`77`	`+return0`
	`78`	`+`
	`79`	`+`
	`80`	`+defmain():`
	`81`	`+print(Solution().findMedianSortedArrays([0,1,2,3,4], [0,1,2]))# 1`
	`82`	`+print(Solution().findMedianSortedArrays([], [1]))#`
	`83`	`+`
	`84`	`+`
	`85`	`+if__name__=="__main__":`
	`86`	`+main()`

`‎src/ssj/leecode/longest_substring.py`

Lines changed: 58 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,58 @@`
	`1`	`+#!/usr/bin/env python`
	`2`	`+# -*- coding:UTF-8`
	`3`	`+__author__='shenshijun'`
	`4`	`+`
	`5`	`+"""`
	`6`	`+Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.`
	`7`	`+"""`
	`8`	`+`
	`9`	`+"""`
	`10`	`+思路:使用两个指针来遍历字符串,他们之间的字符是不重复的字符.前面的指针每次前进一步都会判断新扫描的字符是不是和两个指针的间的字符重复`
	`11`	`+s a f b r g r e g`
	`12`	`+ ^ ^`
	`13`	`+ \| \|index`
	`14`	`+start_index`
	`15`	`+为了这个目的,使用了哈希表.`
	`16`	`+如果重复,那么就找到一个连续的非重复字符串,这里就是afbrg(index现在在r的位置),判断这个字符串长度和已有的最大长度的大小,`
	`17`	`+并且记录下最大值.发生重复之后的处理非常重要,是把前面重复的部分丢弃掉,这样后面的字符串还是一个非重复的字符串(start_index在g的位置)`
	`18`	`+这样的目的是尽量构建一个长的非重复字符串`
	`19`	`+`
	`20`	`+如果没有重复,那么就把字符和对应的索引放入哈希表,以备后面使用`
	`21`	`+`
	`22`	`+如果限定了字符集,那么可以使用数组来模拟哈希表,这样的效率更高.`
	`23`	`+"""`
	`24`	`+`
	`25`	`+`
	`26`	`+classSolution(object):`
	`27`	`+deflengthOfLongestSubstring(self,s):`
	`28`	`+"""`
	`29`	`+ :type s: str`
	`30`	`+ :rtype: int`
	`31`	`+ """`
	`32`	`+ifnots:`
	`33`	`+return0`
	`34`	`+tmp_dict= {}`
	`35`	`+# 字符串不为空,因此最小值是1`
	`36`	`+max_length=1`
	`37`	`+start_index=0`
	`38`	`+forindex,chinenumerate(s):`
	`39`	`+ifchintmp_dict:`
	`40`	`+ifmax_length<index-start_index:`
	`41`	`+max_length=index-start_index`
	`42`	`+dup_index=tmp_dict[ch]`
	`43`	`+foriinrange(start_index,dup_index+1):`
	`44`	`+deltmp_dict[s[i]]`
	`45`	`+start_index=dup_index+1`
	`46`	`+tmp_dict[ch]=index`
	`47`	`+# 注意结束的时候如果没有重复,那么会安静退出循环而不发生任何比较,所以在退出循环的时候要比较`
	`48`	`+returnlen(tmp_dict)iflen(tmp_dict)>max_lengthelsemax_length`
	`49`	`+`
	`50`	`+`
	`51`	`+defmain():`
	`52`	`+print(Solution().lengthOfLongestSubstring("bbbbbb"))# 1`
	`53`	`+print(Solution().lengthOfLongestSubstring("abcabcbb"))# 3`
	`54`	`+print(Solution().lengthOfLongestSubstring("dvdfefqwfqwef"))# 3`
	`55`	`+`
	`56`	`+`
	`57`	`+if__name__=="__main__":`
	`58`	`+main()`

`‎src/leecode/two_sum.pyrenamed to‎src/ssj/leecode/two_sum.py`

File renamed without changes.

`‎src/lib/init.pyrenamed to‎src/ssj/lib/init.py`

File renamed without changes.

`‎src/lib/queue.pyrenamed to‎src/ssj/lib/queue.py`

File renamed without changes.

`‎src/lib/set.pyrenamed to‎src/ssj/lib/set.py`

File renamed without changes.

`‎src/lib/stack.pyrenamed to‎src/ssj/lib/stack.py`

File renamed without changes.

`‎src/list/init.pyrenamed to‎src/ssj/list/init.py`

File renamed without changes.

`‎src/list/linked_list.pyrenamed to‎src/ssj/list/linked_list.py`

File renamed without changes.

`‎src/list/mutiarray_linkedlist.pyrenamed to‎src/ssj/list/mutiarray_linkedlist.py`

File renamed without changes.

`‎src/list/skip_list.pyrenamed to‎src/ssj/list/skip_list.py`

File renamed without changes.

`‎src/list/stack.pyrenamed to‎src/ssj/list/stack.py`

File renamed without changes.

`‎src/map/init.pyrenamed to‎src/ssj/map/init.py`

File renamed without changes.

`‎src/map/hash_map.pyrenamed to‎src/ssj/map/hash_map.py`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -12,7 +12,7 @@ class HashMap(object):`
`12`	`12`	`# 来自算法导论乘法哈希函数的值,暂时仅支持2**32个元素`
`13`	`13`	`HASH_CONST=2654435769`
`14`	`14`	`DEFAULT_SIZE_POWER=3`
`15`		`-DEFAULT_SIZE=2<<DEFAULT_SIZE_POWER#aka16`
	`15`	`+DEFAULT_SIZE=2<<DEFAULT_SIZE_POWER#aka8`
`16`	`16`	`DEFAULT_LOAD_FACTOR=0.75# 默认装载因子0.75`
`17`	`17`
`18`	`18`	`classNode(object):`