10の簡単なアルゴリズムの問題
11822 ワード
前言
最近は以前Cで書いたデータ構造やアルゴリズムを使ったものを振り返ると、自分のアルゴリズムやデータ構造が本当に弱いことに気づき、今はJavaで書き直して、温め直しています.
ゆっくりと积み重ねていくしかないでしょう～次のテーマは简単ですが、アルゴリズムの大物はこの文章を直接无视できます～入门やアルゴリズムの弱い学生は参考にしてみてください～
ソートに関連する小さなアルゴリズム(配列をマージしたり、数値の各ビット値を取得したりする和)の多くは、集計ソート(配列をマージしたり)、バケツソート(数値の各ビットの値を取得したり)さえできれば問題ありません.8つの基本的なソートに慣れていない学生は、【8つの基本的なソートのまとめ】を見ることができます.
紙幅の問題で、1編10本ずつ書きましょう～
間違ったところがあったり、より良い実現があったりしたら、より適切な理解方法でコメントを惜しまないでほしいですね～皆さん、交流してください
10の簡単なアルゴリズムの問題
タイトルの総覧 2 2 2 D配列の列ごとの最小値 を取得する.は“1!+4!(2の平方)+9!(3の平方)+...+nの値を求めます 配列対角線要素の和 印刷楊輝三角形 サルが桃を食べる問題 単語の個数を計算する アルファベットが完全に同じかどうかを判断する は、1つの数が2であるか否かを判断する次の である.数字がugly number であるか否かを判断する
一、1-n階乗の和
1-n階乗の和はどう計算しますか?1の階乗は である.2の階乗は である. 3の階乗は である.4の階乗は である. .........
今、私たちはこれらの階乗の和を要求します.考え方: 3階乗の和実は2階乗の和+3の階乗 4階乗の和実は3階乗の和+4の階乗 .......
二、二次元配列の各列の最小値を取得する
2 D配列の列ごとの最小値の取得
構想:列を遍歴し、列の中行を遍歴する
私たちは一般的に配列を操作します.行から列までです.今回は各列の最小値が要求されるので,内部forループでループする必要があるのは行である.
三、“1!+4!(2の平方)+9!(3の平方)+…+nの値を求めます
"1!+4!(2の平方)+9!(3の平方)の値を求めます
考え方:まず平方を求めて、それから階乗を求めて、最後に加算すればいいです～
四、配列対角線要素の和
配列対角線要素の和
考え方:行と列が等しい限り、すなわち対角線の要素 である.
五、楊輝三角形を印刷する
ヤングさんかくけい
楊輝の三角形はこのような形をしています.
ps:画像ソースネット、侵入削除～
法則:各行の最初の行と最後の行は1です. さらに推算:第1列はすべて1であり、第1行はすべて1であり、列数が行数に等しい場合は1 である.
現在の値は、ヘッダ上の値にヘッダ上の左の値を加える に等しい.第1行1列、第2行2列、第3行3列......
コード実装:
結果:
六、猿が桃を食べる問題
サルはn個の桃を摘み取り、当日は半分余り、翌日も残りの桃の半分余りを食べ、10日目には桃は1個しか残っていない.問:猿は初日に桃を何個摘んだか
考え方:当日にn個の桃があると仮定し、前日の桃の半分が1個少ない 当日桃の個数を出すことができます:繰返し式によると: 再帰的にも循環的にも解決できます.
再帰方式:
ループ:
結果:
七、単語の個数を計算する
文字を入力して、中の単語の個数を計算して、単語の間はスペースで隔てて、1つのスペースは隔てて、1つの単語を代表しています
考え方:文字を1回繰り返し、スペース列から非スペース列に変換した回数を累計します.回数は単語の個数 です.はシンボル変数flagを定義し、0はスペース状態を表し、1は非スペース状態 を表す.
結果:
八、アルファベットが完全に同じかどうかを判断する
2つの文字列sとtを与えて、この2つの文字列の中のアルファベットが完全に同じかどうかを判断する(順序が異なる場合がある)
考え方:はこの2つの文字列を遍歴し、各文字から である.
要点: を比較する.
コード実装:
結果:
九、一つの数が2であるかどうかを判断する
1つの数が2のどちらかを判断する
考え方:は2を除いて余数を取り、余数が0でないまで【2の倍数に対してこの場合】、1に等しいかどうかを見て2のいずれかを判断することができる .
結果:
この問題にはもう一つの解決策があります.ビット演算です.2のn次方はいずれも1つの特徴があり,バイナリはいずれも100000 である. 2 2のn乗のバイナリ-1と2のn乗のバイナリがビットと演算を行うと、0 に違いない.
十、一つの数字がugly numberかどうかを判断する
1つの数字がugly numberかどうかを判断する(分解された素因数は2、3、5の3つの数字しかない)
考え方: 2 2,3,5からなると、この数は2,3,5で絶えず除算され、最後に1が得られ、この数は純粋に2,3,5からなる. この数が2であるか否かを先に判断した次の方と同様の考え方～ .
コード:
結果:
まとめ
そう、あなたは間違っていません.簡単なアルゴリズムもまとめなければなりません.
実はこれらの比較的簡単なアルゴリズムには「やり方」があると思います.もしあなたがそのやり方を知っていれば、あなたは簡単に考えられます.もしあなたがそのやり方を知らないなら、できない可能性があります(考えられません).
一定の「やり方」を蓄積した後、私たちは経験に基づいてアルゴリズムの問題を推測し、どのようにしたのかを推測することができます.
簡単な例を挙げます.乗算は加算の基礎の上にありますが、乗算はどうやって学びましたか.背負い込んで出てきた、 nの階乗を求めるのは
2 2 2 D配列の列ごとの最小値を取得 外層循環制御列数、内層循環制御行数、これが各列を巡る方法～ である.
は“1!+4!(2の平方)+9!(3の平方)+...+nの値を求めます まず平方を求めて、更に階乗を求めて、最後にsum変数 をセットします
配列対角線要素の和 行と列の位置が等しい、すなわち対角線上の要素 である.
印刷楊輝三角形 楊輝三角形の法則を探し出す:第1行、第1列と列の値が行の値に等しい時の要素はすべて1で、残りはすべて頭の上の値と頭の上の左の値の です
サルが桃を食べる問題 条件により、前日の桃を推定し、当日の桃(法則)を出すことができる.サルはみな等しい条件(桃の半分以上が残っている)にあるので、循環や再帰 を考えるべきだ.
単語の個数を計算する 各単語の間にスペースがある法則を利用して、変数でこの状態(アルファベットとスペース)の変換を覚えて、単語の個数を計算することができます!
アルファベットが完全に同じかどうかを判断 は各アルファベットをそれぞれ配列にロードし、
一つの数が2の次の方かどうかを判断する 最佳方案:2的某次方在二進法都有个特徴: 10000(n個0)--->ps:プログラマーの整数～......では、この数より1桁少ないバイナリは01111に違いありません.2人は .次案:2のある次の方の数は絶えず縮小し(
数字がugly numberかどうかを判断する で分解された素因数は2、3、5の3つの数字しかなく、この問題は実はその数が2であるかどうかを判断するいずれかのアップグレード版である.この数を縮小し続ける(
文章に間違いがあれば指摘を歓迎し、みんなで交流します.微信で技術の文章を読むことに慣れて、もっと多くのJava資源を獲得したい学生は、微信の公衆番号に注目することができます:Java 3 y
最近は以前Cで書いたデータ構造やアルゴリズムを使ったものを振り返ると、自分のアルゴリズムやデータ構造が本当に弱いことに気づき、今はJavaで書き直して、温め直しています.
ゆっくりと积み重ねていくしかないでしょう～次のテーマは简単ですが、アルゴリズムの大物はこの文章を直接无视できます～入门やアルゴリズムの弱い学生は参考にしてみてください～
ソートに関連する小さなアルゴリズム(配列をマージしたり、数値の各ビット値を取得したりする和)の多くは、集計ソート(配列をマージしたり)、バケツソート(数値の各ビットの値を取得したり)さえできれば問題ありません.8つの基本的なソートに慣れていない学生は、【8つの基本的なソートのまとめ】を見ることができます.
紙幅の問題で、1編10本ずつ書きましょう～
間違ったところがあったり、より良い実現があったりしたら、より適切な理解方法でコメントを惜しまないでほしいですね～皆さん、交流してください
10の簡単なアルゴリズムの問題
タイトルの総覧
1-n階乗の和一、1-n階乗の和
1-n階乗の和はどう計算しますか?
1 1*2 1*2*3 1*2*3*4 今、私たちはこれらの階乗の和を要求します.考え方:
/**
* 1-n
*/
public static void Factorial(int n) {
//
double sum = 0;
// ， 1
double factorial = 1;
for (int i = 1; i <= n; i++) {
factorial = factorial * i;
sum = (int) (sum + factorial);
}
System.out.println(" ：Java3y" + " " + sum);
}二、二次元配列の各列の最小値を取得する
2 D配列の列ごとの最小値の取得
構想:列を遍歴し、列の中行を遍歴する
私たちは一般的に配列を操作します.行から列までです.今回は各列の最小値が要求されるので,内部forループでループする必要があるのは行である.
/**
*
*/
public static void minArray() {
//
int[][] arrays = {
{23, 106, 8, 234},
{25, 9, 73, 19},
{56, 25, 67, 137}
};
//
int maxColLength = arrays[0].length;
//
int[] minArray = new int[maxColLength];
//
for (int i = 0; i < maxColLength; i++) {
//
int min = arrays[0][i];
//
for (int j = 1; j < arrays.length; j++) {
//
if (arrays[j][i] < min) {
min = arrays[j][i];
}
}
//
minArray[i] = min;
}
System.out.println(" ：Java3y" + " " + minArray);
}
三、“1!+4!(2の平方)+9!(3の平方)+…+nの値を求めます
"1!+4!(2の平方)+9!(3の平方)の値を求めます
考え方:まず平方を求めて、それから階乗を求めて、最後に加算すればいいです～
/**
* "1！+4！(2 )+9！(3 )+...+n
*/
public static void calculate() {
double sum = 0;
for (int i = 1; i <= 3; i++) {
//
int square = i * i;
// ， 1
double factorial = 1;
//
for (int j = 1; j <= square; j++) {
factorial = factorial * j;
}
sum = sum + factorial;
}
System.out.println(" ：Java3y" + " " + sum);
}四、配列対角線要素の和
配列対角線要素の和
考え方:
/**
*
*/
public static void arraySum() {
int[][] arrays = {
{23, 106, 8, 234},
{25, 9, 73, 19},
{56, 25, 67, 137},
{33, 22, 11, 44},
};
//
int sum = 0;
for (int i = 0; i < arrays.length; i++) {
for (int j = 0; j < arrays[i].length; j++) {
if (i == j) {
sum = sum + arrays[i][j];
}
}
}
System.out.println(" ：Java3y" + sum);
}五、楊輝三角形を印刷する
ヤングさんかくけい
楊輝の三角形はこのような形をしています.
ps:画像ソースネット、侵入削除～
法則:
コード実装:
/**
*
*/
public static void PascalTriangle() {
//
int[][] arrays = new int[10][];
//
for (int i = 0; i < arrays.length; i++) {
//
arrays[i] = new int[i + 1];
//
for (int j = 0; j <= i; j++) {
// ， ， ， 1
if (i == 0 || j == 0 || j == i) {
arrays[i][j] = 1;
} else {
// +
arrays[i][j] = arrays[i - 1][j] + arrays[i - 1][j - 1];
}
}
}
System.out.println(" ：Java3y" + "-------------------------------");
for (int[] array : arrays) {
for (int value : array) {
System.out.print(value + "\t");
}
System.out.println();
}
System.out.println(" ：Java3y" + "-------------------------------");
}結果:
六、猿が桃を食べる問題
サルはn個の桃を摘み取り、当日は半分余り、翌日も残りの桃の半分余りを食べ、10日目には桃は1個しか残っていない.問:猿は初日に桃を何個摘んだか
考え方:
f(n - 1) = f(n)/2 - 1,f(n) = 2 * f(n - 1) + 2 再帰方式:
/**
*
* @param x
*/
public static int monkeyQue(int x) {
if (x <= 0) {
return 0;
} else if (x == 1) {
return 1;
} else {
return 2 * monkeyQue(x - 1) + 2;
}
}ループ:
int x = 1;
for (int i = 1; i <= 9; i++) {
x = (x + 1) * 2;
}結果:
七、単語の個数を計算する
文字を入力して、中の単語の個数を計算して、単語の間はスペースで隔てて、1つのスペースは隔てて、1つの単語を代表しています
考え方:
/**
* ，
*
* @param str
*/
public static int countWord(String str) {
// 0 ，1
int flag = 0;
//
int num = 0;
for (int i = 0; i < str.length(); i++) {
if (String.valueOf(str.charAt(i)).equals(" ") ) {
flag = 0;
} else if (flag == 0) {
num++;
flag = 1;
}
}
return num ;
}
結果:
八、アルファベットが完全に同じかどうかを判断する
2つの文字列sとtを与えて、この2つの文字列の中のアルファベットが完全に同じかどうかを判断する(順序が異なる場合がある)
考え方:
'a'を減算して配列にそれぞれ格納し、その後、この2つの配列が等しいかどうかを見て要点:
'c'-'a'=2で格納位置を算出し、複数あれば+1でよいので、配列サイズコード実装:
/**
* s t， （ ）
*/
public static void isAnagram() {
//
char[] array1 = new char[26];
char[] array2 = new char[26];
String s1 = "pleasefollowthewechatpublicnumber";
String s2 = "pleowcnumberthewechatpubliasefoll";
for (int i = 0; i < s1.length(); i++) {
char value = s1.charAt(i);
//
int index = value - 'a';
array1[index]++;
}
for (int i = 0; i < s2.length(); i++) {
char value = s2.charAt(i);
//
int index = value - 'a';
array2[index]++;
}
for (int i = 0; i < 26; i++) {
if (array1[i] != array2[i]) {
System.out.println(" ");
return;
}
}
System.out.println(" ");
}
結果:
九、一つの数が2であるかどうかを判断する
1つの数が2のどちらかを判断する
考え方:
/**
* 2
*/
public static void isPowerOfTwo() {
int num = 3;
if (num == 0) {
System.out.println(" ");
}
while (num % 2 == 0) {
num = num / 2;
}
if (num == 1) {
System.out.println(" ");
} else {
System.out.println(" ");
}
}
結果:
この問題にはもう一つの解決策があります.ビット演算です.
if(num <= 0){
System.out.println(" ");
}
else if(num == 1){
System.out.println(" ");
}
else{
if( (num & (num-1) ) == 0){
System.out.println(" ");
}
else{
System.out.println(" ");
}
}十、一つの数字がugly numberかどうかを判断する
1つの数字がugly numberかどうかを判断する(分解された素因数は2、3、5の3つの数字しかない)
考え方:
コード:
/**
* ugly number（ 2、3、5 3 ）
* @param num
*/
public static void isUgly(int num) {
if (num <= 0) {
System.out.println(" ");
} else {
while (num % 2 == 0) {
num = num / 2;
}
while (num % 3 == 0) {
num = num / 3;
}
while (num % 5 == 0) {
num = num / 5;
}
if (num == 1) {
System.out.println(" ");
} else {
System.out.println(" ");
}
}
}結果:
まとめ
そう、あなたは間違っていません.簡単なアルゴリズムもまとめなければなりません.
実はこれらの比較的簡単なアルゴリズムには「やり方」があると思います.もしあなたがそのやり方を知っていれば、あなたは簡単に考えられます.もしあなたがそのやり方を知らないなら、できない可能性があります(考えられません).
一定の「やり方」を蓄積した後、私たちは経験に基づいてアルゴリズムの問題を推測し、どのようにしたのかを推測することができます.
簡単な例を挙げます.
9*9乗算表は誰が背負い込んだことがありませんか?例えば2+2+2+2+2を見て、乗算(套路)をしてから、誰がゆっくりと加算しますか.5つの2が見えて、直接2*5を得ました1-n階乗の和1*2*3*4*...nで、実際には1つの循環の過程で、和を求めるのはsum変数をセットすればいいです!'c-a'はアルファベットcが配列の位置(つまり2)にある.アルファベットの出現回数が一意ではないため,配列の値を比較した(2回出現した場合,値は2,3回出現した場合,値は3).2つの配列をロードする値が一致している限り、アルファベットは同じです.&演算をして、0に違いありません.この特性でこの数が2のいずれかであるかを非常によく判断するnumber % 2 == 0であれば縮小でき、毎回number / 2)、最後の商は必然的に1である.number%2||%3||%5==0、毎回number / 2 | / 3 /5)、最後の商は必ず1である.文章に間違いがあれば指摘を歓迎し、みんなで交流します.微信で技術の文章を読むことに慣れて、もっと多くのJava資源を獲得したい学生は、微信の公衆番号に注目することができます:Java 3 y