資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學透過將字首加1來最小化使字串迴文的運算次數
在這個問題中，我們將計算透過增加給定字串的字首字元所需的運算次數。
我們將使用字元差異來計算使字串迴文所需的最小運算次數。
問題陳述
我們得到一個包含數字字元的字串nums。我們需要計算將字串轉換為迴文所需的最小運算次數。
在一個操作中，我們可以選擇字串的任何字首並將所有字首字元加1。
示例
輸入
nums = "22434"
輸出
2
解釋
首先，我們可以選擇前2個字元並遞增所有字元。因此，字串變為33434。
之後，我們可以選擇'3'字首，字串變為43434，這是一個迴文串。
輸入
nums = '151'
輸出
0
解釋 - 字串已經是迴文串。所以它輸出0。
輸入
nums = "32102"
輸出
-1
解釋 - 不可能透過遞增字首值將字串轉換為迴文串。
方法1
如果字串滿足以下兩個條件，我們可以根據問題陳述使字串迴文。
將字串分成兩等份後，第一部分的數字應該小於第二部分。
在左半部分，起始字元應該大於結束字元，因為我們需要選擇任何字首並將每個字元加1。
演算法
步驟1 − 將q初始化為len - 1，將p初始化為0，因為我們將其用作索引指標。將maxOps初始化為最大整數值以儲存最小運算元，並將'curr'初始化為0以儲存最大差值。
步驟2 − 開始遍歷字串，直到q > p。
步驟3 − 如果索引q處的字元小於索引p處的字元，則返回-1，因為將字串轉換為迴文是不可能的。
步驟4 − 將索引q和p處的字元的ASCII值之差儲存到'diff'變數中。
步驟5 − 將'curr'和'diff'的最大值儲存在'curr'變數中。
步驟6 − 如果'maxOps'值小於'diff'，則返回-1。
步驟7 − 使用'diff'值更新'maxOps'。
步驟8 − 將p加1，將q減1。
步驟9 − 返回'curr'值。
示例
#include <stdio.h>
#include <string.h>
#include <limits.h>
int makePalindrome(char alpha[], int len) {
int q = len - 1;
int p = 0;
int maxOpes = INT_MAX;
int curr = 0;
// Traverse from both ends
while (q > p) {
// It is not possible to make the string palindromic
if (alpha[q] < alpha[p]) {
return -1;
}
// Get character difference
int diff = alpha[q] - alpha[p];
// Get the maximum current difference
curr = (curr > diff) ? curr : diff;
// At the center side difference should be less than the characters at the end
if (maxOpes < diff) {
return -1;
}
maxOpes = diff;
p++;
q--;
}
return curr;
}
int main() {
char nums[] = "22434";
int len = strlen(nums);
printf("The number of minimum operations required to make the string palindromic is %d\n", makePalindrome(nums, len));
return 0;
}
輸出
The number of minimum operations required to make the string palindromic is 2
#include <bits/stdc++.h>
using namespace std;
int makePalindrome(string alpha, int len) {
int q = len - 1;
int p = 0;
int maxOpes = INT_MAX;
int curr = 0;
// Travere from both ends
while (q > p) {
// It is not possible to make string palindromic
if (alpha[q] < alpha[p]) {
return -1;
}
// Get character difference
int diff = alpha[q] - alpha[p];
// Get the maximum current difference
curr = max(curr, diff);
// At the center side difference should be less than the characters at the end
if (maxOpes < diff) {
return -1;
}
maxOpes = diff;
p++;
q--;
}
return curr;
}
int main() {
string nums = "22434";
int len = nums.length();
cout << "The number of minimum operations required to make string palindromic is " << makePalindrome(nums, len);
return 0;
}
輸出
The number of minimum operations required to make string palindromic is 2
public class Main {
public static int makePalindrome(String alpha) {
int len = alpha.length();
int q = len - 1;
int p = 0;
int maxOpes = Integer.MAX_VALUE;
int curr = 0;
// Traverse from both ends
while (q > p) {
// It is not possible to make the string palindromic
if (alpha.charAt(q) < alpha.charAt(p)) {
return -1;
}
// Get character difference
int diff = alpha.charAt(q) - alpha.charAt(p);
// Get the maximum current difference
curr = Math.max(curr, diff);
// At the center side difference should be less than the characters at the end
if (maxOpes < diff) {
return -1;
}
maxOpes = diff;
p++;
q--;
}
return curr;
}
public static void main(String[] args) {
String nums = "22434";
int len = nums.length();
System.out.println("The number of minimum operations required to make the string palindromic is " + makePalindrome(nums));
}
}
輸出
The number of minimum operations required to make the string palindromic is 2
def make_palindrome(alpha):
q = len(alpha) - 1
p = 0
max_opes = float('inf')
curr = 0
# Traverse from both ends
while q > p:
# It is not possible to make the string palindromic
if alpha[q] < alpha[p]:
return -1
# Get character difference
diff = ord(alpha[q]) - ord(alpha[p])
# Get the maximum current difference
curr = max(curr, diff)
# At the center side difference should be less than the characters at the end
if max_opes < diff:
return -1
max_opes = diff
p += 1
q -= 1
return curr
nums = "22434"
print(f"The number of minimum operations required to make the string palindromic is {make_palindrome(nums)}")
輸出
The number of minimum operations required to make the string palindromic is 2
時間複雜度 − O(N)，用於遍歷字串。
空間複雜度 − O(1)，因為我們不使用任何額外的空間。
在解決方案中，我們檢查從開頭到中心的差異，如果任何中心側字元具有更高的差異，則返回-1。程式設計師可以嘗試從中心遍歷字串，並檢查起始側的較高差異。
更新於：2023年10月23日
133 次瀏覽
廣告