What is “ARTS”? Algorithm: at least one Leetcode Algorithm problem per week; Review: Read and comment on at least one technical article in English; Tip: Learn at least one technical skill; Share: To Share a technical article with ideas and thoughts.

Algorithm

LC 230. Kth Smallest Element in a BST

What is the meaning of the passage?

Find the KTH smallest node in the binary search tree, and notice that K starts at 1. Because it’s a binary search tree, we can think about it in terms of its basic property, which is that everything on the right is bigger than everything on the left. When we talk about binary search trees, we almost always think of middle-order traversal, and the order obtained by middle-order traversal of binary search trees is from smallest to largest. So it’s easy to get the following solution:

public int kthSmallest(TreeNode root, int k) {
    List<TreeNode> nodes = new ArrayList<>();

    helper(root, nodes);

    return nodes.get(k - 1).val;
}

private void helper(TreeNode root, List<TreeNode> nodes) {
    if (root == null) {
        return;
    }

    helper(root.left, nodes);
    nodes.add(root);
    helper(root.right, nodes);
}
Copy the code

The time complexity of this solution is order n, and the space complexity is order h plus n, where h is the height of the tree, and if the tree is balanced, then h is equal to LGN, and the worst case is h is equal to n, ignoring the constant term, and the space complexity is order n.

If binary trees are frequently modified (deleted and inserted), how can they be optimized? I initially thought the problem meant further optimization in space or time, so I wrote an iterative solution that, by counting, would return as soon as it found the KTH smallest node, without going through it again. So the worst time and space complexity is the same as before, but it’s optimized a little bit, so if the binary tree is balanced, the space complexity can go up to O(LGN), the time complexity depends on K, and the average is also O(LGN).

But when I looked at the answer, I realized that the additional question was not to optimize the complexity, but to optimize the design. This design is optimized not only for searching for the KTH smallest element, but also for insertion and deletion. This requires maintaining a linked list (similar to the LRU structure) at the bottom of the binary tree. This optimization is also constant, but I won’t go into details.


Reference code:

public int kthSmallest(TreeNode root, int k) {
    TreeNode pointer = root;
    Stack<TreeNode> stack = new Stack<>();

    int count = 0;
    while(pointer ! =null| |! stack.isEmpty()) {while(pointer ! =null) {
            stack.push(pointer);
            pointer = pointer.left;
        }

        pointer = stack.pop();
        if (++count == k) {
            return pointer.val;
        }

        pointer = pointer.right;
    }

    return -1;
}
Copy the code


Review

The Weekend Experiment That Will Change Your Life

3 Adventures to Plan for a Better Week

Both articles are written by the same author on how to spend your time more productively and how to enjoy more with your limited time. One way to keep track of your time is to keep track of what you do and where you spend most of your time. If you want to know how to be more efficient, you need to know where you are wasting your time.

Most of the time, we feel as if we’re reasonably productive and getting a lot done during our workday. But when it comes to the weekend, it seems as if nothing has been done has passed quickly. This is because your workday is full of tasks, you know exactly what you need to do, and you can see progress on those tasks every day. And we don’t have a good plan for the weekend, we think that the weekend should be relaxing, thinking of nothing is the best. There’s nothing wrong with relaxing, but you need to know exactly what to do to relax and how much time you need to do it. Only by being aware, can we make greater use of our time and not be different from what we expect.

Is it time-consuming to track time and make plans? No, it probably only takes the same amount of time each day as rinsing. The reason we don’t do it is because we don’t want to get out of our comfort zone and think about it. But the author also says that once you start tracking and tracking your time, you’ll realize that you actually have a lot of it, but it’s slipping away. On the other hand, making plans to relax during the weekend can increase your level of anticipation, giving you something to look forward to and not getting too frustrated or anxious about what’s going on right now. It’s up to you to decide what you want to do, but generally it’s something that gives you a sense of relaxation and that you feel you can enjoy. It’s best to have some variety, because trying something new and different always arouses curiosity and makes people look forward to it.


Tip

Recently I checked about Elastic Search and Solr for my project. Both of these are near-real-time search engines, so which one should you choose?

