검지 offer-java(4)

두 함수를 실현하는데, 각각 서열화와 반서열화 두 갈래 나무에 쓰인다

public class Solution{
    String Serialize(TreeNode root){
        if(root==null)
            return "";
        StringBuilder sb=new StringBuilder();
        Serialize2(root,sb);
        return sb.toString();
    }
    void Serialize2(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append("#,");
            return ;
        }
        sb.append(root.val);
        sb.append(',');
        Serialize2(root.left,sb);
        Serialize2(root.right,sb);
    }
    int index=-1;
    TreeNode Deserialize(String str){
        if(str.length()==0)
            return null;
        String[] strs=str.split(",");
        return Deserialize2(strs);
    }
    TreeNode Deserialize2(String[] strs){
        index++;
        if(!strs[index].equals("#")){
            TreeNode root=new TreeNode(0);
            root.val=Integer.parseInt(strs[index]);
            root.left=Deserialize2(strs);
            root.right=Deserialize2(strs);
            return root;
        }
        return null;
    }
}

두 갈래 검색 트리, 그중의 k번째 큰 결점을 찾으세요.예를 들어, 5/\3 7/\/\2 4 6 8에서 세 번째 결점의 값은 결점 수치 크기 순서대로 4입니다.

public class Solution{
    int k;
    TreeNode KthNode(TreeNode pRoot,int k){
        this.k=k;
        return helper(pRoot);
    }
    private TreeNode helper(TreeNode pRoot){
        TreeNode temp=null;
        if(pRoot!=null){
            if((temp=helper(pRoot.left))!=null)return temp;
            if(--k==0)return pRoot;
            if((temp=helper(pRoot.right))!=null)return temp;
        }
        return null;
    }
}

중위수

import java.util.*;
public class Solution{
    ArrayList<Integer> list=new ArrayList<>();
    public void Insert(Integer num){
        list.add(num);
        Collections.sort(list);
    }
    public Double getMedian(){
        int mid=list.size()/2;
        if(list.size()%2==0){
            Integer a=list.get(mid);
            Integer b=list.get(mid-1);
            double s=((double)a+(double)b)/2;
            return s;
        }else
            return (double)list.get(mid);
    }
}

수조와 슬라이딩 창의 크기를 정해서 모든 슬라이딩 창의 수치의 최대 값을 찾아냅니다.예를 들어 수조 {2,3,4,2,6,2,5,1}과 슬라이딩 창의 크기 3을 입력하면 모두 6개의 슬라이딩 창이 존재하는데 그들의 최대치는 각각 {4,4,6,6,6,5}이다.수조 {2,3,4,2,6,2,5,1}에 대한 슬라이딩 창은 다음과 같은 6개가 있습니다. {[2,3,4], 2,6,2,5,1}, {2,2,3,5,1}, {2,3,4,2,2,5,1}, {2,3,4,2,2,2,2,2,2], 5, 1}, {2,3,4,2,4,2,2,2,2,2,2,2,5], 5,1}, {2,3,4,2,4,2,5,2,5,1}.

import java.util.*;
public class Solution{
    public ArrayList<Integer> maxInWindow(int[] num,int size){
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(num==null||size<=0)
            return list;
        int len=num.length;
        ArrayList<Integer> temp=null;
        if(len<size)
            return list;
        else{
            for(int i=0;i<num.length-size+1;i++){
                temp=new ArrayList<>();
                for(int j=i;j<size+i;j++)   
                    temp.add(num[j]);
                Collections.sort(temp);
                list.add(temp.get(temp.size()-1));
            }
        }
        return list;
    }
}

행렬의 경로는 하나의 행렬에 문자열을 포함하는 모든 문자가 존재하는지 판단하는 함수를 설계하십시오.경로는 행렬의 임의의 칸에서 시작할 수 있으며, 한 걸음 한 걸음 행렬에서 왼쪽, 오른쪽, 위로, 아래로 칸을 이동할 수 있다.만약 한 경로가 행렬의 어떤 칸을 지나갔다면, 이 경로는 이 칸에 다시 들어갈 수 없습니다.예를 들어 a b c e s f c s a d e 행렬에는 문자열'bcced'의 경로가 포함되어 있지만 행렬에는'abcb'경로가 포함되지 않습니다. 문자열의 첫 번째 문자 b가 행렬의 첫 번째 줄, 두 번째 칸을 차지한 후에 경로가 이 칸에 다시 들어갈 수 없기 때문입니다.

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(rows<0||cols<0||str.length==0||matrix.length!=rows*cols||matrix.length==0||str.length>matrix.length)
            return false;
        int[] mark=new int[matrix.length];
        for(int i=0;i<rows;i++)
            for(int j=0;j<cols;j++)
                if(hasPath(matrix, rows, cols, str, i, j, 0, mark))
                    return true;
        return false;
    }
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str,int i,int j,int num,int[] mark)
    {
        int Index=i*cols+j;
        if(i<0||i>=rows||j<0||j>=cols||matrix[Index]!=str[num]||mark[Index]==1)
            return false;
        if(num==str.length-1)
            return true;
        mark[Index]=1;
        if(hasPath(matrix, rows, cols, str, i, j+1, num+1, mark)
            ||hasPath(matrix, rows, cols, str, i, j-1, num+1, mark)
            ||hasPath(matrix, rows, cols, str, i+1, j, num+1, mark)
            ||hasPath(matrix, rows, cols, str, i-1, j, num+1, mark))
        return true;
        mark[Index]=0;
        return false;
    }

}

지상에는 m행과 n열의 네모난 칸이 있다.한 로봇이 좌표 0, 0의 칸부터 이동한다. 매번 왼쪽, 오른쪽, 위, 아래 네 방향으로만 한 칸을 이동할 수 있지만 행 좌표와 열 좌표의 수위의 합이 k보다 큰 칸에 들어갈 수 없다.예를 들어 k가 18일 때 로봇은 칸(35,37)에 들어갈 수 있다. 왜냐하면 3+5+3+7=18이기 때문이다.단, 3+5+3+8=19로 칸(35,38)에 들어갈 수 없습니다.실례지만 이 로봇은 몇 개의 칸에 도달할 수 있습니까?

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        int[][] flag=new int[rows][cols];
        return process(0,0,rows,cols, flag, threshold);
    }
    private int process (int i,int j, int rows ,int cols ,int[][] flag, int threshold){
        if(i<0 || i>=rows || j<0 || j>=cols || numSum(i)+numSum(j) > threshold || flag[i][j]==1)
            return 0;
        flag[i][j]=1;
        return process(i-1,j,rows, cols,flag,threshold)+
            process(i+1,j,rows,cols,flag,threshold)+
            process(i,j+1,rows,cols,flag,threshold)+
            process(i,j-1,rows,cols,flag,threshold)+1;
    }
    private int numSum(int i){
        int sum=0;
        while(i>0){
            int tmp=i%10;
            sum+=tmp;
            i=i/10;
        }
        return sum;
    }
}