A. 两个single linked list,每一个节点里面一个0-9的数字,输入就相当于两个大数
了。然后返回这两个数的和(一个新list)。这两个输入的list长度相等。
当时的要求是:1. 不用递归。2.然后要求算法在最好的情况下,只遍历两个list一次
。最差的情况下两遍。
当时让我首先说说什么情况2遍,什么情况1遍,然后开始写。这个题目看上去不难,但
是写起来挺考验基本功的。大家准备面试练习的时候可以写写。
B. Count Inversions
http://www.geeksforgeeks.org/counting-inversions/
刚开始想到这个解法,但是有个坎没绕过去,觉得有些情况下处理不了,后来经过沟通
发现其实可以。
A. 第一题比较简单,是leetcode上有的。若是逆序排列的话,那么就一级一级往上算,搞个count当进位。若是顺序的话,就需要两遍,因为single linked list只能往一边走。所以我的思路是,先计算第一遍,把和都存在一个数组里面,假如可以有额外空间的话,都不用再遍历第二遍,直接处理这个数组就好了。就能得出值,但若要inplace, 不能给additional space, 那么只能再走一遍。这个时候要注意9+9等于18的情况。
B. 此题就是找一个un sorted array里面,顺序不对的element对。比如2,4,1,3,5 就有 [2,1],[4,1],[4,3]三对。
brute force O(n^2)这里就不说了。
网上有一种叫enhanced merge sort,就是recursively bottom up, 先把数组分两边,叫left, right。左边有一个元素a[i]比右边数组的一个元素a[j]大的,那么a[i]到a[mid]全是inversions. 这个时候左右 两边都是sorted的,因为是从最地层一路做上来的,每次找到的inversion count都相加。
http://www.geeksforgeeks.org/counting-inversions/
Subscribe to:
Post Comments (Atom)
Leetcode 316. Remove Duplicate Letters
这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...
-
首先声明一下,这里的面试题主要所指数据结构和算法的题目,题目的分析集中在Leetcode上面的题目上。 我认为一道面试题由以下几个方面组成的 Question Data structure in question Data structure in solutio...
-
Given an array A of integer with size of n( means n books and number of pages of each book) and k people to copy the book. You must distribu...
-
1166. Design File System Medium 62 4 Add to List Share You are asked to design a file system which provides two functions: crea...
No comments:
Post a Comment