Rehabilitation type force deduction brush question notes D2

Catalog

Code section

topic 9

topic 13

topic 14

topic 20

topic 4

  topic 21

topic 15

java Small knowledge part

topic 9

topic 13

topic 14

topic 20

topic 4

topic 15

---

Code section

topic 9

9. Palindrome number

The difficulty is simple 1746 Switch to English to receive dynamic feedback

Give you an integer  x , If  x  Is a palindrome integer , return  true ; otherwise , return  false .

Palindrome number refers to positive order （ From left to right ） Reverse order （ From right to left ） Read all the same integers . for example ,121  It's palindrome. , and  123  No .

         Refer to the comments for revised code ：

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        else if (x == 0) return true;
        else
        {
            int xorigion = x;
            int X = 0;
            while (x != 0)
            {
                X = X * 10 + x % 10;
                x = x / 10;                  
            }
            if(X == xorigion) return true;
            else return false;
        }
    }
}

        First, judge the special situation . For the rest , Through one while Loop to get his palindrome number . Finally, judge return.

topic 13

13. Roman numeral to integer

The difficulty is simple 1641 Switch to English to receive dynamic feedback

Roman numerals contain the following seven characters : I, V, X, L,C,D  and  M.

 character            The number 
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

for example , Rome digital  2  Write to do  II , Two parallel 1 .12  Write to do  XII , That is to say  X + II . 27  Write to do   XXVII, That is to say  XX + V + II .

Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write  IIII, It is  IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as  IX. This special rule only applies to the following six cases ：

• I  Can be placed in  V (5) and  X (10) Left side , To express 4 and 9.
• X  Can be placed in  L (50) and  C (100) Left side , To express 40 and  90. 
• C  Can be placed in  D (500) and  M (1000) Left side , To express  400 and  900.

Given a Roman number , Convert it to an integer .

        Own code , A little longer , But time 100%, Memory 95%：

class Solution {
    public int romanToInt(String s) {
        char [] S = s.toCharArray();
        int res = 0;
        for(int i = 0 ; i < S.length ; i ++)
        {
            if((i+1)< S.length)
            {
                if(S[i] == 'I')
                {
                    if(S[i+1] != 'V' && S[i+1] != 'X')
                    {
                        res += 1;
                    }
                    else if(S[i+1] == 'V')
                    {
                        res += 4;
                        i ++;
                    }
                    else if(S[i+1] == 'X')
                    {
                        res += 9;
                        i ++;
                    }
                }
                else if(S[i] == 'X')
                {
                    if(S[i+1] != 'L' && S[i+1] != 'C')
                    {
                        res += 10;
                    }
                    else if(S[i+1] == 'L')
                    {
                        res += 40;
                        i ++;
                    }
                    else if(S[i+1] == 'C')
                    {
                        res += 90;
                        i ++;
                    }
                }
                else if(S[i] == 'C')
                {
                    if(S[i+1] != 'D' && S[i+1] != 'M')
                    {
                        res += 100;
                    }
                    else if(S[i+1] == 'D')
                    {
                        res += 400;
                        i ++;
                    }
                    else if(S[i+1] == 'M')
                    {
                        res += 900;
                        i ++;
                    }
                }
                else if(S[i] == 'V') res += 5;
                else if(S[i] == 'L') res += 50;
                else if(S[i] == 'D') res += 500;
                else if(S[i] == 'M') res += 1000;
                }
            else
            {
                if(S[i] == 'I') res +=1;
                else if(S[i] == 'V') res += 5;
                else if(S[i] == 'X') res += 10;
                else if(S[i] == 'L') res += 50;
                else if(S[i] == 'C') res += 100;
                else if(S[i] == 'D') res += 500;
                else if(S[i] == 'M') res += 1000;
            }
        }
        return res;
    }
}

        The idea of compiling principle is applied , First judge the characters in two groups （IV,IX,XL,XC,CD,CM）, Then judge a single character .

topic 14

14. The longest common prefix

The difficulty is simple 1950 Switch to English to receive dynamic feedback

Write a function to find the longest common prefix in the string array .

