前言 清明不小心就拖了兩天沒更了~~ 這是十道演算法題的第二篇了 ~上一篇回顧: "十道簡單演算法題" 最近在回顧以前使用C寫過的數據結構和演算法的東西,發現自己的演算法和數據結構是真的薄弱,現在用Java改寫一下,重溫一下。 只能說慢慢積累吧~下麵的題目難度都是簡單的,演算法的大佬可直接忽略這篇文章了~入門 ...
前言
清明不小心就拖了兩天沒更了~~
這是十道演算法題的第二篇了~上一篇回顧:十道簡單演算法題
最近在回顧以前使用C寫過的數據結構和演算法的東西,發現自己的演算法和數據結構是真的薄弱,現在用Java改寫一下,重溫一下。
只能說慢慢積累吧~下麵的題目難度都是簡單的,演算法的大佬可直接忽略這篇文章了~入門或者演算法薄弱的同學可參考一下~
很多與排序相關的小演算法(合併數組、獲取數字每位值的和),我都沒有寫下來了,因為只要會了歸併排序(合併數組),會了桶排序(獲取數字每位的值),這些都不成問題了。如果還不太熟悉八大基礎排序的同學可看:【八大基礎排序總結】
由於篇幅問題,每篇寫十道吧~
如果有錯的地方,或者有更好的實現,更恰當的理解方式希望大家不吝在評論區留言哦~大家多多交流
十道簡單演算法題
題目的總覽
- 刪除下標為k的元素
- 找出常用的數字
- 丟失的數字
- 將0放在數組最後
- 找出數組的單個數字
- 畫三角形星星
- 羅馬數字倒轉成阿拉伯數字
- 啤酒與飲料
- 簡單凱撒密碼
- 求最大公約數
一、刪除下標為k的元素
刪除下標為k的元素
思路:數組後一位往前覆蓋即可~
/**
* 刪除下標為k的元素
*/
public static void deleteK() {
//固定的常量(比數組元素的個數要大)
int N = 10;
int[] arrays = new int[N];
//對數組進行初始化
for (int i = 0; i < 8; i++) {
arrays[i] = i;
}
//要刪除下標
int k = 7;
for (int i = k; i < N - 1; i++) {
arrays[i] = arrays[i + 1];
}
System.out.println("公眾號:Java3y" + arrays);
}
二、找出常用的數字
給你一個長度為n的數組,其中有一個數字出現的次數至少為n/2,找出這個數字
這道題可以用棧的思想來做:
- 如果棧是空的,那麼先把數據存進去
- 然後繼續遍歷其他的數據,只要發現棧中的數據和遍歷中的數據不一樣,那麼就出棧
- 如果是相同的,那麼就入棧
- 其實就是捉住數字出現的次數多於數組一半的長度這裡入手。如果這個數出現的次數是大於這個數組長度的2/1,那麼最後留下的肯定是這個數
/**
* 找出常用的數字:
* 給你一個長度為n的數組,其中有一個數字出現的次數至少為n/2,找出這個數字
*/
public static void findMajorityElement(int[] arrays) {
//構建一個靜態棧
int[] stack = new int[arrays.length];
// 棧的front指針
int front = -1;
// 遍歷給出的數組
for (int i = 0; i < arrays.length; i++) {
// 判斷該棧為空,那麼直接將元素入棧
if (front == -1) {
stack[++front] = arrays[i];
} else if (stack[front] == arrays[i]) { // 該元素是否與棧的元素一致-->繼續入棧
stack[++front] = arrays[i];
} else {
// 只要不一致,就出棧
front--;
}
}
// 只要該數字出現次數大於數組長度的2/1,那麼留下來的數字肯定在棧頂中
System.out.println("關註公眾號:Java3y--->" + stack[0]);
}
優化:
- 其實沒必要用整個棧來裝載數組,因為我們就使用棧頂元素(出現次數最多的那個),而棧的大小也可以通過一個變數就可以來確定了
- 只要元素相同->入棧(長度+1)。元素不相同-->出棧(長度-1)
- 最終留下來的肯定是出現最頻繁的那個數字!
public static void findMajorityElement2(int[] arrays) {
// 裝載棧的元素
int candidate = -1;
// 棧的大小(長度)
int count = 0;
// 遍歷給出的數組
for (int i = 0; i < arrays.length; i++) {
// 判斷該棧為空,那麼直接將元素入棧
if (count == 0) {
candidate = arrays[i];
count++;
} else if (candidate == arrays[i]) { // 該元素是否與棧的元素一致-->入棧(棧多一個元素)
count++;
} else {
// 只要不一致-->出棧(棧少一個元素)
count--;
}
}
// 只要該數字出現次數大於數組長度的2/1,那麼留下來的數字肯定在棧頂中
System.out.println("關註公眾號:Java3y--->" + candidate);
}
三、丟失的數字
給你一個數組{0,1,2,3,....n},其中有一個數字缺失,請把缺失的數字找出來
思路:
- 創建一個數組(題目數組的長度+1,因為題目的數組缺失了一個)
- 創建的數組元素用特殊的符號(數字)來進行填滿
- 將題目給出的數組遍歷並填充到創建的數組上,用index(0,1,2,3..)替代
- 最後遍歷創建的數組,哪個還是特殊的符號就是缺失的數字,返回index(缺失的數字)即可
/**
* 找到缺失的數字
*
* @param arrays
*/
public static void missingNumber(int[] arrays) {
// 定義要填充到新數組的數字(隨意)
int randomNumber = 89898980;
// 創建一個新的數組(比已缺失的數組多一個長度)
int[] newArrays = new int[arrays.length + 1];
// 填充特殊的數字進新數組中
for (int i = 0; i < newArrays.length; i++) {
// 隨意填充數組到新數組中
newArrays[i] = randomNumber;
}
// 遍歷題目的數組並使用index替代掉新數組的元素
for (int i = 0; i < arrays.length; i++) {
// 題目數組的值[0,1,2,3,4,...n]其中有一個缺失
int index = arrays[i];
// 重新填充到新數組上,index對應著題目數組的值
newArrays[index] = 3333333;
}
// 遍歷新數組,只要還有值為89898980,那麼那個就是缺失的數字
for (int i = 0; i < newArrays.length; i++) {
if (newArrays[i] == randomNumber) {
System.out.println("關註公眾號:Java3y---->缺失的數字是:" + i);
}
}
}
結果:
優化:
- 題目給出的數組
{0,1,2,3,4,5,....n}
其中缺失一個數字,要把缺失的數字找出來...我們可以回顧一下高中學過的等差求和公式:Sn=(a1+an)n/2
- 假設我們沒有缺失數字,等差求和公式可以快速得出答案。比如:
{0,1,2,3}
--->(0+3)*4/2
--->6,如果此時缺失的是2呢,就是說題目的給出的數組是:{0,1,3}
,我們利用等差公式求和之後減去數組每個元素,最後剩下的數就是缺失的數字!6-1-3-0
--->2
所以,我們可以寫出這樣的代碼:
/**
* 利用等差公式找到缺失的數字
*
* @param arrays
*/
public static void missingNumber2(int[] arrays) {
// 套用等差求和公式
int sum = (arrays[0] + arrays[arrays.length - 1]) * (arrays.length + 1) / 2;
// 遍曆數組,得出的sum減去數組每一位元素,最後即是缺失的數字
for (int value : arrays) {
sum = sum - value;
}
System.out.println("關註公眾號:Java3y---->缺失的數字是:" + sum);
}
結果:
四、將0放在數組最後
將一個數組的元素,其中是0的,放在數組的最後
思路:
- 使用一個變數zero來記住該數組有多少個0
- 遍歷這個數組,如果發現不是0的,就往數組前面移動,如果發現是0就zero++
- 數組移動的位置剛好是
arr[i-zero]
的
代碼實現:
/**
* 移動元素0到數組最後
*
* @param arrays
*/
public static void moveZero(int[] arrays) {
// 記錄該數組有多少個0元素
int zero = 0;
for (int i = 0; i < arrays.length; i++) {
// 只要元素不為0,那麼就往前面移動
if (arrays[i] != 0) {
arrays[i - zero] = arrays[i];
} else {
// 如果為0,那麼zero ++
zero++;
}
}
// 1. 前面已經將非0的元素移動到數組的前面了
// 2. 將為0的元素填滿數組,填充的位置就從length - zero開始
int j = arrays.length - zero;
while (j < arrays.length) {
arrays[j] = 0;
j++;
}
System.out.println("關註公眾號:Java3y---->" + arrays);
}
結果:
還可以換種思路(差別不大):將數組分成幾個部分:在j之前的沒有0,j到i全是0,i後面還沒有遍歷
- 如果遍歷到的數字不是0,那麼跟j進行交換,j++(保證j前面沒有0和j到i全是0)
- 直至i遍歷完畢後,j前面都不是0,j-i都是0(這就完成我們的任務了)
代碼實現:
/**
* 移動元素0到數組最後
*
* @param arrays
*/
public static void moveZero2(int[] arrays) {
// 在j前面的元素都不是0
int j = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] != 0) {
// 跟j進行交換,保證j的前面都不是0
int temp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = temp;
j++;
}
}
// 直至i遍歷完畢後,j前面都不是0,j-i都是0(這就完成我們的任務了)
System.out.println("關註公眾號:Java3y---->" + arrays);
}
結果還是一樣的:
五、找出數組的單個數字
給你一個數組,除了一個數字外,其他的數字都出現了兩次,請把這個只出現一次的數字找出來。
思路:
- 將該數組遍歷一次,記錄每個數字出現的次數
- 如果該數字出現的次數只有1,那麼該數字就是單個數字~
/**
* 找出數組的單個數字
* @param nums
* @return
*/
public static void singleNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int count = countNumber(nums, nums[i]);
// 如果該元素只出現一次,那麼就是它了!
if (count == 1) {
System.out.println("關註公眾號:Java3y--->單一的元素是:" + nums[i]);
return ;
}
}
}
/**
* 找出每個元素出現的次數
* @param nums 數組
* @param value 想知道出現次數的元素
*/
public static int countNumber(int[] nums,int value) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (value == nums[i]) {
count++;
}
}
// 返回該元素出現的次數
return count;
}
結果:
優化:
這個問題最佳的解法是用到了位運算的異或操作:
- 如果
5^5=0
- 如果
5^7^5 = 7
- 如果
5^6^6^5^7^8^7 = 8
從上面的例子可以看出:一堆數字做異或運算^
,倆倆相同數字就會被抵消掉~,所以這個特性對於這個題目而言就再適合不過的了:
/**
* 找出數組的單個數字
* @param nums
* @param numsSize
* @return
*/
public static int singleNumber(int[] nums, int numsSize) {
// 第一個數和數組後面的數做^運算,留下的必然是單個數字
int k = nums[0];
for (int i = 1; i < numsSize; i++) {
k = (k ^ nums[i]);
}
return k;
}
六、畫三角形星星
畫三角形星星
就是要畫上面那種三角形星星,那怎麼畫呢??
思路:
- 首先,我們可以發現:每行**星星的個數是(2*行數-1),每行的空格數就是最大行數減去第n行**(最大4行,第4行沒有空格,最大4行,第三行1個空格)
- 有了上面的規律,套個for迴圈即可生成三角形星星~
實現代碼:
/**
* 畫星星
*/
public static void drawStar() {
// 我要畫5行的星星
int row = 5;
for (int i = 1; i <= 5; i++) {
// 空格數等於最大行數 - 當前行數
for (int j = 1; j <= row - i; j++) {
System.out.print(" ");
}
// 星星數等於(當前行數*2-1)
for (int j = 1; j <= i * 2 - 1; j++) {
System.out.print("*");
}
// 每畫一行就換一次行
System.out.println();
}
}
結果:
七、羅馬數字倒轉成阿拉伯數字
羅馬數字倒轉成阿拉伯數字
羅馬數字我們可能在英語的題目中看得是比較多的,一般常用的我們是阿拉伯數字,那怎麼轉成阿拉伯數字呢??我們先來瞭解一下羅馬數字:
ps:來源360百科
規則在圖上已經說得挺明白的了,我舉幾個例子:
- 左邊的數比右邊小,則是用右邊的數減去左邊的
- 左邊的數比右邊大,則是用右邊的數加上左邊的
看了上面的例子估計我們會手算將羅馬數字轉成阿拉伯數字了,那麼用程式怎麼寫呢???
思路是這樣的:
- 先找到羅馬數字最大的那個數字
- 要是左邊的數比右邊小,則是用右邊的數減去左邊的
- 左邊的數比右邊大,則是用右邊的數加上左邊的
- .....如此迴圈則最後獲取阿拉伯數字
首先,我們先定義羅馬數字和對應的阿拉伯數字(相當於查表)
// 定義羅馬數字
char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
// 羅馬數字對應的阿拉伯數字
int values[] = { 1, 5, 10, 50, 100, 500, 1000};
隨後,我們得找到羅馬數字當前的最大值,找到最大值之前就先得把羅馬數字轉成是阿拉伯數字
/**
* 將羅馬數字轉成阿拉伯數字,實際上就是一個查表的過程
*
* @param roman
* @return
*/
public static int digitsToValues(char roman) {
// 定義羅馬數字
char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
// 羅馬數字對應的阿拉伯數字
int values[] = {1, 5, 10, 50, 100, 500, 1000};
for (int i = 0; i < digits.length; i++) {
if (digits[i] == roman) {
return values[i];
}
}
return 0;
}
上面的方法已經可以將羅馬數字轉成阿拉伯數字了,接下來我們要查找出最大值了
/**
* 找到當前羅馬數字最大值的角標
*
* @param digits
* @return
*/
public static int findMaxIndex(String digits, int L, int R) {
// 假設第一個是最大的
int max = digitsToValues(digits.charAt(L));
int maxIndex = L;
for (int i = L; i < R; i++) {
// 將羅馬數字轉成是阿拉伯數字
int num = digitsToValues(digits.charAt(i));
if (max < num) {
max = num;
maxIndex = i;
}
}
return maxIndex;
}
找到了當前羅馬數字的最大值那要怎麼做???
- 左邊的比右邊的要小,則右邊的減去左邊的值
- 左邊的比右邊的要大,則右邊的加上左邊的值
- ....///實際上是一個遞歸的過程
於是乎,我們可以寫出下麵的代碼:
/**
* 將羅馬數字轉成阿拉伯數字
*
* @param romanNumber
* @param L
* @param R
*/
public static int romanToNumber(String romanNumber, int L, int R) {
// 如果只有一個羅馬數字,那麼可以直接返回了(遞歸出口)
if (L == R) {
return digitsToValues(romanNumber.charAt(L));
} else if (L > R) { // 如果L和R已經越界了,那麼說明沒有值了
return 0;
} else {
// 找到當前羅馬數字最大值的角標
int maxIndex = findMaxIndex(romanNumber, L, R);
// 得到最大值
int max = digitsToValues(romanNumber.charAt(maxIndex));
// 在最大值左邊的,則用最大值減去左邊的
int left = romanToNumber(romanNumber, L, maxIndex - 1);
// 在最大值右邊的,則用最大值加上右邊的
int right = romanToNumber(romanNumber, maxIndex + 1, R);
return max - left + right;
}
}
測試一下:
八、啤酒與飲料
啤酒每罐2.3元,飲料每罐1.9元。小明買了若幹啤酒和飲料,一共花了82.3元。我們還知道他買的啤酒比飲料的數量少,請你計算他買了幾罐啤酒。
這是藍橋杯的一道題,我們可以使用暴力搜索即可解出:
- 如果82.3全買啤酒最多能買82.3/2.3=35瓶
- 如果82.3全買飲料最多能買82.3/1.9=43瓶
- 以此作為控制條件
/**
* 啤酒與飲料題目
*/
public static void beerAndDrink() {
// 啤酒
for (int i = 0; i < 36; i++) {
// 飲料
for (int j = 0; j < 44; j++) {
// 錢剛好花光了,並且啤酒比飲料少
if (2.3 * i + j * 1.9 == 82.3 && i < j) {
System.out.println("關註公眾號:Java3y--------------->啤酒買了" + i);
}
}
}
}
測試:
九、簡單凱撒密碼
簡單凱撒密碼
凱撒密碼是啥?簡單來說:就是通過移位來進行加密
- 比如,A-->B,B-->C,C-->D.......
上面就是最簡單的凱撒密碼,將所有的字母進行移一位,實現加密
下麵我們也來玩一下吧~
左移動和右移動:
/**
* 右移
*/
public static int rotateRight(int ch) {
if (ch >= 'A' && ch <= 'Y') {
return ch + 1;
} else if (ch >= 'a' && ch <= 'y') {
return ch + 1;
} else if (ch == 'Z') {
return 'A';
} else if (ch == 'z') {
return 'a';
} else {
return ch;
}
}
/**
* 左移
*/
public static int rotateLeft(int ch) {
if (ch >= 'B' && ch <= 'Z') {
return ch - 1;
} else if (ch >= 'b' && ch <= 'z') {
return ch - 1;
} else if (ch == 'A') {
return 'Z';
} else if (ch == 'a') {
return 'z';
} else {
return ch;
}
}
加密:
/**
* 加密
* @param ch
* @param shift
* @return
*/
public static int encode(int ch, int shift) {
// 如果沒有移動,則直接返回
if (shift == 0) {
return ch;
} else if (shift > 0) {
// 如果shift移動的是正數,那麼就向右移動
for (int i = 0; i < shift; i++) {
ch = rotateRight(ch);
}
return ch;
} else {
// 如果shift移動的是負數,那麼就向左移動
for (int i = 0; i < -shift; i++) {
ch = rotateLeft(ch);
}
return ch;
}
}
測試:
String s = "HELLO WORLD";
char[] ch = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
ch[i] = (char) encode(s.charAt(i), 3);
}
System.out.println("關註公眾號:Java3y" + ch);
結果:
十、求最大公約數
求一個數的最大公約數
演算法:是兩個數相餘,直到餘數為0,如果餘數不為0,就用除數和餘數求餘
- 若發現餘數為0,那麼當前的除數就是最大公約數
/**
* 求最大公約數
*
* @param num1
* @param num2
*/
public static int gcd(int num1, int num2) {
// 求餘數
int r = num1 % num2;
// 如果餘數為0,那麼除數就是最大公約數
if (r == 0) {
return num2;
} else {
// 否則,則用除數和餘數來進行運算
return gcd(num2, r);
}
}
結果:
總結
沒錯,你沒看錯,簡單的小演算法也要總結!
其實我覺得這些比較簡單的演算法是有"套路"可言的,你如果知道它的套路,你就很容易想得出來,如果你不知道它的套路,那麼很可能就不會做了(沒思路)。
積累了一定的"套路"以後,我們就可以根據經驗來推斷,揣摩演算法題怎麼做了。
舉個很簡單的例子:
- 乘法是在加法的基礎之上的,那乘法我們是怎麼學的?背(積累)出來的,
9*9
乘法表誰沒背過?比如看到2+2+2+2+2
,會了乘法(套路)以後,誰還會慢慢加上去。看見了5個2,就直接得出2*5
了
- 刪除下標為k的元素
- 後一位往前一位覆蓋即可
- 找出常用的數字
- 利用棧的思想,只要該數組出現的次數大於2分之1,那麼他肯定是在棧裡面
- 丟失的數字
- 實現1:兩個數組進行遍歷,如果某一個不存在,利用數組的角標就可以找到~
- 實現2:使用等差求和公式,缺失的數字可以減出來!
- 將0放在數組最後
- 實現1:使用變數zero來記住有多少個0,只要不是0就往前面移動,最後將zero補全!
- 實現2:將數組分成3個部分;在j之前的沒有0,j到i全是0,i後面還沒有遍歷,直至i遍歷完畢後,j前面都不是0,j-i都是0(這就完成我們的任務了)
- 找出數組的單個數字
- 實現1:遍曆數組計算某個元素出現的次數,外層再遍曆數組,只要該元素出現的次數是1,那麼它就是單個的!
- 實現2:位運算的異或操作,相同的兩個數字會抵消掉!
- 畫三角形星星
- 找到畫星星和空格的規律!星星和空格都與行數有關聯!
- 羅馬數字倒轉成阿拉伯數字
- 將羅馬數組和阿拉伯數字對應起來,“查表”進行轉換!找到最大的值,左邊比右邊要小,則右減左。反之右加左!
- 啤酒與飲料
- 使用暴力查詢的方式來將具體的值搜索出來!
- 簡單凱撒密碼
- char本質上就是int,移動時要主要Z,A這些字元~
- 求最大公約數
- 如果餘數為0,那麼除數就是最大公約數,否則就是除數和餘數再繼續運算!
文章的目錄導航:https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li
如果文章有錯的地方歡迎指正,大家互相交流。習慣在微信看技術文章,想要獲取更多的Java資源的同學,可以關註微信公眾號:Java3y