Summary of simple topics

The longest public substring

class Solution {
    
    public String longestCommonPrefix(String[] strs) {
    
        if(strs.length == 0) 
            return "";
        String ans = strs[0];  // Treat the first string as ans
        for(int i =1;i<strs.length;i++) {
    
            int j=0;
            // See how many elements in the two character erasure strings are the same , If it's different, it's up to the cycle 
            // At the end of the loop ,j Not included . So it doesn't include the second j An element of 
            for(;j<ans.length() && j < strs[i].length();j++) {
    
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);  // What comes out here is 0-j,j not 
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

Valid parenthesis

        public static boolean isValid(String s){
    
        if(s.isEmpty()){
    
            return true;
        }
        Stack<Character> stack = new Stack<Character>(); 
        // More ingenious , stay c When left parenthesis , Press the corresponding right bracket into stack.
        // stay c When it is a right bracket , eject stack, See if c.
        for(char c:s.toCharArray()){
    
            if(c == '('){
    
                stack.push(')');
            }
            else if(c == '['){
    
                stack.push(']');
            }
            else if(c == '{'){
    
                stack.push('}');
            } // stay c When it's a closing bracket , Directly pop up stack, See if it's with c equal 
            else if(stack.empty() || c!=stack.pop()){
       
                return false;
            }
        }
        if(stack.empty()){
    
            return true;
        }
        return false;			// Other situations are directly judged as false
    }
}

Merge two ordered lists

// There are three main things here : l1 l2 cur,  Just position these three things .
//l1 It is the anchor point of the first linked list 
//l2 It is the anchor point of the second linked list 
class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        //  Similar to the merge process in merge sort 
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
    
            if (l1.val < l2.val) {
    
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
    
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        
        //  Any one is empty , Connect another list directly 
        if (l1 == null) {
    
            cur.next = l2;
        } 
        if (l2 == null) {
    
            cur.next = l1;
        }
        return dummyHead.next; 
          
        //dummyHead It's not a head node , Its next node is the head node we need 
    }

Remove duplicates from ordered arrays

class Solution {
    
    public int removeDuplicates(int[] nums) {
    
        int len = nums.length;
        int j=0;
        for(int i=1; i<nums.length; i++){
    
            if(nums[i-1]==nums[i]){
    
                len--;    
            }
            else{
    
                nums[++j] = nums[i];
            }
        }
        return len;
    }
}

// Using double pointer method 
 public int removeDuplicates(int[] nums) {
    
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
    
        if(nums[p] != nums[q]){
    
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}

Remove elements

class Solution {
    
    public int removeElement(int[] nums, int val) {
    
        int j=-1;
        for(int i=0; i<nums.length; i++){
    
            if(nums[i]!=val){
    
                nums[++j] = nums[i];
            }
        }
        return j+1;

    }
}

Search insert location

public int searchInsert(int[] nums, int target) {
    
    for(int i = 0; i < nums.length;i++){
    
        if(nums[i] >= target){
    
            return i;
        }
    }
    return nums.length;
}

Maximum array sum

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
    
     // The previous gain is a positive gain for now , Take the present num Plus the previous positive gain 
            if(sum > 0) {
    	
                sum += num;
            } 
     // The previous gain is a negative gain for now , Just don't let the previous negative gain , Only need to sum Update to the current num Just go  
            else {
    
                sum = num;
            }
            ans = Math.max(ans, sum); // Compare the size , if sum It gets bigger after changes , Update the maximum value 
        }
        return ans;
    }
}

The length of the longest string

class Solution{
    
    public int lengthOfLastWord(String s) {
    
        char[] ch = s.toCharArray();
        int temp = 0;
        for(int i=0; i<ch.length; i++){
    
            if(ch[i]==' '){
     // At the last string , take temp Turn into 0
                temp = 0;
            }   
            temp++;
        }
        return temp-1;
    }
}

Only once

// XOR operation is simple 
class Solution {
    
     public int singleNumber(int[] nums) {
    
         int ans=0;
        for(int i=0;i<nums.length;i++){
    
            ans^=nums[i];   // Exclusive or operation 
        }
        return ans;
    }
}

climb stairs

class Solution {
    
    public int climbStairs(int n) {
    
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
    
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Delete duplicate elements from the sort list

class Solution {
    
    public ListNode deleteDuplicates(ListNode head) {
    
        ListNode temp = head;
        while(temp != null && temp.next != null){
    
            if(temp.val == temp.next.val){
    	
                temp.next = temp.next.next;	// This step is the most error prone place , Change linked list temp The direction of , Not change temp Location of nodes . intend , So you go through this temp The position of is unchanged .
            }
            else{
    
                temp = temp.next;
            }   
        }
        return head;
    }
}

Reverse a linked list

// Use the iterative method , Continuous iteration . Until we reach the final destination .
    public static ListNode reverseListIterative(ListNode head) {
    
        ListNode prev = null; // Front pointer node 
        ListNode curr = head; // Current pointer node 
        // Each cycle , Point the current node to the node in front of it , Then the current node and the previous node move back 
        while (curr != null) {
    
            ListNode nextTemp = curr.next; // Temporary node , Staging the next node of the current node , Used to move back 
            curr.next = prev; // Point the current node to the node in front of it 
            prev = curr; // The front pointer moves back 
            curr = nextTemp; // The current pointer moves back 
        }
        return prev;
    }

Merge two ordered arrays

class Solution {
    
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
    
            if (p1 == m) {
    
                cur = nums2[p2++];		// The first array is full , Add the second one , Last p2 One more 
            } else if (p2 == n) {
    
                cur = nums1[p1++];      // The second array is full , Add in the first one , Last p1 One more 
            } else if (nums1[p1] < nums2[p2]) {
    
                cur = nums1[p1++];		// In this case , take P1 Add in , Last p1 One more 
            } else {
    
                cur = nums2[p2++];		// In this case , take p2 Add in , Last p2 One more 
            }
            sorted[p1 + p2 - 1] = cur;	// Add the value of the corresponding array 
        }
        for (int i = 0; i != m + n; ++i) {
    
            nums1[i] = sorted[i];		// According to the title , Will all 
        }
    }
}