本文主要是介绍随便贴几个算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
求二叉树的深度
public int maxDepth(TreeNode root) {
return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
上面这个方法是递归调用,如果使用非递归应该怎么计算二叉树的深度呢, 可以参考下面的求二叉树的最大宽度 的方法,这个方法是将每一层的node都添加都 一个队列中,我们可以利用这个思想,然后记录一共添加了多少层,那么这就是 二叉树的深度。
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
//创建一个队列
Deque<TreeNode> deque = new LinkedList<>();
deque.push(root);
int count = 0;
while (!deque.isEmpty()) {
//每一层的个数
int size = deque.size();
while (size-- > 0) {
TreeNode cur = deque.pop();
if (cur.left != null)
deque.addLast(cur.left);
if (cur.right != null)
deque.addLast(cur.right);
}
count++;
}
return count;
}
求二叉树的宽度
private static int getWidth(BiNode head) {
if(head==null){
return 0;
}
int maxWidth=1;
LinkedList<BiNode> list=new LinkedList<>();
list.add(head);
while (list.size()!=0) {
int size=list.size();
if(size>maxWidth){
maxWidth=size;
}
for(int i=0;i<size;i++){
BiNode node=list.poll();
if (node.left!=null) {
list.add(node.left);
}
if (node.right!=null) {
list.add(node.right);
}
}
}
return maxWidth;
}
二叉树的遍历
public void preOrder(Node node)
{
list.add(node); //先将根节点存入list
//如果左子树不为空继续往左找,在递归调用方法的时候一直会将子树的根存入list,这就做到了先遍历根节点
if(node.lchid != null)
{
preOrder(node.lchid);
}
//无论走到哪一层,只要当前节点左子树为空,那么就可以在右子树上遍历,保证了根左右的遍历顺序
if(node.rchild != null)
{
preOrder(node.rchild);
}
}
public void inOrder(Node node)
{
if(node.lchid!=null){
inOrder(node.lchid);
}
list.add(node);
if(node.rchild!=null){
inOrder(node.rchild);
}
}
public void postOrder(Node node)
{
if(node.lchid!=null){
postOrder(node.lchid);
}
if(node.rchild!=null){
postOrder(node.rchild);
}
list.add(node);
}
//二叉树前序遍历非递归的方式
public
void
preorder(TreeNode root, ArrayList<Integer> list) {
Stack<TreeNode> stack =
new
Stack<>();
stack.push(root);
while
(!stack.isEmpty()) {
TreeNode curr = stack.pop();
list.add(curr.val);
if
(curr.right !=
null
) {
stack.push(curr.right);
}
if
(curr.left !=
null
) {
stack.push(curr.left);
}
}
}
//二叉树中序遍历采用非递归的方式
public
void
inorder(TreeNode root, ArrayList<Integer> list) {
Stack<TreeNode> stack =
new
Stack<>();
TreeNode curr = root;
while
(!stack.isEmpty() || curr !=
null
) {
while
(curr !=
null
) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
list.add(curr.val);
curr = curr.right;
}
}
二分查找 (折半查找)前提必须是有序的数组
public static int recursionBinarySearch(int[] arr,int key,int low,int high){ //递归的实现方式if(key < arr[low] || key > arr[high] || low > high){ return -1; } int middle = (low + high) / 2; //初始中间位置 if(arr[middle] > key){ //比关键字大则关键字在左区域 return recursionBinarySearch(arr, key, low, middle - 1); }else if(arr[middle] < key){ //比关键字小则关键字在右区域 return recursionBinarySearch(arr, key, middle + 1, high); }else { return middle; } }
public static int commonBinarySearch(int[] arr,int key){ //非递归的实现方式int low = 0; int high = arr.length - 1; int middle = 0; //定义middle if(key < arr[low] || key > arr[high] || low > high){ return -1; } while(low <= high){ middle = (low + high) / 2; if(arr[middle] > key){ //比关键字大则关键字在左区域 high = middle - 1; }else if(arr[middle] < key){ //比关键字小则关键字在右区域 low = middle + 1; }else{ return middle; } } return -1; //最后仍然没有找到,则返回-1
}
反转链表:
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head!=null){
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
字符串的反转,
static String reverse(String string) {
char[] array = string.toCharArray();
int i = 0, j = array.length - 1;
while (i < j) {
char tem = array[i];
array[i] = array[j];
array[j] = tem;
i++;
j--;
}
return String.valueOf(array);
}
翻转整个句子的函数(反转句子,但是单子顺序不变)
static String reverseSentence(String string){
String reversedString=reverse(string);
String[] splitStrings=reversedString.split(" ");
String resultString="";
for(String str:splitStrings){
resultString=resultString+reverse(str)+" ";
}
return resultString;
}
二叉树的反转
递归方式:
· public TreeNode invertNode(TreeNode root) {
· if(root==null)
· return root;
· TreeNode temp=root.left;
· root.left=invertNode(root.right);
· root.right=invertNode(temp);
· return root;
· }
非递归方式:
1. public TreeNode invertNode(TreeNode root) {
2. if(root==null)
3. return null;
4. Queue<TreeNode> queue=new LinkedList<TreeNode>();
5. queue.add(root);
6. while(queue!=null){
7. TreeNode current=queue.poll();
8. TreeNode temp=current.left;
9. current.left=current.right;
10. current.right=temp;
11. if(current.left!=null)
12. queue.add(current.left);
13. if(current.right!=null)
14. queue.add(current.right);
15. }
16. return root;
17. }
18. 、
阶乘:
public static long getNFactorial(int n){
if(n==0){
return 1l;
}
return n*getNFactorial1(n-1);
}
1. /**
2. * 求1+2!+3!+...+20!的和
3. * @author Vivinia
4. *
5. */
6. public class factorial {
7. public static void main(String args[]) {
8. long sum=0,num=1; //sum用于加和,num作为每一个数阶乘后的结果
9. for(int i=1;i<=20;i++) {
10. num*=i; //num始终保留上一次阶乘的结果,所以只需要乘i
11. sum+=num; //每次阶乘后相加
12. }
13. System.out.println("1+2!+3!+...+20!="+sum);
14. }
15. }
汉诺塔问题:
/**
* 将A汉诺塔上的n个盘子通过C移动到B的递归方法
* @param n //汉诺塔上盘子的个数
* @param A //开始时有盘子的汉诺塔
* @param B //要将盘子移动到上面的目标汉诺塔
* @param C //中介汉诺塔
* @throws IllegalArgumentException when n<=0
*/
public static void HanoiTowers1(int n,char A,char B,char C){
if(n<=0){
throw new IllegalArgumentException("n must be >=1");
}
if(n==1){
System.out.println(A+"->"+B);
}
else{
HanoiTowers1(n-1,A,C,B); // 将除去最大的盘子的n个盘子从A通过B移动到C
System.out.println(A+"->"+B);//将最大的盘子从A移动到B
HanoiTowers1(n-1,C,B,A); //将除去最大的盘子的n-1个盘子从C通过A移动到B
}
}//HanoiTowers1(int n,char A,char B,char C)
最长公共子序列:比如字符串1:BDCABA;字符串2:ABCBDAB
则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
这是一个动态规划的题目。对于可用动态规划求解的问题,一般有两个特征:①最优子结构;②重叠子问题
//求解str1 和 str2 的最长公共子序列
- public static int lcs(String str1, String str2) {
- int len1 = str1.length();
- int len2 = str2.length();
- int c[][] = new int[len1+1][len2+1];
- for (int i = 0; i <= len1; i++) {
- for( int j = 0; j <= len2; j++) {
- if(i == 0 || j == 0) {
- c[i][j] = 0;
- } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
- c[i][j] = c[i-1][j-1] + 1;
- } else {
- c[i][j] = max(c[i - 1][j], c[i][j - 1]);
- }
- }
- }
- return c[len1][len2];
- }
给定一个整型数组和一个整数,要找出数组中的两个数字,使得这两个数字的和等于给定的和。
例如,输入数组numbers={1,2,3,4,5,6,7},给定和为9,则要找出2和7,3和6,4和5的位置。
1. public int[] twoSumSolution2(int[] numbers,int sum) {
2.
3. int[] ret=new int[2];
4. HashMap<Integer, Integer>map=new HashMap<Integer,Integer>();
5. for (int i = 0; i < numbers.length; i++) {
6. if (map.containsKey(numbers[i])) {
7. int index=map.get(numbers[i]);
8. ret[0]=index+1;
9. ret[1]=i+1;
10. }else {
11. map.put(sum-numbers[i], i);//把总和减去当前数作为key放入map,然后与新进来的数字比对
12. }
13. }
14. return ret;
15. }
这篇关于随便贴几个算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!