1. Sum of two numbers （ Simple questions ）
Title Description ：
Given an array of integers nums And a target value target, Please find the target value with and in the array Two integer , And return their array subscripts .
You can assume that there is only one answer for each input . however , You can't reuse the same elements in this array .
Examples :
given nums = [2, 7, 11, 15], target = 9
because nums + nums = 2 + 7 = 9
So go back [0, 1]
code ：
class Solution { public static int[] twoSum(int[] nums, int target) { Map<
Integer, Integer> map = new HashMap<>(); for(int i = 0 ; i < nums.length ;i++) {
map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int j = target -
nums[i]; if(map.containsKey(j) && map.get(j) != i) { return new int[] {i, map.
get(j)}; } } return new int; } }
Method analysis ：

In order to optimize the runtime complexity , We need a more efficient way to check whether the target element exists in the array . If it exists , We need to find its index . What is the best way to keep each element in an array corresponding to its index ? Hashtable .
By trading space for speed , We can change the search time from O(n)O(n) Down to O(1)O(1). Hash tables are built for this purpose , It supports approximate
Constant time for quick search . I use it “ approximate ” To describe , Because once there's a conflict , Search time may degenerate to
O(n)O(n). But as long as you choose the hash function carefully , The time taken to look up in the hash table should be amortised to O(1)O(1).

A simple implementation uses two iterations . In the first iteration , We add the value of each element and its index to the table . then , In the second iteration , We will examine the target element for each element （target
- nums[i]target−nums[i]） Does it exist in the table . be careful , The target element cannot be nums[i]nums[i] itself !

optimization ： In fact, this method can be more optimized , We can do it all at once . While iterating and inserting elements into the table , We will also go back to check if the target element for the current element already exists in the table . If it exists , So we've found the corresponding solution , And return it immediately . That is to say, join in at the same time map Element edge query .

* Add two numbers together （ Medium questions ）
Title Description ：
Give two Non empty Is used to represent two nonnegative integers . among , Their respective digits are based on Reverse order How to store , And each node of them can only store One
number . If , Let's add up the two numbers , A new linked list is returned to represent their sum . You can assume that except for numbers 0 outside , Neither of these two numbers can be used 0 start .
Examples ：
input ：(2 -> 4 -> 3) + (5 -> 6 -> 4)
output ：7 -> 0 -> 8
reason ：342 + 465 = 807

