面白いアルゴリズムの問題-2
12035 ワード
二叉サーチツリーと双方向リンク表
一本の二叉検索ツリーを入力して、二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.
1.lastNodeのポインタを使って一番右のノードを指します.
文字列を入力し、文字列のすべての配列を辞書順に印刷します.例えば文字列a b cを入力すると、文字a,b,cによって並べられるすべての文字列abc,acb,bac,bca,cabおよびcbaがプリントされる.
1.最初の数を標準numとし、後の要素は同じcount+1で、count-1ではない.count==0の時、numは新しい数を指して、count=1を命令して、更にこのように続けて、後を知っています.
2.最後に得たnumでもう一度遍歴して、出現回数が本当にarray.length/2より大きいかどうか見てください.
一番小さいK個の数
n個の整数を入力して、一番小さいK個の数を探します.例えば4,5,1,6,2,7,3,8という8つの数字を入力すると、最小の4つの数字は1,2,3,4です.
1.まず前のK個の数に対して最大の山を作ってください.
2.Kの後の数は順にトップの元素と比較して、山の頂より小さいのは山の頂の元素を削除して、この元素をチームに入れて、ずっとこの山をK元素として維持しています.
3.最後の山のK個の数が求められている元素です.
1.Collectionの関数を定義し、リスト内のすべての組み合わせを組み合わせの大きさに並べ替える.
1.Nの長さの配列、p 2、p 3、p 5の3つのポインタを作ります.
2.3つのポインタはそれぞれ対応する数に乗り、一番小さいのは配列の次の数に加えられます.これは選択したポインタだけ後退します.他のものは変わりません.
1.正規並べ替えで解決する
1.配列内のすべての数を異ならないか、または結果を得たmayor(同じ全部が相殺され、残りは2つの異なる数).
2.mayorの最後の一つが1の数を見つけます.
3.回数によって配列を2つのグループに分け、2つの異なる数をそれぞれ2つのグループに落とし、最後に異種または最後の数を求める.
明さんは数学が大好きで、ある日彼は数学の宿題をする時、9～16の和を計算するように要求しました.彼はすぐに正しい答えを書いたのは100です.しかし、彼はこれに満足していません.どれぐらいの連続的な正数系列があるかということと、100(少なくとも2つの数を含む)であるかを彼は考えています.まもなく、彼は他の組の連続正数と100のシーケンスを獲得します.18,19,20,21,22.今は問題をあなたに任せます.すべてとSの連続正数シーケンスをすぐに見つけられますか?Good Luck
1)私達が探しているのはSとの連続正数列なので、このシーケンスは公差が1の等差数列です.このシーケンスの中間値は平均値の大きさを表しています.シーケンスの長さがnであると仮定すれば、このシーケンスの中間値は(S／n)で得られ、シーケンスの中間値と長さを知ることができ、このシーケンスは容易に求められなくなる.
2)条件を満たすnは2つの場合に分けられます.
nが奇数の場合、シーケンスの中間の数はちょうどシーケンスの平均値ですので、条件は:(n&1)==1&sum%n==0です.
nが偶数の場合、シーケンスの中間の2つの数の平均値はシーケンスの平均値であり、この平均値の小数点以下は0.5であるため、条件は:(sum%n)*2==n.
3)問題からn>=2が分かりますが、nの最大値はいくらですか?私たちはnを2からSまで全部遍歴することができますが、大部分遍歴は必要ではありません.nをできるだけ大きくするために、シーケンスを1から開始します.
等差数列の合計式によると、S=(1+n)*n/2となります.
最後に例を挙げます.sum=100を入力すると、n=13~2を遍歴するだけでいいです.n=8の場合、シーケンス[9,10,11,13,14,15,16];n = 5の場合、シーケンス[18,19,20,21,22]を取得します.
完全コード:時間の複雑さは
毎年六一子供の日に、牛客はいくつかの小さいプレゼントを用意して孤児院の子供たちを見舞いに行きます.今年もこのようです.HFは牛客のベテランとして、もちろんいくつかの小さいゲームを用意しました.その中には、まず子供たちを大きな輪にするゲームがあります.それから、彼は無作為に1つの数mを指定して、番号が0の子供に新聞を開始させます.m-1という子供は毎回列に並んで歌を歌います.そしてプレゼント箱の中から任意のプレゼントを選んでください.そしてもう圏内に戻りません.彼の次の子供から、0…m-1の番号を続けます.このままでは…最後の子供までショーをしなくてもいいです.そして牛客の名前が高い「名探偵コナン」の典蔵版をもらいます.このプレゼントはどの子供がもらえるか考えてみてください.(注:子供の番号は0からn-1まで)
1.行列arr[]で1からnまで記録し、しゃがんだら0とする.
2.indexは歩いた人数を記録し、dunNumbersは歩いたことがあるがしゃがんだ人数を記録し、dunsはしゃがんだ人数を記録している.
一本の二叉検索ツリーを入力して、二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.
1.lastNodeのポインタを使って一番右のノードを指します.
/**
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) {
TreeNode lastNode = null;
lastNode = ConvertNode(pRootOfTree, lastNode);
while(lastNode != null && lastNode.left != null){
lastNode = lastNode.left;
}
return lastNode;
}
public TreeNode ConvertNode(TreeNode root, TreeNode lastNode){
if(root == null)
return null;
if(root.left != null)
lastNode = ConvertNode(root.left, lastNode);
root.left = lastNode;
if(lastNode != null)
lastNode.right = root;
lastNode = root;
if(root.right != null){
lastNode = ConvertNode(root.right, lastNode);
}
return lastNode;
}
}文字列を入力し、文字列のすべての配列を辞書順に印刷します.例えば文字列a b cを入力すると、文字a,b,cによって並べられるすべての文字列abc,acb,bac,bca,cabおよびcbaがプリントされる.
import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList Permutation(String str) {
ArrayList list = new ArrayList();
int index = 0;
Permutation(list, index, str.toCharArray());
Collections.sort(list);
return list;
}
public void Permutation(ArrayList list, int index, char[] str){
if(index == str.length - 1)
list.add(new String(str));
else{
for(int i = index; i < str.length; i++){
if(i == index || str[i] != str[index])
{
swap(str, i, index);
Permutation(list, index+1, str);
swap(str, index, i);
}
}
}
}
public void swap(char[] str, int i, int j){
if(str.length < 2)
return;
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
} 1.最初の数を標準numとし、後の要素は同じcount+1で、count-1ではない.count==0の時、numは新しい数を指して、count=1を命令して、更にこのように続けて、後を知っています.
2.最後に得たnumでもう一度遍歴して、出現回数が本当にarray.length/2より大きいかどうか見てください.
一番小さいK個の数
n個の整数を入力して、一番小さいK個の数を探します.例えば4,5,1,6,2,7,3,8という8つの数字を入力すると、最小の4つの数字は1,2,3,4です.
1.まず前のK個の数に対して最大の山を作ってください.
2.Kの後の数は順にトップの元素と比較して、山の頂より小さいのは山の頂の元素を削除して、この元素をチームに入れて、ずっとこの山をK元素として維持しています.
3.最後の山のK個の数が求められている元素です.
import java.util.*;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList list = new ArrayList();
if(input == null || input.length < k || k == 0)
return list;
for(int i = k/2 - 1; i >= 0; i--){
adjustMaxHeap(input, i, k-1);
}
for(int i = k; i < input.length; i++){
if(input[i] < input[0])
{
int temp = input[i];
input[i] = input[0];
input[0] = temp;
adjustMaxHeap(input, 0, k-1);
}
}
for(int i = 0; i < k; i++){
list.add(input[i]);
}
return list;
}
public void adjustMaxHeap(int[] input, int pos, int length){
int child = 0;
int temp;
for(temp = input[pos]; 2*pos+1 <= length; pos = child)
{
child = 2*pos+1;
if(child < length && input[child] < input[child+1])
{
child++;
}
if(input[child] > temp){
input[pos] = input[child];
}
else{
break;
}
}
input[pos] = temp;
}
} 1.Collectionの関数を定義し、リスト内のすべての組み合わせを組み合わせの大きさに並べ替える.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
ArrayList list = new ArrayList();
int n = numbers.length;
String s = "";
for(int i = 0; i < n; i++)
{
list.add(numbers[i]);
}
Collections.sort(list, new Comparator(){
public int compare(Integer s1, Integer s2)
{
String str1 = s1 + "" + s2;
String str2 = s2 + "" + s1;
return str1.compareTo(str2);
}
});
for(int data : list)
{
s += data;
}
return s;
}
} 1.Nの長さの配列、p 2、p 3、p 5の3つのポインタを作ります.
2.3つのポインタはそれぞれ対応する数に乗り、一番小さいのは配列の次の数に加えられます.これは選択したポインタだけ後退します.他のものは変わりません.
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
int[] pUgly = new int[index];
pUgly[0] = 1;
int nextUgly = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
while(nextUgly < index)
{
int min = Min(2*pUgly[p2], 3*pUgly[p3], 5*pUgly[p5]);
pUgly[nextUgly] = min;
if(2*pUgly[p2] <= pUgly[nextUgly])
p2++;
if(3*pUgly[p3] <= pUgly[nextUgly])
p3++;
if(5*pUgly[p5] <= pUgly[nextUgly])
p5++;
nextUgly++;
}
return pUgly[nextUgly-1];
}
public int Min(int p1, int p2, int p3)
{
return p1 >= p2 ? (p2 > p3 ? p3 : p2) : (p1 > p3 ? p3 : p1);
}
}import java.util.*;
public class Solution {
public int FirstNotRepeatingChar(String str) {
Map map = new HashMap();
char[] ch = str.toCharArray();
for(int i = 0; i < ch.length; i++)
{
if(map.containsKey(ch[i]))
{
map.put(ch[i], map.get(ch[i])+1);
}
else{
map.put(ch[i], 1);
}
}
for(int i = 0; i < ch.length; i++)
{
if(map.get(ch[i]) == 1)
return i;
}
return -1;
}
} 1.正規並べ替えで解決する
public class Solution {
public int InversePairs(int [] array) {
if(array.length <= 1 || array == null)
return 0;
int[] copy = new int[array.length];
for(int i = 0; i < array.length; i++)
copy[i] = array[i];
int count = 0;
count = InverseCorePairs(array, copy, 0, array.length-1)%1000000007;
return count % 1000000007;
}
public int InverseCorePairs(int[] array, int[] copy, int start, int end)
{
if(start == end)
{
return 0;
}
int mid = (start+end)>>1;
int left = InverseCorePairs(array, copy, start, mid)%1000000007;
int right = InverseCorePairs(array, copy, mid+1, end)%1000000007;
int i = mid;
int j = end;
int copyIndex = end;
int count = 0;
while(i >= start && j >= mid+1)
{
if(array[i] > array[j])
{
copy[copyIndex--] = array[i--];
count += j - mid;
if(count >= 1000000007)
count = count % 1000000007;
}
else{
copy[copyIndex--] = array[j--];
}
}
for(;i >= start; i--)
{
copy[copyIndex--] = array[i];
}
for(; j >= mid+1; j--)
{
copy[copyIndex--] = array[j];
}
for(int ii = start; ii <= end; ii++)
array[ii] = copy[ii];
return (left + count + right)%1000000007;
}
}
1.配列内のすべての数を異ならないか、または結果を得たmayor(同じ全部が相殺され、残りは2つの異なる数).
2.mayorの最後の一つが1の数を見つけます.
3.回数によって配列を2つのグループに分け、2つの異なる数をそれぞれ2つのグループに落とし、最後に異種または最後の数を求める.
//num1,num2 1 。
// num1[0],num2[0]
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int mayor = 0;
for(int i = 0; i < array.length; i++)
{
mayor ^= array[i];
}
int flag = 1;
while((flag & mayor) == 0)
flag <<= 1;
for(int i = 0; i < array.length; i++)
{
if((array[i] & flag) == 0)
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}
}
}明さんは数学が大好きで、ある日彼は数学の宿題をする時、9～16の和を計算するように要求しました.彼はすぐに正しい答えを書いたのは100です.しかし、彼はこれに満足していません.どれぐらいの連続的な正数系列があるかということと、100(少なくとも2つの数を含む)であるかを彼は考えています.まもなく、彼は他の組の連続正数と100のシーケンスを獲得します.18,19,20,21,22.今は問題をあなたに任せます.すべてとSの連続正数シーケンスをすぐに見つけられますか?Good Luck
1)私達が探しているのはSとの連続正数列なので、このシーケンスは公差が1の等差数列です.このシーケンスの中間値は平均値の大きさを表しています.シーケンスの長さがnであると仮定すれば、このシーケンスの中間値は(S／n)で得られ、シーケンスの中間値と長さを知ることができ、このシーケンスは容易に求められなくなる.
2)条件を満たすnは2つの場合に分けられます.
nが奇数の場合、シーケンスの中間の数はちょうどシーケンスの平均値ですので、条件は:(n&1)==1&sum%n==0です.
nが偶数の場合、シーケンスの中間の2つの数の平均値はシーケンスの平均値であり、この平均値の小数点以下は0.5であるため、条件は:(sum%n)*2==n.
3)問題からn>=2が分かりますが、nの最大値はいくらですか?私たちはnを2からSまで全部遍歴することができますが、大部分遍歴は必要ではありません.nをできるだけ大きくするために、シーケンスを1から開始します.
等差数列の合計式によると、S=(1+n)*n/2となります.
最後に例を挙げます.sum=100を入力すると、n=13~2を遍歴するだけでいいです.n=8の場合、シーケンス[9,10,11,13,14,15,16];n = 5の場合、シーケンス[18,19,20,21,22]を取得します.
完全コード:時間の複雑さは
import java.util.ArrayList;
public class Solution {
public ArrayList > FindContinuousSequence(int sum) {
ArrayList> list = new ArrayList>();
for(int n = (int)Math.sqrt(2*sum); n>=2; n--)
{
if(((n&1)==1 && sum%n == 0) || ((sum%n)*2 == n))
{
ArrayList l = new ArrayList();
for(int j = 0, k = sum/n - (n-1)/2; j < n; j++)
{
l.add(k++);
}
list.add(l);
}
}
return list;
}
} 毎年六一子供の日に、牛客はいくつかの小さいプレゼントを用意して孤児院の子供たちを見舞いに行きます.今年もこのようです.HFは牛客のベテランとして、もちろんいくつかの小さいゲームを用意しました.その中には、まず子供たちを大きな輪にするゲームがあります.それから、彼は無作為に1つの数mを指定して、番号が0の子供に新聞を開始させます.m-1という子供は毎回列に並んで歌を歌います.そしてプレゼント箱の中から任意のプレゼントを選んでください.そしてもう圏内に戻りません.彼の次の子供から、0…m-1の番号を続けます.このままでは…最後の子供までショーをしなくてもいいです.そして牛客の名前が高い「名探偵コナン」の典蔵版をもらいます.このプレゼントはどの子供がもらえるか考えてみてください.(注:子供の番号は0からn-1まで)
1.行列arr[]で1からnまで記録し、しゃがんだら0とする.
2.indexは歩いた人数を記録し、dunNumbersは歩いたことがあるがしゃがんだ人数を記録し、dunsはしゃがんだ人数を記録している.
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n < 1 || m < 1)
return -1;
int[] arr = new int[n];
for(int i = 0; i < n; i++)
arr[i] = i+1;
int index = 0;
int duns = 0;
int dunNumbers = 0;
while(duns != n-1)
{
if(arr[index%n] == 0)
{
dunNumbers++;
index++;
}
else{
if((index+1-dunNumbers)%m==0)
{
arr[index%n] = 0;
index++;
duns++;
}
else{
index++;
}
}
}
for(int i = 0; i < arr.length; i++)
if(arr[i] != 0)
return arr[i]-1;
return -1;
}
}