{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 规定\n",
"\n",
"## 锚点\n",
"\n",
"- () : 插入一行\n",
"- [] : 插入多行\n",
"- <- : 注意，一定不能错"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 二分查找(binary-search-template)\n",
"\n",
"```java\n",
"public class Solution{\n",
" public int binarySearch(int[] nums, int target){\n",
" if(nums == null && nums.length == 0)return -1;\n",
" \n",
" int start = 0;\n",
" int end = nums.length - 1;\n",
" int mid;\n",
" \n",
" while(start + 1 < end){\n",
" mid = start + (end - start) / 2;\n",
" if(nums[mid] > target){\n",
" end = mid;\n",
" }else if(nums[mid] < target){\n",
" start = mid;\n",
" }else{\n",
" end = mid;\n",
" }\n",
" }\n",
" \n",
" if(nums[start] == target){\n",
" return start;\n",
" }\n",
" if(nums[end] == target){\n",
" return end;\n",
" }\n",
" \n",
" return -1;\n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"hidden": true
},
"outputs": [
{
"ename": "SyntaxError",
"evalue": "invalid syntax (<ipython-input-1-a2c9ccf424d4>, line 1)",
"output_type": "error",
"traceback": [
"\u001b[0;36m File \u001b[0;32m\"<ipython-input-1-a2c9ccf424d4>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m public class Solution{\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
]
}
],
"source": [
"public class Solution{\n",
" public int binarySearch(int[] nums, int target){\n",
" if(nums == null && nums.length == 0)return -1;\n",
" \n",
" int start = 0;\n",
" int end = nums.length - 1;\n",
" int mid;\n",
" \n",
" while(start + 1 < end){\n",
" mid = start + (end - start) / 2;\n",
" if(nums[mid] > target){\n",
" end = mid;\n",
" }else if(nums[mid] < target){\n",
" start = mid;\n",
" }else{\n",
" end = mid;\n",
" }\n",
" }\n",
" \n",
" if(nums[start] == target){\n",
" return start;\n",
" }\n",
" if(nums[end] == target){\n",
" return end;\n",
" }\n",
" \n",
" return -1;\n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 宽度优先搜索(bfs_template)\n",
"```java\n",
"public class Solution{\n",
" public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){\n",
" ArrayList result = new ArrayList();\n",
" \n",
" if(root == null){\n",
" return result;\n",
" }\n",
" \n",
" Queue<TreeNode> queue = new LinkedList<TreeNode>();\n",
" queue.offer(root);\n",
" \n",
" while(!queue.isEmpty()){\n",
" ArrayList<Integer> level = new ArrayList<Integer>();\n",
" int size = queue.size();\n",
" for(int i = 0; i < size; i++) {\n",
" TreeNode head = queue.poll();\n",
" level.add(head.val);\n",
" if(head.left != null){\n",
" queue.offer(head.left);\n",
" }\n",
" if(head.right != null){\n",
" queue.offer(head.right);\n",
" }\n",
" }\n",
" result.add(level);\n",
" }\n",
" \n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"hidden": true
},
"outputs": [],
"source": [
"public class Solution{\n",
" public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){\n",
" ArrayList result = new ArrayList();\n",
" \n",
" if(root == null){\n",
" return result;\n",
" }\n",
" \n",
" Queue<TreeNode> queue = new LinkedList<TreeNode>();\n",
" queue.offer(root);\n",
" \n",
" while(!queue.isEmpty()){\n",
" ArrayList<Integer> level = new ArrayList<Integer>();\n",
" int size = queue.size();\n",
" for(int i = 0; i < size; i++) {\n",
" TreeNode head = queue.poll();\n",
" level.add(head.val);\n",
" if(head.left != null){\n",
" queue.offer(head.left);\n",
" }\n",
" if(head.right != null){\n",
" queue.offer(head.right);\n",
" }\n",
" }\n",
" result.add(level);\n",
" }\n",
" \n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 深度优先搜索(dfs_template)\n",
"\n",
"## Template 1: Traverse\n",
"```java\n",
"public class Solution{\n",
" public void traverse(TreeNode root){\n",
" if(root == null){\n",
" return;\n",
" }\n",
" // do something with root\n",
" traverse(root.left);\n",
" // do something with root\n",
" traverse(root.right);\n",
" // do something with root\n",
" }\n",
"}\n",
"```\n",
"## Template 2: Divide & Conquer\n",
"```java\n",
"public class Solution{\n",
" public ResultType traversal(TreeNode root){\n",
" // null or left\n",
" if(root == null){\n",
" // do something and return;\n",
" }\n",
" \n",
" // Divide 问题分解\n",
" ResultType left = traversal(root.left);\n",
" ResultType right = traversal(root.right);\n",
" \n",
" // Conquer 问题合并\n",
" ResultType result = Merge from left and right\n",
" return result;\n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"hidden": true
},
"outputs": [],
"source": [
"# Template 1: Traverse\n",
"\n",
"public class Solution{\n",
" public void traverse(TreeNode root){\n",
" if(root == null){\n",
" return;\n",
" }\n",
" // do something with root\n",
" traverse(root.left);\n",
" // do something with root\n",
" traverse(root.right);\n",
" // do something with root\n",
" }\n",
"}\n",
"\n",
"# Template 2: Divide & Conquer\n",
"\n",
"public class Solution{\n",
" public ResultType traversal(TreeNode root){\n",
" // null or left\n",
" if(root == null){\n",
" // do something and return;\n",
" }\n",
" \n",
" // Divide 问题分解\n",
" ResultType left = traversal(root.left);\n",
" ResultType right = traversal(root.right);\n",
" \n",
" // Conquer 问题合并\n",
" ResultType result = Merge from left and right\n",
" return result;\n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 二叉树递归遍历(binary_tree_preorder_traversal_template)\n",
"```java\n",
"public class Solution {\n",
"\n",
"\n",
" //模板\n",
" public ArrayList<Integer> preorderTraversal(TreeNode root) {\n",
" ArrayList<Integer> result = new ArrayList<Integer>();\n",
" traversal(root, result);\n",
" return result;\n",
" }\n",
"\n",
"\n",
" public void traversal(TreeNode root, ArrayList<Integer> result) {\n",
" if (root == null) {\n",
" return;\n",
" }\n",
" //do sth with the root(eg:print visit result.add(root.val);) 前序这一行\n",
" traversal(root.left, result);\n",
" //do sth with the root(eg:print visit result.add(root.val);) 中序在一样\n",
" traversal(root.right, result);\n",
" //do sth with the root(eg:print visit result.add(root.val);) 后序在者一样\n",
" }\n",
"}\n",
"\n",
"class TreeNode {\n",
" int val;\n",
" TreeNode left;\n",
" TreeNode right;\n",
"\n",
" TreeNode(int x) {\n",
" val = x;\n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"hidden": true
},
"outputs": [],
"source": [
"public class Solution {\n",
"\n",
"\n",
" //模板\n",
" public ArrayList<Integer> preorderTraversal(TreeNode root) {\n",
" ArrayList<Integer> result = new ArrayList<Integer>();\n",
" traversal(root, result);\n",
" return result;\n",
" }\n",
"\n",
"\n",
" public void traversal(TreeNode root, ArrayList<Integer> result) {\n",
" if (root == null) {\n",
" return;\n",
" }\n",
" //do sth with the root(eg:print visit result.add(root.val);) 前序这一行\n",
" traversal(root.left, result);\n",
" //do sth with the root(eg:print visit result.add(root.val);) 中序在一样\n",
" traversal(root.right, result);\n",
" //do sth with the root(eg:print visit result.add(root.val);) 后序在者一样\n",
" }\n",
"}\n",
"\n",
"class TreeNode {\n",
" int val;\n",
" TreeNode left;\n",
" TreeNode right;\n",
"\n",
" TreeNode(int x) {\n",
" val = x;\n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 动态规划(dynamic_programing_template)\n",
"```java\n",
"public class Solution {\n",
"//DP的题型在leetcode里一共有几种\n",
"//1.矩阵DP matrix（eg 机器人左上到右下 triangle）\n",
"//2. 1维DP sequence （eg word break ， jump game）\n",
"//3. 2维DP 2sequence （eg edit distan等把A词变成B词的）\n",
"//4. Interval (eg merge interval, insert interval)\n",
"//\n",
"//所以 这几类题 要怎么做呢\n",
"//1. status \n",
"// Matrix : f[i][j] 从1,1走到i,j ...\n",
"// Sequence : f[i] 前i个 ***\n",
"// 2 Sequences : f[i][j] word1前i个匹配上word前j个 *** \n",
"// Interval : f[i][j] 表示区间i-j ***\n",
"\n",
"//2.Transfer DP 推导过程\n",
"//LCS: f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1) longest common sequence\n",
"// LIS: f[i] = max(f[j] + 1, a[i] >= a[j]) longest increasing sequence\n",
"// 分析最后一次划分/最后一个字符/最后***\n",
"\n",
"//3. initialize 初始状态\n",
"// f[i][0] f[0][i]\n",
"// f[0]\n",
"// LIS: f[1..n] = 1;\n",
"\n",
"//4. answer \n",
"// LIS: max{f[i]}\n",
"// LCS: f[n][m]\n",
"\n",
"\n",
"//5. loop \n",
"// Interval: 区间从小到大，先枚举区间长度. Palindrome Patitioning II \n",
"\n",
"\n",
"\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"hidden": true
},
"outputs": [
{
"ename": "SyntaxError",
"evalue": "invalid syntax (<ipython-input-2-11e0e90ddae5>, line 1)",
"output_type": "error",
"traceback": [
"\u001b[0;36m File \u001b[0;32m\"<ipython-input-2-11e0e90ddae5>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m public class Solution {\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
]
}
],
"source": [
"public class Solution {\n",
"//DP的题型在leetcode里一共有几种\n",
"//1.矩阵DP matrix（eg 机器人左上到右下 triangle）\n",
"//2. 1维DP sequence （eg word break ， jump game）\n",
"//3. 2维DP 2sequence （eg edit distan等把A词变成B词的）\n",
"//4. Interval (eg merge interval, insert interval)\n",
"//\n",
"//所以 这几类题 要怎么做呢\n",
"//1. status \n",
"// Matrix : f[i][j] 从1,1走到i,j ...\n",
"// Sequence : f[i] 前i个 ***\n",
"// 2 Sequences : f[i][j] word1前i个匹配上word前j个 *** \n",
"// Interval : f[i][j] 表示区间i-j ***\n",
"\n",
"//2.Transfer DP 推导过程\n",
"//LCS: f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1) longest common sequence\n",
"// LIS: f[i] = max(f[j] + 1, a[i] >= a[j]) longest increasing sequence\n",
"// 分析最后一次划分/最后一个字符/最后***\n",
"\n",
"//3. initialize 初始状态\n",
"// f[i][0] f[0][i]\n",
"// f[0]\n",
"// LIS: f[1..n] = 1;\n",
"\n",
"//4. answer \n",
"// LIS: max{f[i]}\n",
"// LCS: f[n][m]\n",
"\n",
"\n",
"//5. loop \n",
"// Interval: 区间从小到大，先枚举区间长度. Palindrome Patitioning II \n",
"\n",
"\n",
"\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true
},
"source": [
"# 排列组合(permute_template)\n",
"\n",
"## 所有排列组合类的做法\n",
"```java\n",
"public class Solution {\n",
"\n",
" public ArrayList<Integer> permute(int[] num){\n",
" Arrays.sort(num);\n",
" ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();\n",
" ArrayList<Integer> path=new ArrayList<Integer>();\n",
" permuteHelper(results,path,num/*?*/);\n",
" return results;\n",
" }\n",
"\n",
"\n",
" private void permuteHelper(ArrayList<ArrayList<Integer>> results,ArrayList<Integer> path,int[] num){\n",
" if(path.size()==num.length){ //是方法结束的条件\n",
" results.add(new ArrayList<Integer>(path));\n",
" return;\n",
" }\n",
" for(int =/*?*/;i<numm.length;i++){\n",
" //提议要求要跳过那些条件\n",
" path.add(num[i]);\n",
" permuteHelper(results, path, num);\n",
" path.remove(path.size()-1);\n",
" }\n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"hidden": true
},
"outputs": [],
"source": [
"# 所有排列组合类的做法\n",
"\n",
"public class Solution {\n",
"\n",
" public ArrayList<Integer> permute(int[] num){\n",
" Arrays.sort(num);\n",
" ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();\n",
" ArrayList<Integer> path=new ArrayList<Integer>();\n",
" permuteHelper(results,path,num/*?*/);\n",
" return results;\n",
" }\n",
"\n",
"\n",
" private void permuteHelper(ArrayList<ArrayList<Integer>> results,ArrayList<Integer> path,int[] num){\n",
" if(path.size()==num.length){ //是方法结束的条件\n",
" results.add(new ArrayList<Integer>(path));\n",
" return;\n",
" }\n",
" for(int =/*?*/;i<numm.length;i++){\n",
" //提议要求要跳过那些条件\n",
" path.add(num[i]);\n",
" permuteHelper(results, path, num);\n",
" path.remove(path.size()-1);\n",
" }\n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 堆排序(heapify_template)\n",
"\n",
"## Version Linpz\n",
"```java\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftdown(int[] A, int k) {\n",
" while (k * 2 + 1 < A.length) {\n",
" int son = k * 2 + 1;\n",
" if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])\n",
" son = k * 2 + 2;\n",
" if (A[son] >= A[k])\n",
" break;\n",
" \n",
" int temp = A[son];\n",
" A[son] = A[k];\n",
" A[k] = temp;\n",
" k = son;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = (A.length - 1) / 2; i >= 0; i--) {\n",
" siftdown(A, i);\n",
" }\n",
" }\n",
"}\n",
"```\n",
"## Version 1: this cost O(n)\n",
"```java\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftdown(int[] A, int k) {\n",
" while (k < A.length) {\n",
" int smallest = k;\n",
" if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {\n",
" smallest = k * 2 + 1;\n",
" }\n",
" if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {\n",
" smallest = k * 2 + 2;\n",
" }\n",
" if (smallest == k) {\n",
" break;\n",
" }\n",
" int temp = A[smallest];\n",
" A[smallest] = A[k];\n",
" A[k] = temp;\n",
" \n",
" k = smallest;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = A.length / 2; i >= 0; i--) {\n",
" siftdown(A, i);\n",
" } // for\n",
" }\n",
"}\n",
"```\n",
"\n",
"## Version 2: This cost O(nlogn)\n",
"```java\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftup(int[] A, int k) {\n",
" while (k != 0) {\n",
" int father = (k - 1) / 2;\n",
" if (A[k] > A[father]) {\n",
" break;\n",
" }\n",
" int temp = A[k];\n",
" A[k] = A[father];\n",
" A[father] = temp;\n",
" \n",
" k = father;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = 0; i < A.length; i++) {\n",
" siftup(A, i);\n",
" }\n",
" }\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"heapify\n",
"\n",
"// Version Linpz\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftdown(int[] A, int k) {\n",
" while (k * 2 + 1 < A.length) {\n",
" int son = k * 2 + 1;\n",
" if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])\n",
" son = k * 2 + 2;\n",
" if (A[son] >= A[k])\n",
" break;\n",
" \n",
" int temp = A[son];\n",
" A[son] = A[k];\n",
" A[k] = temp;\n",
" k = son;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = (A.length - 1) / 2; i >= 0; i--) {\n",
" siftdown(A, i);\n",
" }\n",
" }\n",
"}\n",
"\n",
"// Version 1: this cost O(n)\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftdown(int[] A, int k) {\n",
" while (k < A.length) {\n",
" int smallest = k;\n",
" if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {\n",
" smallest = k * 2 + 1;\n",
" }\n",
" if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {\n",
" smallest = k * 2 + 2;\n",
" }\n",
" if (smallest == k) {\n",
" break;\n",
" }\n",
" int temp = A[smallest];\n",
" A[smallest] = A[k];\n",
" A[k] = temp;\n",
" \n",
" k = smallest;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = A.length / 2; i >= 0; i--) {\n",
" siftdown(A, i);\n",
" } // for\n",
" }\n",
"}\n",
"\n",
"\n",
"// Version 2: This cost O(nlogn)\n",
"public class Solution {\n",
" /**\n",
" * @param A: Given an integer array\n",
" * @return: void\n",
" */\n",
" private void siftup(int[] A, int k) {\n",
" while (k != 0) {\n",
" int father = (k - 1) / 2;\n",
" if (A[k] > A[father]) {\n",
" break;\n",
" }\n",
" int temp = A[k];\n",
" A[k] = A[father];\n",
" A[father] = temp;\n",
" \n",
" k = father;\n",
" }\n",
" }\n",
" \n",
" public void heapify(int[] A) {\n",
" for (int i = 0; i < A.length; i++) {\n",
" siftup(A, i);\n",
" }\n",
" }\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"navigate_num": "#000000",
"navigate_text": "#333333",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700",
"sidebar_border": "#EEEEEE",
"wrapper_background": "#FFFFFF"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "297px",
"width": "252px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": false,
"toc_section_display": "block",
"toc_window_display": false,
"widenNotebook": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}