If no common prefix exists , Returns an empty string  "".

        After repairing the violent recursive code several times ：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int len = strs.length ;
        String res;
        if(len == 0) return "";
        if(len == 1) return strs[0];
        if(strs[0].length() == 0) return "";

        char [] string1 , string2 , nextarray;
        string1 = strs[0].toCharArray();
        string2 = strs[1].toCharArray();
        nextarray = new char[200];
        for(int i = 0 ; i < 200 ; i++)
        {
            nextarray[i] = 'A';
        }
        int i = 0;
        while(i < string1.length && i < string2.length && string1[i] == string2[i])
        {
            nextarray[i] = string1[i];
            i ++;
        }
        String nextstring = new String(nextarray);
        String [] tonext = new String[len-1];
        tonext[0] = nextstring;
        for(int j = 1 ; j < len -1 ; j ++)
        {
            tonext[j] = strs[j+1];
        }
        if(len == 2) 
        {
            i = 0;
            while(nextarray[i] != 'A') i ++;
            nextstring = nextstring.substring(0,i);
            return nextstring;
        }
        res = longestCommonPrefix(tonext);

        return res;
    }
}

        First judge the special situation . Convert the first two strings to an array , Declaration initialization char Array nextarray Used to store prefix . Find the longest prefix of the first two strings , Deposit in nextarray Array . Declaration string nextstring take nextarray Array to string , take nextstring The string and the remaining strings are stored in the string array tonext.

        Judge if there are only two strings , be return The current longest prefix .

        Progressive recursion .

topic 20

20. Valid parenthesis

The difficulty is simple 2873 Switch to English to receive dynamic feedback

Given one only includes  '(',')','{','}','[',']'  String  s , Determines whether the string is valid .

Valid string needs to meet ：

1. Opening parentheses must be closed with closing parentheses of the same type .
2. The left parenthesis must be closed in the correct order .

        My code is as follows , Use the stack to solve ：

class Solution {
    public boolean isValid(String s) {
        char[] S = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0 ; i < S.length ; i++)
        {
            if(S[i] == '(') stack.push(')');
            else if(S[i] == '[') stack.push(']');
            else if(S[i] == '{') stack.push('}');
            else
            {
                if(stack.isEmpty() == true) return false;
                else if(S[i] != stack.pop()) return false;
            }
        }
        if(stack.isEmpty()) return true;
        else return false;
    }
}

        For each preceding bracket （(,[,{）, Stack the other half of its corresponding bracket , This can reduce the number of judgments during stack comparison .

topic 4

4. Find the median of two positive arrays

Difficulty 4849 Switch to English to receive dynamic feedback

Given two sizes, they are  m  and  n  Positive order of （ From small to large ） Array  nums1  and  nums2. Please find and return the values of these two positive ordered arrays   Median  .

The time complexity of the algorithm should be  O(log (m+n)) .

        My code is as follows , It's too long , There is much room for improvement ：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 , len2;
        len1 = nums1.length;
        len2 = nums2.length;
        int flag1 = (len1+len2)/2;;
        int med1 = 0 , med2 = 0;
        double med11 ,med22 , med = 0;
        if(len1 == 0 && len2 ==0) return med;
        if((len1+len2)%2 == 0) // even numbers 
        {
            int i1 = 0 , i2 = 0;
            for(int i = flag1 ; i >= 0 ; i--)
            {
                if(i != 0)
                {
                    if(i1 == len1)
                    {
                        med1 = nums2[i2];
                        i2 ++;
                    }
                    else if(i2 == len2)
                    {
                        med1 = nums1[i1];
                        i1 ++;
                    }
                    else if(nums1[i1] > nums2[i2])
                    {
                        med1 = nums2[i2];
                        i2 ++;
                    }
                    else if(nums1[i1] <= nums2[i2])
                    {
                        med1 = nums1[i1];
                        i1 ++;
                    }
                }
                else if(i == 0)
                {
                    if(i1 == len1)
                    {
                        med2 = nums2[i2];
                        i2 ++;
                    }
                    else if(i2 == len2)
                    {
                        med2 = nums1[i1];
                        i1 ++;
                    }
                    else if(nums1[i1] > nums2[i2])
                    {
                        med2 = nums2[i2];
                        i2 ++;
                    }
                    else if(nums1[i1] <= nums2[i2])
                    {
                        med2 = nums1[i1];
                        i1 ++;
                    }
                }
            }
            med11 = (double)med1;
            med22 = (double)med2;
            med = (med11 + med22) / 2;
        }
        else // Odd number 
        {
            int i1 = 0 , i2 = 0;
            for(int i = flag1 ; i >= 0 ; i--)
            {
                if(i1 == len1)
                {
                    med = nums2[i2];
                    i2 ++;
                }
                else if(i2 == len2)
                {
                    med = nums1[i1];
                    i1 ++;
                }
                else if(nums1[i1] > nums2[i2])
                {
                    med = nums2[i2];
                    i2 ++;
                }
                else if(nums1[i1] <= nums2[i2])
                {
                    med = nums1[i1];
                    i1 ++;
                }
            }
        }
        return med;
    }
}

        First judge the special situation . Determine whether the sum of the lengths of the two arrays is even or odd , And calculate separately . Even numbers need to take the middle two numbers to average , Odd numbers need to take the middle number , That is, even numbers need to be taken Small numbers and Small number , And odd numbers need to be taken Small number . adopt for Get the number of cycles , In the cycle, it is necessary to first judge the boundary crossing .

  topic 21

21. Merge two ordered lists

The difficulty is simple 2129 Switch to English to receive dynamic feedback

Merge two ascending linked lists into a new   Ascending   Link list and return . The new linked list is made up of all the nodes of the given two linked lists . 

        Own code ：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){return list2;}
        if(list2 == null){return list1;}
        ListNode root = new ListNode();
        ListNode res = root;
        while(list1 != null && list2 != null)
        {
            if(list1.val <= list2.val)
            {
                res.next = list1;
                res = res.next;
                list1 = list1.next;
            }
            else
            {
                res.next = list2;
                res = res.next;
                list2 = list2.next;
            }
        }
        if(list1 == null && list2 != null)
        {
            res.next = list2;
        }
        else if(list2 == null && list1 != null)
        {
            res.next = list1;
        }
        return root.next;

    }
}

        First judge the special situation . Judge the original linked list val value , And connect the smaller node to the target linked list . If one is used up , Just connect the other one directly .

