一、图
题目描述
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];
}
}
