8 孤舟钓客

尚未进行身份认证

人生如梦,梦何曾醒?不过旧愁新怨。但无他。回首向来萧瑟处,也无风雨也无晴。夜阑风静彀纹平,小舟从此逝,江海寄馀生。

等级
TA的排名 9k+

将正方形矩阵顺时针旋转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

转圈打印矩阵

题目给定一个整数矩阵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

字典树(前缀树)的实现

题目字典树又称为前缀树或Trie树,是处理字符串常见的数据结构。假设组成所有单词的字符仅是’a’~'z’的小写字母,请实现字典树结构,包括如下功能:insert,添加word,可重复添加delete,删除word,如果word添加过多次,仅删除一个search,查询word是否在字典树中prefix_number,返回以字符串pre为前缀的单词数量实现import random...

2020-01-17 23:24:24

找到指定的新类型字符

题目新型字符定义如下:长度为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

找到字符串的最长无重复字符子串

题目给定一个字符串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

括号字符串的有效性和最长有效长度

题目给定一个字符串s,判断是不是整体有效的括号字符串。例如:s = ‘()’ -> Trues = ‘())’ -> False思路遍历字符串,记录待匹配的’(‘的个数count,遇到’(’, count += 1,遇到’)’, count -= 1,如果过程中count < 0,返回False。遍历完成,且count恰好为0,返回True实现def is_v...

2020-01-14 21:27:35

数组中两个字符串的最小距离

题目给定一个字符串数组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

翻转字符串

题目给定字符数组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

字符串的调整与替换

题目给定一个字符类型的数组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

在有序但有空的数组中查找字符串

题目给定一个字符串数组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

判断字符数组中是否所有字符都只出现过一次

题目给定一个字符类型数组,判断数组中是否所有的字符都只出现过一次。要求时间复杂度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

字符串的统计字符串

题目给定一个字符串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

替换字符串中连续出现的指定字符

题目给定三个字符串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

将整数数字字符串转为整数值

题目给定一个字符串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

判断两个字符串是否互为旋转词

题目一个字符串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

去掉字符串中连续出现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

字符串中数字子串的求和

题目给定字符串s,求其中全部数字串所代表的数字之和,忽略小数点,如A1.3包含两个数字1,3紧挨着数字的字符若为’-’,出现奇数个’-'数字为负数,否则为偶数例如,A1CD2E33,返回36思路记录几个变量结果 ans当前收集到的数字 num正负, positive遍历字符串,若为数字,根据正负,改变数字num不是数字是‘-’,若前一个字符是’-'则posit...

2020-01-06 23:29:11

判断两个字符串是否互为变形词

题目给定两个字符串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

调整搜索二叉树的两个错误的节点

题目一棵二叉查找树,其中两个节点的值调换了位置,找出这两个错误节点。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

在二叉树中找到累加和为指定值的最长路径长度

在二叉树中找到累加和为指定值的最长路径长度题目给定一棵二叉树根节点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

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。