- 博客(226)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 数据结构和算法
数据结构和算法是程序设计的基础，最近时常感觉自己这方面的欠缺，决定花费一些业余时间补一补。书架上找到了很久以前买的却没看过的《程序员代码面试指南》，决定尝试用python实现下里面的题目作为练习。学习书中的解题手段，同时练习python。1.栈和队列设计一个有getMin功能的栈由两个栈实现队列如何仅用递归函数和栈操作逆序一个栈猫狗队列用一个栈实现另一个栈的排序用栈求解汗诺塔问题...
2019-10-27 18:18:49
465
原创 luapy (0)
一直想学习点编译、虚拟机相关的东西，最近看到一本有趣的书《自己动手实现Lua：（虚拟机、编译器和标准库）》，作者张秀宏。书中代码用Go实现的，git提供了java实现。本博客以学习本书相关代码为目的，尝试用python3实现简单的Lua编译器、虚拟机。lua binary chunk...
2018-12-16 21:33:57
749
原创 babyos2（0）——从零开始
起因读硕士时曾尝试写一个玩具内核,取名babyos，不料剑走偏锋，玩起了在裸机上绘图，而忽视了操作系统学习中真正精华的部分，后来求职、答辩、毕业、工作，就放下了。然而心里一直记着这回事。近两年对围棋比较有兴趣，本科毕设做过中国象棋AI，自然对Alpha Go很感兴趣。前一阵子Alpha Go Zero刷爆了各种圈，就想学点深度学习的东西，好自己写一个围棋AI玩，当然目标定的比较低，能下过我...
2017-11-10 22:25:54
3226
2
原创 将正方形矩阵顺时针旋转90度
题目给定一个矩阵matrix，把矩阵顺时针转动90度：1 2 34 5 67 8 9->7 4 18 5 29 6 3思路比较简单的思路1）先上下对称->7 8 94 5 61 2 32）对角互换->7 4 18 5 29 6 3实现def rotate(matrix): if matrix is None or len(mat...
2020-01-18 20:05:34
1523
1
原创 转圈打印矩阵
题目给定一个整数矩阵matrix，请按转圈打印的方式打印，如：1 2 34 5 67 8 9打印为：1，2，3，6，9，8，7，4，5思路一圈一圈地打印，每圈打印的时候分四个方向打印，圈之间可以递归，也可以循环。实现1def cycle_print1(matrix): def recursive(matrix, row_beg, row_end, col_beg, col...
2020-01-18 19:39:17
392
原创 字典树（前缀树）的实现
题目字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。假设组成所有单词的字符仅是’a’~'z’的小写字母，请实现字典树结构，包括如下功能：insert，添加word，可重复添加delete，删除word，如果word添加过多次，仅删除一个search，查询word是否在字典树中prefix_number，返回以字符串pre为前缀的单词数量实现import random...
2020-01-17 23:24:24
493
原创 找到指定的新类型字符
题目新型字符定义如下：长度为1或2的字符串可以仅是小写字母，如’e’大写字母+小写字母，如‘Ab’大写字母+大写字母，如’AB‘给定一个字符串s，s一定是若干新型字符组合的结果，比如’eaCCBi’由新型字符’e’, ‘a’, ‘CC’, 'Bi’组成。再给定一个整数k，返回k位置指定的新型字符。s = ‘aaABCDEcBCg’k = 7 -> ‘Ec’k ...
2020-01-16 20:56:36
257
原创 找到字符串的最长无重复字符子串
题目给定一个字符串s，返回s的最长无重复字符子串的长度。例如s = ‘abcd’ -> 4s = ‘aabcb’ -> 3思路记录每个字符前一次出现的位置positios，及到当前字符满足不重复子串的前一个位置prev，遍历字符串过程，遍历到位置i，字符为c，positions[c]为前一个c出现的位置记为prev_c，用prev_c跟prev比较，如果大于prev，则...
2020-01-15 22:56:46
665
原创 括号字符串的有效性和最长有效长度
题目给定一个字符串s，判断是不是整体有效的括号字符串。例如：s = ‘()’ -> Trues = ‘())’ -> False思路遍历字符串，记录待匹配的’(‘的个数count，遇到’(’, count += 1，遇到’)’， count -= 1，如果过程中count < 0，返回False。遍历完成，且count恰好为0，返回True实现def is_v...
2020-01-14 21:27:35
450
原创 数组中两个字符串的最小距离
题目给定一个字符串数组arr，再给定两个字符串s1, s2，返回在arr中，s1与s2的最小距离。如果s1, s2为None或不在arr中，返回-1。例如：arr = [‘1’, ‘3’, ‘3’, ‘3’, ‘2’, ‘3’, ‘1’]s1 = ‘1’s2 = ‘2’返回2arr = [‘CD’]s1 = ‘CD’s2 = ‘AB’返回-1思路用pos1, pos2记录s...
2020-01-12 21:54:46
471
原创 翻转字符串
题目给定字符数组chars，在单词间逆序，对空格位置没有特别要求。例如：‘dog loves pig’ -> ‘pig loves dog’‘I’m a student.’ -> ‘student. a I’m’思路‘dog loves pig’-> ‘gip sevol god’-> ‘pig loves dog’先整体逆序，再按单词逆序。实现1...
2020-01-12 14:48:59
138
原创 字符串的调整与替换
题目给定一个字符类型的数组chars，chars右半区全是空字符，左半区不含空字符。现在想将左半区所有空格替换为’%20’，假设右半区足够大，请完成替换函数。如左半区’a_b___c’ -> ‘a%20b%20%20%20c’思路算出替换后的最右边位置，从右往左替换。实现def replace(s): chars = list(s) n = chars.count...
2020-01-11 21:31:01
548
原创 在有序但有空的数组中查找字符串
题目给定一个字符串数组arr，arr中有些位置为None，但不为None的位置上，字符串有序。给定一个字符串s，返回s在arr中出现的最左的位置。如 arr = [None, ‘a’, None, ‘a’, None, 'b, None, ‘c’]s = ‘a’, 返回1s = None 返回-1s = ‘d’, 返回-1思路尽可能利用二分搜索，但如果二分过程中找到的位置为None，...
2020-01-11 18:38:41
265
原创 判断字符数组中是否所有字符都只出现过一次
题目给定一个字符类型数组，判断数组中是否所有的字符都只出现过一次。要求时间复杂度O(N)思路使用字典存储出现过的字符，遍历数组过程中，判断每一个字符是否出现过实现def is_unique(s): if s is None: return True char_map = {} for c in s: if c in char_m...
2020-01-10 21:38:22
617
原创 字符串的统计字符串
题目给定一个字符串s，返回s 的统计字符串。例如’aaabbadddffc’的统计字符串为’a_3_b_2_a_1_d_3_f_2_c_1’。思路从一个位置beg开始找相同符号，到第一个不同的字符或超出字符串长度end，end-beg为相同字符个数。实现def count_string(s): if s is None or len(s) == 0: return...
2020-01-10 20:50:37
595
原创 替换字符串中连续出现的指定字符
题目给定三个字符串s, f, t，把s中所有f字串替换成t，对连续出现的f要求只替换成一个t。思路把s中出现f的地方先用特殊标记记录下来，然后遍历s，把特殊标记换成t。实现def replace(s, f, t): def clear(chars, beg, end): for i in range(beg, end+1): chars[i...
2020-01-09 21:44:17
216
原创 将整数数字字符串转为整数值
题目给定一个字符串s，如果s符合日常书写的整数形式，并属于32位整数的范围，返回s代表的整数，否则返回0.例如‘123’ -> 123‘023’ -> 0‘A13’ -> 0‘0’ -> 0‘2147483647’ -> 2147483647‘2147483647’ -> 0 (溢出）‘-123’ -> -123思路首先检查s是不...
2020-01-08 23:01:12
1683
原创 判断两个字符串是否互为旋转词
题目一个字符串s，如果把s前面任意部分移到后面形成的字符串叫s 的旋转词。给定字符串s1, s2，判断s1, s2是否互为旋转词。思路如果s1, s2长度不同，一定不互为旋转词；‘123’, ‘231’互为旋转词，可以发现若s2后面再拼一个s2得到’23[123]1’，s1一定是s2s2的字串；实现def is_rotation1(a, b): if a is None or ...
2020-01-07 23:04:21
199
原创 去掉字符串中连续出现k个0的字串
题目给定一个字符串s和一个整数k，如果s中正好有连续的k个’0’字符出现，把k个’0’字符去掉，返回处理后的字符串。如s=‘A00B’，k=2，返回’AB’s=‘A0000B000’，k=3，返回’A0000B’思路维护一个计数count，表示找到几个连续的’0’，维护找到的第一个’0’的位置start，遍历字符串，过程中，找到一个’0’，count += 1，且如果start为-...
2020-01-07 19:53:51
237
原创 字符串中数字子串的求和
题目给定字符串s，求其中全部数字串所代表的数字之和，忽略小数点，如A1.3包含两个数字1，3紧挨着数字的字符若为’-’，出现奇数个’-'数字为负数，否则为偶数例如，A1CD2E33，返回36思路记录几个变量结果 ans当前收集到的数字 num正负, positive遍历字符串，若为数字，根据正负，改变数字num不是数字是‘-’，若前一个字符是’-'则posit...
2020-01-06 23:29:11
291
原创 判断两个字符串是否互为变形词
题目给定两个字符串s1, s2，如果s1, s2中出现的字符种类一样且每种字符出现的次数一样，则s1, s2互为变形词。判断s1, s2是否为变形词。如“123”, "231"互为变形词“123”, “2331” 不互为变形词思路遍历s1，统计每个字符个数，遍历s2，每个字符，s1字符个数统计对应字符-1，若减到负数，说明个数不匹配，返回False。遍历完成则返回True实现f...
2020-01-05 22:17:37
306
1
原创 调整搜索二叉树的两个错误的节点
题目一棵二叉查找树，其中两个节点的值调换了位置，找出这两个错误节点。TreeNodeclass TreeNode(): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightBinarySea...
2020-01-05 12:13:07
630
原创 在二叉树中找到累加和为指定值的最长路径长度
在二叉树中找到累加和为指定值的最长路径长度题目给定一棵二叉树根节点root和一个正数k，二叉树节点值类型为整型，求累加和为k的最长路径。路径是指从根节点到任意一个节点的路径的子路径。-33-9102116例如k=6，可以找到从根的一条路径 [-3, 3, 0, 6]k=-9，可以找到从根的一条路径-3, [-9]，子路径-9满足和为-9.k=3，可以找到从根的一条路径-3, [3,...
2020-01-05 11:52:06
436
原创 未排序整数数组中累加和为给定值的最长子数组长度
未排序整数数组中累加和为给定值的最长子数组长度题目给定一个无序数组arr，其元素可正，可负，可为0，给定一个整数k，求arr所有的子数组中，累加和为k的最长子数组长度。思路构建一个映射关系map[sum] = index, 表示[0, index] 子数组的累加和为sum，且index是sum最早出现的位置。从头遍历数组并求累加和，假设当前累加和为current，假如current-k在...
2020-01-04 22:07:38
343
原创 未排序正数数组中累加和为给定值的最长子数组长度
未排序正数数组中累加和为给定值的最长子数组长度题目给定一个无序正整数数组arr及一个正数k，求arr的所有子数组中元素相加和为k的最长子数组长度。思路两个指针left, right，可以表示子数组[left, right], current是子数组的和，若current小于k，right右移若current大于k，left左移若current等于k，更新结果def max_le...
2020-01-03 23:25:17
328
原创 找到二叉树中的最大二叉搜索子树
找到二叉树中的最大二叉搜索子树题目给定一棵二叉树的根节点root，已知其中所有节点值都不一样，找到含有节点最多的搜索二叉子树，返回该子树的根节点。01234561011121314151620例如上图表示的二叉树，最大的二叉搜索子树为10为根节点的子树。思路后续遍历过程中，当遍历到cur节点时，从左右子树收集最大二叉子树的根节点该子树的节点树该子树中的最小值该子树中的最大值...
2020-01-01 20:36:07
677
原创 打印二叉树边界节点
打印二叉树边界节点二叉树节点class TreeNode(): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def is_leaf(self): return ...
2019-12-31 22:33:42
238
原创 在二叉树中找到两个节点的最近公共祖先
在二叉树中找到两个节点的最近公共祖先题目给定一棵二叉树的头节点root，以及这棵树中的两个节点node1, node2，返回node1, node2的最近公共祖先节点。TreeNode"""Data Structures And Algorithms find lowest ancestor of tow nodes in a binary tree"""import ran...
2019-12-30 22:13:27
957
原创 判断 t1 树中是否含有与 t2 树拓扑结构完全相同的子树
判断 t1 树中是否含有与 t2 树拓扑结构完全相同的子树题目给定两棵树t1, t2的根节点root1, root2，判断t1中是否有与t2拓扑结构完全相同的子树。思路其实就是判断t2是不是t1的子树，可以得到两棵树的先序序列s1和s2，判断s2是不是s1的子串。TreeNode"""Data Structures And Algorithms: check if tree2...
2019-12-29 21:45:00
419
原创 根据后序数组重建搜索二叉树
根据后序数组重建搜索二叉树题目BST 用于测试class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = Noneclass BST(): def __init__(self, root=None): ...
2019-12-28 20:26:11
319
原创 Your python3 install is corrupted. Please fix the '/usr/bin/python3' symlink.
升级Ubuntu遇到下面问题：Your python3 install is corrupted. Please fix the ‘/usr/bin/python3’ symlink.被错误提示误导了，以为是python3链接有问题，试了好几个办法，都没解决问题，➜ ~ cat /var/log/dist-upgrade/main.log2019-12-24 20:51:02,719 I...
2019-12-24 21:11:08
6780
3
原创 判断 t1 树是否包含 t2 树全部的拓扑结构
判断 t1 树是否包含 t2 树全部的拓扑结构题目给定两棵树的根节点root1和root2，判断root1树是否包含root2树的全部拓扑结构。如：3214None21None返回True思路满足条件的情况：root1.val == root2.val，且由根root1能找到root2的所有拓扑结构root1的左子树包含root2的所有拓扑结构root1的右子树包含root2...
2019-12-22 21:46:10
158
原创 二叉树的序列化和反序列化
二叉树的序列化和反序列化题目已知二叉树节点值类型为32位整型，序列化和反序列化该树。class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None self.parent = NoneBSTcl...
2019-12-20 20:23:55
104
原创 在二叉树中找到一个节点的后继节点
在二叉树中找到一个节点的后继节点题目假设二叉搜索树节点带有父节点指针：class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None self.parent = None给定二叉搜索树上一个节点n...
2019-12-19 22:09:49
202
原创 如何较为直观地打印二叉树
如何较为直观地打印二叉树题目给定一棵二叉树，实现一个较为直观地打印方法BST（用于测试）class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None self.parent = Nonecl...
2019-12-17 22:23:29
390
原创 二叉树节点间的最大距离问题
二叉树节点间的最大距离问题求二叉树两节点间的最大距离（可能过根节点，也可能不过），LeetCode 543思路最大距离可能来自三种情况：根节点左子树上的最大距离根节点右子树上的最大距离左孩子最大深度ldepth，到根节点，到右孩子最大深度rdepth实现1 def max_distance(self): def post_order(node): ...
2019-12-16 21:17:42
261
原创 先序、中序和后序数组两两结合重构二叉树
先序、中序和后序数组两两结合重构二叉树题目已知一棵二叉树所有节点值都不同，1）给定先序、中序序列，2）给定中序、后序序列3）给定先序、后序序列重构二叉树BST实现先实现一棵二叉排序树用于测试import operatorclass TreeNode(): def __init__(self, val): self.val = val ...
2019-12-15 21:10:09
153
原创 统计和生成所有不同的二叉树
统计和生成所有不同的二叉树题目给定一个整数n，如果n<1，代表空树，否则代表中序遍历的结果为1,2,3…n，求可能的二叉树结构有多少。例如：n=-1表示空树，返回1n=2，中序遍历的1，2，满足的二叉树有：1null2nullnull1null2nullnull思路假设f(n)表示中序遍历序列为1,2…n可表示的二叉树数目，该树一定是二叉搜索树。则1,2,…n都可以表示根节...
2019-12-11 23:01:07
434
原创 通过有序数组生成平衡搜索二叉树
通过有序数组生成平衡搜索二叉树题目给定一个有序数组，其中没有重复值，生成一棵平衡二叉搜索树，要求该树中序遍历结果跟给定的有序数组一致。思路思路比较简单，找到中间元素做根节点，左边的递归生成左子树，右边的递归生成右子树。实现class TreeNode(): def __init__(self, key, val): self.key = key ...
2019-12-08 19:04:58
174
原创 通过先序和中序数组生成后续数组
通过先序和中序数组生成后续数组问题已知一棵二叉树所有的节点值都不同，给定先序和中序序列，不重建二叉树，生成后序序列。如：preorder: 1 2 4 5 3 6 7inorder: 4 2 5 1 6 3 7=>postorder: 4 5 2 6 7 3 1思路preorder: 1 2 4 5 3 6 7inorder: 4 2 5 1 6 3 7先序序列的...
2019-11-30 23:26:05
522
Qt 真三装备连连看
2012-12-23
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人