Java教程

Java--算法--实战题目

本文主要是介绍Java--算法--实战题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  1. 题目一:
    1. package com.model.tree;
      
      /**
       * @Description:测试类
       * @Author: 张紫韩
       * @Crete 2021/8/15 16:14
       * 根据树的后序遍历,的到原来的树
       */
      public class TreeDemo01 {
          public static void main(String[] args) {
              int[] arr={2,4,3,6,8,7,5};
              TreeNode treeNode = buildTree(arr, 0, arr.length - 1);
              System.out.println(treeNode);
      
          }
      
          public  static TreeNode buildTree(int[] arr,int left,int right){
              if (left>right) return null;
      
              if (left==right){
                  return new TreeNode(arr[right]);
              }else {
                  TreeNode resTree=new TreeNode(arr[right]);
      //可以使用二分法得到第一个大于 arr[right]的下标mid
                  int mid = right-1;
                  for (int i = left; i < right; i++) {
                      if (arr[i]>arr[right]){
                          mid=i;
                          break;
                      }
                  }
                  TreeNode leftNode = buildTree(arr, left, mid-1);
                  TreeNode rightNode = buildTree(arr, mid, right-1);
                  resTree.setLeft(leftNode);
                  resTree.setRight(rightNode);
                  return resTree;
              }
      
          }
      }
      //树节点
      class TreeNode{
          private int val;
          private TreeNode left;
          private TreeNode right;
      
          public TreeNode() {
          }
      
          public TreeNode(int val) {
              this.val = val;
          }
      
          public TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      
          public int getVal() {
              return val;
          }
      
          public void setVal(int val) {
              this.val = val;
          }
      
          public TreeNode getLeft() {
              return left;
          }
      
          public void setLeft(TreeNode left) {
              this.left = left;
          }
      
          public TreeNode getRight() {
              return right;
          }
      
          public void setRight(TreeNode right) {
              this.right = right;
          }
      
          @Override
          public String toString() {
              return "TreeNode{" +
                      "val=" + val +
                      ", left=" + left +
                      ", right=" + right +
                      '}';
          }
      }
  2. 题目二:

    1. package com.model.question;
    2. /**
       * @Description:测试类
       * @Author: 张紫韩
       * @Crete 2021/8/16 10:59
       * 两个字符串是否是同源异构的
       * 同源异构:即两个字符串有相同的字母并且字母数量也相等组成
       *
       * 一个字符串的子串是否是另一个字符串的同源字符串 abcbca : abc
       */
      public class QuestionDemo03 {
          public static void main(String[] args) {
              System.out.println(isSame("abcabac", "aabbcca"));
      
              System.out.println(isInclude("abcdeefgjkl", "abc"));
      
          }
      //    使用是窗口的方式解决问题,检测str1字串的子串是否是另一个字符串str2的同源字符串
          public static boolean isInclude(String str1,String str2){
              if (str1.length()<str2.length()){
                  return false;
              }
              int[] count=new int[256];
              int len1 = str1.length();
              int len2 = str2.length();
              char[] char1 = str1.toCharArray();
              char[] char2 = str2.toCharArray();
              int flag=0;
      //        形成欠债表
              for (char c2:char2){
                  count[c2]++;
              }
      
      //        第一个窗口是否是进行还债
              for (int i = 0; i < len2; i++) {
                  if (count[char1[i]]--<=0){
                      flag++;
                  }
              }
      //        判断第一个窗口是否是和str2同源
              if (flag==0) {System.out.println("index:"+0); return true;}
      
      //       窗口向后移动,判断后面的窗口是否是同源的
              for (int i = len2; i <len1; i++) {
      //            将原来窗口的第一个取出
                  if (count[char1[i-len2]]++<0){
                    flag--;
                  }
      //            将窗口的后面一个加入
                  if (count[char1[i]]--<=0){
                      flag++;
                  }
      //            判断当前窗口的字符串是否是同源
                  if (flag==0){
                      System.out.println("index:"+(i-len2+1));
                      return true;
                  }
              }
              return false;
          }
      
      
      
      
      
      //    简单的判断两个字符串是否是同源字符串
          public static boolean isSame(String str1,String str2){
              if (str1.length()!=str2.length()) return false;
              int[] temp=new int[256];
              char[] char1 = str1.toCharArray();
              char[] char2 = str2.toCharArray();
              for (char c1:char1){
                  temp[c1]++;
              }
              for (char c2:char2){
                  if (temp[c2]==0){
                      return false;
                  }
                  temp[c2]--;
              }
              return true;
          }
      }
  3. 题目三:
  4.  题目四:

    1. package com.model.tree;
      
      import com.sun.jmx.remote.internal.ArrayQueue;
      import sun.misc.Queue;
      
      import java.awt.*;
      import java.util.ArrayDeque;
      import java.util.ArrayList;
      
      /**
       * @Description:测试类
       * @Author: 张紫韩
       * @Crete 2021/8/25 23:02
       * 二叉树的层序遍历
       */
      public class TreeDemo03 {
          public static void main(String[] args) {
      
              TreeNode head = new TreeNode(0);
              head.left=new TreeNode(1);
              head.right=new TreeNode(2);
              head.right.right=new TreeNode(3);
              head.right.right.right=new TreeNode(4);
      
              traverse(head);
      
          }
      
      //    使用队列实现对树 的层序遍历
          public static void traverse(TreeNode head){
              if (head==null){
                  return;
              }
              ArrayList<ArrayList<TreeNode>> resList = new ArrayList<>();
      
              ArrayDeque<TreeNode> deque = new ArrayDeque<>();
              deque.addLast(head);
              int size;
              while (!deque.isEmpty()){
                  size=deque.size();
                  ArrayList<TreeNode> temp = new ArrayList<>();
                  for (int i = 0; i <size ; i++) {
                      TreeNode node = deque.pollFirst();
                      temp.add(node);
                      if (node.left!=null) deque.addLast(node.left);
                      if (node.right!=null) deque.addLast(node.right);
                  }
                  resList.add(temp);
              }
      
              System.out.println(resList);
          }
      }

       

          

            
这篇关于Java--算法--实战题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!