Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

An example Analysis of Java Product problem

2025-01-24 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "Java product problem example analysis". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Interview questions: turn things upside down

In a binary search tree, two nodes are reversed. It is required to implement an algorithm to restore the correct binary search tree without changing the tree structure. It is easy to give an implementation of space O (n), so how to give an implementation of space O (1)?

Product analysis of selflessness

Title:

Give you an array A [1. N], please construct a new array B [1. N] in O (n) time, such that B [I] = A [1] * A [2] *. * A [n] / A [I]. You can't use division.

Analysis:

When you see the question, don't be nervous, be clear-headed and see through the interviewer's original intention. In fact, he is using the formula of division, but he asks you not to use division to confuse you.

Requires that B [I] = A [0] * be calculated without division. * A [n] / A [I], you can get B [I] = A [0] * by simply changing the form. * A [I-1] * A [I + 1] * … * A [n], a total of 1 times multiplication. Each B [I] is calculated, and the total time complexity is O (n ^ 2). Do not meet the requirements of the topic, the number of multiplication must be reduced. How to reduce the number of multiplication? Continue to analyze, through the above transformation, we can find that B [I] is obtained by multiplying two parts:

A [0] *... * A [I-1] A [ionization 1] *... * A [n]

Let's first look at the * * part. When calculating B [I], we can use the * * part of B [I]. You only need to multiply A [I] to get the * * part of B [I].

The second part is the same, after calculating A [item1] *. * A [n], and then calculate A [I] * A [I + 1] * … * A [n], just multiply by A [I]. A [I] * A [I + 1] *... * A [n] is the second part of B [I-1].

Based on this analysis, two new arrays are constructed: C and D (two arrays are used for convenient explanation).

C [I] = A [0] *... * A [I-1] = C [I-1] * A [I-1] D [I] = A [I-1] * … * A [n] = D [ionization 1] * A [iatro1}

Building C and D is the time complexity of O (n) (C traverses the array from front to back, D traverses one side of the array from back to front), then B [I] = C [I] * D [I] is also the time complexity of O (n). The time complexity of the whole algorithm is O (n).

This is the end of the question.

But the interviewer's question is not finished, they will continue to ask, the space of this solution is O (n), can it be realized in the case of space O (1)?

First look at an array of only five numbers, A [1], A [2], A [3], A [4], A [5].

First, traverse from beginning to end:

B [1] = A [1] B [2] = B [1] * A [2] B [3] = B [2] * A [3] B [4] = B [3] * A [4] B [5], temporary variable Centra [5]

Then traverse from end to end:

B [4] = B [3] * C, C=C*A [4] B [3] = B [2] * C, C=C*A [3] B [2] = B [1] * C, C=C*A [2] B [1] = C

Through this small example, we get the algorithm, which can be extended to any number of elements. This is a common technique in interviews.

This is the end of the content of "example Analysis of Java Product". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 271

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report