当前位置：网站首页>String exercise summary 2
String exercise summary 2
2022-06-24 22:17:00 【Dream building boy】
Catalog
3、 ... and . Find all palindrome substrings of a string （ The central expansion method ）
5、 ... and . Split palindrome string （ The split string is all palindromes ）
6、 ... and . Restore IP Address
7、 ... and . Minimum cover substring
8、 ... and . Letter combination of telephone number
One . Longest text substring
1. subject
Give you a string s, find s The longest palindrome substring in .
Example ：
Input ：s = "babad" Output ："bab" explain ："aba" It's the same answer .
2. The illustration
3. Code
public String longestPalindrome(String s) {
// Set two pointers to save the start and end positions of the palindrome string
int begin = 0;
int end = 0;
for(int i=0; i<s.length(); i++) {
// The string length has parity , So we need to find the maximum value in parity
int len1 = huiWenLen(s, i, i);
int len2 = huiWenLen(s, i, i+1);
int len = Math.max(len1, len2);
if(len>end-begin) {
// When it's even , Such as abb（ The result is bb） At this time, if will be counted more begin=i-len/2 You'll lose one , Cause error
begin = i-(len-1)/2;
end = i+len/2;
}
}
// The string is intercepted from begin Start , To end+1 end （ It doesn't contain end+1）
return s.substring(begin, end+1);
}
// Start from the current element to both sides to find whether it is a palindrome string
public int huiWenLen(String str, int left, int right) {
int l = left, r = right;
while(l>=0 && r<str.length() && str.charAt(l)==str.charAt(r)) {
l--;
r++;
}
return r-l-1;
}Two . Find the full arrangement of all sets of the array （ It is the same as finding all substrings of a string ）
1. subject
Now there is a set of integers without repeating elements S, seek S All subsets of
Be careful ：
The elements in the subset you give must be arranged in ascending order
The given solution set cannot have duplicate elements
Example ：
Input ：[1,2,3]
Return value ：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
2. The illustration
3. Code
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(S==null || S.length==0) {
return res;
}
for(int i=0; i<=S.length; i++) {
// Control length , Call a recursive function to find
dfsColl(S, 0, i, res, new ArrayList<>());
}
return res;
}
public void dfsColl(int[] arr, int begin,int len , ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
// Meet the specified length , Just add it to the result set
if(len == list.size()) {
res.add(new ArrayList<>(list));
}
// Look back from the starting position
for(int i=begin; i<arr.length; i++) {
// Add the current element to list in
list.add(arr[i]);
// And then recursively look back
dfsColl(arr, i+1, len, res, list);
// After finding the specified length of the current element , Delete current element
list.remove(list.size()-1);
}
}3、 ... and . Find all palindrome substrings of a string （ The central expansion method ）
1. subject
Give you a string s , Please count and return this string Palindrome string Number of .
Palindrome string Is reading the same string as reading it backwards .
Substring Is a sequence of consecutive characters in a string .
A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/palindromic-substrings
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Example ：s="aaba"
Output res= 6 , The palindrome string has a ,a ,b ,a ,aa ,aba
2. The idea diagram
（1） Method 1
First of all, a character must be palindrome , When centered on this character , Continue to separate with left and right When extending to both sides and validating as a substring , This is a kind of thinking , But there is a situation , That is, the same two characters can also be formed as a center to spread out , for example aa, At this time, we have to distinguish according to parity （ There may be a question , There may also be 3 Or 4 As a palindrome Center ; because 3 One is 1 Extensions of ,4 One is 2 Extensions of , So we just discuss it according to parity 2 And 1 individual ）; Use 2 When expanding with characters as the center , Need to judge this 2 Characters are equal to each other before expansion .
（2） Method 2
Ideas and methods 1 identical , It is only merged when expanding according to odd and even numbers , Reduce the amount of code .
First of all, we can see from the above processing results , All in all s.length*2-1 Centers need to be expanded ; Then find the relationship , Then we can sum up , from 【0,s.length*2-1】 Between , All the left edges left=i/2; All right edges right=left+i%2;
After that, it is solved by the method of center expansion （ Even numbers are also determined in the process of expansion 2 Whether the characters as the center are equal ）.
3. Code
（1） Method 1
public int countSubstrings(String s) {
// Here itself is palindrome , So first count yourself
int res = s.length();
// Extend with odd numbers
for(int i=0; i<s.length(); i++) {
int left = i-1;
int right = i+1;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
// Extend with even numbers
for(int i=0; i<s.length()-1; i++) {
// explain 2 Characters can be used as the Extension Center
if(s.charAt(i)==s.charAt(i+1)) {
res++;
int left = i-1;
int right = i+2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
}
return res;
}（2） Method 2
public int countSubstrings(String s) {
int res = 0;
// All in all, you need to match len*2-1 Time , Then it will expand to both sides according to parity , If it's palindrome
//res++, Otherwise, judge the next one （ Pay attention to the boundary problem in the process of judgment ）
for(int i=0; i<s.length()*2-1; i++) {
int left = i/2;
int right = left+i%2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
return res;
}Four . Find binary sum
1. subject
Given two binary numbers represented by strings , Back to their and .
Data range ： The string length satisfies 1\le n \le 10^5 \1≤n≤105 , The string contains only 0 and 1, And ensure that except 0 There is no leading zero for binary numbers other than .
Example ：
Input ："101","1"
Return value ："110"
2. The idea diagram
Ideas ：
Ideas ：
First, you need to save the number to be carried and name it carry（ The initial value is 0）,
Then calculate the sum of the current position ( Value containing carry ), sum=A.charAt(i)+B.charAt(i),
When calculating the sum of the current position, you also need to judge whether the length of the source string is exceeded each time , If more than , The current result position is 0
The next step is to save the carry values , Use for the next sum
Then save the sum of the current position
The illustration ：
3. Code
public String binaryAdd (String A, String B) {
// write code here
int aL = A.length()-1;
int bL = B.length()-1;
// It means carry
int carry = 0;
StringBuilder sb = new StringBuilder();
while(aL>=0 || bL>=0 || carry>0) {
// Get the current result of each string
int a = (aL<0?'0':A.charAt(aL--))-'0';
int b = (bL<0?'0':B.charAt(bL--))-'0';
// Sum up （ Contains the carry of the low bit and the sum of the high bit ）
int sum = a+b+carry;
// Save carry results
carry = sum/2;
// Save the result of the current position after carry
sb.append(sum%2);
}
// Finally, reverse the spliced results
return sb.reverse().toString();
}5、 ... and . Split palindrome string （ The split string is all palindromes ）
1. subject
Give you a string s, Would you please s Split into some substrings , So that each substring is Palindrome string . return s All possible segmentation schemes .
Example ：
Input ：s = "aab" Output ：[["a","a","b"],["aa","b"]]
2. The idea diagram
3. Code
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
char[] charArray = s.toCharArray();
dfs(charArray, 0, s.length(), new ArrayList<>());
return res;
}
// Find all palindrome substrings
public void dfs(char[] charArray, int index, int len, ArrayList<String> list) {
// Description string has been processed
if(index == len) {
res.add(new ArrayList<>(list));
return;
}
// Take one part in turn , First judge whether it is palindrome , If it is a palindrome, it will be processed downward , If it's not palindrome , Skip the current loop
for(int i=index; i<len; i++){
if(!isPartion(charArray, index, i)) {
continue;
}
list.add(new String(charArray, index, i-index+1));
dfs(charArray, i+1, len, list);
// After processing the substring of the current layer , Delete the , Then process the following substrings of the current layer
list.remove(list.size()-1);
}
}
// Judge whether it is a palindrome string
public boolean isPartion(char[] charArray, int left, int right) {
while(left < right) {
if(charArray[left++] != charArray[right--]) {
return false;
}
}
return true;
}
6、 ... and . Restore IP Address
1. subject
It works IP Address It's just four integers （ Each integer is located in 0 To 255 Between the composition of , And it can't contain leading 0）, Use... Between integers '.' Separate .
for example ："0.1.2.201" and "192.168.1.1" yes It works IP Address , however "0.011.255.245"、"192.168.1.312" and "[email protected]" yes Invalid IP Address .
Given a string containing only numbers s , It is used to indicate a IP Address , Returns all possible valid IP Address , These addresses can be accessed through s Insert '.' To form . you You can't Reorder or delete s Any number in . You can press whatever Return the answers in order .
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/restore-ip-addresses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
2. The idea diagram
3. Code
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
int len = s.length();
dfs(s, 0, 0, len, new ArrayList<String>());
return res;
}
// Perform a deep search for processing
public void dfs(String s, int beign, int count, int len, ArrayList<String> list) {
// Processing to the end , Just save and return
if(beign == len) {
if(count==4)
res.add(String.join(".", list));
return;
}
// prune （ The length of the characters is less than the number of intercepts , Characters longer than the number of interceptions 3 times ）
if(len-beign<(4-count) || len-beign>3*(4-count)) {
return;
}
// Handle the current 3 Characters （1,2,3 Connect them separately ）
for(int i=0; i<3; i++) {
if(i+beign>=len) {
break;
}
int tmp = segment(s, beign,beign+i+1);
if(tmp != -1){
list.add(""+tmp);
dfs(s, beign+i+1, count+1, len, list);
// to flash back
list.remove(list.size()-1);
}
}
}
// Determine whether the intercepted string conforms to ip Specification of address , Conformity is translated into numbers
public int segment(String s, int left, int right) {
// When the first length is greater than 1 And the first is 0 When you return to
if(right-left>1 && s.charAt(left)=='0') {
return -1;
}
// Find the string of 10 Base result
int res = 0;
for(int i=left; i<right; i++) {
res = res*10+s.charAt(i)-'0';
}
// Description over ip length
if(res>255) {
return -1;
}
return res;
}7、 ... and . Minimum cover substring
1. subject
Give you a string s 、 A string t . return s Covered by t The smallest string of all characters . If s There is no coverage in t Substring of all characters , Returns an empty string "" .
Example ：
2. The idea diagram
The solution idea is to use two hash Table to store strings s and t The number of times characters appear in , First count the string t, After that, we can use the idea of sliding window to take s Characters in are added to hash in , It is equivalent to expanding the window , In the statistical process, if The element on the left side of the window is not in t Contain or contain but repeat more , In this case, you need to reduce the size of the window , These operations are based on hash Table to operate . One more in the middle count Mark whether the element in the window already contains t All characters in , I need one more len To identify whether it is the smallest covering substring .
3. Code
public String minWindow(String s, String t) {
HashMap<Character,Integer> ms = new HashMap<>();
HashMap<Character,Integer> mt = new HashMap<>();
// Statistics first t The number of times characters appear in
for(int i=0; i<t.length(); i++) {
mt.put(t.charAt(i), mt.getOrDefault(t.charAt(i), 0)+1);
}
// Save the result value
String res="";
// Record the current length , Then shorten the string according to the length
int len = Integer.MAX_VALUE;
//left and right Represents the left and right boundaries of the sliding window ;count Record t stay s Number of existing in
for(int left=0,right=0,count=0; right<s.length(); right++) {
// Put the element first ms in
ms.put(s.charAt(right), ms.getOrDefault(s.charAt(right), 0)+1);
// Determine whether the character also appears in t in
if(mt.containsKey(s.charAt(right))) {
// You also need to determine whether the current character is t necessary （ Avoid repeated useless characters ）
if(ms.get(s.charAt(right))<=mt.get(s.charAt(right))) {
count++;
}
}
// If s Of left The element of position is not contained in t in or The number of characters exceeds the specified number , Then delete the character
while(left<right && (!mt.containsKey(s.charAt(left)) ||
ms.get(s.charAt(left))>mt.get(s.charAt(left)))) {
ms.put(s.charAt(left), ms.get(s.charAt(left))-1);
left++;
}
// Satisfy count length then （ according to len） Determine whether to shorten the interval , If shortened , modify res
if(count==t.length() && right-left+1<len) {
len = right-left+1;
res = s.substring(left, right+1);
}
}
return res;
}8、 ... and . Letter combination of telephone number
1. subject
Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .
Example ：
Input ：digits = "23" Output ：["ad","ae","af","bd","be","bf","cd","ce","cf"]
2. Graphic thinking
The character corresponding to each number is processed by recursive backtracking , When recursion reaches the end of the string , Just save the results , End recursion .
3. Code
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.length()==0) {
return res;
}
Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
dfs(0, digits, new StringBuilder(), map, res);
return res;
}
public void dfs(int index, String digits, StringBuilder sb, Map<Character, String> map, List<String> res) {
if(index==digits.length()) {
// Indicates that the number has been processed to the end
res.add(new String(sb));
return;
}
// Not finished with , Just process the number of the current position ( Get all the characters corresponding to the current number )
String str = map.get(digits.charAt(index));
// Loop through the current character and recursively process the next number
for(int i=0; i<str.length(); i++) {
sb.append(str.charAt(i));
// recursive
dfs(index+1, digits, sb, map, res);
// to flash back
sb.deleteCharAt(sb.length()-1);
}
}边栏推荐
- Shutter precautions for using typedef
- Yida technology signed a contract with seven wolves to help the digital transformation of "Chinese men's wear leader"
- 如何比较两个或多个分布：从可视化到统计检验的方法总结
- Summary of papers on traveling salesman problem (TSP)
- Flutter： Unsupported value: false/true
- 排查到解决问题的过程：浏览器突然无法访问网页，错误代码：0x80004005，最终定位：“电脑打开热点，电脑就不能上网了”
- Interviewer: you said you are proficient in redis. Have you seen the persistent configuration?
- KT6368A蓝牙芯片的主从机之前透传功能说明，2.4G跳频自动连接
- [notes of Wu Enda] multivariable linear regression
- Multithreaded finalization
猜你喜欢
![[notes of Wu Enda] multivariable linear regression](/img/b1/60a702aaca58b0afa57ac2f552dabf.png)
[notes of Wu Enda] multivariable linear regression
Flutter-使用 typedef的注意事项
![leetcode：515. Find the maximum value in each tree row [brainless BFS]](/img/87/1926d783fb6f8d8439213d86b5da40.png)
leetcode：515. Find the maximum value in each tree row [brainless BFS]
Réduire le PIP à la version spécifiée (mettre à jour le PIP avec pycharm avant de le réduire à la version originale)
How to grab the mobile phone bag for analysis? Fiddler artifact may help you!
EasyBypass
PostMan工具介绍及安装使用
性能测试工具wrk安装使用详解
Flutter 库冲突问题解决
Ideal L9, new trend of intelligent cockpit
随机推荐
Flutter 库冲突问题解决
关于自动控制原理资料更新
04A interrupt configuration
字符串习题总结2
socket done
Object. Defineproperty and reflect Fault tolerance of defineproperty
02--- impossible phenomenon of longitudinal wave
是真干不过00后，给我卷的崩溃，想离职了...
Servlet details
产业互联网时代，并不存在传统意义上的互联网
Mysql 通过表明获取字段以及注释
TKKC round＃3
SAP interface debug setting external breakpoints
印刷行业的ERP软件的领头羊
ansible基本配置
虚拟人的产业发展现状
Cannot find reference 'imread' in 'appears in pycharm__ init__. py‘
进程的通信方式
leetcode-201_ 2021_ 10_ seventeen
Description of software version selection of kt6368a Bluetooth dual-mode transparent chip