資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學最小化移除不相鄰的字元以使給定字串為空所需的操作次數
在本文中，我們將深入探討一個引人入勝的字串操作問題。“最小化移除不相鄰的字元以使給定字串為空所需的操作次數”。這個問題是增強您對字串、字元移除和演算法思維理解的絕佳方式。
問題陳述
給定一個字串，任務是最小化使給定字串為空所需的不相鄰字元移除操作次數。一次操作中，您可以移除任何兩個不相鄰的字元。
解決方案方法
解決此問題的方法是使用棧資料結構。我們迭代字串的字元，對於每個字元，如果棧非空且棧頂不等於當前字元，我們從棧中彈出棧頂字元。否則，我們將當前字元壓入棧中。所需的操作次數是最後棧中剩餘字元的個數。
示例
以下是上述方法的程式：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
int minimizeRemovals(char* str) {
int size = 0;
char* stack = (char*)malloc(strlen(str) * sizeof(char));
for (int i = 0; str[i] != '\0'; i++) {
if (size > 0 && stack[size - 1] != str[i]) {
size--; // Pop the top element from the stack
} else {
stack[size] = str[i]; // Push the character onto the stack
size++;
}
}
free(stack);
return size;
}
int main() {
char str[] = "abba";
int operations = minimizeRemovals(str);
printf("The minimum number of removal operations is: %d\n", operations);
return 0;
}
輸出
The minimum number of removal operations is: 0
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int minimizeRemovals(string str) {
stack<char> s;
for (char c : str) {
if (!s.empty() && s.top() != c) {
s.pop();
} else {
s.push(c);
}
}
return s.size();
}
int main() {
string str = "abba";
int operations = minimizeRemovals(str);
cout << "The minimum number of removal operations is: " << operations << endl;
return 0;
}
輸出
The minimum number of removal operations is: 0
import java.util.Scanner;
public class Main {
public static int minimizeRemovals(String str) {
java.util.Stack<Character> stack = new java.util.Stack<>();
for (char c : str.toCharArray()) {
if (!stack.isEmpty() && stack.peek() != c) {
stack.pop(); // Pop the top element from the stack
} else {
stack.push(c); // Push the character onto the stack
}
}
return stack.size();
}
public static void main(String[] args) {
String str = "abba";
int operations = minimizeRemovals(str);
System.out.println("The minimum number of removal operations is: " + operations);
}
}
輸出
The minimum number of removal operations is: 0
def minimize_removals(s):
stack = []
for c in s:
if stack and stack[-1] != c: # Check if the stack is not empty and the top element is different from the current character
stack.pop() # Pop the top element from the stack
else:
stack.append(c) # Push the character onto the stack
return len(stack)
def main():
s = "abba"
operations = minimize_removals(s)
print("The minimum number of removal operations is:", operations)
if __name__ == "__main__":
main()
輸出
The minimum number of removal operations is: 0
帶測試用例的解釋
當我們將此字串傳遞給minimizeRemovals函式時，它會迭代字串的字元。過程如下：
它將'a'壓入棧中。
然後它將'b'壓入棧中，因為'b'不等於棧頂('a')。
當遇到下一個'b'時，它會發現棧頂也是'b'，因此它不執行移除操作，'b'被壓入棧中。
現在棧頂是'b'，下一個字元是'a'。由於'a'不等於'b'，它透過彈出棧頂來執行移除操作。現在棧頂是'b'。
最後，它在字串中遇到'a'，它不等於棧頂('b')。因此，它透過彈出棧頂來執行移除操作。
在函式結束時，棧中沒有剩餘字元，這表明所有不相鄰的字元都已從字串中移除。因此，函式返回0，這是使給定字串為空所需的最小移除操作次數。
結論
此問題提供了一個使用棧資料結構進行字串操作的絕佳機會。這是一個練習編碼技能和了解如何使用棧解決問題的優秀問題。
更新於：2023年10月23日
820 次瀏覽
廣告