우객검지 Offer 문제 요약 - 2020/2/05 - JAVA

1. 두 갈래 나무의 깊이 개인 해석: 이 문제는 매우 간단하다. 나무의 깊이만 요구하면 귀속을 통해 쉽게 해결할 수 있다.AC 소스:

public class Solution
{
	public int TreeDepth(TreeNode root)
	{
		if(root == null)
			{
				return 0;
			}
		int left = TreeDepth(root.left);
		int right = TreeDepth(root.right);
		return Math.max(left,right)+1;
	}
}

2. 균형 이차수 개인 해석: 이 문제는 이차수 깊이를 구하는 진급판에 해당하고 귀속적인 방식으로 해결한다.AC 소스:

public class Solution
{
	public boolean IsBalanced_Solution(TreeNode root)
	{
		return getDepth(root) != -1;
	}
	private int getDepth(TreeNode root)
	{
		if(root == null)
			return 0;
		int left = getDepth(root.left);
		if(left == -1)
			return -1;
		int right = getDepth(root.right);
		if(right == -1)
			return -1;
		return Math.abs(left-right)>1? -1 :1+Math.max(left,right);
	}
}

3. S를 위한 두 숫자의 개인적인 해석: 두 숫자의 차이가 절대치가 클수록 그들의 곱셈은 작기 때문에 쌍바늘의 방법으로 하나는 처음부터 시작하고 하나는 끝부터 반복하며 세 가지 상황이 있다. 1).x+y=sum은 결과 2).x+y>sum y– 3).x+y AC 소스:

import java.util.ArrayList;
public class Solution
{
	public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum)
	{
		ArrayList<Integer> result =new ArrayList<>();
		int x=0;
		int y=array.length-1;
		while(x<y)
		{
			if(array[x]+array[y])==sum
			{
				result.add(array[x]);
				result.add(array[y]);
				break;
			}
			else if(array[x]+array[y]>sum)
			{
				y--;
			}
			else
			{
				x++;
			}
			}
			return result;
	}
}

4. 수조에 한 번만 나타나는 숫자 개인 해석: 이 문제는 다른 사상을 사용해야 한다. 한 개의 수이나 그 자신은 0이다. 그래서 처음에 수조에 있는 수를 모두 같거나 한 번 남기고 한 개의 숫자만 남았다. 그리고 우리는 이 숫자에서 마지막 답안에 필요한 두 개의 숫자를 분리한다.AC 소스:

public class Solution
{
	public void FindNumsAppearOnce(int[] array,int[]num1,int[]num2)
	{
		int length=array.length;
		if(length==2)
		{
			num1[0]=array[0];
			num2[0]=array[1];
			return;
		}
		int bitResult=0;
		for(int i=0;i<length;i++)
			bitResult ^= array[i];
		int index = findFirst1(bitResult);
		for(int i=0;i<length;i++)
		{
			if(isBit1(array[i],index))
				num1[0]^=array[i];
			else
				num2[0]^=array[i];
		}
	}
	private int findFirst1(int bitResult)
	{
		int index=0;
		while(((bitResult&1)==0)&&index<32)
		{
			bitResult >>=1;
			index++;
		}
		return index;
	}
	private boolean isBit1(int target,int index)
	{
		return ((target>>index)&1)==1;
	}
}

5. S를 위한 연속 정수 서열 개인 해석: 동적 창의 생각으로 이 문제를 해결한다. 두 가지 시작점은 동적 창의 양쪽에 해당하고 그 창의 값의 합에 따라 창의 위치와 크기를 확정한다. 연속적이고 차이가 1인 서열이기 때문에 구화 공식은 (a0+an)*n/2이다. 같으면 창 범위의 모든 수를 결과 집합에 추가한다. 현재 창의 합이sum보다 작으면그러면 오른쪽 창을 오른쪽으로 이동합니다. 현재 창 안의 값의 합이sum보다 크면 왼쪽 창을 오른쪽으로 이동합니다.AC 소스:

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > result = new ArrayList<>();
        int plow = 1,phigh = 2;
        while(phigh > plow){
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            if(cur == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int i=plow;i<=phigh;i++){
                    list.add(i);
                }
                result.add(list);
                plow++;
            }else if(cur < sum){
                phigh++;
            }else{
                plow++;
            }
        }
        return result;
    }
}