資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究不大於 N 且不包含 S 中任何數字的最大數字
尋找不大於給定數字 N 且不包含字串 S 中任何數字的最大數字的挑戰是一個涉及字串操作和數論的問題。目標是確定小於或等於 N 的最大可能數字，同時排除字串 S 中找到的所有數字。
例如，考慮 N 等於 1000 且 S 等於“42”的情況。在這種情況下，不大於 N 且不包含 S 中任何數字的最大數字將是 999。這是因為 999 是可以使用數字 0、1、3、5、6、7、8 和 9（不包括字串 S 中的數字 4 和 2）形成的最大可能數字。
可以使用不同的方法來解決此問題，例如遍歷直到 N 的所有數字並驗證其數字是否不存在於 S 中，或者使用更復雜的方法，例如動態規劃或回溯法。
演算法
步驟 1 - 我們將在 main() 函式中宣告名為“N”和“S”的兩個字串變數。
步驟 2 - 我們將把這兩個變數作為引數傳遞給 LargestNumberFinder() 函式。
步驟 3 - 我們將隱式地將字串數字 N 和 S 轉換為整數，以進行比較等數學運算。
步驟 4 - 我們將手動或透過建立每次都執行相同操作的函式來刪除儲存在 N 中的數字中的前導 0。
步驟 5 - 然後，我們將開始比較兩個字串的數字，找出不大於“N”且不包含字串“S”中任何數字的最大數字。
方法 1：- 簡單方法
使用另一個字串中存在的所有數字在給定字串中查詢最大數字的基本方法如下。main 函式宣告變數並呼叫 LargestNumberFinder 函式。此函式以兩個字串作為輸入，檢查小於 N 的每個值是否在其所有數字都存在於字串 S 中。如果滿足條件，則以字串格式返回該值。attendance 函式用於確定儲存在“i”中的值是否屬於字串 S，同時將 S 轉換為整數資料型別。輸入字串轉換為整數，並使用迴圈來評估條件。程式碼輸出給定字串中具有所有數字都存在於另一個字串中的最大數字。
示例
該程式碼是一個解決方案，它查詢小於 N（輸入字串轉換為整數）的最大數字，該數字由字串 S 中找到的數字組成。該程式碼使用兩個函式“attendance”和“LargestNumberFinder”來確定和返回最大數字。“attendance”函式以整數“i”和字串“s”作為輸入，檢查儲存在“i”中的值是否屬於字串“s”，並將“s”轉換為整數資料型別。“LargestNumberFinder”函式以兩個字串“x”和“s”作為輸入，將“x”轉換為整數，然後使用“attendance”函式檢查小於 N 的每個值是否所有數字都存在於“s”中。main 函式宣告變數並呼叫 LargestNumberFinder 函式，該函式以字串形式返回最大數字。
#include <iostream>
#include <string>
#include <vector>
// function to check whether value stored in ‘i’ is part of string S while also converting S into integer data type.
bool attendance(int i, std::string s) {
while (i) {
int first_digit = i % 10;
i /= 10;
int t = std::stoi(s);
bool found = false;
while (t) {
int second_digit = t % 10;
t /= 10;
if (second_digit == first_digit) {
found = true;
break;
}
}
if (!found)
return false;
}
return true;
}
// function to input two strings and check for each value less than N with all digits present in S.
std::string LargestNumberFinder(std::string x, std::string s) {
int N = std::stoi(x);
for (int i = N; i >= 1; i--) {
if (attendance(i, s)) {
return std::to_string(i);
}
}
return "-1";
}
// main function to declare the variables and call the function.
int main() {
std::string N = "100709";
std::string S = "70";
std::cout << LargestNumberFinder(N, S);
}
輸出
77777
方法 2：- 高效方法
查詢透過用給定字串 S 的數字替換給定數字字串 N 的數字可以形成的最大可能數字的第二種方法是一種高效的方法。這種方法首先檢查 S 中是否存在 N 的每個數字，並用 S 中不存在的最大數字替換找到的第一個數字。然後用 S 中不存在的最大數字替換其餘的數字。然後刪除前導零，並將結果作為最大可能數字返回。這種方法比以前的方法更有效，因為它不需要對字串進行排序。
示例
該程式碼解決了查詢可以從給定字串“N”中形成的最大數字的問題，方法是用字串“S”中不存在的最大數字替換一個數字。該程式碼使用一種高效的方法來解決該問題。“LargestNumberFinder”函式接受兩個字串輸入“num”和“s”，並返回最大可能的數字。向量“vis_s”用於儲存字串“s”的值。程式碼首先識別字符串“num”的第一個屬於字串“s”的數字。然後它用字串“s”中不存在的最大數字交換該數字。然後程式碼查詢字串“s”中找不到的最大數字，並用該數字替換字串“num”中的其餘數字。從最終字串中刪除前導零，如果字串為空，則函式返回“0”。該程式碼透過使用輸入“N”和“S”呼叫該函式來輸出結果。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// function to check for all values of String N with String S and replacing the digit if found same with the largest possible digit not present in S.
string LargestNumberFinder(string num, string s) {
vector<bool> vis_s(10, false);
for (int i = 0; i < (int)s.size(); i++) {
vis_s[int(s[i]) - 48] = true;
}
int n = num.size();
int in = -1;
for (int i = 0; i < n; i++) {
if (vis_s[(int)num[i] - '0']) {
in = i;
break;
}
}
if (in == -1) {
return num;
}
for (char dig = num[in]; dig >= '0'; dig--) {
if (vis_s[(int)dig - '0'] == 0) {
num[in] = dig;
break;
}
}
char LargestDig = '0';
for (char dig = '9'; dig >= '0'; dig--) {
if (vis_s[dig - '0'] == false) {
LargestDig = dig;
break;
}
}
for (int i = in + 1; i < n; i++) {
num[i] = LargestDig;
}
int Count = 0;
for (int i = 0; i < n; i++) {
if (num[i] == '0')
Count++;
else
break;
}
num.erase(0, Count);
if ((int)num.size() == 0)
return "0";
return num;
}
int main() {
string N = "161516";
string S = "756";
cout << LargestNumberFinder(N, S);
return 0;
}
輸出
149999
結論
透過這篇文章，我們更深入地瞭解了此類問題背後的原因，並理解了有助於我們將這些基本概念用於文章開頭提到的主要現實生活問題的概念。例如，在我們的程式碼中，我們分別處理每個問題，然後像一件精美的工藝品一樣將程式碼縫合在一起，類似地，我們將使用這個概念並嘗試逐一解決問題。我們通常會從簡單的方法開始，但我們會敏銳地關注並努力找到更有效的方法。誰知道，在閱讀這篇文章之後，你會找到更好、更有效的方法，並進一步簡化解決方案。因此，讓我們堅持我們對思維和編碼能力的信念，同時我們告別。
110 次瀏覽
