검 지 offer 알고리즘 문제 분석 및 정리 (4)
58543 단어 알고리즘
목차
1. 두 개의 정렬 된 링크 를 합 친다.
두 개의 단조 로 운 증가 하 는 링크 를 입력 하고 두 개의 링크 를 합성 한 링크 를 출력 합 니 다. 물론 우 리 는 합성 한 링크 가 단조 로 운 규칙 을 만족 시 켜 야 합 니 다.사고방식 1: 비 귀속
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)return list2;
if(list2==null)return list1;
ListNode t=new ListNode(520);// ， next
ListNode list=t;
while(list1!=null&&list2!=null){
if(list1.val<=list2.val){
t.next=list1;
t=t.next;
list1=list1.next;
}
else{
t.next=list2;
t=t.next;
list2=list2.next;
}
}
if(list1==null)t.next=list2;
if(list2==null)t.next=list1;
return list.next;
}
}사고방식 2: 귀속
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)return list2;
if(list2==null)return list1;
ListNode t=null;
if(list1.valelse{
t=list2;
t.next=Merge(list1,list2.next);
}
return t;
}
} 2. 두 갈래 검색 트 리 가 양 방향 링크 로 전환
이 진 트 리 를 입력 하고 이 진 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 트 리 의 노드 포인터 의 방향 만 조정 할 수 있 습 니 다.사고 1: 재 귀, FL 함 수 는 한 나 무 를 양 방향 링크 후의 머리 노드 와 꼬리 노드 로 되 돌려 주 고 뿌리 노드 의 좌우 두 개의 나 무 를 각각 재 귀 한 다음 에 재 귀 된 좌우 두 단 과 중간의 뿌리 노드 를 양 방향 으로 연결 시 켜 결합 시킨다.
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)return null;
TreeNode[] A=FL(pRootOfTree);
return A[0];
}
TreeNode[] FL(TreeNode p){
TreeNode[] t=new TreeNode[2];// ，
if(p.left==null&&p.right==null){
t[0]=p;
t[1]=p;
}
else if(p.right==null){
TreeNode[] t1=FL(p.left);
p.left=t1[1];
p.left.right=p;
t[0]=t1[0];
t[1]=p;
}
else if(p.left==null){
TreeNode[] t1=FL(p.right);
p.right=t1[0];
p.right.left=p;
t[0]=p;
t[1]=t1[1];
}
else{
TreeNode[] t1=FL(p.left);
TreeNode[] t2=FL(p.right);
p.left=t1[1];
p.left.right=p;
p.right=t2[0];
p.right.left=p;
t[0]=t1[0];
t[1]=t2[1];
}
return t;
}
}이전 노드 를 재 귀적 으로 옮 겨 다 니 며 pre 로 저장 합 니 다.
public class Solution{
TreeNode head=null;
TreeNode pre=null;
public TreeNode Convert(TreeNode root) {
f(root);
return head;
}
void f(TreeNode t){
if(t==null)return;
f(t.left);
if(pre!=null){
pre.right=t;
t.left=pre;
}
else{
head=t;
}
pre=t;
f(t.right);
}
}
/**
// ，
public class Solution {
TreeNode head = null;
public TreeNode Convert(TreeNode root) {
TreeNode pre = null;
f(root, pre);
return head;
}
void f(TreeNode t, TreeNode pre) {
if (t == null) return;
f(t.left, pre);
if (pre != null) {
pre.right = t;
t.left = pre;
} else {
head = t;
}
pre = t;
f(t.right, pre);
}
}
*/사고 2: 재 귀적 이지 않 고 중간 순서 로 옮 겨 다 닌 다.
import java.util.Stack;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)return null;
Stack s=new Stack<>();
TreeNode t=pRootOfTree;
TreeNode pre=null;
TreeNode head=null;
do{
if(t!=null){
s.push(t);
t=t.left;
}
else{
t=s.pop();
if(pre==null){ //
pre=t;
head=pre; //
}
else{ //
pre.right=t;
t.left=pre;
pre=t; // pre
}
t=t.right;
}
}while(t!=null||!s.isEmpty());
return head;
}
} 사고 3: 스 택 을 사용 하 든 재 귀 하 든 모두 O (n) 의 공간 을 사용 해 야 한다. Morris Traversal 방법 은 앞의 두 가지 방법 과 달리 이 방법 은 O (1) 공간 만 필요 하고 O (n) 시간 안에 우 객 망 @ 정 만 모험 기 를 완성 할 수 있다.
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
TreeNode p = pRootOfTree, pre = null, res = null;
while (p != null) {//p ， p
//p ， ， p
while (p.left != null) {
// p ， ， p ， p
TreeNode q = p.left;
while (q.right != null) {
q = q.right;
}
q.right = p;
// p p ，p p ， p
TreeNode tmp = p.left;
p.left = null;
p = tmp;
}
//p ，p ， p pre
p.left = pre;
if (pre == null) {
res = p;
} else {
pre.right = p;
}
pre = p;
//p p
p = p.right;
}
return res;
}
}3. 배열 에서 첫 번 째 로 중복 되 는 숫자
길이 가 n 인 배열 의 모든 숫자 는 0 에서 n - 1 의 범위 안에 있다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모른다.숫자 마다 몇 번 씩 반복 되 는 지 모 르 겠 어 요.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 7 인 배열 {2, 3, 1, 0, 2, 5, 3} 을 입력 하면 해당 하 는 출력 은 첫 번 째 중복 되 는 숫자 2 입 니 다.사고 1: 상태 배열 로 표시
public boolean duplicate(int numbers[],int length,int [] duplication) {
int[] count=new int[length];
for(int i=0;icount[numbers[i]]++;
}
for(int i=0;iif(count[numbers[i]]>1){
duplication[0]=numbers[i];
return true;
}
}
return false;
}
} 그러나 int 배열 의 점용 공간 이 좀 크다. 문제 가 중복 되 는 숫자 만 찾 는 것 을 감안 하여 중복 되 는 숫자 가 도대체 몇 번 반복 되 는 지 에 관심 이 없 기 때문에 불 배열 이나 bit - map 는 우 객 망 @ Aurora 1 에서 나 올 수 있다.
// ， ， ，
public boolean duplicate(int numbers[], int length, int[] duplication) {
boolean[] k = new boolean[length];
for (int i = 0; i < k.length; i++) {
if (k[numbers[i]] == true) {
duplication[0] = numbers[i];
return true;
}
k[numbers[i]] = true;
}
return false;
}사고 2: 문제 가 배열 의 수가 length - 1 을 초과 하지 않 을 것 이 라 고 보장 하기 때문에 이 배열 자 체 를 배열 로 표시 하고 어떻게 표시 합 니까? num [i] + = length 를 단점 은 첫째, 원래 의 배열 을 바 꾸 었 습 니 다. 만약 에 입력 한 배열 이 잘못 되면 안에 length - 1 을 초과 하면 자신 이 추가 한 것 인지 원래 이렇게 큰 것 인지 알 수 없습니다.2. length 가 너무 크 면 몇 번 더 하면 Integer. MAX 가 넘 칠 수 있 습 니 다.VALUES。 왕 할아버지
bool duplicate(int numbers[], int length, int* duplication) {
for(int i=0;i!=length;++i){
int index=numbers[i]%length;//
if(numbers[index]>=length){// length-1
*duplication=index;
return 1;
}
numbers[index]+=length;
}
return 0;
}
사고방식 3: 교환 을 통 해 판단 하면 모든 중 복 된 수 를 찾 을 수 있다. 그러나 첫째, 그것 은 원수 조 를 바 꾸 었 다.2. 수입 016645778 에 대해 수출 한 것 은 6 이 아니 라 7 이 고 첫 번 째 중복 되 는 수 는 6 이 우 객 망 에서 온 것 이 분명 합 니 다. @ CV 라 는 벽돌 을 옮 기 는 것 입 니 다.
/*
1、
2、 ， ， ,numbers[i] numbers[numbers[i]]，
， true, ， 。 ， false
*/
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(length<=0||numbers==NULL)
return false;
//
for(int i=0;i<length;++i)
{
if(numbers[i]<=0||numbers[i]>length-1)
return false;
}
for(int i=0;i<length;++i)
{
while(numbers[i]!=i)
{
if(numbers[i]==numbers[numbers[i]])
{
*duplication = numbers[i];
return true;
}
// numbers[i] numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
};4. 스 택 의 압 입 팝 업 시퀀스 가 일치 하 는 지 여부
두 개의 정수 서열 을 입력 하 십시오. 첫 번 째 서열 은 창고 의 압축 순 서 를 표시 합 니 다. 두 번 째 서열 이 창고 의 팝 업 순서 가 될 수 있 는 지 판단 하 십시오.창고 에 쌓 인 모든 숫자 가 같 지 않다 고 가정 하 세 요.예 를 들 어 서열 1, 2, 3, 4, 5 는 특정한 스 택 의 압 입 순서 이 고 서열 4, 5, 3, 2, 1 은 이 스 택 서열 에 대응 하 는 팝 업 서열 이지 만 4, 3, 5, 1, 2 는 이 스 택 서열 의 팝 업 서열 일 수 없다.(주의: 이 두 서열 의 길 이 는 같다) 사고방식 1: 아 날로 그 창고 의 상태
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
ArrayList a=new ArrayList<>();
//
int index=-1;
for(int m=0;mif(popA[0]==pushA[m]){
index=m;
break;
}
}
if(index==-1)return false;// ？！
// a
int i=0;
for(;i<index;i++){
a.add(pushA[i]);
}
//
for(int j=1;j//
index=-1;
for(int m=0;mif(popA[j]==pushA[m]){
index=m;
break;
}
}
if(index==-1)return false;// ？！ ？
// ，
if(index>i){
for(i++;i<index;i++){
a.add(pushA[i]);//
}
}
// ，
else if(popA[j]==a.get(a.size()-1)){
a.remove(a.size()-1);
}
// ， ， ，
else{
return false;
}
}
return true;
}
} 마찬가지 로 아 날로 그 창고 의 상태 입 니 다. 대신 의 답 은 더욱 간결 하고 정련 은 우 객 망 @ Alias 에서 왔 습 니 다.
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack s = new Stack();
//
int popIndex = 0;
for(int i = 0; i< pushA.length;i++){
s.push(pushA[i]);
// ，
while(!s.empty() &&s.peek() == popA[popIndex]){
//
s.pop();
//
popIndex++;
}
}
return s.empty();
}
} 5. 배열 에 한 번 만 나타 나 는 숫자
하나의 정형 배열 에서 두 개의 숫자 를 제외 하고 다른 숫자 들 은 모두 짝수 로 나 타 났 다.프로그램 을 써 서 이 두 개의 한 번 만 나 오 는 숫자 를 찾 아 보 세 요.사고 1: O (n2) O (n 2) 시간 복잡 도, 바람 직 하지 않다.
import java.util.Iterator;
import java.util.LinkedList;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
LinkedList l=new LinkedList<>();
boolean f;
for(int i=0;ifalse;
// ， ，
Iterator it=l.iterator();
while(it.hasNext()){
if(it.next().equals(array[i])){
it.remove();
f=true;
break;
}
}
/**//foreach remove
for(Integer j:l){
if(j==array[i]){
l.remove(j);
f=true;
break;
}
}*/
//
if(!f)l.add(array[i]);
}
num1[0]=l.getFirst();
num2[0]=l.getLast();
}
} ArrayList Remove 방법 으로 만 나 는 구덩이 에 관심 을 가 져 야 합 니 다.
사고방식 2: 이 또는 대 법 은 우 객 망 @ 고 후 에서 온다.
/**
* ， ，
* @param array
* @param num1
* @param num2
*/
public static void findNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length <= 1){
num1[0] = num2[0] = 0;
return;
}
int len = array.length, index = 0, sum = 0;
//DABCDC ， AB
for(int i = 0; i < len; i++){
sum ^= array[i];
}
//AB 0， 1， 1
for(index = 0; index < 32; index++){
if((sum & (1 << index)) != 0) break;
}
// ， ，AB ，
for(int i = 0; i < len; i++){
if((array[i] & (1 << index))!=0){
num2[0] ^= array[i];
}else{
num1[0] ^= array[i];
}
}
/**// @drdr
int split = sum&~(sum - 1);// ！！！
for(int i = 0; i < len; i++){
if((array[i] & split)!=0){
num2[0] ^= array[i];
}else{
num1[0] ^= array[i];
}
}
*/
}
/**
* a ， 2 ，
* @param a
* @return
*/
public static int find1From2(int[] a){
int len = a.length, res = 0;
for(int i = 0; i < len; i++){
res = res ^ a[i];
}
return res;
}
/**
* a ， 3 ，
* @param a
* @return
*/
public static int find1From3(int[] a){
int[] bits = new int[32];
int len = a.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < 32; j++){
bits[j] = bits[j] + ( (a[i]>>>j) & 1);
}
}
int res = 0;
for(int i = 0; i < 32; i++){
if(bits[i] % 3 !=0){// 3 ， 1
res = res | (1 << i);
}
}
return res;
}사고 3: HashMap
6. 피 보 나치 수열
모두 가 피 보 나치 수열 을 알 고 있 습 니 다. 지금 은 정수 n 을 입력 하 라 고 요구 하고 있 습 니 다. 피 보 나치 수열 의 n 번 째 항목 (0 부터 0 번 째 항목 은 0) 을 출력 하 십시오.사고 1: 단순 한 재 귀, 효율 이 낮 고 중복 되 는 계산 이 많아 서 StackOverflow 가 가능 합 니 다.
public class Solution {
public int Fibonacci(int n) {
if(n==0)return 0;// if
if(n==1)return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
}꼬리 귀환, 소 객 망 에서 넘 치 는 것 을 피 할 수 있 습 니 다 @ a000000000
public class Solution {
public int Fibonacci(int n) {
return Fibonacci(n,0,1);
}
private static int Fibonacci(int n,int acc1,int acc2){
if(n==0) return 0;
if(n==1) return acc2;
else return Fibonacci(n - 1, acc2, acc1 + acc2);
}
}
사고 2: 교체 소 객 망 @ fanhk
class Solution {
public:
int Fibonacci(int n) {
int f = 0, g = 1;
while(n-->0) {
g += f;
f = g - f;
}
return f;
}
};
초 운 천
public class Solution {
public int Fibonacci(int n) {
int preNum=1;
int prePreNum=0;
int result=0;
if(n==0)return 0;
if(n==1)return 1;
for(int i=2;i<=n;i++){
result=preNum+prePreNum;
prePreNum=preNum;
preNum=result;
}
return result;
}
}사고 3: 빠 른 속도, O (logn) O (l o g n) 의 시간 복잡 도 는 우 객 망 @ elseyu 에서 나온다.
/*
* O(logN) ： f(n) = f(n-1) + f(n-2)，
* [f(n),f(n-1)] = [f(n-1),f(n-2)] * {[1,1],[1,0]}
* :[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)
* ：
* 1.
* 2. （ ， O(N)）
*/
public class Solution {
public int Fibonacci(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
//
int[][] base = {{1,1},
{1,0}};
// base n-2
int[][] res = matrixPower(base, n - 2);
// [f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)，f(n)
//1*res[0][0] + 1*res[1][0]
return res[0][0] + res[1][0];
}
//
public int[][] multiMatrix(int[][] m1,int[][] m2) {
// ， n*m m*p, n*p
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
/*
* ：
* 1. ， m^n, O(logn)？ ：
* ， 10^75, 75 ：1001011, ：
* 10^75 = 10^64*10^8*10^2*10
* 2. ，
*/
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
// res
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
} //
//
int[][] tmp = m;
//p
for ( ; p != 0; p >>= 1) {
// ，
if ((p&1) != 0) {
res = multiMatrix(res, tmp);
}
//
tmp = multiMatrix(tmp, tmp);
}
return res;
}
}7 과 S 의 두 숫자
정렬 을 늘 리 는 배열 과 숫자 S 를 입력 하고 배열 에서 두 개의 수 를 찾 아 그들의 합 을 S 로 만 듭 니 다. 만약 에 여러 쌍 의 숫자 가 S 와 같 으 면 두 수의 곱 을 가장 적 게 출력 합 니 다.사고방식: 좌우 강요 법
import java.util.ArrayList;
public class Solution {
public ArrayList FindNumbersWithSum(int [] array,int sum) {
ArrayList A=new ArrayList();
int len=array.length;
if(len<2)return A;
int small=-1,large=-1,M=Integer.MAX_VALUE;
for(int m=0,n=len-1;mif(array[m]+array[n]else if(array[m]+array[n]>sum){n--;}
else{// ，
if(m*n//
}
}
if(small==-1)return A;
A.add(array[small]);
A.add(array[large]);
return A;
}
} 그러나 찾 은 첫 번 째 숫자 는 그들 사이 의 거리 가 가장 멀 기 때문에 곱 하기 가 가장 작 기 때문에 선별 하 는 작업 은 면 할 수 있다 는 것 을 증명 할 수 있다.
8. 이 진 트 리 의 다음 노드
이 진 트 리 와 그 중 하 나 를 지정 합 니 다. 중간 순 서 를 옮 겨 다 니 는 다음 결점 을 찾 아 되 돌려 주 십시오.주의 하 세 요. 나무의 결점 은 좌우 자 결점 뿐만 아니 라 아버지 결점 을 가리 키 는 지침 도 포함 되 어 있 습 니 다.
사고: 이 노드 는 오른쪽 나무 가 있 고 다음 점 은 오른쪽 나무의 가장 왼쪽 노드 이다.만약 에 오른쪽 나무 가 없 으 면 자신 이 자신의 아버지 노드 의 왼쪽 노드 인지 판단 한다. 만약 에 다음 노드 가 자신의 아버지 노드 이 고 자신 이 자신의 아버지 노드 의 오른쪽 노드 라면 위로 아들 노드 를 찾 는 것 이 아버지 노드 의 왼쪽 노드 인 상황 이다.
/**
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode){
if(pNode.right!=null){
TreeLinkNode t=pNode.right;
while(t.left!=null)t=t.left;
return t;
}
TreeLinkNode p=pNode.next;//parent-node
TreeLinkNode c=pNode;//child-node
while(p!=null&&p.right==c){
c=p;
p=p.next;
}
return p;
}
}9. 숫자 가 정렬 배열 에 나타 난 횟수
정렬 배열 에 나타 난 숫자 를 집계 합 니 다.
사고 1: 잠시 반응 하지 못 한 것 을 용서 하 세 요. 무시 하 세 요.
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int c=0;
for(int i=0;iif(array[i]==k)c++;
}
return c;
}
} 사고방식 2: 2 분 찾기, O (logn) O (l o g n) 의 시간 복잡 도 는 우 객 망 @ 피자 아저씨
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int length = array.length;
if(length == 0){
return 0;
}
int firstK = getFirstK(array, k, 0, length-1);
int lastK = getLastK(array, k, 0, length-1);
if(firstK != -1 && lastK != -1){
return lastK - firstK + 1;
}
return 0;
}
//
private int getFirstK(int [] array , int k, int start, int end){
if(start > end){
return -1;
}
int mid = (start + end) >> 1;
//int mid=start+(end-start)>>1 // ， start + end
if(array[mid] > k){
return getFirstK(array, k, start, mid-1);
}else if (array[mid] < k){
return getFirstK(array, k, mid+1, end);
}else if(mid-1 >=0 && array[mid-1] == k){
return getFirstK(array, k, start, mid-1);
}else{
return mid;
}
}
//
private int getLastK(int [] array , int k, int start, int end){
int length = array.length;
int mid = (start + end) >> 1;
while(start <= end){
if(array[mid] > k){
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else if(mid+1 < length && array[mid+1] == k){
start = mid+1;
}else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}
그리고 더 깔끔 한 소 객 망 @ drdr.
// data ， ， k ， k-0.5 k+0.5
// ， 。
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
}
private:
int biSearch(const vector<int> & data, double num){
int s = 0, e = data.size()-1;
while(s <= e){
int mid = (e - s)/2 + s;
if(data[mid] < num)
s = mid + 1;
else if(data[mid] > num)
e = mid - 1;
}
return s;
}
};상기 방법 은 k 가 배열 에 존재 하지 않 더 라 도 두 번 에 되 돌아 오 는 값 을 찾 는 것 은 똑 같 습 니 다. 0 으로 줄 이 는 것 은 문제 가 없습니다.
10. 이 진 트 리 를 여러 줄 로 인쇄 합 니 다.
위 에서 아래로 두 갈래 나 무 를 층 별로 인쇄 하고 같은 층 의 결점 은 왼쪽 에서 오른쪽으로 출력 합 니 다.각 층 마다 한 줄 씩 출력 합 니 다.
사고 1: 첫 번 째 생각 은 각 층 의 노드 사이 에 null 노드 를 추가 하여 구분 할 수 있 지만 구분자 없 이 계산 할 수 있 습 니 다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > AA=new ArrayList<ArrayList<Integer>>();
if(pRoot==null)return AA;
Queue<TreeNode> q=new LinkedList<>();
q.offer(pRoot);
int count,c;
ArrayList<Integer> A=new ArrayList<>();
while(!q.isEmpty()){
count=q.size();
c=0;
while(c++<count){//
if(q.peek().left!=null)q.offer(q.peek().left);
if(q.peek().right!=null)q.offer(q.peek().right);
A.add(q.peek().val);
q.poll();
}
// ， A clear，AA clear
AA.add(new ArrayList<>(A));
A.clear();
}
return AA;
}
}사고 2: 층 차 를 옮 겨 다 니 며 돌아 갈 수 있 습 니 다. 확장 사 고 는 우 객 망 @ spursKawhi 에서 왔 습 니 다.
//
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
depth(pRoot, 1, list);
return list;
}
private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
if(root == null) return;
if(depth > list.size())// ArrayList，
list.add(new ArrayList<Integer>());
list.get(depth -1).add(root.val);//
depth(root.left, depth + 1, list);
depth(root.right, depth + 1, list);
}
}사고 3: 두 개의 대기 열 로 각 층 의 노드 를 교체 하여 저장 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