topic 15

15. Sum of three numbers

Medium difficulty 4161 Switch to English to receive dynamic feedback

Give you one containing  n  Array of integers  nums, Judge  nums  Are there three elements in  a,b,c , bring  a + b + c = 0 ？ Please find out all and for  0  Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

        Learn from the modified code ：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        int a , b , c , j , k;
        if(len < 3) {return res;}
        if(len == 3 && nums[0]+nums[1]+nums[2] != 0) {return res;}
        if(len == 3 && nums[0]+nums[1]+nums[2] == 0) 
        {
            res.add(Arrays.asList(nums[0],nums[1],nums[2]));
            return res;
        }
        Arrays.sort(nums);
        for(int i = 0 ; i < len ; i++)
        {
            if(nums[i] > 0) {return res;}
            if(i > 0 && nums[i] == nums[i-1]) {continue;}
            a = nums[i];
            j = i + 1;
            k = len -1;
            while(j < k)
            {
                b = nums[j];
                c = nums[k];
                if(a + b + c == 0)
                {
                    res.add(Arrays.asList(a,b,c));
                    j ++;
                    k --;
                    while(j < k && j > i + 1 && nums[j] == nums[j-1]) {j ++;}
                    while(j < k && k < len -1 && nums[k] == nums[k+1]) {k --;}
                }
                else if(a + b + c > 0) {k--;}
                else if(a + b + c < 0) {j++;}
            }
        }
        return res;
    }
}

         First judge the special situation . Sort the array first . Use for Cycle are nums[i] The order of traversal , Judge out the special situation . Use j,k To locate i The following array part , And point to the beginning and end of this part respectively . utilize while Cycle guarantee j Always in k Before . Judge whether the sum of the three equals 0, And according to and 0 Relationship adjustment j,k Location .

        Add judgment to prevent repeated fetching .

java Small knowledge part

topic 9

        If there are special circumstances, judge first .

topic 13

        For arrays 、 The linked list should judge whether it is out of bounds .

        +=,-= Connecting is an operator , No space is allowed in the middle .

topic 14

        The length of the array is .length, The string length is .length().

         String truncation with ：

nextstring = nextstring.substring(0,i);

topic 20

        Stack operations ：

Stack<Character> stack = new Stack<Character>(); // Declaration of stack 
stack.push(')'); // Push 
stack.isEmpty() // Out of the stack 
stack.pop() // Judge stack empty 

topic 4

        if In the judgment, judge the situation of crossing the boundary first, and then judge other situations .

topic 15

        data type List, Meaning for List from List form , Inner layer List from int form .

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

          How to add new data ：

res.add(Arrays.asList(nums[0],nums[1],nums[2]));

        Sorting method ：

Arrays.sort(nums);