剑指Offer——知识点储备-常用算法

剑指Offer——知识点储备-常用算法

快速排序

  • 注:若排序是有序的,采用快排,则退化为冒泡排序。

解决这个问题,采用两个选取基准的方法:
(1)随机选取基数(在这个区间内随机取一个数)
出现的恶劣情况是整个数组全相等,还是退化为冒泡排序
(2)三数取中法
把待排序列分成等长的子序列,最佳的是取中间数为基准
举例:待排序序列为:8 1 4 9 6 3 5 2 7 0
左边为:8,右边为0,中间为6.
我们这里取三个数排序后,中间那个数作为枢轴,则枢轴为6

四种优化方式:

  • 优化方式1:插排
    当待排序序列的长度分割到一定大小后(如子序列长度小于10),使用插入排序
  • 优化方式2:聚集相等元素
  • 优化方式3:采用尾递归
  • 优化方式4:采用并行或多线程处理子序列

堆排序

全排列

/** * 字符串的排列:(考察的知识点就是全排列) * 输入字符: a b c * 输出字符:abc ,acb,bac,bca,cab,cba * * @param args */
	public static void main(String[] args) { 
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){ 
			String str=sc.next();
			ArrayList<String> re=Permutation(str);
			for(String s:re){ 
				System.out.println(s);
			}
		}

	}
	public static ArrayList<String> Permutation(String str) { 
	     ArrayList<String> re=new ArrayList<String>();
	     if(str==null||str.length()==0){ 
	    	 return re;
	     }
			HashSet<String> set=new HashSet<String>();
			fun(set,str.toCharArray(),0);
			re.addAll(set);//将出现的字符串保存在list集合中
			Collections.sort(re);
			return re;
			
		}
	static void  fun(HashSet<String> re,char[] str, int k){ 
		if(k==str.length){ 
			re.add(new String(str));
			return;
		}
		for(int i=k;i<str.length;i++){ //在for循环中,第一次初始化,然后判断,执行for循环体。执行完后i+1,在判断(初始化只执行一次)
			swap(str,i,k);
			fun(re,str,k+1);
			swap(str,i,k);//防止元素的重复,进行复原
			}
}
	//将数组中的两个数进行交换
	static void   swap(char[] str,int i,int j){ 
		if(i!=j){ //相同就不用交换了
			char t=str[i];
			str[i]=str[j];
			str[j]=t;
		}
	}    
   }

二进制数中1的个数(用与运算)

static int  NumberOf3(int n) { 
		int count=0;
		while(n!=0){ //整数不为0,必有1
			++count;
			n=n&(n-1);
			
		}
		return count;
	}

反转二叉树(就是二叉树的镜像)

public void Mirror(TreeNode root) { 
	 if(root==null) { //为空结点
  	   return;
     }
     if(root.left==null&&root.right==null){ //表明该结点是叶子节点或只是根为的节点
  	   return;
     }
     //交换当前节点的左右子树
     TreeNode temp;
     temp=root.left;
     root.left=root.right;
     root.right=temp;
     if(root.left!=null){ 
  	   Mirror(root.left);
     }
     if(root.right!=null){ 
  	   Mirror(root.right);
     }
	}

通过前序、中序,重建二叉树

/** * 解题的步骤: * 1:递归的结束条件,只有到叶子节点,递归才结束(preStart==preEnd&&inStart==inEnd) * 2:在中序中找到根,通过根算出左子树的长度,右子树的长度(左右子树各有多少个节点) * 3:通过左子树的长度,算出前序左子树的起始节点(preStart+1,preStart+leftTree),中序左子树的起始节点(inStart,root-1),递归前提条件是leftLength>0(若为0,那就是叶子节点了) * 4:同上算出右子树的递归 */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
    	if(pre==null||in==null){ //只要一个为空,另一个必为
    		return null;
    	}
    	TreeNode root=binaryTree(pre,in,0,pre.length-1,0,in.length-1);
    	return root;
    }
    public TreeNode binaryTree(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd){ 
    	//构造一个结点
    	TreeNode node=new TreeNode(pre[preStart]);
    	node.left=null;
    	node.right=null;
    	//现在要想想递归的结束条件是什么,preStart=preEnd和inStart=inEnd,表明这是一个叶子节点
    	if(preStart==preEnd&&inStart==inEnd){ 
    		return node;
    	}
    	//现在要找出根节点
    	int root=0;
    	//肯定在in数组中找了
    	for(int i=inStart;i<in.length;i++){ 
    		if(pre[preStart]==in[i]){ 
    			root=i;
    			break;
    		}
    	}
    	//找到根节点,就得算出左右子树的长度(肯定是通过in数组)
    	int leftTree=root-inStart;//要去掉根节点即第一个节点
    	int rightTree=inEnd-root;
    	if(leftTree>0){ 
    		node.left=binaryTree(pre,in,preStart+1,preStart+leftTree,inStart,root-1);
    	}
    	if(rightTree>0){ 
    		node.right=binaryTree(pre, in, preStart+leftTree+1, preEnd, root+1, inEnd);
    	}
    	
    	
    	return node;
    }
}

动态规划

  动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解决由上一次子问题的解推出。

贪心算法

  每次选最大的,然后选择第二大的,在选第三大的,……,直到满足条件后结束或到最后也不能满足条件结束。

    原文作者:No Silver Bullet
    原文地址: https://blog.csdn.net/sunhuaqiang1/article/details/53067090
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