データ構造プログラミング問題(更新継続)
いくつかのデータ構造のプログラミング問題を記録します.
1、ツリーの深さを計算する
2、逆順にチェーンテーブルを出力する
上の方法は再帰的にスタックの機能を実現し,先進的に後出することである.
自分の愚かな方法:
3、二叉木の前序遍歴と中序遍歴を知り、木構造を復元し、ルートノードを返す
前シーケンスループシーケンスと中シーケンスループシーケンスは、一意のツリーを決定することができる.
先行シーケンスの特徴により、先行シーケンス(PreSequence)の最初の要素(PreSequence[0])が二叉木のルート(root)であることが知られ、次いで、中間シーケンス(InSequence)でこのルート(root)が検索され、中間シーケンスの特徴に基づいて、検索されたルート(root)の前のシーケンスがルートである左サブツリーの中シーケンスがシーケンスを巡回することが知られている.後ろのシーケンスはルートの右サブツリーの中シーケンスでシーケンスを遍歴します.中系列遍歴系列(InSequence)の根元の前にleft個の要素を設ける.前シーケンス(PreSequence)では、ルート(root)に続くleft個の要素シーケンス(すなわちPreSequence[1…left])がルートである左サブツリーの前シーケンス遍歴シーケンス、後のルートである右サブツリーの前シーケンス遍歴シーケンスである.一方,左サブツリーを構築する問題は,二叉木全体を構築する問題と同様であるが,このとき前シーケンスはPreSequence[1...left]),中シーケンスはInSequence[0...left-1]であり,それぞれ元のシーケンスのサブ列であり,右サブツリーを構築するのと同様に再帰的に解決できることは明らかである.
4、反復と再帰の選択
階段を跳ぶ:一度に1段の階段を跳ぶことも、2段を跳ぶこともできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
反復:
再帰:
再帰を使用すると、エラーが報告され、実行がタイムアウトすることがよくあります.プログラムが所定の時間内に実行されず、ループが間違っているか、アルゴリズムが複雑すぎているかを確認してください.
これは、再帰的に多くの冗長コードが呼び出され、実行時間が長すぎるためです.したがって、反復は冗長コードを減らすことができますが、再帰はプログラムをより明確にします.
5、逆置きチェーンテーブル
6、スピードポインタの応用
①チェーンテーブルにループがあるか否かの判断
チェーンテーブルを指定します.チェーンテーブルにリングがある場合は、リングの入口ノードを指定します.そうでない場合はnullを返します.
出会ったノードからリングの開始ノードまでの距離は、チェーンテーブルの開始点からリングの開始ノードまでの距離に等しい!
7、二叉木を遍歴し、上から下へ遍歴し、同級要素を左から右へ遍歴する
8、二叉木の三種類の遍歴方式
9、ダブルスタックのソート:スタックを昇順にソートします(つまり、最大要素はスタックの一番上にあります)、最大1つの追加のスタックを使用して一時データを保存するしかありませんが、要素を他のデータ構造にコピーしてはいけません.
int[]numbers(C++でvector<int>)が与えられ、最初の要素がスタックトップである場合は、ソートされたスタックに戻ります.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
10、二叉木のバランスを判断する
基本思想は深さを計算して対比することである.
11、単一チェーンテーブルの最後からn番目のノードを削除する
構想:間隔nの2つのポインタを利用!!Brilllllllliant!!
12、単一チェーンテーブルの重複要素を削除する
私の本方法..(どうしてこの言葉はいつも出てくるのか):
1、ツリーの深さを計算する
public class Solution {
public int TreeDepth(TreeNode pRoot) {
return pRoot == null ? 0 : Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1;
}
}2、逆順にチェーンテーブルを出力する
public class Solution {
ArrayList arrayList=new ArrayList();
public ArrayList printListFromTailToHead(ListNode listNode) {
if(listNode!=null){
this.printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}
} 上の方法は再帰的にスタックの機能を実現し,先進的に後出することである.
自分の愚かな方法:
public ArrayList printListFromTailToHead(ListNode listNode) {
Stack res = new Stack();
ArrayList relist = new ArrayList();
if(listNode==null){
return null;
}
while (listNode.next != null) {
res.push(listNode.val);
listNode = listNode.next;
}
res.push(listNode.val);
while(!res.isEmpty()) {
relist.add((Integer) res.pop());
}
return relist;
} 3、二叉木の前序遍歴と中序遍歴を知り、木構造を復元し、ルートノードを返す
前シーケンスループシーケンスと中シーケンスループシーケンスは、一意のツリーを決定することができる.
先行シーケンスの特徴により、先行シーケンス(PreSequence)の最初の要素(PreSequence[0])が二叉木のルート(root)であることが知られ、次いで、中間シーケンス(InSequence)でこのルート(root)が検索され、中間シーケンスの特徴に基づいて、検索されたルート(root)の前のシーケンスがルートである左サブツリーの中シーケンスがシーケンスを巡回することが知られている.後ろのシーケンスはルートの右サブツリーの中シーケンスでシーケンスを遍歴します.中系列遍歴系列(InSequence)の根元の前にleft個の要素を設ける.前シーケンス(PreSequence)では、ルート(root)に続くleft個の要素シーケンス(すなわちPreSequence[1…left])がルートである左サブツリーの前シーケンス遍歴シーケンス、後のルートである右サブツリーの前シーケンス遍歴シーケンスである.一方,左サブツリーを構築する問題は,二叉木全体を構築する問題と同様であるが,このとき前シーケンスはPreSequence[1...left]),中シーケンスはInSequence[0...left-1]であり,それぞれ元のシーケンスのサブ列であり,右サブツリーを構築するのと同様に再帰的に解決できることは明らかである.
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0||in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),
Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),
Arrays.copyOfRange(in, i+1,in.length));
}
}
return node;
}
}4、反復と再帰の選択
階段を跳ぶ:一度に1段の階段を跳ぶことも、2段を跳ぶこともできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
反復:
public int JumpFloor(int target) {
if(target == 1 || target == 2) {
return target;
}
// ， ，
// ： = +
int jumpSum = 0;//
int jumpSumBackStep1 = 2;// ( 3 )
int jumpSumBackStep2 = 1;// ( 3 )
for(int i = 3; i <= target; i++) {
jumpSum= jumpSumBackStep1 + jumpSumBackStep2;
jumpSumBackStep2 = jumpSumBackStep1;//
jumpSumBackStep1 = jumpSum; //
}
return jumpSum;
}再帰:
public class Solution {
public int jumpFloor(int number) {
if(number <= 0)
return 0;
else if(number == 1)
return 1;
else if(number == 2)
return 2;
else
return jumpFloor(number-1) + jumpFloor(number-2);
}
}再帰を使用すると、エラーが報告され、実行がタイムアウトすることがよくあります.プログラムが所定の時間内に実行されず、ループが間違っているか、アルゴリズムが複雑すぎているかを確認してください.
これは、再帰的に多くの冗長コードが呼び出され、実行時間が長すぎるためです.したがって、反復は冗長コードを減らすことができますが、再帰はプログラムをより明確にします.
5、逆置きチェーンテーブル
//java
public ListNode ReverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
//
ListNode pre=null;
ListNode next=null;
ListNode cur=head;
while(cur!=null){
next=cur.next;
cur.next=pre;//cur.next--->pre
pre=cur;
cur=next;
}
return pre;
}6、スピードポインタの応用
①チェーンテーブルにループがあるか否かの判断
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode fast = head, slow = head;
while(fast != null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
// fast ， fast.next
// ， next ， true
return head.next == head;
} チェーンテーブルを指定します.チェーンテーブルにリングがある場合は、リングの入口ノードを指定します.そうでない場合はnullを返します.
public ListNode detectCycle(ListNode head) {
// ，
ListNode meetNode = meetNode(head);
if(meetNode == null){
return null;
}
ListNode slow = head;
// ，
while(slow != meetNode){
slow = slow.next;
meetNode = meetNode.next;
}
return slow;
}
public ListNode meetNode(ListNode head){
if(head == null){
return null;
}
ListNode meetNode;
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
meetNode = slow;
return meetNode;
}
}
// fast ， fast.next
// ， next ， true
return head.next == head ? head : null;
}出会ったノードからリングの開始ノードまでの距離は、チェーンテーブルの開始点からリングの開始ノードまでの距離に等しい!
7、二叉木を遍歴し、上から下へ遍歴し、同級要素を左から右へ遍歴する
public class Solution {
public ArrayList PrintFromTopToBottom(TreeNode root) {
ArrayList list = new ArrayList();
if(root==null){
return list;
}
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
list.add(treeNode.val);
}
return list;
}
} 8、二叉木の三種類の遍歴方式
/**
*
*
* ，
*
* @param node
*
*/
public static void preOrderTraverse(Node node) {
if (node == null)
return;
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
/**
*
*
* ，
*
* @param node
*
*/
public static void inOrderTraverse(Node node) {
if (node == null)
return;
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
/**
*
*
* ，
*
* @param node
*
*/
public static void postOrderTraverse(Node node) {
if (node == null)
return;
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
} 9、ダブルスタックのソート:スタックを昇順にソートします(つまり、最大要素はスタックの一番上にあります)、最大1つの追加のスタックを使用して一時データを保存するしかありませんが、要素を他のデータ構造にコピーしてはいけません.
int[]numbers(C++でvector<int>)が与えられ、最初の要素がスタックトップである場合は、ソートされたスタックに戻ります.これはスタックであることに注意してください.これは、ソート中に最初の要素にしかアクセスできないことを意味します.
import java.util.*;
public class TwoStacks {
public ArrayList twoStacksSort(int[] numbers) {
// write code here
ArrayList result = new ArrayList<>(numbers.length);
//
Stack stack = new Stack<>();
int index = numbers.length - 1;
for (int i = index; i >= 0; i--) {
stack.push(numbers[i]);
}
Stack resultStack = new Stack<>();//
while (!stack.empty()) {
if (resultStack.empty()) {
resultStack.push(stack.pop());
} else {
int a = stack.pop();
int b = resultStack.pop();
int popNum = 0;
if (a < b) {
stack.push(b);
while (!resultStack.empty() && a < (b = resultStack.pop())) {
stack.push(b);
popNum++;
}
}
if (a >= b) {
resultStack.push(b);
}
resultStack.push(a);
while(popNum>0){
resultStack.push(stack.pop());
popNum--;
}
}
}
// ArrayList
while (!resultStack.empty()) {
result.add(resultStack.pop());
}
return result;
}
} 10、二叉木のバランスを判断する
public class Balance {
public boolean isBalance(TreeNode root) {
// write code here
if(root==null)
return true;
if(Math.abs(deepth(root.left)-deepth(root.right))>1)
return false;
else
return isBalance(root.left)&isBalance(root.right);
}
public int deepth(TreeNode root){
if(root==null)
return 0;
return Math.max(deepth(root.left),deepth(root.right))+1;
}
}基本思想は深さを計算して対比することである.
11、単一チェーンテーブルの最後からn番目のノードを削除する
構想:間隔nの2つのポインタを利用!!Brilllllllliant!!
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0);
ListNode slow = start, fast = start;
slow.next = head;
//Move fast in front so that the gap between slow and fast becomes n
for(int i=1; i<=n+1; i++) {
fast = fast.next;
}
//Move fast to the end, maintaining the gap
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
//Skip the desired node
slow.next = slow.next.next;
return start.next;
}12、単一チェーンテーブルの重複要素を削除する
私の本方法..(どうしてこの言葉はいつも出てくるのか):
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode headbak = head;
while(head != null && head.next!=null){
if(head.val == head.next.val){
head.next = head.next.next;
}else{
head = head.next;
}
}
return headbak;
}
}public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}