摘要:前言最近在回顧以前使用寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西,發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱,現(xiàn)在用改寫一下,重溫一下。
前言
最近在回顧以前使用C寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西,發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱,現(xiàn)在用Java改寫一下,重溫一下。
只能說慢慢積累吧~下面的題目難度都是簡單的,算法的大佬可直接忽略這篇文章了~入門或者算法薄弱的同學(xué)可參考一下~
很多與排序相關(guān)的小算法(合并數(shù)組、獲取數(shù)字每位值的和),我都沒有寫下來了,因為只要會了歸并排序(合并數(shù)組),會了桶排序(獲取數(shù)字每位的值),這些都不成問題了。如果還不太熟悉八大基礎(chǔ)排序的同學(xué)可看:【八大基礎(chǔ)排序總結(jié)】
由于篇幅問題,每篇寫十道吧~
如果有錯的地方,或者有更好的實現(xiàn),更恰當(dāng)?shù)睦斫夥绞较M蠹也涣咴谠u論區(qū)留言哦~大家多多交流
十道簡單算法題 題目的總覽1-n階乘之和
獲取二維數(shù)組每列最小的值
求"1!+4!(2的平方)+9!(3的平方)+...+n的值
數(shù)組對角線元素之和
打印楊輝三角形
猴子吃桃子問題
計算單詞的個數(shù)
判斷字母是否完全一樣
判斷一個數(shù)是不是2的某次方
判斷一個數(shù)字是不是ugly number
一、1-n階乘之和1-n階乘之和怎么算?
1的階乘是1
2的階乘是1*2
3的階乘是1*2*3
4的階乘是1*2*3*4
.........
現(xiàn)在我們要求這些階乘的和。思路:
3階乘的和其實上就是2階乘的和+3的階乘
4階乘的和其實上就是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); }二、獲取二維數(shù)組每列最小的值
獲取二維數(shù)組每列最小的值
思路:遍歷列,再遍歷列中行
我們一般操作數(shù)組都是從行開始,再到列的。這次要求的是每列的最小值,因此需要在內(nèi)部for循環(huán)遍歷的是行
/** * 求出二維數(shù)組每列的最小值 */ public static void minArray() { //二維數(shù)組 int[][] arrays = { {23, 106, 8, 234}, {25, 9, 73, 19}, {56, 25, 67, 137} }; //獲取列數(shù) int maxColLength = arrays[0].length; //使用一個數(shù)組來裝載每列最小的值 int[] minArray = new int[maxColLength]; //控制列數(shù) for (int i = 0; i < maxColLength; i++) { //假設(shè)每列的第一個元素是最小的 int min = arrays[0][i]; //控制行數(shù) for (int j = 1; j < arrays.length; j++) { //找到最小值 if (arrays[j][i] < min) { min = arrays[j][i]; } } //賦值給裝載每列最小的值的數(shù)組 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++) { //得到平方數(shù) 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); }四、數(shù)組對角線元素之和
數(shù)組對角線元素之和
思路:
只要行和列相等,即是對角線的元素
/** * 數(shù)組對角線之和 */ 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:圖片來源網(wǎng)上,侵刪~
規(guī)律:
每行的第一個和最后一個都是1
進一步推算:第1列全部為1,第一行全都是1,當(dāng)列數(shù)等于行數(shù)為1
當(dāng)前值等于頭上的值加頭上的左邊的值
第一行一列,第二行兩列,第三行三列.......
代碼實現(xiàn):
/** * 打印楊輝三角形 */ public static void PascalTriangle() { //打印十行的楊輝三角形 int[][] arrays = new int[10][]; //行數(shù) for (int i = 0; i < arrays.length; i++) { //初始化第二層的大小 arrays[i] = new int[i + 1]; //列數(shù) for (int j = 0; j <= i; j++) { //是第一列,第一行,行數(shù)等于列數(shù),那么通通為1 if (i == 0 || j == 0 || j == i) { arrays[i][j] = 1; } else { //當(dāng)前值等于頭上的值+頭上左邊的值 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 + " "); } System.out.println(); } System.out.println("公眾號:Java3y" + "-------------------------------"); }
結(jié)果:
六、猴子吃桃子問題猴子摘下了n個桃子,當(dāng)天吃掉一半多一個,第二天也是吃掉剩下桃子的一半多一個,到了第十天,桃子只剩下了1個。問:猴子第一天摘了多少個桃子
思路:
假設(shè)當(dāng)天有n個桃子,它是前一天桃子的一半少1個,f(n - 1) = f(n)/2 - 1,
我們就可以推出當(dāng)天桃子的個數(shù):根據(jù)遞推公式:f(n) = 2 * f(n - 1) + 2
用遞歸和循環(huán)都可解決:
遞歸方式:
/** * 猴子吃桃問題 * @param x 天數(shù) */ public static int monkeyQue(int x) { if (x <= 0) { return 0; } else if (x == 1) { return 1; } else { return 2 * monkeyQue(x - 1) + 2; } }
循環(huán)方式:
int x = 1; for (int i = 1; i <= 9; i++) { x = (x + 1) * 2; }
結(jié)果:
七、計算單詞的個數(shù)輸入一段字符,計算出里面單詞的個數(shù),單詞之間用空格隔開 ,一個空格隔開,就代表著一個單詞了
思路:
把字符遍歷一遍,累計由空格串轉(zhuǎn)換為非空格串的次數(shù),次數(shù)就是單詞的個數(shù)
定義一個標志性變量flag,0表示的是空格狀態(tài),1表示的是非空格狀態(tài)
/** * 輸入一段字符,計算出里面單詞的個數(shù) * * @param str 一段文字 */ public static int countWord(String str) { // 0 表示空格狀態(tài),1 表示非空格狀態(tài) int flag = 0; // 單詞次數(shù) 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 ; }
結(jié)果:
八、判斷字母是否完全一樣給定兩個字符串s和t,判斷這兩個字符串中的字母是不是完全一樣(順序可以不一樣)
思路:
遍歷這兩個字符串,用每個字符減去"a",將其分別存入到數(shù)組中去,隨后看這兩個數(shù)組是否相等即可
要點:
"c"-"a"=2即可計算出存儲的位置,如果有多個,則+1即可,后面我們來比較數(shù)組大小
代碼實現(xiàn):
/** * 給定兩個字符串s和t,判斷這兩個字符串中的字母是不是完全一樣(順序可以不一樣) */ public static void isAnagram() { //分別存儲字符串的字符 int[] array1 = new int[26]; int[] array2 = new int[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("相同"); }
結(jié)果:
九、判斷一個數(shù)是不是2的某次方判斷一個數(shù)是不是2的某次方
思路:
除2取余數(shù),直至余數(shù)不為0【針對2的倍數(shù)這種情況】,看是不是等于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("不是"); } }
結(jié)果:
這題還有另一種解決方式,就是位運算:
2的n次方都有一個特點,二進制都是1000000
如果 2的n次方的二進制-1和2的n次方二進制做按位與運算,那么得出的結(jié)果肯定是0
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("不是"); } }十、判斷一個數(shù)字是不是ugly number
判斷一個數(shù)字是不是ugly number(分解出來的質(zhì)因數(shù)只有2、3、5這3個數(shù)字)
思路:
如果是由2,3,5組成的,那么這個數(shù)不斷除以2,3,5,最后得出的是1,這個數(shù)就是純粹用2,3,5組成的
跟之前判斷該數(shù)是否2的某次方是一樣的思路~
代碼:
/** * 判斷一個數(shù)字是不是ugly number(分解出來的質(zhì)因數(shù)只有2、3、5這3個數(shù)字) * @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("是"); } } }
結(jié)果:
總結(jié)沒錯,你沒看錯,簡單的小算法也要總結(jié)!
其實我覺得這些比較簡單的算法是有"套路"可言的,你如果知道它的套路,你就很容易想得出來,如果你不知道它的套路,那么很可能就不會做了(沒思路)。
積累了一定的"套路"以后,我們就可以根據(jù)經(jīng)驗來推斷,揣摩算法題怎么做了。
舉個很簡單的例子:
乘法是在加法的基礎(chǔ)之上的,那乘法我們是怎么學(xué)的?背(積累)出來的,9*9乘法表誰沒背過?比如看到2+2+2+2+2,會了乘法(套路)以后,誰還會慢慢加上去??匆娏?個2,就直接得出2*5了
1-n階乘之和
求n的階乘就用1*2*3*4*...n,實際上就是一個循環(huán)的過程,求和就套個sum變量即可!
獲取二維數(shù)組每列最小的值
外層循環(huán)控制列數(shù),內(nèi)層循環(huán)控制行數(shù),這就是遍歷每列的方法~
求"1!+4!(2的平方)+9!(3的平方)+...+n的值
先求平方,再求階乘,最后套個sum變量
數(shù)組對角線元素之和
行和列的位置相等,即是對角線上的元素
打印楊輝三角形
找出楊輝三角形的規(guī)律:第一行、第一列和列值等于行值時上的元素都是1,其余的都是頭上的值加頭上的左邊的值
猴子吃桃子問題
根據(jù)條件,我們可以推算出前一天桃子,進而推出當(dāng)天桃子(規(guī)律)。猴子都是在相等的條件(剩下桃子的一半多一個),因此就應(yīng)該想到循環(huán)或者遞歸
計算單詞的個數(shù)
利用每個單詞間會有個空格的規(guī)律,用變量來記住這個狀態(tài)(字母與空格)的轉(zhuǎn)換,即可計算出單詞的個數(shù)!
判斷字母是否完全一樣
將每個字母都分別裝載到數(shù)組里面去,"c-a"就是字母c在數(shù)組的位置了(也就是2)。由于字母出現(xiàn)的次數(shù)不唯一,因此我們比較的是數(shù)組的值(如果出現(xiàn)了兩次,那么值為2,如果出現(xiàn)了3次,那么值為3)。只要用于裝載兩個數(shù)組的值都吻合,那么字母就是一樣!
判斷一個數(shù)是不是2的某次方
最佳方案:2的某次方在二進制都有個特點:10000(n個0)--->ps:程序員的整數(shù)~..........那么比這個數(shù)少一位的二進制肯定是01111,它倆做&運算,那么肯定為0。用這個特性就非常好判斷該數(shù)是否是2的某次方了
次方案:2的某次方的數(shù)不斷縮小(只要number % 2 == 0就可以縮小,每次number / 2),最后的商必然是1。
判斷一個數(shù)字是不是ugly number
分解出來的質(zhì)因數(shù)只有2、3、5這3個數(shù)字,這題其實就是判斷該數(shù)是否為2的某次方的升級版。將這個數(shù)不斷縮小(只要number%2||%3||%5==0,每次number / 2 | / 3 /5 ),最后的商必然是1。
如果文章有錯的地方歡迎指正,大家互相交流。習(xí)慣在微信看技術(shù)文章,想要獲取更多的Java資源的同學(xué),可以關(guān)注微信公眾號:Java3y
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/71067.html
摘要:前言清明不小心就拖了兩天沒更了這是十道算法題的第二篇了上一篇回顧十道簡單算法題最近在回顧以前使用寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西,發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱,現(xiàn)在用改寫一下,重溫一下。 前言 清明不小心就拖了兩天沒更了~~ 這是十道算法題的第二篇了~上一篇回顧:十道簡單算法題 最近在回顧以前使用C寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西,發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱,現(xiàn)在用Java改寫一下,...
摘要:前言在兩家大廠工作了年,當(dāng)了年的前端面試官,把一些較難的面試題與答案匯總在我的中。請說出至少種方法,越難越好難度阿里騰訊這種題有簡單方法,也有難的方法,我建議大伙在面試的時候,盡量往難的說。 前言 在兩家大廠工作了6年,當(dāng)了3年的前端面試官,把一些較難的面試題與答案匯總在我的Github中。希望對大家有所幫助,助力大家進入自己理想的企業(yè)。 項目地址是:https://github.co...
摘要:前言在兩家大廠工作了年,當(dāng)了年的前端面試官,把一些較難的面試題與答案匯總在我的中。請說出至少種方法,越難越好難度阿里騰訊這種題有簡單方法,也有難的方法,我建議大伙在面試的時候,盡量往難的說。 前言 在兩家大廠工作了6年,當(dāng)了3年的前端面試官,把一些較難的面試題與答案匯總在我的Github中。希望對大家有所幫助,助力大家進入自己理想的企業(yè)。 項目地址是:https://github.co...
摘要:前言在兩家大廠工作了年,當(dāng)了年的前端面試官,把一些較難的面試題與答案匯總在我的中。請說出至少種方法,越難越好難度阿里騰訊這種題有簡單方法,也有難的方法,我建議大伙在面試的時候,盡量往難的說。 前言 在兩家大廠工作了6年,當(dāng)了3年的前端面試官,把一些較難的面試題與答案匯總在我的Github中。希望對大家有所幫助,助力大家進入自己理想的企業(yè)。 項目地址是:https://github.co...
閱讀 3198·2021-11-10 11:35
閱讀 1305·2019-08-30 13:20
閱讀 1126·2019-08-29 16:18
閱讀 2141·2019-08-26 13:54
閱讀 2166·2019-08-26 13:50
閱讀 966·2019-08-26 13:39
閱讀 2483·2019-08-26 12:08
閱讀 1958·2019-08-26 10:37