第四周作业

Jerrydreamaker · Jerrydreamaker · commit 72ed7f89b08f · 2019-07-01T09:15:19.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Week_04/id_28/LeetCode_198_28.java b/Week_04/id_28/LeetCode_198_28.java
@@ -0,0 +1,29 @@
+public class LeetCode_198_28 {
+    public int rob(int[] nums) {
+
+
+        Integer[] arr=new Integer[nums.length];
+        //Integer max=Integer.MIN_VALUE;
+        return nums.length==0 ? 0 : dp(nums,arr,nums.length-1);
+
+    }
+
+    public int dp(int[] nums,Integer[] arr,int i){
+        if(arr[i] == null){
+            if (i==0){
+                arr[i] = nums[0];
+            }else if(i==1){
+                arr[i] = Math.max(nums[0],nums[1]);
+            }else {
+                arr[i]=Math.max(dp(nums,arr,i-2)+nums[i],dp(nums,arr,i-1));
+            }
+        }
+        return arr[i];
+    }
+
+    public static void main(String[] args) {
+        int[] arr= {1,2,3,1};
+        System.out.println(new LeetCode_198_28().rob(arr));
+        System.out.println("hello");
+    }
+}
diff --git a/Week_04/id_28/LeetCode_213_28.java b/Week_04/id_28/LeetCode_213_28.java
@@ -0,0 +1,47 @@
+public class LeetCode_213_28 {
+    public int rob(int[] nums) {
+
+
+        Integer[] arr1=new Integer[nums.length];
+        Integer[] arr2=new Integer[nums.length];
+
+        return nums.length==0 ? 0 : Math.max(dp1(nums,arr1,nums.length-1),dp2(nums,arr2,nums.length-1));
+
+    }
+
+    public int dp1(int[] nums,Integer[] arr,int i){
+        if(arr[i] == null){
+            if (i==0){
+                arr[i] = nums[0];
+            }else if(i==1){
+                arr[i] = nums[0];
+            }else if(i<nums.length-1){
+                arr[i]=Math.max(dp1(nums,arr,i-2)+nums[i],dp1(nums,arr,i-1));
+            }else {
+                arr[i]=dp1(nums,arr,i-1);
+            }
+        }
+        return arr[i];
+    }
+
+
+    public int dp2(int[] nums,Integer[] arr,int i){
+        if(arr[i] == null){
+            if (i==0){
+                arr[i] = 0;
+            }else if(i==1){
+                arr[i] = nums[1];
+            }else {
+                arr[i]=Math.max(dp2(nums,arr,i-2)+nums[i],dp2(nums,arr,i-1));
+            }
+        }
+        return arr[i];
+    }
+
+
+
+    public static void main(String[] args) {
+        int[] arr= {1,2,1,1};
+        System.out.println(new LeetCode_213_28().rob(arr));
+    }
+}
diff --git a/Week_04/id_28/LeetCode_337_28.java b/Week_04/id_28/LeetCode_337_28.java
@@ -0,0 +1,44 @@
+import levelTravel429.Node;
+
+import java.util.*;
+
+public class LeetCode_337_28 {
+
+
+
+    public int rob(TreeNode root) {
+        if(root==null){
+            return 0;
+        }
+        Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
+        return dp(root,map);
+
+    }
+
+    public Integer dp(TreeNode node,Map<TreeNode,Integer> map){
+        if (node==null){
+            return 0;
+        }
+        if(!map.containsKey(node) ){
+            int left=dp(node.left,map);
+            int right=dp(node.right,map);
+            int left_left=(node.left==null? 0:dp(node.left.left,map));
+            int left_right=(node.left==null? 0:dp(node.left.right,map));
+            int right_left=(node.right==null? 0:dp(node.right.left,map));
+            int right_right=(node.right==null? 0:dp(node.right.right,map));
+            map.put(node,Math.max(Math.max(Math.max(left+right,
+                    (node.left==null? 0:node.left.val)+right_left+right_right),
+                    (node.right==null? 0:node.right.val)+left_left+left_right),
+                    node.val+left_left+left_right+right_left+right_right));
+        }
+        System.out.println(map.get(node));
+        return map.get(node);
+    }
+
+    public static void main(String[] args) {
+        TreeNode root=new TreeNode(1);
+        root.left=new TreeNode(2);
+        root.right=new TreeNode(3);
+        System.out.println(new LeetCode_337_28().rob(root));
+    }
+}
diff --git a/Week_04/id_28/LeetCode_53_28.java b/Week_04/id_28/LeetCode_53_28.java
@@ -0,0 +1,34 @@
+public class LeetCode_53_28 {
+
+    public int maxSubArray(int[] nums) {
+
+        int maxArrayLength=Integer.MIN_VALUE;
+        Integer[] arr=new Integer[nums.length];
+        for (int i=0;i<nums.length;i++){
+            maxArrayLength=Math.max(maxArrayLength,max(nums,arr,i));
+
+        }
+        return maxArrayLength;
+    }
+
+
+    public int max(int[] nums,Integer[] arr,int index){
+        if(arr[index]!=null){
+            return arr[index];
+        }
+        if(index==0){
+            arr[0]=nums[0];
+            return nums[0];
+        }else {
+            int ret= Math.max(0,max(nums,arr,index-1)) + nums[index];
+            arr[index] =ret ;
+            return ret ;
+        }
+    }
+
+    public static void main(String[] args) {
+        int[] arr= {-2,1,-3,4,-1,2,1,-5,4};
+        System.out.println(new LeetCode_53_28().maxSubArray(arr));
+    }
+
+}
