0343 new algo added.

liuyubobobo · liuyubobobo · commit 10890c4de22f · 2019-07-24T16:48:12.000-07:00
diff --git a/0343-Integer-Break/cpp-0343/CMakeLists.txt b/0343-Integer-Break/cpp-0343/CMakeLists.txt
@@ -3,5 +3,5 @@ project(cpp_0343)
 
 set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
 
-set(SOURCE_FILES main.cpp)
+set(SOURCE_FILES main3.cpp)
 add_executable(cpp_0343 ${SOURCE_FILES})
diff --git a/0343-Integer-Break/cpp-0343/main.cpp b/0343-Integer-Break/cpp-0343/main.cpp
@@ -44,6 +44,7 @@ class Solution {
     }
 };
 
+
 int main() {
 
     cout << Solution().integerBreak(2) << endl;
diff --git a/0343-Integer-Break/cpp-0343/main2.cpp b/0343-Integer-Break/cpp-0343/main2.cpp
@@ -33,6 +33,7 @@ class Solution {
     }
 };
 
+
 int main() {
 
     cout << Solution().integerBreak(2) << endl;
diff --git a/0343-Integer-Break/cpp-0343/main3.cpp b/0343-Integer-Break/cpp-0343/main3.cpp
@@ -0,0 +1,45 @@
+/// Source : https://leetcode.com/problems/integer-break/description/
+/// Author : liuyubobobo
+/// Time   : 2019-07-24
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+/// Dynamic Programming
+/// Deal with 2, 3 and 4 seperately
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(n)
+class Solution {
+
+public:
+    int integerBreak(int n) {
+
+        assert(n >= 1);
+        if(n == 2) return 1;
+        if(n == 3) return 2;
+
+        vector<int> memo(n + 1, -1);
+        memo[0] = 0;
+        memo[1] = 1;
+        memo[2] = 2;
+        memo[3] = 3;
+        for(int i = 2 ; i <= n ; i ++)
+            for(int j = 1 ; j <= i / 2 ; j ++)
+                memo[i] = max(memo[i], memo[j] * memo[i - j]);
+
+        return memo[n];
+    }
+};
+
+
+int main() {
+
+    cout << Solution().integerBreak(2) << endl;
+    cout << Solution().integerBreak(3) << endl;
+    cout << Solution().integerBreak(4) << endl;
+    cout << Solution().integerBreak(10) << endl;
+
+    return 0;
+}
diff --git a/0343-Integer-Break/java-0343/src/Solution3.java b/0343-Integer-Break/java-0343/src/Solution3.java
@@ -0,0 +1,34 @@
+/// Source : https://leetcode.com/problems/integer-break/description/
+/// Author : liuyubobobo
+/// Time   : 2019-07-24
+
+/// Dynamic Programming
+/// Deal with 2, 3 and 4 seperately
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(n)
+public class Solution3 {
+
+    public int integerBreak(int n) {
+
+        if(n < 1)
+            throw new IllegalArgumentException("n should be greater than zero");
+        if(n == 2) return 1;
+        if(n == 3) return 2;
+
+        int[] memo = new int[n+1];
+        memo[1] = 1;
+        memo[2] = 2;
+        memo[3] = 3;
+        for(int i = 2 ; i <= n ; i ++)
+            for(int j = 1 ; j <= i / 2 ; j ++)
+                memo[i] = Math.max(memo[i], memo[j] * memo[i - j]);
+
+        return memo[n];
+    }
+
+    public static void main(String[] args) {
+
+        System.out.println((new Solution2()).integerBreak(2));
+        System.out.println((new Solution2()).integerBreak(10));
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -44,6 +44,7 @@ class Solution {`
`44`	`44`	`}`
`45`	`45`	`};`
`46`	`46`
	`47`	`+`
`47`	`48`	`int main() {`
`48`	`49`
`49`	`50`	`cout << Solution().integerBreak(2) << endl;`
Original file line number	Diff line number	Diff line change
`@@ -33,6 +33,7 @@ class Solution {`
`33`	`33`	`}`
`34`	`34`	`};`
`35`	`35`
	`36`	`+`
`36`	`37`	`int main() {`
`37`	`38`
`38`	`39`	`cout << Solution().integerBreak(2) << endl;`