preface
Today is the first day, so let's simply send it to the topic to play, not for anything else, just for pleasure.
Although this is a simple topic, I didn't expect that I didn't pay attention to several variables. I was stunned and adjusted for a long time. You should be more careful.
Sum of two numbers
Given an integer array nums and an integer target value target, please find the two with and as the target value target in the array
Integers and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot be repeated in the answer.
You can return answers in any order.
Example 1:
Input: num = [2,7,11,15], target = 9, output: [0,1] explanation: because num [0] + num [1]==
9, return [0, 1]. Example 2:
Input: num = [3,2,4], target = 6, output: [1,2]
At first glance, this topic is actually quite simple. The best way to think of is to take two pointers to scan one before the other, and then add the two numbers to see if it is the result we want.
class Solution {
public int[] twoSum(int[] nums, int target)
{
int n = nums.length;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (nums[i] + nums[j] == target)
{
return new int[]{i, j};
}
}
}
return new int[0];
}
}
However, we actually have a more nice method, that is, we can use hash functions to reduce the time complexity. In fact, we use dictionaries called map s in java
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
We can directly store our numerical elements and corresponding subscripts in the map. Then you don't ask (if you ask for 9, then I directly traverse the 9-element and so on, which is not equal to another element in the map) and we can directly put our search and element addition together, because we know that we don't need to add elements down and scan.
For ease of understanding, you can view the python code directly
class Solution:
def twoSum(self, nums, target):
hashtable = {}
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
Oh, by the way, it is necessary to say that the python syntax used by many people now seems to be 3.9x. Although there is no problem, it looks strange.
Palindrome number
Give you an integer X. if x is a palindrome integer, return true; Otherwise, false is returned.
Palindromes are integers that are read in the same positive order (from left to right) and reverse order (from right to left). For example, 121 is palindrome, not 123.
Example 1:
Input: x = 121 output: true example 2:
Input: x = -121 output: false interpretation: read from left to right, which is - 121. Read from right to left, 121 -. Therefore, it is not a palindrome number.
This is actually very simple. The simplest thing is that you turn it into a string and scan it from the front to the back two pointers (array subscript points to).
But we can actually optimize it. The principle is the same. We scan at both ends. But the difference is that for the former, we need to convert it into a string and then scan it, which will bring some memory consumption. For the other, we use the remainder method and then splice numbers, which is also scanning before and after.
class Solution {
public boolean isPalindrome(int x) {
if(x<0||x%10==0 && x!=0){
//Negative numbers and single digits are not palindromes
return false;
}
int rev = 0;
//We extract half and half, take out the bits, and then in turn
while (x>rev){
rev = rev * 10 + x%10;
x /=10;
}
return x==rev||x==rev/10;
}
}
For example, 1221
If we take out the last 1 and 2 in half, the reverse combination is 12. If this 12 is equal to the previous 12, it is not a palindrome.
The detail to note here is that 12321 is odd. In our code, it is combined from the back, that is, rev = 123 exits the loop x= 12. At this time, x == rev/10 is established.
Roman numeral to integer
Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
Character value I 1 V 5 X 10 L
50 C 100 D 500 M 1000 e.g. Roman numeral 2
Write as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.
Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is in the number 5
To the left of, the number represented is equal to the large number 5 minus the decimal number 1 to get the value 4. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:
I can be placed to the left of V (5) and X (10) to represent 4 and 9. X can be placed to the left of L (50) and C (100)
40 and 90. C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Given a Roman numeral, convert it to an integer.
Example 1:
Input: s = "III" output: 3
There are two points to this question
The first point is:
Note that it is the rule of Roman characters. If the number represented by character a is smaller than that represented by character B, we should subtract the value represented by a from the overall addition result. If the number represented by a is larger than that represented by B, we should directly add the value represented by A. The relationship between a and B is AB
The second point is:
First of all, we found that the speed of adding Roman character elements to the map dynamically is faster than that of adding them directly, and the performance consumption is less.
class Solution {
public int romanToInt(String s) {
Map<Character,Integer> map = new HashMap<>();
String chars = "IVXLCDM";
int j = 1;
for(int i=1;i<=chars.length();i++){
if(i!=1)
if (i%2==0)
j*=5;
else
j*=2;
map.put(chars.charAt(i-1),j);
}
j = 0;
for(int i=0;i<s.length();i++){
int value = map.get(s.charAt(i));
if(i<s.length()-1 && value<map.get(s.charAt(i+1))){
j-=value;
}
else
j+=value;
}
return j;
}
}
Valid parentheses
Given a string s that only includes' (',') ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
The left parenthesis must be closed with the same type of right parenthesis. The left parentheses must be closed in the correct order. Example 1:
Input: s = "()" output: true example 2:
Input: s = "() [] {}" output: true
There's nothing to say about this. Stack.
class Solution {
public boolean isValid(String s) {
if(s == null || s.length() == 1){
return false;
}
Stack<Character> chars = new Stack<Character>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c=='(' || c=='[' || c=='{'){
chars.push(c);
}
else {
if(chars.isEmpty())
return false;
if(c==')'&& chars.peek()=='('){
chars.pop();
}else if (c==']' && chars.peek()=='['){
chars.pop();
}
else if (c=='}' && chars.peek()=='{'){
chars.pop();
}
else
return false;
}
}
if(chars.isEmpty())
return true;
return false;
}
}
Merge two ordered linked lists
Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4] output: [1,1,2,3,4,4] example 2:
Input: l1 = [], l2 = [] output: [] example 3:
Input: l1 = [], l2 = [0] output: [0]
What we should pay attention to here is that
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
This is the definition of the linked list they give. You must give an element value first.
class Solution6 {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode res = new ListNode(0);
ListNode cur = res;
while (list1!=null && list2!=null){
if(list1.val > list2.val){
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
else {
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}
}
if(list1==null){
cur.next = list2;
}
else {
cur.next = list1;
}
return res.next;
}
}
Here, we adopt the strategy of sacrificing space, which can still be optimized. We can choose to directly merge the two into list1 or list2, and operate directly on list1, but it is not easy to understand. We can directly use recursion, but I think it consumes a lot of energy.
Longest Common Prefix
This topic is very simple, but I didn't pay attention to it when I wrote it. I always couldn't pass it. Then I checked it, but I found that the standard code given has a logic problem, although it can pass the test set.
Title:
Write a function to find the longest common prefix in a string array.
Returns the empty string '' if there is no public prefix.
Example 1:
Input: strs = ["flower", "flow", "flight"] output: "fl" example 2:
Input: strs = ["dog", "racecar", "car"] output: "" explanation: the input does not have a public prefix.
Let's take a look at the standard code first
class Solution {
public String longestCommonPrefix(String[] strs)
{
if (strs == null || strs.length == 0)
{
return "";
}
String prefix = strs[0];
int count = strs.length;
for (int i = 1; i < count; i++)
{
prefix = longestCommonPrefix(prefix, strs[i]);
if (prefix.length() == 0)
{
break;
}
}
return prefix;
}
public String longestCommonPrefix(String str1, String str2) {
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index)== str2.charAt(index))
{
index++;
}
return str1.substring(0, index);
}
}
Find out what he is. He takes out the first word and compares it with the rest of the words, that is, execution
longestCommonPrefix(), but about this function, you can see what it does. It is to compare the common points in front of two words, then return the common prefix between the two words, and then return it to prefix. The problem comes. Suppose there are three words, the prefix of the first and second words is ab, and the first and third words are abc. The first strs[1] prefix is ab, the second strs[2] prefix is abc, and then the loop ends. At this time, the prefix is abc. The problem comes. Obviously, the prefix in the three words should be AB, not abc. But I don't know why this code can pass the test set!!!
ok, let's take a look at my code
class Solution {
public String longestCommonPrefix(String[] strs) {
String firstworld = strs[0];
String answer = "";
int index = 0;
boolean flag = true;
out:for(int i = 0;i<firstworld.length();i++){
char c = firstworld.charAt(i);
for(int j=1;j<strs.length;j++){
if(i>=strs[j].length()){
break out;
}
else {
if(c !=strs[j].charAt(i) )
flag = false;
}
}
if(flag)
index ++;
}
answer = firstworld.substring(0,index);
return answer;
}
}
The idea is the same. Take out the first word, but I directly compare the first letter of the first word with the letters in the corresponding position of the remaining words. Once the compared alphanumeric exceeds the length of the current word, it means that the whole word is the longest prefix. If not, I find that the current letter is not right, Then all the preceding are the same prefix.
Of course, you can also scan in another way, mainly words.