26. Delete new elements in the array

Given a sort array, you need to delete duplicate elements in place so that each element appears only once, returning the new length of the array after removal.

Do not use extra array space, you must modify the input array in place and do so with O(1) extra space.

Example 1:
Given array nums = [1,1,2],
The function should return a new length of 2, and the first two elements of the original array nums are modified to 1, 2.

Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
The function should return a new length of 5, and the first five elements of the original array nums are modified to 0, 1, 2, 3, 4.

class Solution {
    public int removeDuplicates(int[] nums) {
   //i refers to the number to be reserved;
   //j traversing the entire array
   int i = 0;
   for(int j = 1; j < nums.length; j++){
       if(nums[i] != nums[j]){
           i++;//Find the number you need to keep, move i back, make room
           nums[i] = nums[j];
       }
   }
   return i+1;
    }
}

633. Sum of squares

Given a non negative integer c, you need to determine whether there are two integers a and b, so that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:
Input: 3
Output: False

class Solution {
    public boolean judgeSquareSum(int c) {
     int i = 0;
     int j = (int) Math.sqrt(c);//Square root
     int target = 0;
     //When the sum of squares of two numbers is equal to 2, both i and j are equal to 1, indicating that i can be equal to J
     while(i<=j){
         target = i*i+j*j;
         if(target == c){
             return true;
         }else if(target < c){
             i++;
         }else{
             j--;
         }
     }
     return false;
    }
}

88. Merge two ordered arrays

Given two ordered integer arrays nums1 and nums2, nums2 is merged into nums1, making num1 an ordered array.

Explain:
The number of elements to initialize nums1 and nums2 is m and n, respectively.
You can assume that nums1 has enough space (space size greater than or equal to m + n) to hold the elements in nums2.

Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
       //Merge sort
       //Since the fill number is after nums1, it starts traversing from the back to the front
       int i1 = m-1;//Point to the end of nums1
       int i2 = n-1; //Point to the end of nums2
       int index = m+n-1;//Point to the end of the merged array

       while(i1>=0 && i2>= 0){
           //If nums1 is large, fill nums1
           if(nums1[i1] > nums2[i2]){
            nums1[index--] = nums1[i1--];
           }else{
               nums1[index--] = nums2[i2--];
           }
        
       }
       //If there is still an array not filled out;
       //If it's nums1, don't worry, because it's supposed to be filled with nums1;
       //If it's nums2, assign it all
       while(i2>=0){
           nums1[index--] = nums2[i2--];
       }
    }
}

141. Circular list

Given a link list, determine whether there are links in the link list.
In order to represent the links in a given linked list, we use the integer pos to represent the position where the end of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: there is a link in the list with the tail connected to the second node.

Idea: traverse. If null is encountered, it must not be a ring;
Traversal, if the previous duplicate node is encountered, it must be a ring.
Two solutions: fast and slow pointer; HashMap
Corresponding situation: fast and slow pointer, imagine that two athletes are running long distance on the playground, and will definitely meet at last.
HashMap think of athletes taking photos every few minutes of running. There must be two photos of repeated scenes at last

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //Head processing
        //Without nodes, a ring cannot be formed;
        //There is only one node, and it can't form a ring
        if(head == null || head.next == null)  return false;

        //Fast and slow pointer
        //Think about running on the playground,
        //If there is a ring, the fast pointer will run twice, and the slow pointer will run once, and they will meet
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
           //Now let the fast pointer go two steps
           //Slow pointer one step
           slow = slow.next;
           fast = fast.next.next;
           //If we meet, there is a ring
           if(slow == fast){
               return true;
           }
       }
       return false;      
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 //Thought: judge whether the link list has a ring or not;
 //Find the entrance to the ring
public class Solution {
    public ListNode detectCycle(ListNode head) {
      //First, carry out a self check on the linked list
      if(head == null || head.next == null){
          return null;
      }

      //Define a fast pointer, a slow pointer, and judge whether there is a ring or not
      //Two steps for fast pointer and one step for slow pointer
      //There are a nodes in front of the ring list entry, b nodes in the ring, and a+b nodes in the chain list
      //So when we meet, the fast pointer takes the s+nb step
      //fast is twice the number of slow steps, so f = s+nb = 2s
      //f = 2nb, s= nb, this is the number of steps taken by the two pointers at the first meeting
      //At this time, we want to know that the circular entrance, s has already taken nb steps, so we just need to let s take step a again and stop,
      //After walking through the list, he (s) comes out of the list port, which is the circular entrance
      //You can find out where the ring entrance is
      //We still use the method of double pointer. We define a pointer, start from the beginning, walk with step a of s, and they will meet again at the circular entrance
      //Because they've gone through the chain together
      ListNode fast = head;
      ListNode slow =head;
      boolean hascycle = false;
      while(fast!=null && fast.next != null){
          fast = fast.next.next;
          slow = slow.next;
          if(fast == slow){
              hascycle = true;
              break;
              //break is to jump out of the loop, in this topic, is to jump out of the if statement;
              //Continue is to jump out of this cycle, but the next cycle will continue
          }
      }
      //Define the third pointer. The place where the third pointer and slow pointer meet is the entrance of the ring 
      if(hascycle){
       ListNode third = head;
       while(slow != third){
           slow = slow.next;
           third = third.next;
       }
       return third;
      }
      return null;
}
}