「这是我参与11月更文挑战的第6天,活动详情查看:2021最后一次更文挑战」
分治法思想
分治法,字面意思是“分而治之”,就是把一个复杂的1问题分成两个或多个相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题可以简单地直接求解,原问题的解即子问题的解的合并。
代表例子有快速排序和归并排序。
例题-所有可能的满二叉树
题目描述
所有可能的满二叉树
满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
示例:
输入:7
输出:[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释:
解题思路
n=1,只需要返回一种情况,根结点即可
n=3,根结点的左右子树都需要一个节点
n>=3时候情况就复杂了
左子树节点个数可以为:1. 3. 5 ....
右子树节点个数可以为:n-1-1. n-1-3. n-1-5...
而左右子树又会有同样的问题,只不过n变得不一样
因此我们可以对左右子树分而治之
最后得到的结果组合即可
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> allPossibleFBT(int n) {
int i=1;
List<TreeNode> list=new ArrayList<>();
if(n==1)list.add(new TreeNode(0));
while (n-1-i>0){
List<TreeNode> ls=allPossibleFBT(i);
List<TreeNode> rs=allPossibleFBT(n-i-1);
for (int i1 = 0; i1 < ls.size(); i1++) {
for (int i2 = 0; i2 < rs.size(); i2++) {
TreeNode treeNode=new TreeNode(0);
treeNode.left=ls.get(i1);
treeNode.right=rs.get(i2);
list.add(treeNode);
}
}
i+=2;
}
return list;
}
}
复制代码
归并排序
package com.company;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// write your code here
int []arr = {4,3,2,1,121,141,1,1,31,51,321,41123,-1,-100,1423,123,-213,11,-7,7,8,-8,8,-9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] array){ //作为函数入口,简化规则
int[] temp=new int[array.length]; //在堆内申请一个array.length的空间,以免后续频繁申请
sort(0,array.length-1,array,temp);
}
public static void sort(int left,int right,int[] array,int[] temp){//分,分开治理
if(left<right){
int mid=(left+right)/2;
sort(left,mid,array,temp);
sort(mid+1,right,array,temp);
merge(left,right,mid,array,temp);
}
}
public static void merge(int left,int right,int mid ,int[] array,int[] temp){//治,进行合并
if(left==right)return;
int mid1=mid+1;
int cur=left;
int leftbank=left;
while (left<=mid&&mid1<=right){
if(array[left]<array[mid1]){
temp[cur++]=array[left];
left++;
}else {
temp[cur++]=array[mid1];
mid1++;
}
}
while (left<=mid||mid1<=right){
if(left<=mid){
temp[cur++]=array[left++];
}
if(mid1<=right){
temp[cur++]=array[mid1++];
}
}
for (int i = leftbank; i <=right ; i++) {
array[i]=temp[i];
}
}
}
复制代码
快速排序
package com.company;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// write your code here
int []arr = {4,3,2,1,121,141,1,1,31,51,321,41123,-1,-100,1423,123,-213,11,-7,7,8,-8,8,-9,211,212,213,214,215,216,217};
quicksort(arr);
System.out.println(Arrays.toString(arr));
}
public static void quicksort(int[] array){
quicksort(array,0,array.length-1);
}
public static void quicksort(int[] array,int left,int right){
if(left>=right)return;
if(right-left==1){
if(array[left]>array[right]){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
return;
}
}
int temp=left;
int l=left+1;
int r=right;
while (l<=r){
if(array[l]<=array[temp]){
l++;
}else if(array[r]>=array[temp]){
r--;
}else {
int value=array[l];
array[l]=array[r];
array[r]=value;
l++;
r--;
}
}
int value=array[r];
array[r]=array[temp];
array[temp]=value;
quicksort(array,left,r-1);
quicksort(array,r+1,right);
}
}
复制代码
近期评论