catalogue
Small diary written in front
Changed the c-plane and power supply for the notebook. Finally, it can support me to press the n key smoothly and use the computer without plug-in. There was a small problem. When fixing the damaged mechanical hard disk cable with insulating tape, it stuck to the original on the back, resulting in startup failure, but it was solved smoothly. Fortunately, the motherboard was not broken, or I would be "completely crazy".
Code part
Question 1576
1576. Replace all question marks
Difficulty simple 99 collection sharing switch to English to receive dynamic feedback
Give you one that contains only lowercase English letters and '?' Character string '?'s, please put all'? ' Convert to several lowercase letters so that the final string does not contain any consecutive characters.
Note: you cannot {modify non '?' Character.
Title Test Case guarantee '?' There are no consecutive repeated characters except ； characters.
Returns the final string after all conversions (which may not be required). If there are multiple solutions, return to any of them. It can be proved that the answer always exists under given constraints.
Own code:
class Solution {
public String modifyString(String s) { //a:97
int len = s.length();
char[] S = s.toCharArray();
if(S[0] == '?')
{
if(len >1 && S[1] >= 97 && S[1] < 122) {S[0] = (char)(S[1]+1);}
else {S[0] = 97;}
}
for(int i = 1 ; i < len ; i ++)
{
if(S[i] != '?') {continue;}
else
{
int head = (int)S[i-1];
if(head == 122) {head = 96;}
if(i != len-1 && S[i+1] != head+1) {S[i] = (char)(head+1);}
else if(i == len-1) {S[i] = (char)(head+1);}
else if(i != len-1 && S[i+1] == head+1)
{
if(head == 121) {S[i] = 97;}
else {S[i] = (char)(head+2);}
}
}
}
String res = new String(S);
return res;
}
}Judge the special situation first. First judge the first position so that the first position is not a question mark. Start from the second position and fill in according to the characters of the previous position. The filling content is the previous letter + 1 (if the previous is z, fill in a).
Question 26
26. Delete duplicates in the ordered array
Difficulty simple 2389 collection sharing switch to English to receive dynamic feedback
I'll give you an ordered array {nums, please In situ Delete the repeated elements so that each element {only appears once, and return the new length of the deleted array.
Do not use additional array space, you must In situ Modify the input array {and do it with O(1) extra space.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the internal operation as follows:
//nums is passed by reference. That is, no copy of the arguments is made
int len = removeDuplicates(nums);
//Modifying the input array in the function is visible to the caller.
//According to the length returned by your function, it will print all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Own code:
class Solution {
public int removeDuplicates(int[] nums) {
int len = nums.length;
if(len == 0 || len == 1) {return len;}
//Double finger needling
int insert , search;
insert = 0;
for(search = 1 ; search < len ; search ++)
{
if(nums[search] == nums[search-1]) {continue;}
else
{
insert ++;
nums[insert] = nums[search];
}
}
return insert+1;
}
}Vaguely, I played this question before, on the acm side (only for a short time). Judge the special situation first. Set double pointers, one for detecting characters and one for positioning insertion position. If the detected character is not equal to its previous character, put the character on the insertion position and move the insertion position back one bit; If they are equal, continue will drop to judge the next character.
Question 27
Difficulty simple 1137 collection sharing switch to English to receive dynamic feedback
Give you an array ， num ， and a value ， val, you need In situ Removes all elements with a value equal to {val}, and returns the new length of the array after removal.
Do not use extra array space, you must only use {O(1) extra space and In situ Modify the input array.
The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the internal operation as follows:
//nums is passed by reference. That is, no copy of the arguments is made
int len = removeElement(nums, val);
//Modifying the input array in the function is visible to the caller.
//According to the length returned by your function, it will print all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Own code:
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
if(len == 0) return 0;
if(len == 1 && nums[0] != val) return 1;
if(len == 1 && nums[0] == val) {nums = null; return 0;}
int search , insert = 0;
for(search = 0 ; search < len ; search ++)
{
if(nums[search] == val)
{
continue;
}
else
{
nums[insert] = nums[search];
insert ++;
}
}
return insert;
}
}This question is essentially the same as question 26, but it is not compared with the previous character, but with val.
Question 5
5. Longest palindrome substring
Medium difficulty 4545 collection sharing switch to English to receive dynamic feedback
Give you a string ， s ， and find the longest palindrome substring in ， s ，.
Own code:
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(len == 0 || len == 1) {return s;}
char[] S = s.toCharArray();
int position = 0 ,lenres = 1;
for(int i = 0 ; i < len ; i++)
{
if(len - i + 1 <= lenres)
{
String res = s.substring(position , position+lenres);
return res;
}
int left , right , right0;
left = i;
right0 = right = len;
while(left < right)
{
left = i;
right = right0-1;
while(left < right && S[left] != S[right]) {right --;}
right0 = right;
while(left < right && S[left] == S[right])
{
left ++;
right --;
}
if(S[left] == S[right])
{
if(right0 - i + 1 > lenres)
{
lenres = right0 - i + 1;
position = i;
}
}
else {continue;}
}
}
String res = s.substring(position , position+lenres);
return res;
}
}To string, use the for loop to gradually shorten the search area. For a search area, set the head as the head of the area and the tail as the tail of the area. Look for the same character as the head from the tail forward and set it as a new tail. Probe inward for the head and tail at the same time to judge whether there is a palindrome. If the segment is a palindrome, compare the length of the segment with the longest palindrome string saved. If it exceeds, update the length and the starting position of the palindrome string; If not, look for the same character as the head from the tail before detection again, return the head and judge again. When shortening the search area, judge whether the new search area is shorter than the length of the longest palindrome string saved. If it is shorter than, it does not need to continue and return directly. If it is longer than, it continues to judge.
java small knowledge part
Question 1576
The number in a~z the Unicode code is 97-122 (61H-7AH). The number of a ~ Z is 65-90 (41H-5AH). The numbers of 0 ~ 9 are 48-57 (30H-39H).
String to char [] toCharArray[]； Char [] to string = new String(S);.
Question 27
To be sure, the length of String string is length()； The length of int array is length.
Question 5
When the region is shortened, judge whether the region has been less than the current maximum length value, which can shorten the algorithm time.
Pay attention to the changes of variables in the cycle and judge which variable values need regression and which do not.