一、图

题目描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

思路

• 看到一个非常有意思的思路，是用图来解释的。值得借鉴。
• 关键：当前位置的左括号数目<右括号
• 图：节点：当前位置的左括号和右括号数目即为(x,y)(x>=y)边：从(x,y)->(x+1,y)，(x,y)->(x,y+1)注意当x==y时，不存在(x,y)->(x,y+1)这条边
• 解：从（0,0）出发到(n,n）的全部路径。
• 上面是大神的思路，敲完后，总结一下：题目要求的是各种输出结果，这种题以后可以往图上考虑考虑。找出题目中的隐含的限制条件作为边界条件，然后确定好当前的状态也就是节点，再确定这个节点到下一个节点的路径，也就是边。

代码

import java.util.ArrayList; public class Solution { public ArrayList<String> generateParenthesis(int n) { ArrayList<String> list = new ArrayList<String>(); help(n,0,0,"",list); return list; } public void help(int n,int x,int y,String tem,ArrayList<String> list){ if(y==n){ list.add(tem); } if(x<n){ help(n,x+1,y,tem+'(',list); } if(x>y){ help(n,x,y+1,tem+')',list); } } }

二、链表

题目描述

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思路

• 题目意思感觉没说明白，意思就是把两个有序的链表合并（splice）到一起组成一个有序链表。
• 开一个空的头节点，或者头指针，搞不清楚。反正明白意思就好，头节点里面不放数值。然后就是循环比较各个节点大小，依次加入新建的链表中。

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); ListNode p = head; while(l1!=null&&l2!=null){ if(l1.val<l2.val){ p.next = l1; l1 = l1.next; } else{ p.next = l2; l2 = l2.next; } p = p.next; } if(l1 == null){ p.next = l2; } if(l2 == null){ p.next = l1; } return head.next; } }

三、动态规划

题目描述

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

思路

• 动态规划，老套路，求什么我们就把以什么作为状态数组dp，同样的，先来一个空间复杂度为m*n的，然后再考虑优化空间。

代码

//空间复杂度m*n public class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; if(grid == null){ return 0; } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j>0){ grid[i][j]+=grid[i][j-1]; } if(j==0&&i>0){ grid[i][j]+=grid[i-1][j]; } if(i*j!=0){ grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]); } } } return grid[m-1][n-1]; } }

import java.util.Arrays; public class Solution { public int minPathSum(int[][] grid) { if(grid == null){ return 0; } int m = grid.length; int n = grid[0].length; int [] dp = new int [n+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[1]=0;//dp[0]空出来，方便操作 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ //注意这里dp数组中下标从1开始 //dp[j]表示空间复杂度为m*n的代码中的grid[i][j-1] //dp[j+1]表示grid[i-1][j] dp[j+1]=Math.min(dp[j],dp[j+1])+grid[i][j]; } } return dp[n]; } }