白色高跟鞋

题解

/ 注册

全部文章 / 题解（共24篇）

2020快手：判断一棵满二叉树是否为二叉搜索树[python][数据结构][树的性质]

讲真没必要那么麻烦真的去构建一棵树，直接利用二叉搜索树的性质，python十几行就结束了。满二叉树：深度为n时共2^n-1个节点二叉搜索树：左节点所有<=根节点<所有右节点核心思路：中序遍历二叉搜索树应单调递增 (由题意知道节点最小值为0，因此预设pre为-1)；同时，...

2020-04-29

6 1497

2020网易：访友[python][动态规划][贪心]

贪心：未到达终点前每一次走的越远越好；由于步数从1~5，不担心直接越过终点，所以直接对五求商向上取整就好。不过这种题目假设给个能否走到的变体条件可能就要靠动态规划才比较好解了。 from math import ceil x = int(input()) print(ceil(x/5)) 动态规...

2020-04-29

1 5543

2020经典DP题目：连续子数组最大和[python][动态规划]

DP的核心思想是，如果以i为终止序号的某个连续序列最大和小于0，那么下一个输入加上一个负数必然小于此输入，于是干脆另起炉灶直接赋值改输入；否则，则一个正数加上该输入，最终结果都要比单纯使用该输入要大。【即把连续序列的和直接当成一个数跟下一个输入进行对比】 N = int(input()) dp = ...

2020-04-29

1 1491

2020网易：矩形重叠[python][数组][数学]

目前想到两种解法，分别为O(n^3)和O(n^2~n^2*ln)，python 7/20行以内搞定。先说简单易理解的方法(7行)0：取所有的矩形角点，对每个角点取所有矩形；判断角点是否在矩形内，特别的，角点在边界上时只应当判断左半边。 n = int(input()) x1s, y1s =...

2020-04-28

5 6405

2020招商银行信用卡中心：推倒吧骨牌[python][数组]

两种解法(35行/13行，复杂度都是O(n))： python35行O(n)：统一向左和向右倒下叠加两个数组判断最终状态 def build_seq(s, flag='R', stop='L', start=0, end=-1, step=1): # flag 开始倒的标志 ...

2020-04-28

2 1187

2020快手：二进制中有多少个1[python][位运算]

剑指Offer原题，不利用API或者暴力统计的话，稍微扩展一种巧妙的解法吧。刚好面试的时候也要求用位运算用小于O(n)的方法求解。注意python2.7不能有中文注释 n = int(raw_input()) # Notice: raw_input() for python 2.7 cnt =...

2020-04-27

1 836

2020字节跳动：找零[python][动态规划][贪心]

模拟+贪心因为存在一元硬币，一定可以找清，所以直接贪心 N = int(input()) remain, cnt = 1024-N, 0 coins = [64, 16, 4] # coins which values greater than 1 for i in range(len(co...

2020-04-27

6 1220

2020字节跳动：万万没想到之聪明的编辑[python][队列][正则][自动机]

解法一：队列+枚举 def repair(s): # AABB -> AAB | AAA -> A queue, res = [], [] for i in s: queue.append(i) if len(queue)==4: ...

2020-04-27

25 1941

2020网易：安置路灯[python][队列][贪心]

【Python15行】提供另一种思路：考虑使用队列+二进制编码来解，复杂度O(n)。贪心作为常规思路，在文末附上。首先，枚举每三位可能的情况：取【.】为1、【X】为0，编成二进制，则点灯和不点等的情况为: 点灯： 4 5 6 7不点： 0 1 2 3 构建一个队列，从左往右扫描入列...

2020-04-27

1 6049

2020小红书：每K个一组反转链表[python][递归]

python20行，O(n)算法，无额外空间开销。需要两个辅助函数： reverse(h, k)：给定一个头节点和k，反转至多k个节点，返回反转后的头节点、下一段的头节点和已反转数； reverse_k(head, k):按K个每组反转链表，返回反转后的头节点； reverse(h, k)就...

2020-04-26

1 952