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

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

剑指Offer原题，不利用API或者暴力统计的话，稍微扩展一种巧妙的解法吧。刚好面试的时候也要求用位运算用小于O(n)的方法求解。  注意python2.7不能有中文注释  n = int(raw_input()) # Notice: raw_input() for python 2.7 cnt = 0 while n: # 复杂度会小于二进制的总位数 n = n & (n-1) # 每次可将最右边的1消去 cnt += 1 print(cnt)

模拟+贪心   因为存在一元硬币，一定可以找清，所以直接贪心  N = int(input()) remain, cnt = 1024-N, 0 coins = [64, 16, 4] # coins which values greater than 1 for i in range(len(coins)): c = remain//coins[i] cnt += c remain -= c*coins[i] print(remain + cnt)   动态规划  若可能不能找清，或不存在1元硬币这种简单情况，用动态规划会更合适。 N = int(input()) remain = 1024...

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

【Python15行】提供另一种思路：考虑使用队列+二进制编码来解，复杂度O(n)。贪心作为常规思路，在文末附上。 首先，枚举每三位可能的情况：    取【.】为1、【X】为0， 编成二进制，则点灯和不点等的情况为:  点灯： 4 5 6 7不点： 0 1 2 3  构建一个队列，从左往右扫描入列，当队列达到三位时进行判断，若为不点灯的情况直接出列，否则清空队列、点灯计数器加一。 Tip：编成二进制的做法只是为了方便阅读，可选。   算法核心： def calc(path): compile_bin = lambda li: int(''.join(queue), 2) # 二进制编码转十进制...

python20行，O(n)算法，无额外空间开销。需要两个辅助函数：  reverse(h, k)：给定一个头节点和k，反转至多k个节点，返回反转后的头节点、下一段的头节点和已反转数； reverse_k(head, k):按K个每组反转链表，返回反转后的头节点；    reverse(h, k)就是单纯反转链表，没什么可说的； reverse_k(head, k)需要加一个判断，调用reverse(h, k)进行反转后，如果本组反转量小于k个，则再次调用reverse(h, k)撤销反转，详见代码。     首先是给出链表的数据结构和读题目的IO，并根据IO构建链表，没什么好说的，大家都能写...

更健壮的做法是，应当留意将导致前一天起床的极端输入(尽管本题约束此类情况不会发生)。python 20行可解决。 把小时数和分钟数直接化成用分钟计时；遍历闹钟组，选出不会导致迟到的闹钟，筛选最晚的闹钟即可。【复杂度O(n)】 # 做一个一天72小时的虚拟，即所有时钟全部加24小时，直接覆盖昨今明三天 # 主要是为了避免需要在前一天起床的情况 N = int(input()) clocks = [] for _ in range(N): Hi, Mi = map(int, input().split()) # 闹钟响起的时分 clocks.append((Hi+24, Mi)) X = int(...

简单问题，可以进行推广：其一，本题中只有三个数，因此直接枚举；其二，若有n个数，则是个dp问题。 # 3个数直接枚举 from functools import reduce a, b, c = map(int, input().split()) all_plus = sum([a, b, c]) all_multi = reduce(lambda i,j: i*j, [a, b, c]) res = [all_plus, all_multi, a+b*c, a*b+c, (a+b)*c, a*(b+c)] print(max(res))  写出其动态转移方程：  # 若有n个数，则是dp问题...

思路：dfs+剪枝。(见代码)要注意的是同样的思路python由于递归上限的问题过不了，因此需要手动设置sys.setrecursionlimit()。 import sys # python 默认递归深度不超过1000，做dfs会比C吃亏 sys.setrecursionlimit(10000000)# 手动修改深度，如果TLE那就是算法的问题 # 小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M) N = int(input()) arr = list(map(int, input().split())) # sum(arr) = M M, res = sum(a...

Python30行解决 思路 ——  for 0~9 循环找出应当相同的数字为same_number：即对每一位进行abs()计算，排序代价选前K个并求和；记录最小值和此时对应的same_number。(详见代码及其中注释) 因为要满足字典序最小输出，分析可得 —— 数字nums[i]变为same_number时，满足临界代价的数字(即代价等于前K个代价的最大值的那几个数字)需要进行判断：若是由小变大，则应从后往前扫逐个变化；否则直接变化即可。   N, K = map(int, input().split()) nums = list(map(int, [i for i in input()...