Это 4-й день моего участия в ноябрьском испытании обновлений, подробности о мероприятии:Вызов последнего обновления 2021 г.
предисловие
Строка — это структура данных, которая очень часто появляется в нашей разработке. Я подготовил здесь несколько небольших вопросов. Независимо от того, являетесь ли вы новичком или экспертом, вы можете попробовать легко решить следующие вопросы. Если у вас есть лучший решение, добро пожаловать на общение в комментариях!
- Как изменить строку без использования встроенных методов Java?
- Напишите программу Java, чтобы проверить, являются ли две строки Anagrams? [Аномальные слова относятся к тому же персонажам в разных позициях]
- Определить, встречаются ли все символы в строке только один раз?
- Как найти повторяющиеся символы в строке?
- Найти все подстроки строки?
- Найти все возможные перестановки входной строки?
Прежде чем вы начнете читать приведенные ниже решения, вы могли бы также подумать о том, как следует решать эти проблемы, а затем посмотреть, соответствуют ли следующие методы тому, что вы думаете.Если ваш метод лучше, оставьте сообщение в области комментариев.
Как перевернуть строку без использования встроенных методов Java?
Есть три способа решить эту проблему:
- использовать цикл
- использовать рекурсию
- Используйте StringBuilder, StringBuffer
Используйте цикл for
Идеи:
- Объявите пустую переменную String для хранения последней перевернутой строки;
- Используйте цикл для перемещения, чтобы перевернуть строку, из последней позиции до 0-й позиции;
- Добавляйте символы в объявленную пустую переменную String во время обхода.
public class ReverseStringForMain {
public static void main(String[] args) {
String blogName = "小黑说Java";
String reverse = "";
for (int i = blogName.length() - 1; i >= 0; i--) {
reverse = reverse + blogName.charAt(i);
}
System.out.println("Reverse of 小黑说Java is: " + reverse);
}
}
использовать рекурсию
Идеи:
- Если длина строки равна 1, обратным результатом является сама строка;
- Если длина строки больше 1, обратный результат — это последний символ строки плюс обратный результат остальной части строки.
public class ReverseStringRecursive {
public static void main(String[] args) {
ReverseStringRecursive rsr = new ReverseStringRecursive();
String blogName = "小黑说Java";
String reverse = rsr.recursiveReverse(blogName);
System.out.println("Reverse of 小黑说Java is:" + reverse);
}
public String recursiveReverse(String orig) {
if (orig.length() == 1){
return orig;
}else{
return orig.charAt(orig.length() - 1) +
recursiveReverse(orig.substring(0, orig.length() - 1));
}
}
}
использовать StringBuffer
Способ использования обратной формы стрингуфера, обратная функция также может быть достигнута строка.
public class StringBufferReverse {
public static void main(String[] args) {
String blogName = "小黑说Java";
StringBuffer sb = new StringBuffer(blogName);
System.out.println("Reverse of 小黑说Java is:" + sb.reverse());
}
}
Напишите программу Java для проверки того, что две строки являются эктопическим словом?
Объяснение: Анаграмма — это два слова, которые состоят из одинаковых букв, но в разном порядке, например: Ангел и Угол.
Есть несколько решений этой проблемы:
- Использование методов класса String
- Используйте Arrays.sort()
- использовать массив подсчета
- Использование мультимножества Гуавы
Использование методов класса String
Идеи:
- Создайте метод, который получает две строковые переменные, чтобы определить, является ли это анаграммой;
- Переберите первое слово String и используйте метод charAt(), чтобы получить из него char c;
- Если значение indexOf(c) второго слова String равно -1, то две строки не являются анаграммами;
- Если значение indexOf(c) второго слова String не равно -1, то удалить символ c из второго слова;
- Если второе слово String является пустой строкой в конце, это означает, что два слова являются анаграммами.
public class StringAnagramMain {
public static void main(String[] args) {
String word = "小黑说Java";
String anagram = "小黑说JAVA";
System.out.println("小黑说Java and 小黑说JAVA are anagrams :" + isAnagramUsingStringMethods(word, anagram));
}
public static boolean isAnagramUsingStringMethods(String word, String anagram) {
if (word.length() != anagram.length())
return false;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = anagram.indexOf(c);
if (index != -1) {
anagram = anagram.substring(0, index)
+ anagram.substring(index + 1, anagram.length());
} else{
return false;
}
}
return anagram.isEmpty();
}
}
Используйте Arrays.sort()
Идея: Отсортируйте две строки напрямую.Если две строки равны после сортировки, это означает, что две строки являются анаграммами.
public class AnagramUsingSort {
public static void main(String[] args) {
String word = "小黑说Java";
String anagram = "小黑说JAVA";
System.out.println("小黑说Java and 小黑说JAVA are anagrams :" + isAnagramUsingArraySort(word, anagram));
}
public static boolean isAnagramUsingArraySort(String word, String anagram) {
String sortedWord = sortChars(word);
String sortedAnagram = sortChars(anagram);
return sortedWord.equals(sortedAnagram);
}
public static String sortChars(String word) {
char[] wordArr = word.toLowerCase().toCharArray();
Arrays.sort(wordArr);
return String.valueOf(wordArr);
}
}
использовать массив подсчета
Идеи:
- Если две строки имеют разную длину, это не анаграммы;
- Создайте массив длиной 256;
- перебрать первую строку str1;
- На каждой итерации мы увеличиваем счетчик первой строки str1 и уменьшаем счетчик второй строки str2;
- Если счетчик любого символа в конце не равен 0, это означает, что две строки не являются анаграммой.
Временная сложность этого метода составляет O(n), но для подсчета массива требуется дополнительное пространство.
public class AnagramCountingMain {
public static void main(String args[])
{
boolean isAnagram = isAnagram("Angle","Angel");
System.out.println("Are Angle and Angel anangrams: "+isAnagram);
}
public static boolean isAnagram(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
int count[] = new int[256];
for (int i = 0; i < str1.length(); i++) {
count[str1.charAt(i)]++;
count[str2.charAt(i)]--;
}
for (int i = 0; i < 256; i++) {
if (count[i] != 0) {
return false;
}
}
return true;
}
}
Использование мультимножества Гуавы
Если вам нравится использовать библиотеку Guava, вы можете использовать MultiSet, чтобы проверить, являются ли две строки анаграммами.
MultiSet позволяет каждому элементу появляться несколько раз и записывает количество каждого элемента.
Конечно, этот метод требует добавления зависимостей Guava в pom.xml.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.1-jre</version>
</dependency>
код показывает, как показано ниже:
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;
public class AnagramMultiSet {
public static void main(String args[])
{
boolean isAnagram = isAnagramMultiset("Angle","Angel");
System.out.println("Are Angle and Angel anangrams: "+isAnagram);
}
public static boolean isAnagramMultiset(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
Multiset<Character> ms1 = HashMultiset.create();
Multiset<Character> ms2 = HashMultiset.create();
for (int i = 0; i < str1.length(); i++) {
ms1.add(str1.charAt(i));
ms2.add(str2.charAt(i));
}
return ms1.equals(ms2);
}
}
Определить, встречаются ли все символы в строке только один раз?
Описание: напримерAppleсимволы в словахpОн появляется много раз, поэтому не совпадает;worldВсе слова в , встречаются только один раз, поэтому совпадают.
Есть несколько решений этой проблемы:
- Использовать хэшсет
- Используя indexOf и lastindexof
- Использовать значение ascii символа
Использовать хэшсет
Зависит от метода add() класса HashSet, который вернет false, если элемент уже существует.
шаг:
- Пройдитесь по каждому символу и добавьте в HashSet;
- Если метод добавления HashSet возвращает false, то это не все уникальные символы.
public class StringAllUniqueCharMain {
public static void main(String[] args) {
System.out.println("Apple has all unique chars :"+ hasAllUniqueChars("apple"));
System.out.println("index has all unique chars :"+ hasAllUniqueChars("index"));
System.out.println("world has all unique chars :"+ hasAllUniqueChars("world"));
}
public static boolean hasAllUniqueChars (String word) {
HashSet alphaSet=new HashSet();
for(int index=0;index < word.length(); index ++) {
char c =word.charAt(index);
if(!alphaSet.add(c))
return false;
}
return true;
}
}
Использование методов indexOf и lastIndexOf
Идея: если indexOf и lastIndexOf возвращают одно и то же значение для символа, в этой строке не будет повторений.
public class StringAllUniqueCharMain {
public static void main(String[] args) {
System.out.println("Apple has all unique chars : "+ hasAllUniqueChars("apple"));
System.out.println("index has all unique chars : "+ hasAllUniqueChars("index"));
System.out.println("world has all unique chars : "+ hasAllUniqueChars("world"));
}
public static boolean hasAllUniqueChars (String word) {
for(int index=0;index < word.length(); index ++) {
char c =word.charAt(index);
if(word.indexOf(c)!=word.lastIndexOf(c))
return false;
}
return true;
}
}
Использовать значение ascii символа
Этот метод является наиболее эффективным.
Идеи:
- Создайте логический массив длиной 26;
- преобразовать char в верхний регистр и получить его значение ascii;
- Вычтите значение ascii из 64, чтобы получить индекс от 0 до 25;
- Если символы не повторяются, в логическом массиве должно быть false;
public class StringAllUniqueCharMain {
public static void main(String[] args) {
System.out.println("Apple has all unique chars : "+ hasAllUniqueChars("apple"));
System.out.println("index has all unique chars : "+ hasAllUniqueChars("index"));
System.out.println("world has all unique chars : "+ hasAllUniqueChars("world"));
}
public static boolean hasAllUniqueChars (String word) {
boolean[] charMap = new boolean[26];
for(int index=0;index < word.length(); index ++) {
// we are substracting char's ascii value to 64, so we get all index
// from 0 to 25.
int asciiCode = (int) word.toUpperCase().charAt(index) - 64;
if(!charMap[asciiCode])
charMap[asciiCode] = true;
else
return false;
}
return true;
}
}
Как найти повторяющиеся символы в строке?
Идеи:
- Создайте HashMap, создайте HashMap, строковый символ будет вставлен как ключ, а его количество будет вставлено как значение;
- Если HashMap уже содержит char, увеличьте его счетчик на 1, иначе поместите char в HashMap;
- Если значение Char больше 1, это означает, что это повторяющийся символ в этой строке.
import java.util.HashMap;
public class StringFindDuplicatesMain {
public static void main(String[] args) {
String str = "juejin.com ";
HashMap<Character, Integer> charCountMap = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (charCountMap.containsKey(c)) {
charCountMap.put(c, charCountMap.get(c) + 1);
} else {
charCountMap.put(c, 1);
}
}
for (Character c : charCountMap.keySet()) {
if (charCountMap.get(c) > 1)
System.out.println("duplicate character : " + c + " ====== " + " count : " + charCountMap.get(c));
}
}
}
Найти все подстроки строки?
Например: если ввод abb, то вывод должен быть a, b, b, ab, bb, abb
Идея: Используйте метод subString класса String, чтобы найти все подстроки.
class SubstringsOfStringMain{
public static void main(String args[]){
String str="abbc";
System.out.println("All substring of abbc are:");
for (int i = 0; i < str.length(); i++) {
for (int j = i+1; j <= str.length(); j++) {
System.out.println(str.substring(i,j));
}
}
}
}
Временная сложность этого решенияO(n^3). потому что у нас есть две петли иStringВременная сложность метода подстроки составляетO(n)
Если вы хотите найти все отдельные подстроки строки, вам нужно использоватьHashSetдля удаления повторяющихся строк.
Найти все возможные перестановки входной строки?
Например: ввод "AB", вывод ["AB", "BA"], ввод "ABC", вывод ["ABC", "ACB", "BAC", "BCA", "CBA", "CAB"] .
Идеи:
- Выньте первый символ строки и рекурсивно введите разные позиции расположения остальных строк;
- Предполагая, что входная строка является ABC, выньте первый символ «A»;
- Выньте B из BC и рекурсивно введите оставшуюся строку «C»;
- Когда длина строки равна 1, она возвращается, поэтому возвращается "C";
- Вставьте извлеченную «B» в каждую позицию строки результата рекурсивного возврата;
- В это время получить БК, КБ, возврат;
- Вставьте извлеченный символ «A» в каждую позицию строки, которая возвращает результат;
- В это время получают [ABC, BAC, BCA] и [ACB, CAB, CBA];
- Конечным результатом возврата является вся сортировка ABC.
import java.util.HashSet;
import java.util.Set;
public class PermutationOfStringJava {
public static void main(String[] args) {
Set<String> set = permutationOfString("ABC");
System.out.println("Permutations of String ABC are:");
for (String str : set) {
System.out.println(str);
}
}
public static Set<String> permutationOfString(String str) {
Set<String> permutationSet = new HashSet<>();
if (str.length() == 1) {
permutationSet.add(str);
return permutationSet;
}
char c = str.charAt(0);
String rem = str.substring(1);
Set<String> permutatedSetForRemainingString = permutationOfString(rem);
for (String permutedString : permutatedSetForRemainingString) {
for (int j = 0; j <= permutedString.length(); j++) {
String permutation = insertFirstCharAtDiffPlaces(permutedString, c, j);
permutationSet.add(permutation);
}
}
return permutationSet;
}
public static String insertFirstCharAtDiffPlaces(String perm, char firstChar, int index) {
return perm.substring(0, index) + firstChar + perm.substring(index);
}
}
резюме
Вышеизложенное — это все содержание этого вопроса, а вы думали об этих методах? Если у вас есть лучший способ, пожалуйста, оставьте сообщение для обмена.
Если это полезно для вас, лайк будет для меня самым большим поощрением.