2.编程题一道:两个无序单向链表,求第n大的数的value或者是node,我直接暴力做的val(遍历2个链表的val到vector然后排序,然后输出第n大的),然后面试官又让做返回node(map(val,node)存储,然后同上)
询问链表是否是有序的,假如链表是有序的,那么等价于Leetcode 4题, 可以在log(n)时间解决,从语境分析,应该是被面试者没get到点。
题目
7个晶体管上的灯的亮暗可以组成0-9的任意一个数字。假设有n组晶体管,每组晶体管中至少有一个亮,可能存在坏了的晶体管。
假设有2组晶体管,第一组是数字2,因为有坏了的可能, 2->2,2->8;其可能为2/8;第2组是数字3,其可能为3/8/9
由此可以组成{23,28,29,83,88,89}
input:n个7位数,即有n组晶体管
output:组成的数字,例如本题的{23,28,29,83,88,89}
典型的回溯暴搜,填n个位置,每个位置有若干的填法,时间复杂度是O(d^n)