Let’s start by looking at what they have in common. Both Elastic Search and Solr are based on an Apache open source project called Lucene. And both technologies are open source. In addition, they are all designed to solve the same problem, namely real-time search and data storage. A lot of people may ask, isn’t there MySql and Mongo databases, why still need them? This brings up a search efficiency issue. Consider a scenario where a user enters the word “iPhone” in the search bar of an e-commerce site like Taobao. A traditional database would certainly compare this word to all the product information in the current database, which would be very expensive if there were a billion product information in the database. A better way to solve this problem is to use a technique called inverted indexing, which Elastic Search and Solr do.

Now let’s focus on the differences between these two things, and of course I’ve referenced some posts on the Internet that I’ve actually used Solr, not Elastic Search.

Solr is a fully open source Apache project, meaning anyone is free to submit code, and the entire project is maintained by the non-profit community. Elastic Search is the company behind Elastic Search, and although the code is open source, Elastic Search is taking the lead in maintaining the project.

In terms of usage, Elastic Search is much easier to use. It’s basically out of the box. It’s more like a product. Solr requires setting up some environments before it can be used, such as setting up zooKeeper and doing some initial configuration.

For dynamic indexes, ES is better. Dynamic indexing refers to updating and indexing in real time. Solr is not suitable for dynamic index updates because of its high IO. However, Solr has an advantage over ES when it is based on static indexes, and its search efficiency is higher than that of ES. The choice between Solr and ES may depend on the actual situation.

Because ES is a product after all, some supporting tools will be relatively complete. ES is simply a storage and computing solution within ELK. ELK also has LogStash and Beat for data collection, Kibana for visual monitoring, and many class libraries in x-Pack. It can be said that there is an ecosystem around ES, and the application scenarios are not only limited to real-time search, but also log analysis, index analysis, security analysis, full-text retrieval and so on. This is why the utilization rate of ES has been increasing over the years compared to Solr.

I’m currently studying Elastic Search, which I think is a very useful technology because Search is indispensable in most businesses.


Share

The two greatest assets in life are your talent and your time

A short essay by Kai-fu Lee. It boils down to learning to track your time, using the most efficient time to do the most important things, and focusing on the things you’re truly passionate about that align with your own life goals.

What struck me in the article was the following sentence:

Physical fitness is important when it comes to getting ahead at work, but it’s the mind, not the body, that really changes your state. What you need to be truly engaged in your work is an attitude, a desire, and a will.

The emphasis is on the last sentence. What exactly do attitude, desire and will mean? Everyone’s understanding may be different, here is my understanding.

The first is attitude. When we do anything, if we only hold the attitude of completing the task, we will pay attention to how to complete the task in the process of doing it, which will actually miss a lot of wonderful discoveries. Often, the real reason we are interested in something is not what good it will do us. For example, work can give you a material foundation, but are you really interested in your job because of that? Are you really interested in exercising and eating right to improve your health? On the other hand, things like playing games, watching TV dramas and brushing Douyin, which do not bring any real benefits, are pursued by a large number of people. Why is that? Because these things have been carefully designed, it is easy for us to find the wonderful and interesting places in them. In fact, there are many things that attract our interest, just to say that for some things, the point of interest here needs us to discover little by little. Going back to the beginning, when you’re not doing something in a completion-oriented way, you have a chance to see the beauty and goodness in it. That’s the attitude we should have.

Then there is desire. Everyone’s experience and background are different, and the things they yearn for are not exactly the same. But then again, we can ask ourselves a question: “What is it in my heart that I aspire to? What is it that keeps me going?” . When we were little, we all had dreams, and in those innocent days, we would tell everyone around us what our dreams were. As we grow up, we don’t talk about our dreams with others, and as time goes by, we even forget our dreams. We seem to be less attached to our dreams, either because of reality or because something has changed inside us. But find what you really want anyway, and it won’t change because of what the outside world thinks. It’s what you really want. I believe that everyone has something deep inside that they really want, and if you find it, you will find your purpose and direction in life.

Finally, there is will, which can be interpreted as persistence or restraint. Stick to what you choose, control your desires, and focus on what you stand for. This can be said to be the necessary factor to get things done, because doing anything is afraid of doing things by halves. Now that we have found the direction and know that there will be results if we stick to it, why not stick to it? There will be bumps, but you always know that’s not the end, right?