code ：
/** * Definition for singly-linked list. * public class ListNode { * int val;
* ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public
ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode d = new ListNode(0);
ListNode p = l1, q = l2, c = d; int sum = 0; while(p != null || q != null){ int
x= (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; sum = sum + x + y;
c.next = new ListNode(sum%10); sum = sum/10; c = c.next; if(p != null){ p = p.
next; } if(q != null){ q = q.next; } } if(sum > 0) c.next = new ListNode(sum);
return d.next; } }
Method analysis ：
First, from the least significant bit, which is the list l1 and l2 The header of the is added . Because every number should be in the 0~9 Within the scope of , When we calculate the sum of two numbers, it may appear “ overflow ”. for example ,5 +
7 =12. under these circumstances , We will set the value of the current bit to 2, And carry it sum = 1 Bring in the next iteration . carry sum It must be
0 or 1, That's because two numbers add up （ Considering carry ） The maximum possible sum is 9 + 9 + 1 = 19.

3. Longest substring without repeating characters （ Medium questions ）
code
public class Solution { public int lengthOfLongestSubstring(String s) { char[]
a= s.toCharArray(); int sum = 0; for(int i = 0; i < a.length ; i++){ ArrayList<
Character> b = new ArrayList<>(); b.add(a[i]); // When there are elements , take sum Value to 1 sum = sum < b.
size() ? b.size() :sum; for(int j = i + 1; j < a.length; j++){ if(b.contains(a[j
]) ){ sum = sum < b.size() ? b.size() :sum; b.clear(); break; } else{ b.add(a[j]
); sum = sum < b.size() ? b.size() :sum; } } } return sum; } }
Method analysis ：
My method belongs to the law of violence , Check each substring , Compare the length of a string without duplicate letters , Filter out the longest record in sum in

optimization ： In the law of violence , Double check a substring for duplicate characters , But it's not necessary . The main idea used in this question is ： sliding window
What is a sliding window ?
It's actually a queue , Like in the example abcabcbb, Enter this queue （ window ） by abc Meet the requirements of the topic , When re entering a, The queue becomes
abca, The requirements are not met at this time . therefore , We're moving
Move this line !

How to move ?
All we have to do is remove the elements on the left side of the queue , Until the title requirements are met !
This queue is maintained all the time , Find out when the longest queue appears , Find the solution !
code ：
public class Solution { public int lengthOfLongestSubstring(String s) { int n =
s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); // current
index of character // try to extend the range [i, j] for (int j = 0, i = 0; j <
n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)),
i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans
; } }
Code two ：
In the past, we didn't match strings s The character set used is assumed .=
When we know that the character set is small , We can replace it with an array of integers as a direct access table Map.
Common tables are shown below ：
int  For letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
int  be used for ASCII code
int  For extension ASCII code
public class Solution { public int lengthOfLongestSubstring(String s) { int n =
s.length(), ans = 0; int[] index = new int; // current index of character
// try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { i = Math.
max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] =
j+ 1; } return ans; } }
4. Longest Palindromic Substring （ Medium questions ）
Title Description ：
Given a string s, find s The longest palindrome substring in . You can assume that s The maximum length of is 1000.
Examples 1：
output : “bab”
be careful : “aba” It's also a valid answer .
Examples 2：
input : “cbbd”
output : “bb”

method code ：
class Solution { public String longestPalindrome(String s) { if (s == null || s
.length() < 1) return ""; int start = 0 , end = 0; for(int i = 0; i < s.length()
;i++){ int len1 = around(s,i,i); int len2 = around(s,i,i+1); int len = Math.max(
len1, len2); if(len > end - start +1){ start = i - (len-1)/2; end = i + len/2; }
} return s.substring(start , end + 1); } public static int around(String s ,int
left,int right){ int i = left, j = right ; while(i >= 0 && j < s.length() && s.
charAt(i) == s.charAt(j)){ i--; j++; } return j - i -1; } }
Method analysis ：
in fact , Just use constant space , We can solve this problem .
We observed that the two sides of palindrome center mirror each other . therefore , Palindrome can be expanded from its center , And only 2n - 1 Such a center .

You may ask , Why 2n - 12n−1 individual , instead of nn Centers ? The reason is that the center of palindrome with even number of letters can be between two letters （ for example “abba”
The center of the two ‘b’ between ）.

* Z Glyph transformation （ Medium questions ）
According to the given number of lines, a given string will be , From top to bottom , From left to right Z Glyph arrangement .
For example, the input string is “LEETCODEISHIRING” The number of rows is 3 Time , The arrangement is as follows ： L C I R E T O E S I I G E D H N
after , Your output needs to be read line by line from left to right , A new string is generated , such as ：“LCIRETOESIIGEDHN”.
Please implement this function to transform the string into the specified number of lines ：
string convert(string s, int numRows);
Examples 1:
input : s = “LEETCODEISHIRING”, numRows = 3
output : “LCIRETOESIIGEDHN”
Examples 2:
input : s = “LEETCODEISHIRING”, numRows = 4
output : “LDREOEIIECIHNTSG”
explain :
L D R E O E I I E C I H N T S G
Method 1 code ：
class Solution { public String convert(String s, int numRows) { if (numRows ==
1) return s; List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i <
Math.min(numRows, s.length()); i++) rows.add(new StringBuilder()); int curRow =
0; boolean goingDown = false; for (char c : s.toCharArray()) { rows.get(curRow).
append(c); if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow+= goingDown ? 1 : -1; } StringBuilder ret = new StringBuilder(); for (
StringBuilder row : rows) ret.append(row); return ret.toString(); } }
Method one analysis ：

In this method, the string is stored in the corresponding position of the new string in the order of each character , Create first StringBuilder Set of , There are altogether numRows group , Each group represents each row , It is then stored in the order of each character in the corresponding line of the new string StringBuilder in , Finally, the string of each line is spliced together .
notes ：
Don't use it String Splicing , Because if the input scale is large , Will cause timeout , No .

Method 2 code ：
class Solution { public: string convert(string s, int numRows) { if (numRows ==
1) return s; string ret; int n = s.size(); int cycleLen = 2 * numRows - 2; for (
int i = 0; i < numRows; i++) { for (int j = 0; j + i < n; j += cycleLen) { ret +
= s[j + i]; if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) ret += s[j +
cycleLen- i]; } } return ret; } };
Method 2 Analysis ：
This method is stored in line by line access , The redistributed characters are stored line by line ,
First access the row 0 All characters in , Then visit the line 1, Then you can 2, Insert the code fragment here …

* Integer inversion （ Simple questions ）
Give one 32 Bit signed integer , You need to reverse the number on each of the integers .
Examples 1:
input : 123
output : 321
Examples 2:
input : -123
output : -321
Examples 3:
input : 120
output : 21
method code ：
class Solution { public int reverse(int x) { long result = 0L; int yu = 0; for(
int i = 0; x != 0; i++) { yu = x % 10; x /= 10; result = result*10 + yu; } if(
result>= -2147483648 &&result <= 2147483647) return (int)result; else return 0;
} }
There's nothing to say about this method , It's easy to understand , The only thing to pay attention to is , Note that when the inverted array exceeds int Handling when the maximum range of the type .

Technology
Daily Recommendation
views 4
views 2