LeetCode Numerical integer power/recursive multiplication [recursive]

LeetCode Numerical integer power/recursive multiplication [recursive]

This is the challenge I participated in more text on the 7th day, event details see: more text challenge

The integer power of the value (the sword refers to Offer 16)

Title description

Realize pow( x , n ) , that is, calculate the n-th power function of x (ie, xn). Do not use library functions, and do not need to consider the issue of large numbers.

Example 1:

Input: x = 2.00000, n = 10 Output: 1024.00000 Copy code

Example 2:

Input: x = 2.10000, n = 3 Output: 9.26100 Copy code

Example 3:

Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Copy code

prompt

  • -100.0 <x <100.0
  • -2^31 <= n <= 2^31-1
  • -10^4 <= xn <= 10^4

Thinking analysis

The problem requires that library functions cannot be used. We can consider using recursion to achieve this problem, because n has both positive and negative numbers. Consider the positive number first, when the positive number is odd,xn=x(n/2) x(n/2) x{x^n = x^(n/2) * x^(n/2) * x} , when it is an even numberxn=x(n/2) x(n/2){x^n = x^(n/2) * x^(n/2)} . In this way, we can decompose step by step until n = 0, pow = 1, as the termination condition.

Code display

Solution 1: The time complexity isO(logn){O(logn)} , the space complexity isO(1){O(1)} .

public double myPow ( double x, int n) { if (n >= 0 ){ return rPow(x,n); } else { return 1/(rPow(x,-(n + 1 )) * x); //The maximum value of an integer and the minimum value of a negative number are not symmetrical -231 <= n <= 231-1 } } public double rPow ( double x, int n) { if (n == 0 ){ return 1 ; } double rPow = rPow(x,n/2 ); if (n% 2 == 0 ){ return rPow * rPow; } else { return rPow * rPow * x; } } Copy code

Recursive Multiplication (Interview Question 08.05)

Title description

Recursive multiplication. Write a recursive function, without using the * operator, to achieve the multiplication of two positive integers. You can use plus, minus, and displacement, but be stingy.

Example 1:

Input: A = 1, B = 10 Output: 10 Copy code

Example 2:

Input: A = 3, B = 4 Output: 12 Copy code

prompt

  • Ensure that the multiplication range will not overflow

Thinking analysis

The title requires that we cannot use multiplication, and try to minimize the use of plus, minus, and displacement. Therefore, we should not write the way of adding a number that is recursively repeated. The local is the same as the integer number of the above. The square problem is very similar, but here is addition. When B is odd,A B=A (B/2) A (B/2) B{A * B = A * (B/2) * A * (B/2) * B} . When it is an even number,A B=A (B/2) A (B/2){A * B = A * (B/2) * A * (B/2)} . B keeps decreasing until B=1 as the termination condition. At the same time, there is a small optimization. Find the minimum value of A and B, and use the minimum value as the number of additions and the maximum value as the value of each addition, so that the number of additions will be reduced.

Code display

Solution 1: The time complexity isO(logn){O(logn)} , the space complexity isO(1){O(1)} .

public int multiply ( int A, int B) { //if (A == 1){ //return B; //} //int value = multiply(A/2,B); //if (A% 2 == 0){ //return value + value ; //} else { //return value + value + B; //} //optimize int max = Math.max(A,B); int min = Math.min(A,B); if (min == 1 ){ return max; } int value = multiply(min/2 ,max); if (min% 2 == 0 ){ return value + value; } else { return value + value + max; } } Copy code

summary

The focus of these two questions is to master how odd and even numbers are decomposed. To master this, it is not difficult to find using recursion.