【JAVA】每日两道算法题0916_链表、递归

素颜马尾好姑娘i 2021-09-24 16:34 330阅读 0赞

### 文章目录 ###

*  LeetCode21
 *  LeetCode334
 *  递归
 *   *  递归三要素
     *  斐波那契数列
     *  99乘法表

# LeetCode21 #

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

标签：`链表`、`递归`

思路：  
1.新的链表不需要重新定义，因为链表的插入是非常方便的。  
2.如果l1或者l2为空链表，不需要合并，直接返回另一个链表。

代码实现：

//递归实现
    class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            if (l1 == null) { return l2;}
            else if (l2 == null) { return l1;}
            else if (l1.val <= l2.val) { 
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }
            else { 
                l2.next = mergeTwoLists(l2.next, l1);
                return l2;
            }
        }
    }

# LeetCode334 #

题目2：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。  
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。  
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

标签：`双指针`、`递归`

思路：将字符串的首尾交换。然后将中间部分作为一个新的字符串，首尾交换、一直到left >= right.递归实现新字符串。

代码实现：

*  暴力解法

class Solution { 
        public void reverseString(char[] s) { 
            int len = s.length;
            for(int i = 0; i < len/2; i++) { 
                char tmp = s[i];
                s[i] = s[len-i-1];
                s[len-1-i] = tmp;
            }      
        }
    }

*  递归解法

class Solution { 
        public void reverseString(char[] s) { 
            helper(s, 0, s.length-1);
        }
    
        private void helper(char[] str,int left,int right) { 
            if (left < right) { 
                char tmp = str[left];
                str[left++] = str[right];
                str[right--] = tmp;
                helper(str, left, right);
            }
            else { 
                return ;
            }
        }
    }

# 递归 #

## 递归三要素 ##

1、明确递归终止条件；  
2、给出递归终止时的处理办法；  
3、提取重复的逻辑，缩小问题规模。

## 斐波那契数列 ##

1，1，2，3，5，8，13，21…

代码实现：

public static int fibonacci(int n){ 
            switch(n){ 
                //终止条件一
                case 0:
                    return 0;
                //终止条件二
                case 1:
                    return 1;
                //在方法中调用自己
                default:
                    return fibonacci(n-1)+fibonacci(n-2);
            }
        }

## 99乘法表 ##

代码实现：

class Solution { 
    	public void multiTable(int i) { 
    		if(i == 1){ 
    			System.out.println('1*1=1');
    		}
    		else { 
    			for (int j =1; j <= i; j++) { 
    				System.out.println(i+'*'+j+'='+(i*j)+'');
    			}
    			m(i-1);
    		}	
    	}
    }