Google intern 面经

You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.

vector* FindPermute(const string& signature);

和这题 http://www.careercup.com/question?id=14912744 类似？

这面经发的也是醉了 一堆人才半天猜出来是什么个意思  。。。

第二题我的代码：

1. void findWiggle(String path) {
   
2.         ListNode fakeHead = new ListNode(0);
   
3.         //start from 1
   
4.         fakeHead.next = new ListNode(1);
   
5.         ListNode iInsert = fakeHead.next;
   
6.         ListNode dInsert = fakeHead;
   
7.         for (int i = 0; i < path.length(); i++) {
   
8.                 if (path.charAt(i) == 'i') {
   
9.                         iInsert.next = new ListNode(i+2);
   
10.                         iInsert = iInsert.next;
    
11.                         dInsert = dInsert.next;
    
12.                 } else {
    
13.                         dInsert.next = new ListNode(i+2);
    
14.                 }
    
15.         }
    
16.         print(fakeHead.next);
    
17. }

复制代码

achilleszou 发表于 2016-11-5 07:40
第二题我的代码：

这对吗？dddddddd怎么处理

qeroqero 发表于 2016-11-6 00:40
这对吗？dddddddd怎么处理

code 少些了一行，用ide 写了一下：

1. 
   
2. class ListNode {
   
3.     int val;
   
4.     ListNode next;
   
5.     ListNode(int val ) {
   
6.         this.val = val;
   
7.     }
   
8. }
   
9. public class Solution {
   
10.     public void print(ListNode node) {
    
11.         while(node != null) {
    
12.             System.out.print(node.val + ",");
    
13.             node = node.next;
    
14.         }
    
15.         System.out.println();
    
16.     }
    
17.     public void findWiggle(String path) {
    
18.         ListNode fakeHead = new ListNode(0);
    
19.         //start from 1
    
20.         fakeHead.next = new ListNode(1);
    
21.         ListNode iInsert = fakeHead.next;
    
22.         ListNode dInsert = fakeHead;
    
23.         for (int i = 0; i < path.length(); i++) {
    
24.             if (path.charAt(i) == 'i') {
    
25.                 iInsert.next = new ListNode(i+2);
    
26.                 iInsert = iInsert.next;
    
27.                 dInsert = dInsert.next;
    
28.             } else {
    
29.                 ListNode tmp =  dInsert.next;
    
30.                 dInsert.next = new ListNode(i+2);
    
31.                 dInsert.next.next = tmp;
    
32.             }
    
33.         }
    
34.         print(fakeHead.next);
    
35.     }
    
36. }
    

复制代码

跑出来是 8,7,6,5,4,3,2,1,

achilleszou 发表于 2016-11-6 03:03
code 少些了一行，用ide 写了一下：跑出来是 8,7,6,5,4,3,2,1,

没太懂。可以稍微解释一下吗？这是贪心？

MicX 发表于 2016-11-6 21:38
没太懂。可以稍微解释一下吗？这是贪心？

1,...n 可以满足任何 长度为n-1 的 类似于 ddididid 这样的wiggle sequence，问题是如何构造。

我用的的是链表，如果当前的字符是i，就把数字放到最后，如果是d，就把当前数字放到最近的i的位置

时间O(n) 空间O(1) (如果结果可以用链表表示的话)，应该是最优解吧

signature是什么完全没看懂...

achilleszou 发表于 2016-11-8 01:28
1,...n 可以满足任何 长度为n-1 的 类似于 ddididid 这样的wiggle sequence，问题是如何构造。

我用的 ...

你的解答没太看懂，能不能讲具体点？谢谢