hash
1. Sum of two numbers
The idea is to save it in the hash table first, and then judge whether it exists again. Use target -
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[]{-1,-1};
}
}
387. The first unique character in a string
The idea is to go through it directly, save the repeated number as false, and then the non repeated number is true. Just return the first one
class Solution {
public int firstUniqChar(String s) {
Map<Character,Boolean> map = new HashMap<>();
int index = 0;
for(int i = 0;i < s.length();i++){
map.put(s.charAt(i),!map.containsKey(s.charAt(i)));
}
for(int i = 0;i< s.length();i++){
if(map.get(s.charAt(i))) return i;
}
return -1;
}
}
Linked list operation
2. Add two numbers
The idea is to cycle to judge whether the current node is empty. If it is not empty, start adding value, and then remember to add carry. Divide the current number / 10 for each carry, and then move the three pointers back. Don't forget to take the remainder when adding the data
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode newhead = new ListNode(0);
ListNode tail = newhead;
int carry = 0;
while(l1!=null||l2!=null){
int x = l1 == null? 0:l1.val;
int y = l2 == null? 0:l2.val;
int temp = x + y +carry;
carry = temp / 10;
tail.next = new ListNode(temp % 10);
tail = tail.next;
if(l1!=null) l1 = l1.next;
if(l2!=null) l2 = l2.next;
}
return newhead.next;
}
}
19. Delete the penultimate node of the linked list
The most simple and easy to think of writing method is to directly calculate the length first, then reach the position according to the length, and then delete it!
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode newhead = new ListNode(0,head);
ListNode cur = newhead;
for(int i =0;i<getlen(newhead)-n;i++){
cur = cur.next;
}
cur.next = cur.next.next;
return newhead.next;
}
int getlen(ListNode node) {
int count = 0;
while (node.next != null) {
count++;
node = node.next;
}
return count;
}
}
61. Rotating linked list
The idea is to form a ring first. Note that you must first define a pointer, then disconnect the ring. Note that the position should take the remainder len-1 (because i + +), and finally disconnect the ring
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode cur = head;
int len = 1;
while(cur.next!=null){
len++;
cur = cur.next;
}
cur.next = head;
//We must pay attention here
int index = len - k % len -1;
ListNode newhead = head;
for(int i = 0;i< index;i++){
newhead = newhead.next;
}
ListNode res = newhead.next;
newhead.next = null;
return res;
}
}
138. Copy linked list with random pointer
The idea is to create a new node, fill the data in the back, and then put a hashtable to get it. As long as it has been saved, it will be retrieved directly
class Solution {
Map<Node,Node> hashtable = new HashMap<>();
public Node copyRandomList(Node head) {
if(head == null) return null;
if(hashtable.containsKey(head)) return hashtable.get(head);
Node node = new Node(head.val);
hashtable.put(head,node);
if(head.next!=null) node.next = copyRandomList(head.next);
if(head.random!=null) node.random = copyRandomList(head.random);
return node;
}
}
206. Reverse linked list
The iterative algorithm is the head insertion method, and the recursive algorithm is to pay attention to the value of the new node and the stop position
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode next = null;
while(cur!=null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
//The return here is 5, but it stops at 4
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
Double pointer traversal (sliding window)
The idea is to use two pointers to realize the sliding window, and then the first pointer uses the hash table to reach the place where there is no repetition, and then counts the maximum value each time, and then the next pointer starts to remove characters one by one
3. Longest substring without repeated characters
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int r = -1,len = s.length(),res = 0;
for(int i = 0;i < len;i++){
if(i != 0){
set.remove(s.charAt(i-1));
}
while(r+1<len && !set.contains(s.charAt(r+1))){
set.add(s.charAt(r+1));
r++;
}
res = Math.max(res,r - i + 1);
}
return res;
}
}
11. Container with the most water
The idea is to record the area each time, and then take the maximum value, and then move the pointer. The large one does not move, and the small one moves
class Solution {
public int maxArea(int[] height) {
int l = 0,r = height.length -1,res = 0;
while(l < r ){
int temp = Math.min(height[l],height[r])*(r - l);
res = Math.max(res,temp);
if(height[l]<height[r]){
l++;
}else{
r--;
}
}
return res;
}
}
26. Delete duplicates in ordered array
The idea is to use the fast and slow pointer. The fast pointer keeps running. If it is wrong, the slow pointer starts running, and then assigned to the slow pointer. Therefore, the index of the slow pointer is actually the length
class Solution {
//Fast and slow pointer
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int l = 0,r = 1;
while(r < nums.length){
if(nums[l]!=nums[r]) nums[++l] = nums[r];
r++;
}
return ++l;
}
}
121. The best time to buy and sell stocks
The idea is to determine the smallest day, and then stop the biggest day. Just count it directly
class Solution {
//The trick is to determine the minimum value
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE,max = 0;
for(int data : prices){
min = Math.min(min,data);
max = Math.max(max,data-min);
}
return max;
}
}
209. Minimum length subarray
The idea is similar to that of finding the longest substring without repeated characters, that is, stop every time you get big, let the left pointer move, and then record it yourself
class Solution {
//It's the same idea as the number of non repeated numbers in the previous statistical array, speed pointer
public int minSubArrayLen(int target, int[] nums) {
if(nums == null || nums.length == 0) return 0;
int l = 0,r = 0,res = 0,min = Integer.MAX_VALUE;
while( r < nums.length){
res += nums[r];
while(target <= res){
min = Math.min(min,r - l + 1);
res -= nums[l];
l++;
}
r++;
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}