剣指offer-java(2)
43575 ワード
(1)スタックの圧入・イジェクトシーケンスは2つの整数シーケンスを入力し、1番目のシーケンスはスタックの圧入順序を表し、2番目のシーケンスがスタックのイジェクト順序であるか否かを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであるはずがない.
(2)上から下へ印刷ツリー上から下へ印刷ツリーの各ノード、同層ノード左から右へ印刷.
3,二叉探索木の後順遍歴シーケンス整数配列を入力し,その配列がある二叉探索木の後順遍歴の結果であるか否かを判断する.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
4.ツリーと値のパスに2つのツリーと整数を入力し、ツリー内のノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.
5.複雑なチェーンテーブルのレプリケーションは、複雑なチェーンテーブルを入力します(各ノードにはノード値があり、2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指します).
6.二叉探索ツリーと双方向チェーンテーブルは二叉探索ツリーを入力し、この二叉探索ツリーを並べ替えた双方向チェーンテーブルに変換し、新しいノードを作成できないことを要求し、ツリー内のノードポインタの指向を調整するしかない.
7.文字列の配列文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.結果はアルファベット順に出力してください.
8,配列の出現回数が半分を超える数字
9,最小K個数
10、連続サブ配列の最大和
11,整数のうち1が出現する回数(1からnまでの整数のうち1が出現する回数)
12、配列を最小の数に並べて正の整数配列を入力し、配列内のすべての数字をつなぎ合わせて1つの数に並べ、つなぎ合わせることができるすべての数字の中で最小の1つを印刷します.例えば配列{3,32321}を入力すると、この3つの数字が並べられる最小数字は321323となる.
13,丑数因子2,3,5のみを含む数を丑数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の醜数を求めます
最初に1回しか現れない文字の位置は、1つの文字列(1<=文字列長<=10000、すべてアルファベットからなる)の中で、最初に1回しか現れない文字の位置を見つけます.空白列の場合は、-1を返します.位置インデックス0から開始
配列内の2つの数値で、前の1つの数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.配列を入力し、この配列の逆シーケンスペアの総数を求めます.
2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
ソート配列に表示される数値の回数を統計します.方法1:
方法2:ソートされた配列または部分的にソートされた配列で1つの数値を検索するか、数値の出現回数を統計する必要がある場合は、二分ルックアップを使用してみてください.
ツリーの深さを求めるツリーを入力します.ルートノードからリーフノードまで順次通過するノード(ルート、リーフノードを含む)は、ツリーのパスを形成し、最長パスの長さはツリーの深さである.
ツリーを入力し、ツリーがバランスツリーであるかどうかを判断します.
1つの整数配列には2つの数字を除いて、他の数字が2回現れた.プログラムを書いて、この2つの一度しか現れない数字を見つけてください.
import java.util.ArrayList;
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
LinkedList<Integer> stack=new LinkedList<Integer>();
if(pushA.length==0||popA.length==0)
return false;
int j=0;
for(int i=0;i<pushA.length;i++){
stack.push(pushA[i));
while(j<pushA.length&& stack.peek()==popA[j]){
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}(2)上から下へ印刷ツリー上から下へ印刷ツリーの各ノード、同層ノード左から右へ印刷.
import java.util.ArrayList;
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
import java.util.*;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
// ，
ArrayList<Integer> list=new ArrayList<Integer>();
LinkedList<Integer> queue=new LinkedList<Integer>();
if(root==null)
return list;
queue.offer(root);
while(queue!=null){
TreeNode node=queue.poll();
if(node.left!=null)
queue.offer(root.left);
if(node.right!=null)
queue.offer(root.right);
list.add(node.val);
}
return list;
}
}3,二叉探索木の後順遍歴シーケンス整数配列を入力し,その配列がある二叉探索木の後順遍歴の結果であるか否かを判断する.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
// ， ， 。 ，
if(sequence.length==0)
return false;
return VerifySquenceOfBST(sequence,0,sequence.length-1);
}
public boolean VerifySquenceOfBST(int[] sequence,int start,int end){
if(end<=start)
return true;
int i=start;
for(;i<end;i++){
if(sequence[i]>sequence[end]){
break;
}
}
for(int j=i;j<end;j++){
if(sequence[j]<sequence[end])
return false;
}
return VerifySquenceOfBST(sequence,start,i-1)&VerifySquenceOfBST(sequence,i,end-1);
}
}4.ツリーと値のパスに2つのツリーと整数を入力し、ツリー内のノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.
import java.util.ArrayList;
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> pathList=new ArrayList<ArrayList<Integer>>();
if(root==null)
return ;
LinkedList<Integer> stack=new LinkedList<Integer>();
findpath(root,target,stack,pathList);
return pathList;
}
public void findpath(TreeNode root,int target,LinkedList<Integer> stack,ArrayList<ArrayList<Integer>> pathList){
if(root==null)
return;
if(root.left==null&&root.right==null){
ArrayList<Integer> list=new ArrayList<Integer>();
for(int i: stack){
list.add(new Integer(i));
}
list.add(new Integer(root.val));
pathList.add(list);
}
}else{
stack.add(new Integer(root.val));
findpath(root.left,target-root.val,stack,pathList);
findpath(root.right,target-root.val,stack,pathList);
stack.remove(stack.size()-1);
}
}5.複雑なチェーンテーブルのレプリケーションは、複雑なチェーンテーブルを入力します(各ノードにはノード値があり、2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタは任意のノードを指します).
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution{
public RandomListNode Clone(RandomListNode pHead){
if(pHead==null)
return null;
RandomListNode head=new RandomListNode(pHead.label);
RandomListNode and=head;
if(pHead.random!=null){
head.random=new RandomListNode (pHead.random.label);
}
while(pHead.next!=null){
pHead=pHead.next;
head.next=new RandomListNode (pHead.label);
if(pHead.random!=null){
head.next.random=new RandomListNode (pHead.random.label);
}
head=head.next;
}
return and;
}
}6.二叉探索ツリーと双方向チェーンテーブルは二叉探索ツリーを入力し、この二叉探索ツリーを並べ替えた双方向チェーンテーブルに変換し、新しいノードを作成できないことを要求し、ツリー内のノードポインタの指向を調整するしかない.
// - ，
public class Solution{
public TreeNode Convert(TreeNode pRootOfTree){
if(pRootOfTree==null)
return null;
if(pRootOfTree.left==null&&pRootOfTree.right==null)
return pRootOfTree;
TreeNode left=Convert(pRootOfTree.left);
TreeNode p=left;
while(p!=null&&p.right!=null)
p=p.right;
if(left!=null){
p.right=pRootOfTree;
pRootOfTree.left=p;
}
TreeNode right=Convert(pRootOfTree.right);
if(right!=null){
pRootOfTree.right=right;
right.left=pRootOfTree;
}
return left!=null?left:pRootOfTree;
}
}7.文字列の配列文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.結果はアルファベット順に出力してください.
import java.util.*;
public class Solution{
public ArrayList<String> Permutation(String str){
ArrayList<String> list=new ArrayList<String>();
if(str==null||str.length()==0)
return list;
char[] c=str.toCharArray();
TreeSet<String> result=new TreeSet<String>();
Permutation(c,0,result);
list.addAll(result);
return list;
}
public void Permutation(char[] c,int begin,TreeSet<String> result){
if(c==null||c.length==0||begin<0||begin>c.length-1)
return;
if(begin==c.length-1)
result.add(String.valueOf(c));
else{
for(int i=begin;i<c.length;i++){
swap(c,begin,i);
Permutation(c,begin+1,result);
swap(c,begin,i);
}
}
}
public void swap(char[] c,int begin, int i){
char tmp=c[begin];
c[begin]=c[i];
c[i]=tmp;
}
}8,配列の出現回数が半分を超える数字
public class Solution{
public int MoreThanHalfNum(int[] array){
if(array==null||array.length==0)
return 0;
int count=0;
int mid=array[(array.length-1)/2];
for(int i: array){
if(i==mid)
count++;
}
if(array.length<count*2)
return mid;
else
return 0;
}
}9,最小K個数
import java.util.*;
public class Solution{
public ArrayList<Integer> getNumber(int[] input,int k){
ArrayList<Integer> list=new ArrayList<Integer>();
if(input==null||input.length==0||input.length<k)
return list;
Arrays.sort(input);
for(int i=0;i<k;i++){
list.add(input[i]);
}
return list;
}
}10、連続サブ配列の最大和
import java.util.*;
public class Solution{
public int findSumOfSubArray(int[] array){
List<Integer> list=new ArrayList<Integer>();
if(array.length==0||array==null)
return 0;
for(int i=0;i<array.length;i++){
int sum=0;
for(int j=i;j<array.length;j++){
sum+=array[j];
list.add(sum);
}
}
Collections.sort(list);
return list.get(list.size()-1);
}
}11,整数のうち1が出現する回数(1からnまでの整数のうち1が出現する回数)
import java.util.*;
public class Solution{
public int NumberOfBetween1AndN(int n){
int i=countNum(n);
return i;
}
public int countNum(int n){
if(n==0)
return 0;
if(n<10)
return 1;
int len=new Integer(n).toString().length();
int first;
int count=0;
for(len--;len>=0;len--){
first=(int)(n/Math.pow(10,len));
if(len==0&&first!=0)
return ++count;
else if(len==0)
return count;
if(first>1)
count+=first*getCount(len)+getCount2(len);
else if(first==1)
count+=n%getCount2(len)+1+first*getCount(len);
n=(int)(n%getCount(len));
}
return count;
}
public int getCount(int len){
return len*(int)(Math.pow(10,len-1));
}
public int getCount2(int len){
return (int)Math.pow(10,len);
}
}12、配列を最小の数に並べて正の整数配列を入力し、配列内のすべての数字をつなぎ合わせて1つの数に並べ、つなぎ合わせることができるすべての数字の中で最小の1つを印刷します.例えば配列{3,32321}を入力すると、この3つの数字が並べられる最小数字は321323となる.
import java.util.*;
public class Solution{
public String PrintMinNumber(int[] numbers){
ArrayList<Integer> list=new ArrayList<Integer>();
String s="";
for(int i=0;i<numbers.length;i++){
list.add(numbers[i]);
}
Collections.sort(list,new Comparator<Integer>(){
public int compare(Integer str1,Integer str2){
String s1=str1+""+str2;
String s2=str2+""+str1;
return s1.compareTo(s2);
}
});
for(int j: list){
s+=j;
}
return s;
}
}13,丑数因子2,3,5のみを含む数を丑数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の醜数を求めます
import java.util.*;
public class Solution{
public int GetUglyNumber(int index){
if(index==1)
return 1;
if(index==0)
return 0;
List<Integer> list=new ArrayList<Integer>();
list.add(1);
int i2=0,i3=0,i5=0;
for(list.size()<index){
int n2=list.get(i2)*2;
int n3=list.get(i3)*3;
int n5=list.get(i5)*5;
int min=Math.min(n2,Math.min(n3,n5));
list.add(min);
if(min==n2)
i2++;
if(min==n3)
i3++;
if(min==n5)
i5++;
}
return list.get(list.size()-1);
}
}最初に1回しか現れない文字の位置は、1つの文字列(1<=文字列長<=10000、すべてアルファベットからなる)の中で、最初に1回しか現れない文字の位置を見つけます.空白列の場合は、-1を返します.位置インデックス0から開始
import java.util.*;
public class Solution{
public int firstNotRepeatingChar(String str){
if(str==null||str.length()==0)
return -1;
for(int i=0;i<str.length();i++){
if(str.length()-str.replaceAll(str.charAt(i)+"","").toString().length()==1)
return i;
}
return -1;
}
}配列内の2つの数値で、前の1つの数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.配列を入力し、この配列の逆シーケンスペアの総数を求めます.
public class Solution{
public int InversePairs(int[] array){
int count=0;
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[i]>array[j])
count++;
}
}
return count;
}
}2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
import java.util.*;
public class Solution{
public ListNode findFirstCommonNode(ListNode pHead1,ListNode pHead2){
if(pHead1==null||pHead2==null)
return null;
int count1=0;
ListNode p1=pHead1;
while(p1!=null){
p1=p1.next;
count1++;
}
int count2=0;
ListNode p2=pHead2;
while(p2!=null){
p2=p2.next;
count2++;
}
// pHead1 pHead2 ，
int flag=count1-count2;
if(flag>0){
while(flag>0){
pHead1=pHead1.next;
flag--;
}
while(pHead1!=pHead2){
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return pHead1;
}
if(flag<=0){
while(flag<0){
pHead2=pHead2.next;
flag++;
}
while(pHead1!=pHead2){
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return pHead1;
}
return null;
}
}ソート配列に表示される数値の回数を統計します.方法1:
public class Solution{
public int getNumber(int[] array,int k){
int count=0;
for(int i=0;i<array.length;i++){
if(array[i]==k)
count++;
}
return count;
}
}方法2:ソートされた配列または部分的にソートされた配列で1つの数値を検索するか、数値の出現回数を統計する必要がある場合は、二分ルックアップを使用してみてください.
public class Solution{
public int getNumber(int[] array,int k){
if(array.length==0)
return 0;
int low=0;
int high=array.length-1;
int mid=(low+high)/2;
int count=0;
while(low<high){
mid=(low+high)/2;
if(array[mid]>k){
high=mid-1;
}else if(array[mid]<k){
low=mid+1;
}else{
count=1;
int temp=mid-1;
while(temp>=0&&array[temp]==array[mid]){
count++;
temp--;
}
temp=mid+1;
while(temp<array.length&&array[temp]==array[mid]){
count++;
temp++;
}
break;
}
}
return count;
}
}ツリーの深さを求めるツリーを入力します.ルートノードからリーフノードまで順次通過するノード(ルート、リーフノードを含む)は、ツリーのパスを形成し、最長パスの長さはツリーの深さである.
public class Solution{
public int TreeDepth(TreeNode root){
if(root==null)
return 0;
int nLeft=TreeDepth(root.left);
int nRight=TreeDepth(root.right);
return nLeft>nRight?(nLeft+1):(nRight+1);
}
}ツリーを入力し、ツリーがバランスツリーであるかどうかを判断します.
：
： 1
import java.util.*;
public class Solution{
public boolean isBalanced(TreeNode root){
if(root==null)
return true;
if(Math.abs(getHight(root.left)-getHeight(root.right))>1)
return false;
return isBalanced(root.left)&isBalanced(root.right);
}
public int getHeight(TreeNode root){
if(root==null)
return 0;
return Math.max(getHeight(root.left),getHeight(root.right));
}
}1つの整数配列には2つの数字を除いて、他の数字が2回現れた.プログラムを書いて、この2つの一度しか現れない数字を見つけてください.
import java.util.*;
//num1,num2 1 。
// num1[0],num2[0]
public class Solution{
public void findNumsAppearOnce(int[] array,int num1[],int num2[]){
if(array.length<2){
num1[0]=0;
num2[0]=0;
return;
}
if(array.length==2||array[0]!=array[1]){
num1[0]=array[0];
num2[0]=array[1];
}
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[i]^array[j]==0)
array[i]=array[j]=0;
}
}
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<array.length;i++){
if(array[i]!=0)
list.add(array[i]);
}
num1[0]=list.get(0);
num2[0]=list.get(1);
}
}