<>2019.7.15～2019.7.19 leetcode Summary of writing questions
1 Sum of two numbers (#2)
Title Description ：
Given an array of integers nums And a target value
target, Please find the two integers in the array whose sum is the target value , 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 .
Thinking of problem solving ：
The conventional idea of violent traversal is not considered , The time complexity is O(n^2), The better way to solve this problem is to use hash table , The time complexity is O(n),
First, create a hash table , Then traverse the array , Set the current value to temp, When the hash table does not exist target-temp Of key Value , Stores the current value in the hash table , If it exists , The result is returned .
code ：
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new
HashMap<>(); for (int i = 0; i < nums.length; i++) { int temp = target -
nums[i]; if (map.containsKey(temp)) { return new int[]{map.get(temp), i}; }
else { map.put(nums[i], i); } } return new int[2]; }
2 Longest substring without repeating characters （#3）
Title Description ：
Given a string , Please find out which one does not contain repeated characters Longest string Length of .
Thinking of problem solving ：
It's not clear , Follow up supplement
code ：
public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); 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; }
3 Find the median of two ordered arrays （#4）
Title Description ：
Given two sizes as m and n Ordered array of nums1 and nums2.
Please find out the median of these two ordered arrays , And the time complexity of the algorithm is required to be O(log(m + n)).
You can assume that nums1 and nums2 It will not be empty at the same time .
Thinking of problem solving ：
The conventional method is to merge two arrays , Then find the median , But the time complexity of this method is 0 O(m+n), The spatial complexity is also 0 O(m+n), Does not meet the requirements of the topic , So consider the idea of dichotomy ,
code ：
public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length; int
n = B.length; if (m > n) { // to ensure m<=n int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp; } int iMin = 0, iMax = m, halfLen = (m + n + 1) /
2; while (iMin <= iMax) { int i = (iMin + iMax) / 2; int j = halfLen - i; if (i
< iMax && B[j-1] > A[i]){ iMin = i + 1; // i is too small } else if (i > iMin
&& A[i-1] > B[j]) { iMax = i - 1; // i is too big } else { // i is perfect int
maxLeft = 0; if (i == 0) { maxLeft = B[j-1]; } else if (j == 0) { maxLeft =
A[i-1]; } else { maxLeft = Math.max(A[i-1], B[j-1]); } if ( (m + n) % 2 == 1 )
{ return maxLeft; } int minRight = 0; if (i == m) { minRight = B[j]; } else if
(j == n) { minRight = A[i]; } else { minRight = Math.min(B[j], A[i]); } return
(maxLeft + minRight) / 2.0; } } return 0.0; }
4 Palindrome number （#9）
Title Description ：
Determine whether an integer is a palindrome number . Palindrome number refers to positive order （ From left to right ） And the reverse order （ Right to left ） Read all the same integers .
Thinking of problem solving ：
The general idea is to apply for two pointers , A pointer to the head of a number , One points to the tail , Compare head to tail , If the same, the head and tail pointer move one bit to the middle together , But this algorithm needs to convert numbers into strings or arrays , Extra space is needed . Another solution is to reverse the second half of the number , If equal to the first half , Then change the number to palindrome number .
code ：
public boolean isPalindrome(int x) { // x Is negative or the last digit is 0, It must not be palindrome if (x < 0 || (x
!= 0 && x % 10 == 0)) { return false; } int reverse = 0; while (x > reverse) {
reverse = reverse * 10 + x % 10; x /= 10; } // distinguish x If the length of is odd or even return x == reverse
|| x == reverse / 10; }
5 Merge two ordered linked lists （#21）
Title Description ：
Merge two ordered linked lists into a new ordered linked list and return . The new linked list is composed of all nodes of two given linked lists .
Thinking of problem solving ：
Classic topic , It's relatively simple
code ：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new
ListNode(0); ListNode temp = head; while (l1 != null && l2 != null) { if
(l1.val < l2.val) { head.next = l1; l1 = l1.next; head = head.next; } else {
head.next = l2; l2 = l2.next; head = head.next; } } if (l1 != null) { head.next
= l1; } if (l2 != null) { head.next = l2; } return temp.next; }
6 Remove duplicate items from sorted array （#26）
Title Description ：
Given a sort array , You need to remove duplicate elements in place , Make each element appear only once , Returns the new length of the array after removal . Do not use extra array space , You have to modify the input array in place and use the
O(1) Complete under the condition of extra space .
Thinking of problem solving ：
Because there is no extra space , So use two pointers , One j Points to the current element , One i Points to the previous element , If the current element is equal to the previous element , be j+1, If the current element is not equal to the previous element , be i+1, And assign the current element to the i+1 Elements of position .
code ：
public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int
i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++;
nums[i] = nums[j]; } } return i + 1; }
7 Removing Elements （#27）
Title Description ：
Give an array nums And a value val, You need to remove all values equal to val Elements of , Returns the new length of the array after removal .
Do not use extra array space , You have to modify the input array in place and use the O(1) Complete under the condition of extra space .
The order of the elements can be changed . You don't need to consider elements in the array that are beyond the new length .
Thinking of problem solving ：
The solution to the above problem is basically the same
code ：
public int removeElement(int[] nums, int val) { int i = 0; for (int j = 0; j <
nums.length; j++) { if (nums[j] != val) { nums[i] = nums[j]; i++; } } return i;
}
8 Delete the penultimate of the linked list N Nodes （#19）
Title Description ：
Given a linked list , Delete the penultimate of the linked list n Nodes , And return the head node of the linked list .
Thinking of problem solving ：
Classic ideas , Set two pointers p1,p2, When p2 From the beginning n Step back ,p1 Start following p2 went together , When p2 At the end of the journey ,p1 It's in the bottom n Locations .
code
public ListNode removeNthFromEnd(ListNode head, int n) { if (head.next ==
null) { return null; } ListNode temp = head; ListNode lastN = head; ListNode
res = lastN; int i = 1; while (temp != null) { temp = temp.next; if (i <= n +
1) { i++; } else { lastN = lastN.next; } } if (i == n + 1) { return head.next;
} if (lastN.next != null) { lastN.next = lastN.next.next; } else { lastN.next =
null; } return res; }
9 climb stairs （#70）
Title Description ：
Suppose you are climbing stairs . need n You can't get to the top of the building .
Every time you can climb 1 or 2 Steps . How many different ways can you climb to the top of a building ?
be careful ： given n Is a positive integer .
Thinking of problem solving ：
Classical dynamic programming problem , To get to the No n There are only two possibilities for a staircase , from n-1 Step jump 1 Step to n rank , Or from n-2 Step jump 2 Step to n rank , Then climb to No n The number of steps is equal to climbing to the first n-1 The number of methods to climb to the n-2 Number of methods of order , Namely f(n)=f(n-1)+f(n-2), At the same time, the initial value is considered , Namely n=1 Time ,f(1)
= 1, n=2 Time ,f(2) = 2. Is it very similar to the math problems you did in high school , ha-ha , Programming is mathematics .
code ：
public int climbStairs(int n) { if (n == 1) { return 1; } if (n == 2) { return
2; } int a = 1; int b = 2; int c = 0; for (int i = 3; i <= n; i++) { c = a + b;
a = b; b = c; } return c; }
10 Merge two ordered arrays （#88）
Title Description ：
Given two arrays of ordered integers nums1 and nums2, take nums2 merge to nums1 in , bring num1 Become an ordered array .
explain :
initialization nums1 and nums2 The number of elements is m and n.
You can assume that nums1 There is enough space （ Space size greater than or equal to m + n） To save nums2 Elements in .
Thinking of problem solving ：
Similar to the idea of merging ordered arrays above
code ：
public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int
j = n - 1; int q = m + n - 1; while (i >= 0 && j >= 0) { nums1[q--] = nums1[i]
> nums2[j] ? nums1[i--] : nums2[j--]; } while (i >= 0) { nums1[q--] =
nums1[i--]; } while (j >= 0) { nums1[q--] = nums2[j--]; } }
11 Constructing binary tree from middle order and post order traversal sequences （#106）
Title Description ：
According to the middle order traversal and post order traversal of a tree, a binary tree is constructed .
be careful :
You can assume that there are no duplicate elements in the tree .
Thinking of problem solving ：
Because the last number of the post order traversal sequence is the value of the root node of the binary tree , meanwhile , In order traversal, the root node is in the middle , And its left part is the left subtree of the root node , The right part is the right subtree of the root node , Except for the last root node in the post order sequence , The left part is left subtree , The right part is the right subtree , Then each part recurs , The binary tree can be constructed .
code ：
public TreeNode buildTree(int[] inorder, int[] postorder) { return
build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); }
public TreeNode build(int[] in, int inBegin, int inEnd, int[] post, int
postBegin, int postEnd) { if (inBegin > inEnd || postBegin > postEnd) { return
null; } int headVal = post[postEnd]; TreeNode head = new TreeNode(headVal); for
(int i = inBegin; i <= inEnd; i++) { if (in[i] == headVal) { head.left =
build(in, inBegin, i - 1, post, postBegin, i - inBegin + postBegin - 1);
head.right = build(in, i + 1, inEnd, post, i - inBegin + postBegin, postEnd -
1); } } return head; }
12 Effective letter heterotopic words （#242）
Title Description ：
Given two strings s and t , Write a function to judge t Is it s The letter ectopic words of .
explain :
You can assume that the string contains only lowercase letters .
Thinking of problem solving ：
It can be seen from the meaning of the title , Hash table can be used to solve this problem , Because it's supposed to be all lowercase letters , Therefore, only one length of 26 Character array of , meanwhile , Because the length of two strings is equal （ If they are not equal, they cannot be heterotopic words ）, When traversing , character string s The corresponding position of the character in the array +1, character string t The corresponding position of the character in the array -1.
After traversing , If two t yes s The letter ectopic words of , Then the value of each position in the array is 0, Otherwise, they are not heterotopic words .
code ：
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) {
return false; } int[] counter = new int[26]; for (int i = 0; i < s.length();
i++) { counter[s.charAt(i) - 'a']++; counter[t.charAt(i) - 'a']--; } for (int a
: counter) { if (a != 0) { return false; } } return true; }
13 3 Power of (326#)
Title Description ：
Give an integer , Write a function to determine if it is 3 To the power of .
Thinking of problem solving ：
It's relatively simple , Cyclic pair 3 You can get the remainder .
code ：
public boolean isPowerOfThree(int n) { if (n < 1) { return false; } while (n %
3 == 0) { n /= 3; } return n == 1; }
14 Odd even list （#328）
Title Description ：
Given a single linked list , Put all the odd and even nodes together . Please note that , The odd node and even node here refer to the parity of the node number , Rather than the parity of the node's values .
Please try using the in place algorithm . The spatial complexity of your algorithm should be O(1), The time complexity should be O(nodes),nodes Is the total number of nodes .
Thinking of problem solving ：
Create two linked lists , An odd node , A storage even node , Finally, even nodes can be connected after odd nodes .
code ：
public ListNode oddEvenList(ListNode head) { ListNode even = new ListNode(0);
ListNode evenTemp = even; ListNode odd = new ListNode(0); ListNode oddTemp =
odd; int i = 1; while (head != null) { if (i % 2 == 0) { even.next = head; even
= even.next; } else { odd.next = head; odd = odd.next; } head = head.next; i++;
} odd.next = evenTemp.next; even.next = null; return oddTemp.next; }
15 Add two numbers together （#2）
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 .
Thinking of problem solving ：
Pay attention to carry control
code ：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead =
new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0;
while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q !=
null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new
ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null)
q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return
dummyHead.next; } }
Technology