YoungForest's blog

This weekend was insanely busy, and I paid the price for my procrastination and laziness. Everything piled up together, and Sunday had a ridiculous number of deadlines. At 10 a.m. I had a meeting with my advisor to discuss how to prepare the make-up exam for the undergraduate Computer Organization course. By the time I got back to the lab after the meeting, the contest had already started. After a brief hesitation over whether to join the contest as planned or first finish preparing the make-up exam, I started this week’s weekly contest. It is one of the few things I have kept doing over the past two months, and continuing it is no longer only about improving my algorithm skills. It is also a huge encouragement for my confidence in taking control of my own life.

Today let’s study two important data structures together: queue and stack.
This article is based on LeetCode’s Explore tutorial, Introduction to Data Structure - Queue & Stack.

Introduction

The most commonly used collection is the array, and its most commonly used data-access operation is random access, usually called subscript access in C++.
But sometimes we want to restrict the order in which data is processed. The most common restrictions are First in first out and Last in first out. They correspond to two data structures: Queue and Stack.

Today was my first LeetCode weekly contest after work started again. I solved three problems and ranked 772 / 4174. Seeing my rank drop from 200+ to 700+ each time felt pretty disappointing. I think the reasons for the drop are: 1. Ranking around 200 was a case where both my state and luck were relatively good; most of the time before, I was also around 700. 2. Although the third problem was Hard, my final submission TLEed. I think if I had had another half hour, I could have ACed it. The reason I did not have enough time later was directly related to spending too much time debugging problems 2 and 4. I am still not familiar enough with many implementations, such as BFS and backtracking, and cannot write them flexibly from memory. Even when solving the fourth problem, I still had to look up C++ APIs on the spot, so my familiarity with the language is also insufficient.

993. Cousins in Binary Tree

Find cousins in a binary tree. “Cousins” means two nodes are on the same level but have different parents.

This article is based on LeetCode’s tutorial Introduction to Algorithms - Recursion I. Its purpose is to help me become more familiar with the important programming concept of “recursion”. If it can also help others, that would be even better.

The structure of this article is exactly the same as LeetCode’s tutorial. It is divided into six parts: Introduction, Principles of Recursion, Recurrence Relation, Memoization, Complexity Analysis, and Conclusion.

Introduction

This contest was the first one after the Spring Festival.

989. Add to Array-Form of Integer

Idea: simulate the written addition process and add digit by digit. The official Solution has a very vivid name for it: Schoolbook Addition.
Time complexity: O(max(N, M)), where N and M are the lengths of A and K, respectively.
Space complexity: O(M-N), namely the space used by the deque.

Because I was staying at home for the holiday, I actually forgot what day of the week it was and only knew which day of the twelfth lunar month it was. Today I finally realized it was already Monday and that I had missed the weekly contest. On this Chinese New Year’s Eve, before watching the Spring Festival Gala with my family, Forest and his whole family wish everyone a happy New Year! I will quickly finish these four contest problems so I can eat New Year’s Eve dinner with peace of mind.

Since official Notes cannot be used during the contest, writing on the blog is a convenient substitute.

985. Sum of Even Numbers After Queries

Today I went home for vacation, with a train at 3:30 p.m. But I still squeezed out time from a busy schedule to join the regular weekly contest. The result was poor because I was not focused enough while going home. I only solved the warm-up problem. The second problem TLEed, and in the end it could have passed by changing one variable to a reference, which was also a lesson: use references whenever possible. I did not have enough time to finish the third problem, though after getting on the train in the afternoon, with no distractions, I finally completed it independently. The idea had actually been correct from the beginning; I just did not have time to debug the details. As for the fourth problem, I did not even have time to finish reading the statement.

984. String Without AAA or BBB

Intuition: since consecutive a or b cannot appear, we can try to directly construct a valid string. The character with more remaining count appears twice, then we insert one of the character with fewer remaining count. When the remaining counts become equal, each character only needs to appear once at a time.

This week, I joined the weekly contest together with my good friend “Female Voice Male”. Competing with a classmate still brings quite a bit of pressure. I have been practicing algorithm problems for half a year, while he is still a beginner. If I lost in the end, that would be embarrassing. Fortunately, the result was acceptable, and I did not embarrass myself. I ACed all problems with 10 minutes left, and every problem passed on the first try, so I was slightly ahead. I have to say that this contest’s problems were much easier than previous ones. My previous level had stayed at solving only two problems with a ranking around 800, while this time my ranking was 356 / 3870. From the ranking, there was some progress.

Below I share the ideas for the four problems.

977. Squares of a Sorted Array

This contest went rather badly. My rank was roughly 1486 / 3845. The problems were:

• The second problem was relatively simple. Since it was an Easy problem, I directly used brute force and got one TLE. Earlier, because of carelessness, I also wrote the wrong variable in the for loop condition once. That caused two penalties.
• The third problem was not very hard either, but in the end I did not think of the O(n) solution. I only thought of an O(n ^ 2) approach. I thought of prefix sums and noticed the keyword divisible, but I did not connect it to the key point that equal prefix sums work.
• For the fourth problem, I thought of DP. I got stuck on the step of “finding the number just slightly larger in the later array”, that is, I did not think of using TreeMap. Fundamentally, this is because I am not familiar enough with basic data structures.

973. K Closest Points to Origin

The weekly LeetCode weekly contest has begun. This week I genuinely improved compared with before. First, I am more familiar with C++; previously I always used Python. The answering process was also smoother, and I almost solved three problems.