有人知道GG的short survey and coding sample 是神马么

早知道好好看论坛了！

liranxixi 发表于 2015-11-24 06:17
我也觉得按理说需要dfs 但是就给的格式而言我不知道怎么判定directory的结构啊~其实我还是没搞懂输入是啥 ...

我就是根据空格看是否是上级目录，你这样，把这个这个string在“\n”处split，变成一个string[], 然后一行行输出每一个string[i]，格式就清晰了

6zy 发表于 2015-11-24 08:22
我就是根据空格看是否是上级目录，你这样，把这个这个string在“\n”处split，变成一个string[], 然后一 ...

你已经做了呀？哦哦，我懂了，就是通过空格的数量来决定层级关系喽~

liranxixi 发表于 2015-11-24 11:41
你已经做了呀？哦哦，我懂了，就是通过空格的数量来决定层级关系喽~

我大概试了试，发现dfs实现起来很困难，要判断的条件太多了，正考虑其他方法

SallyWu 发表于 2015-11-24 07:24
早知道好好看论坛了！

那求问第二题怎么做你知道么？是dfs么？

我是自己定义了一个树节点类，然后根据缩进parse成树，然后对树进行dfs
感觉这个题主要难在写parser，如果成功parse成树的话，对树遍历就很容易很容易。有点像是体力活的感觉。

    public static int[] duplicateNumber(int[] input){
            int[] result = new int[input.length+1];
            if(input == null ||input.length == 0) return new int[0];
            if(input.length == 1) return new int[]{input[0],input[0]};
            int i = 0;
            int j = 0;
. 1point 3 acres            while(i < input.length - 1){
                    if(input[i] <= input[i+1]) {
                            result[j++] = input[i++];
                    }
                    else{
                            result[j++] = input[i];
                            while(j < result.length)
                                    result[j++] = input[i++];
                            return result;
                           
                    }
                   
            }
            result[j] = input[input.length - 1];
            result[j+1] = input[input.length - 1];
            return result;
    }

菠萝君 发表于 2015-11-25 08:49
public static int[] duplicateNumber(int[] input){
            int[] result = new int;
            if(input = ...

-baidu 1point3acres第一题我也是这么做的~你知道第二题应该咋做么？

static int max = Integer.MIN_VALUE;
    public class TreeNode{
            String val;
            LinkedList<TreeNode> children;
            TreeNode parent;
            int indexOfStart;
           
            public TreeNode(String val,TreeNode parent, int indexOfStart){
                    this.val = val;
                    children = new LinkedList<TreeNode>();
                    this.parent = parent;
                    this.indexOfStart = indexOfStart;
            }
    }
   
    public   TreeNode parseString(String str){
            if(str == null || str.length() == 0) return null;
            String[] string = str.split("\n");
            TreeNode root = new TreeNode("",null,-1);
            TreeNode current = root;
              for(String s :string){
                    int j = 0;
                    while(s.charAt(j) == ' '){
                            j++;
                    }
                    TreeNode temp = new TreeNode(s, current, j);
                    if(j == current.indexOfStart+1){
                            current.children.add(temp);
                    }
                    else{
                            while(j != current.indexOfStart+1){
                                    current = current.parent;
                            }
                            current.children.add(temp);
                    }
                    current = temp;
            }
              return root;
    }
   
    public static void helper(TreeNode root,int length){
            length += root.val.length() - root.indexOfStart;
            if(length > max){
                    max = length;
                    System.out.println(root.val);
                    System.out.println(max);
            }
            for(int i = 0; i < root.children.size(); i++){
                    helper(root.children.get(i),length+1);
            }
    }

就是建一个tree 然后dfs 搜索 最后返回max

下午同学写了，第一题的输入实际上是一个int 所以要把每一个数字拆出来。第二题的话他好像要求只是jpeg png 和gif 后缀的，所以在我的代码基础上加一个后缀的判断就好了，不是这个后缀的直接就不放到tree里就好了。这个代码应该是没有问题的

菠萝君 发表于 2015-11-25 11:50
static int max = Integer.MIN_VALUE;
    public class TreeNode{
            String val;

好赞！我也在想是不是应该用树dfs，但是还要自己建个树……如果我用一个stack来实现可以么，就是通过空格数量来进行层级判断。比如这样：
public class Solution {
        public int longestPath(String files) {
                if(files == null || files.length() == 0) return 0;
                String[] strs = files.split("\n");
                Stack<String> stack = new Stack<>();
                stack.push(strs[0]);
                int count = strs[0].length()+1;
                int max = count;
                int space = 0;
                for(int i=1; i<strs.length; i++) {
                        for(int j=0; j<strs[i].length(); j++) {
                                if(strs[i].charAt(j) == ' ') {
                                        space++;
                                }
                                else break;
                        }
                        if(space == stack.size()) {
                                if(strs[i].contains(".")) {
                                        max = Math.max(max, (strs[i].contains("jpeg")||strs[i].contains("gif"))?count+strs[i].length()-space:0);
                                }
                                else {
                                        stack.push(strs[i]);
                                        count += strs[i].length()+1-space;
                                }
                        }
                        else if(space < stack.size()) {
                                while(space < stack.size()) {
                                        String temp = stack.pop();
                                        count -= temp.length()+1-space;
                                }
                                stack.push(strs[i]);
                                count += strs[i].length()+1-space;
                        }
                        space = 0;
                }
                return max;
. Χ        }
}