資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學從後往前，隔位相加自然數，求下一個數字
如果要儲存一個很大的整數，可以使用數字字串來儲存數值。眾所周知，計算機使用int資料型別無法儲存大於32位的數字。因此，為了避免溢位，在這個問題中，我們將採用數字字串作為輸入，而不是int變數，這樣我們就可以在大規模數字上處理這個問題。
問題陳述
在這個問題中，我們需要透過從後往前，隔位相加自然數來找到下一個數字。我們將得到一個數字字串，並必須將最終輸出作為字串本身返回。讓我們看看如何解決這個問題。
讓我們透過一些例子來理解這個問題。
輸入
s = “12345678”
輸出
16375879
解釋
首先，我們將取最後一位數字“8”，並加上第一個自然數“1”。我們將得到 (8 + 1) = 9 作為新的數字字串的最後一位數字。
然後我們將保留“7”，因為我們必須交替執行操作。
接下來，我們將取“6”，並加上第二個自然數“2”。我們將得到 (6 + 2) = 8 作為新的數字字串的第三位數字。
然後我們將保留“5”，因為我們必須交替執行操作。
接下來，我們將取“4”，並加上第三個自然數“3”。我們將得到 (4 + 3) = 7 作為新的數字字串的第五位數字。
然後我們將保留“3”，因為我們必須交替執行操作。
接下來，我們將取“2”，並加上第四個自然數“4”。我們將得到 (2 + 4) = 6 作為新的數字字串的第七位數字。
然後我們將保留“1”，因為我們必須交替執行操作。
因此，我們將得到最終的數字字串“16375879”。
輸入
s = “78930”
輸出
18231
解釋
首先，我們將取最後一位數字“0”，並加上第一個自然數“1”。我們將得到 (0 + 1) = 1 作為新的數字字串的最後一位數字。
然後我們將保留“3”，因為我們必須交替執行操作。
接下來，我們將取“9”，並加上第二個自然數“2”。我們將得到 (9 + 2) = 11
現在，我們需要將這個兩位數轉換為一位數，我們可以透過對其取模9來輕鬆做到這一點，這將給我們“2”作為新的數字字串的第三位數字。
然後我們將保留“8”，因為我們必須交替執行操作。
接下來，我們將取“7”，並加上第三個自然數“3”。我們將得到 (7 + 3) = 10
現在，我們需要將這個兩位數轉換為一位數，我們可以透過對其取模9來輕鬆做到這一點，這將給我們“1”作為新的數字字串的第五位數字。
因此，我們將得到最終的數字字串“18231”。
問題說明
讓我們嘗試理解這個問題並找到它的解決方案。在這個問題中，我們得到一個數字字串，我們必須記住以下條件來修改我們的字串：
從1、2、3等等一直加到無窮大的自然數，從最後一位開始隔位相加。
這意味著如果我們將最後一位數字的索引從1開始算作奇數位，我們將修改位於奇數位置的數字，並保持其餘數字不變。
如果加法後沒有得到一位數，我們應該透過連續加數字直到它變成一位數來將其變成一位數，或者我們可以使用另一種邏輯，對修改後的數字取模9，這將給我們相同的值，並且在更短的時間內也能給我們一位數。
在下面的文章中，我們將藉助於簡單程式碼中的註釋來理解這種簡單的方法：
演算法
定義一個臨時數字，並將addNum初始化為“0”。
定義一個空字串，它將包含最終輸出。
從字串的末尾開始迴圈，並將字元轉換為整數。
如果數字位於偶數位置，則從1開始一直加到無窮大的自然數。
將加法後得到的數字轉換為一位數。
將數字轉換為字元。
將字元附加到最終輸出字串中。
示例
以下是各種程式語言中上述方法的實現：
#include <bits/stdc++.h>
using namespace std;
// Function to find the next number by adding natural numbers in order on alternating indices from last
string Helper(string s){
// Define a temporary integer
// Initialize the number we will add in the numeric string integers by 0
int temp = 0, addNum = 0;
// Define the empty string ans
string ans = "";
// Store the length of the numerical string
int n = s.size();
// Start the loop to get the new string
for (int i = n - 1; i >= 0; i--) {
// Store the digit at ith position in the integer form rather character form
int num = s[i] - '0';
// Check if the position is even or not, if even alter the digit
if (temp % 2 == 0) {
addNum += 1;
num += addNum;
// Check if the digit becomes greater than or equal to 10
if (num >= 10) {
// If yes, we need to take a modulus of 9 to make it single digit
num %= 9;
// Check if the single digit is 0, and change the digit back to 9
if (num == 0)
num = 9;
}
}
// Store the result
ans = to_string(num) + ans;
temp += 1;
}
// Return the result
return ans;
}
int main(){
// Give the input string of numerical
string s = "12345678";
// Call the Helper function
cout << "The following number by adding natural numbers in order on alternating indices on the string " << s << " from the last is: "<< Helper(s);
return 0;
}
輸出
The following number by adding natural numbers in order on alternating indices on the string 12345678 from the last is: 16375879
public class Main {
public static String Helper(String s) {
// Define a temporary integer
// Initialize the number we will add in the numeric string integers by 0
int temp = 0, addNum = 0;
// Define the empty string ans
StringBuilder ans = new StringBuilder();
int n = s.length();
for (int i = n - 1; i >= 0; i--) {
int num = Character.getNumericValue(s.charAt(i));
// Check if the position is even or not, if even alter the digit
if (temp % 2 == 0) {
addNum += 1;
num += addNum;
// Check if the digit becomes greater than or equal to 10
if (num >= 10) {
// If yes, we need to take a modulus of 9 to make it single digit
num %= 9;
// Check if the single digit is 0, and change the digit back to 9
if (num == 0) {
num = 9;
}
}
}
ans.insert(0, num);
temp += 1;
}
// Return the result
return ans.toString();
}
public static void main(String[] args) {
// Give the input string of numerical
String s = "12345678";
// Call the Helper function
String result = Helper(s);
System.out.println("The following number by adding natural numbers in order on alternating indices on the string " + s + " from the last is: " + result);
}
}
輸出
The following number by adding natural numbers in order on alternating indices on the string 12345678 from the last is: 16375879
def Helper(s):
# Define a temporary varaible
# Initialize the number we will add in the numeric by 0
temp = 0
addNum = 0
# Define the empty ans
ans = ""
n = len(s)
# Start the loop to get the new string
for i in range(n - 1, -1, -1):
num = int(s[i])
# Check if the position is even or not, if even alter the digit
if temp % 2 == 0:
addNum += 1
num += addNum
# Check if the digit becomes greater than or equal to 10
if num >= 10:
# If yes, we need to take a modulus of 9 to make it single digit
num %= 9
# Check if the single digit is 0, and change the digit back to 9
if num == 0:
num = 9
ans = str(num) + ans
temp += 1
# Return the result
return ans
# Give the input string of numerical
s = "12345678"
# Call the Helper function
result = Helper(s)
print("The following number by adding natural numbers in order on alternating indices on the string", s, "from the last is:", result)
輸出
The following number by adding natural numbers in order on alternating indices on the string 12345678 from the last is: 16375879
上述程式碼的複雜度
時間複雜度 - O(n); 其中n是字串的長度
空間複雜度 - O(1); 我們在上述程式碼中沒有將任何變數儲存在任何資料結構中。
結論
在這篇文章中，我們透過從後往前，隔位相加自然數來找到下一個數字。我們透過對從最後一位開始的隔位數字進行操作並將其餘數字保持不變來得到解決方案。我們將使用數字字串而不是實際數字，這樣我們就可以處理具有更多數字的大數值。
93 次瀏覽
