记录一下这个难过的双休，2019.3.16-2019.3.17，16号上午字节跳动笔试，四道题只做出1道半，输入输出搞的半死，第三题类似于leetcode上的分糖问题，数组初始化的时候全部赋为0了，要是赋维1就做出来了，唉，气死了。17号下午做两道深搜的题目，全都死在java引用上面了，卡了一下午多，现在想想c++的指针是多么的方便。

　　下午的两道题分别是牛客网和leetcode上的深度优先搜索，这两道题套路完全一样。

　　1.二叉树中和为某一值的路径：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

　　这道题的解法详见下面，其中有个问题就是java中值和址的问题。

　　这里要详细说明。首先如果传的是int等基本数据类型和string，那么你使用下面的方法是改变不了a的值的：

1 class Solution{ 2     public void fun(int a){ 3         a++; 4     } 5     public static void main(String []args){ 6         int a=1; 7         fun(a); 8         System.out.println(a); 9         //这里会输出a=110     }11 }

　　而其他的类都是传地址的，也就是说在函数外面定义TreeNode1=root，函数定义fun(TreeNode2){}，这时候其实两个TreeNode是不一样的两个东西，只是指向的东西一样而已。也就是说你在函数里面是有可能改变这个类里面的某些属性的，比如在函数里面写TreeNode2.val=2，那么真正的val真的变成了2。但是如果你在函数里面令TreeNode2=root2，那么只是函数里面的TreeNode2换了一个东西指了而已，函数外面的TreeNode1还是指向的root。

　　例如在ArrayList<ArrayList<Integer>> ans中加入一个ArrayList temp，先add一个为【1，2】的temp，然后改变temp，变为【1，2，3】，再add。但是这时候ans里面的数据是【1，2，3】【1，2，3】，为什么呢，因为temp传的是地址，也就是说当temp改变为【1，2，3】之后，其实是temp指向的那块地方的东西变成了【1，2，3】，所以之前已经add进ans的数据也一起改变为【1，2，3】了。要解决这个问题，就要在每次add前新建一个ArrayList，把temp克隆过去clone，这样的话每个ArrayList指向的就是两个地址，其中一个改变不会影响令一个。

1 import java.util.ArrayList; 2 /** 3 public class TreeNode { 4     int val = 0; 5     TreeNode left = null; 6     TreeNode right = null; 7  8     public TreeNode(int val) { 9         this.val = val;10 11     }12 13 }14 */15 public class Solution {16     public ArrayList
     
      
       > FindPath(TreeNode root,int target) {17         if(root==null)18             return new ArrayList
       
        
         >();19         ArrayList
         
          
           > ans =new ArrayList
           
            
             >();20 ArrayList
             
               temp=new ArrayList
              
               ();21 help(root,target,ans,temp);22 //System.out.println(ans.get(0).size());23 24 for(int i=0;i
               
                ans.get(j).size()){27 ArrayList
                
                  temp2;28 temp2=ans.get(j);29 ans.set(j,ans.get(i));30 ans.set(i,temp2);31 }32 33 }34 }35 return ans;36 }37 void help(TreeNode root,int target,ArrayList
                 
                  
                   > ans,ArrayList
                   
                     temp){38 //System.out.println("aaaa");39 if(root==null){40 //temp.remove(temp.size()-1);41 return;42 }43 temp.add(root.val);44 45 if(root.val==target && root.right==null && root.left==null){ 46 ArrayList
                    
                      te=new ArrayList
                     
                      ();47 te=(ArrayList
                      
                       )temp.clone();48 ans.add(te);49 temp.remove(temp.size()-1);50 return;51 }52 if(root.val!=target && root.right==null && root.left==null){53 temp.remove(temp.size()-1);54 return;55 }56 help(root.left,target-root.val,ans,temp);57 help(root.right,target-root.val,ans,temp);58 temp.remove(temp.size()-1);59 return;60 61 62 }63 }
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

　　2.79：Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

　　这道题有两个坑，一个是if(i>=0 && i<board.length && j>=0 && j<board[0].length && board[i][j]==word.charAt(num) && flag[i][j]==0)中，有可能会造成数组越界的判断条件放前面，不然会造成数组越界。第二个，如果你想减少一部分java引用带来的困扰，就要使用回溯法，这点很重要。

1 class Solution3 { 2     int ans=0; 3     public boolean exist(char[][] board, String word) { 4         int n=board.length; 5         int m=board[0].length; 6         int[][] flag3=new int [n][m]; 7         int num=0; 8         if(n==0) 9             return false;10         for(int i=0;i
     
      =0 && i
      
       =0 && j