Force buckle day32

540、 A single element in an ordered array  

Give you an ordered array of integers only , among Each element appears twice , Only one number will appear once . Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once . The solution you designed Must satisfy  O(log n)  Time complexity and  O(1)  Spatial complexity .

  Topic analysis ：1. Ordered array 2. The time complexity is O(logn）———— Two points search

Through the example, it can be found that ： The subscript of a single number must be even .

class Solution {
    public int singleNonDuplicate(int[] nums) {
        // The subscript of a single number must be even 
        int left=0,right=nums.length-1;
        while(left<right){       //left<=right  The array index range will be exceeded 
            int mid=left+(right-left)/2;
            if(nums[mid]==nums[mid-1]){// The midpoint is equal to the one on the left 
                if((mid-left)%2==0){//mid There are even elements on the left of , The subscript of a single number is even , It shows that a single number may exist here 
                    right=mid-2;//-2 Is to exclude nums[mid-1] This element , because nums[mid]==nums[mid-1]
                }else{
                    left=mid+1;// If mid There are only an odd number of elements on the left , Then go directly to the other side to find 
                }
            }else if(nums[mid]==nums[mid+1]){// The midpoint is equal to the one on the right 
                if((right-mid)%2==0){//mid There are even elements on the right of , It shows that a single number may exist here 
                    left=mid+2;//+2 Is to exclude nums[mid+1] This element , because nums[mid]=nums[mid+1]
                }else{
                    right=mid-1;
                }
            }else{
                return nums[mid];
            }
        }
        return nums[left];
    }
}

541、 Reverse string II

Given a string  s  And an integer  k, From the beginning of the string , Each count to  2k  Characters , Just reverse this  2k  The first... In the character  k  Characters .

• If the remaining characters are less than  k  individual , Reverse all remaining characters .
• If the remaining characters are less than  2k  But greater than or equal to  k  individual , Before reversal  k  Characters , The rest of the characters remain the same .

1. The character inversion of the string is to convert the string into an array

2. From the beginning of the string , Each count to  2k  Characters , Just reverse this  2k  The first... In the character  k  Characters . Use the following for Circular thinking , Do not use

int count=1;
for(int i=0;i<2*k;i++){
    if(count==2*k){
        sb.reverse();
    }
    count=count*2;
    sb.append(s.charAt(i));
}

Use this idea ==>for (int i = 0; i < n; i =i + 2 * k) {          // Learn this for loop
                                    reverse(arr, i, Math.min(i + k, n) - 1);
                           }

3. there Math.min It's to judge     If the remaining characters are less than  k  individual , Reverse all remaining characters .

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i =i + 2 * k) {// Learn this for loop 
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

543、 The diameter of a binary tree

Given a binary tree , You need to calculate its diameter and length . Two branches of a tree Diameter length Is one of the path lengths of any two nodes Maximum . This path may or may not pass through the root node .

The longest diameter of the binary tree is 4-2-1-3/5-2-1-3

  The longest diameter of the binary tree can be 8-7-5-2-1-3  return 5

  namely ： The maximum depth of the left and right nodes , The longest diameter is added together

If maxLength Function termination condition 3 The return is return max; because max Depending on left+right, If return max, that right and left As long as there is recursion , They have been changing （ It's changing all the time ）【 Example ：4 Of left=1,9 Of left=0, So free return left=1, Then it becomes left=0 了 】 that max And it's changing all the time . Should be

return Math.max(left,right)+1, use max To hold the left and right The length of , such max It will be fixed .

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max=0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        maxLength(root);
        return max;
    }
    public int maxLength(TreeNode root){
        if(root==null) return 0;// Termination conditions 1
        if(root.left==null&root.right==null) return 1;// Termination conditions 2
        // Recursion of single-layer logic , When you end recursion ,return Termination conditions 2,3 Can be used .
        // If the termination condition 3 Of return yes  return max, It would be wrong . Outside say 
        int left=maxLength(root.left);
        int right=maxLength(root.right);
        max=Math.max(left+right,max);
        return Math.max(left,right)+1;// Termination conditions 3


    }
}