ARTS #012
ARTS #012
ARTS is an activity initiated by
由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.
ARTS 012
This is article 12
Algorihm algorithm question
leetcode algorithm question 241.Reorganize String: Difficulty: Moderate
442. Find All Duplicates in an Array
Difficulty: Medium
Given an array of integers, 1 ≤ a[i] ≤ n ( n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
**Input:**
[4,3,2,7,8,2,3,1]
**Output:**
[2,3]
Solution
Language: C
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
}
The idea is to count the number of times a number appears. My implementation is as follows. The time complexity is O(n); the question requires no additional space. The memory applied here is used to store the results. I don’t know if the space complexity is considered a violation.
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
int *charCount = (int*)malloc(sizeof(int) * (numsSize+1));
memset(charCount, 0, sizeof(int) * (numsSize+1));
for (int i = 0; i < numsSize; i++) {
int data = nums[i] ;
charCount[data]++;
}
* returnSize = 0;
for (int i =0; i < numsSize +1; i++) {
int data = charCount[i] ;
if (data > 1) {
charCount[(*returnSize)++] =i;
}
}
return charCount;
}
I found a clever answer in the discussion area, as follows, for example, if the input nums is [2,3,2], the first time num=abs(nums[0]); The value of num is 2, and the value of nums corresponding to 2-1 is 3, and then a negative sign is added. At this time, nums is [2,-3,2]. When num=abs(nums[2); is used for the third time, the value of num is 2, and the value of nums corresponding to -1 is -3, indicating that the corresponding subscript has already appeared.
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
if(nums==NULL||numsSize<2)
{
*returnSize=0;
return NULL;
}
*returnSize=0;
int *result=(int *)malloc(sizeof(int)*(numsSize/2));
for(int i=0;i<numsSize;i++)
{
int num=abs(nums[i]);
if(nums[num-1]>0)
nums[num-1]=-nums[num-1];
else
result[(*returnSize)++]=num;
}
return result;
}
Review
This article comes from https://medium.freecodecamp.org/how-to-think-like-a-programmer-lessons-in-problem-solving-d1d8bf1de7d2
This article focuses on how programmers should solve problems: The way that new programmers solve bugs is to try it over and over again, which is very inefficient (The way that new programmers solve bugs is to try it over and over again, which is very inefficient). The right approach should be to establish your own general approach to the problem, including the following steps: 1 The first thing to do is to figure out the problem and really understand it. 2. Instead of rushing to solve a problem, take the time to analyze and think about it and make a plan. 3. Break down the problem. Break down the big problem into small problems. 4. When you encounter a small problem that is difficult to solve, first don’t be impatient and settle down. You can solve it by re-examining the problem, searching, and debug. 5 Don’t be afraid to encounter problems. Only by solving more problems can you improve your ability to become an expert (Don’t be afraid to encounter problems. Only by solving more problems can you improve your ability to become an expert)
The details of the article are as follows:
How to think like a programmer — lessons in problem solving
By Richard Reis
If you’re interested in programming, you may well have seen this quote before: If you’re interested in programming, you’ve probably seen this quote:
“Everyone in this country should learn to program a computer, because it teaches you to think.” — Steve Jobs
You probably also wondered what does it mean, exactly, to think like a programmer? And how do you do it?? You may also be wondering, what exactly does it mean to think like a programmer? How do you do it?
Essentially, it’s all about a more effective way for problem solving. Essentially, it’s a more efficient way to solve a problem.
In this post, my goal is to teach you that way. In this article, my goal is to teach you this way.
By the end of it, you’ll know exactly what steps to take to be a better problem-solver. By the end, you’ll know how to solve the problem better.
Why is this important?
Problem solving is the meta-skill. Problem solving is a meta-skill.
We all have problems. Big and small. How we deal with them is sometimes, well…pretty random. We all have problems. Big and small. The way we deal with these problems is sometimes random. pretty random. random/random
Unless you have a system, this is probably how you “solve” problems (which is what I did when I started coding): Unless you have a system in place, this is probably how you “solve” the problem (this is what I did when I started coding):
- Try a solution.
- If that doesn’t work, try another one.
- If that doesn’t work, repeat step 2 until you luck out.
Look, sometimes you luck out. But that is the worst way to solve problems! And it’s a huge, huge waste of time. Look, sometimes you’re just out of luck. But that’s the worst way to solve a problem! It’s a very, very waste of time.
The best way involves a) having a framework and b) practicing it. The best way is to a) have a framework and b) practice it.
“Almost all employers prioritize problem-solving skills first. Almost all employers prioritize problem-solving skills first.
Problem-solving skills are almost unanimously the most important qualification that employers look for….more than programming languages proficiency, debugging, and system design.
Demonstrating computational thinking or the ability to break down large, complex problems is just as valuable (if not more so) than the baseline technical skills required for a job.” —Hacker Rank (2018 Developer Skills Report)#### Have a framework To find the right framework, I followed the advice in Tim Ferriss’ book on learning,“The 4-Hour Chef”. To find the right framework, I followed the advice in Tim Ferriss’ book on learning,
It led me to interview two really impressive people: C. Jordan Ball (ranked 1st or 2nd out of 65,000+ users on Coderbyte), and V. Anton Spraul (author of the book “Think Like a Programmer: An Introduction to Creative Problem Solving”).
I asked them the same questions, and guess what? Their answers were pretty similar! I asked them the same question and guess what? Their answers were very similar!
Soon, you too will know them.
Sidenote: this doesn’t mean they did everything the same way. Everyone is different. You’ll be different. But if you start with principles we all agree are good, you’ll get a lot further a lot quicker. Sidenote: This doesn’t mean they do everything the same way. Everyone is different. You will be different. But if you start with good principles that we all agree on, you’ll go further and faster.
“The biggest mistake I see new programmers make is focusing on learning syntax instead of learning how to solve problems.” — V. Anton Spraul The biggest mistake I see new programmers make is focusing on learning syntax instead of learning how to solve problems.
So, what should you do when you encounter a new problem? So, what should you do when you encounter a new problem?
Here are the steps:
1. Understand
Know exactly what is being asked. Most hard problems are hard because you don’t understand them (hence why this is the first step). Know exactly what is being asked. Most puzzles are difficult because you don’t understand them (hence this first step).
How to know when you understand a problem? When you can explain it in plain English. How do you know when you understand a question? When you can explain it in plain English.
Do you remember being stuck on a problem, you start explaining it, and you instantly see holes in the logic you didn’t see before? Do you remember being stuck on a problem, you started explaining it, and then you immediately saw holes in the logic you hadn’t seen before?
Most programmers know this feeling. Most programmers know this feeling.
This is why you should write down your problem, doodle a diagram, or tell someone else about it (or thing… some people use a rubber duck). This is why you should write your problem down, draw a diagram, or tell someone (or something else…some people use rubber ducks).
“If you can’t explain something in simple terms, you don’t understand it.” — Richard Feynman
2. Plan
Don’t dive right into solving without a plan (and somehow hope you can muddle your way through). Plan your solution! Don’t dive headlong into problem solving without a plan (and hope you can get by). Plan your solution! (Don’t dive right into (Don’t dive right into))
Nothing can help you if you can’t write down the exact steps. If you can’t write down the exact steps, nothing will help you.
In programming, this means don’t start hacking straight away. Give your brain time to analyze the problem and process the information. In programming, this means don’t start hacking right away. Give your brain time to analyze the problem and process the information.
To get a good plan, answer this question: To get a good plan, answer this question:
“Given input X, what are the steps necessary to return output Y?” Given input X, what are the steps required to return output Y?
Sidenote: Programmers have a great tool to help them with this… Comments! Sidenote: Programmers have a great tool to help them achieve this… Notes!
3. Divide
Pay attention. This is the most important step of all.
Do not try to solve one big problem. You will cry. Don’t try to solve a big problem. You will cry.
Instead, break it into sub-problems. These sub-problems are much easier to solve.
Then, solve each sub-problem one by one. Begin with the simplest. Simplest means you know the answer (or are closer to that answer). Then, solve each sub-problem one by one. Start with the simplest. The simplest meaning is that you know the answer (or are closer to that answer).
After that, simplest means this sub-problem being solved doesn’t depend on others being solved. After this, the simplest approach means that the solution of a subproblem does not depend on the solution of other problems.
Once you solve every sub-problem, connect the dots. Once you’ve solved each sub-problem, connect the dots.
Connecting all your “sub-solutions” will give you the solution to the original problem. Congratulations! Connecting all “sub-solutions” will give you the solution to the original problem. Congratulations!
This technique is a cornerstone of problem-solving. Remember it (read this step again, if you must). This technique is the cornerstone of problem solving. Memorize it (read this step again if necessary).> “If I could teach every beginning programmer one problem-solving skill, it would be the ‘reduce the problem technique.’ “If I could teach every beginning programmer one problem-solving skill, it would be the ‘reduce the problem technique.’ "
For example, suppose you’re a new programmer and you’re asked to write a program that reads ten numbers and figures out which number is the third highest. For a brand-new programmer, that can be a tough assignment, even though it only requires basic programming syntax. For example, suppose you are a new programmer and you are asked to write a program that reads 10 numbers and then works out which number is the third highest. This can be a daunting task for a brand new programmer, although it only requires basic programming syntax.
If you’re stuck, you should reduce the problem to something simpler. Instead of the third-highest number, what about finding the highest overall? Still too tough? What about finding the largest of just three numbers? Or the larger of two? If you get stuck, you should simplify the problem. Instead of the third highest number, how to find the highest overall? Still too harsh? What about finding the largest of three numbers? Or the larger of the two?
Reduce the problem to the point where you know how to solve it and write the solution. Then expand the problem slightly and rewrite the solution to match, and keep going until you are back where you started.” —V. Anton Spraul Simplify the problem to the point where you know how to solve it and write a solution. Then expand the problem a little, rewrite the solution so it matches, and keep going until you’re back to where you started.
4. Stuck?
By now, you’re probably sitting there thinking “Hey Richard… That’s cool and all, but what if I’m stuck and can’t even solve a sub-problem??” Now, you’re probably sitting there thinking “Hey Richard…” That’s cool, but what if I’m stuck and can’t even solve the subproblem?
First off, take a deep breath. Second, that’s fair. First, take a deep breath. Second, it’s fair.
Don’t worry though, friend. This happens to everyone! Don’t worry, friend. This happens to everyone!
The difference is that the best programmers/problem-solvers are more curious about bugs/errors than irritated. The difference is that the best programmers/problem solvers are more curious about bugs/bugs than annoyed.
In fact, here are three things to try when facing a whammy: In fact, there are three things you can try when something bad happens to you:
- Debug: Go step by step through your solution trying to find where you went wrong. Programmers call this debugging (in fact, this is all a debugger does). Debugging: Step through your solution, trying to figure out what went wrong. The programmer calls this debugging (in fact, this is all the debugger does).
“The art of debugging is figuring out what you really told your program to do rather than what you thought you told it to do.” —Andrew Singer The art of debugging is finding out what you really tell your program to do, not what you think you tell it to do
- Reassess: Take a step back. Look at the problem from another perspective. Is there anything that can be abstracted to a more general approach? Reassess: Take a step back. Look at this problem from another angle. Is there anything that can be abstracted into a more general method?
“Sometimes we get so lost in the details of a problem that we overlook general principles that would solve the problem at a more general level. […] “Sometimes we get so caught up in the details of a problem that we lose sight of the general principles for solving problems at a more general level.”
The classic example of this, of course, is the summation of a long list of consecutive integers, 1 + 2 + 3 + … + n, which a very young Gauss quickly recognized was simply n(n+1)/2, thus avoiding the effort of having to do the addition.” —C. Jordan Ball Of course, the most classic example is the sum of a long list of consecutive integers, 1 + 2 + 3 +…+ n, which a very young Gauss quickly recognized as n(n+1)/2, so that there was no need to add anymore.
Sidenote: Another way of reassessing is starting anew. Delete everything and begin again with fresh eyes. I’m serious. You’ll be dumbfounded at how effective this is. Side note: Another way to reevaluate is to start over. Delete everything and start over with fresh eyes. I’m serious. You’ll be surprised how effective this is.
- Research: Ahh, good ol’ Google. You read that right. No matter what problem you have, someone has probably solved it. Find that person/ solution. In fact, do this even if you solved the problem! (You can learn a lot from other people’s solutions). Research: Ah, good. You read that right. Whatever problem you have, someone has probably solved it. Find that person/solution. In fact, do it even if you solve the problem! (You can learn a lot from other people’s solutions).
Caveat: Don’t look for a solution to the big problem. Only look for solutions to sub-problems. Why? Because unless you struggle (even a little bit), you won’t learn anything. If you don’t learn anything, you wasted your time. Note: Don’t look for solutions to big problems. Find only solutions to subproblems. Why? Because unless you try (even a little bit), you won’t learn anything. If you learn nothing, you’re wasting your time.
Practice
Don’t expect to be great after just one week. If you want to be a good problem-solver, solve a lot of problems! Don’t expect to be great in just one week. If you want to be a good problem solver, solve a lot of problems!
Practice. Practice. Practice. It’ll only be a matter of time before you recognize that “this problem could easily be solved with <insert concept here>.” Practice. Practice. Practice. Sooner or later you will realize “this problem can be easily solved by <insert concept here>”.
How to practice? There are options out the wazoo! How to practice? There are many options!Chess puzzles, math problems, Sudoku, Go, Monopoly, video-games, cryptokitties, bla… bla… bla…. chess game, math problems, sudoku, monopoly, video games, cryptokitties, bla bla bla…
In fact, a common pattern amongst successful people is their habit of practicing “micro problem-solving.” For example, Peter Thiel plays chess, and Elon Musk plays video-games. In fact, a common pattern among successful people is that they practice micro-problem-solving. For example, Peter Thiel plays chess and Elon Musk plays video games.
“Byron Reeves said ‘If you want to see what business leadership may look like in three to five years, look at what’s happening in online games.’ "Byron Reeves said, 'If you want to know what business leadership will look like in three to five years, look at what’s happening in online gaming. ’”
Fast-forward to today. Elon [Musk], Reid [Hoffman], Mark Zuckerberg and many others say that games have been foundational to their success in building their companies.” — Mary Meeker (2017 internet trends report) Fast forward to today. Elon Musk, Reid Hoffman, Mark Zuckerberg and many others have said gaming was the cornerstone of their successful companies.
Does this mean you should just play video-games? Not at all. Does this mean you should only play video games? You’re welcome.
But what are video-games all about? That’s right, problem-solving! But what exactly are video games about? Yes, problem solved!
So, what you should do is find an outlet to practice. Something that allows you to solve many micro-problems (ideally, something you enjoy). So, what you should do is find an outlet for practice. Something that allows you to solve a lot of small problems (ideally, something you enjoy).
For example, I enjoy coding challenges. Every day, I try to solve at least one challenge (usually on Coderbyte). For example, I love programming challenges. Every day, I try to solve at least one challenge (usually at Coderbyte).
Like I said, all problems share similar patterns. As I said, all questions have similar patterns.
Conclusion
That’s all folks! This is everyone!
Now, you know better what it means to “think like a programmer.” Now, you know what “think like a programmer” means.
You also know that problem-solving is an incredible skill to cultivate (the meta-skill). You also know that problem solving is an incredible skill (meta-skill).
As if that wasn’t enough, notice how you also know what to do to practice your problem-solving skills! If that’s not enough, note that you also know how to practice problem-solving skills!
Phew… Pretty cool right? Cool right?
Finally, I wish you encounter many problems. Finally, I wish you lots of problems.
You read that right. At least now you know how to solve them! (also, you’ll learn that with every solution, you improve). You read that right. At least now you know how to solve it! (Also, you will learn that you will improve with every solution).
“Just when you think you’ve successfully navigated one obstacle, another emerges. But that’s what keeps life interesting.[…] Just when you think you’ve successfully crossed one hurdle, another one pops up. But that’s what makes life interesting.
Life is a process of breaking through these impediments — a series of fortified lines that we must break through. Life is a process of breaking through these barriers—a series of defenses that we must break through.
Each time, you’ll learn something. Every time, you learn something.
Each time, you’ll develop strength, wisdom, and perspective. Each time, you will develop strength, wisdom, and insight.
Each time, a little more of the competition falls away. Until all that is left is you: the best version of you.” —Ryan Holiday (The Obstacle is the Way) Each time, more competition disappears. Until you become the best version of yourself. ——Ryan Holliday (The Obstacle is the Road)
Now, go solve some problems!
And best of luck 🙂
Special thanks to C. Jordan Ball and V. Anton Spraul. All the good advice here came from them.
Also, all the programming knowledge I’ve acquired in such a short time wouldn’t have happened without Lambda School. Can’t thank/ recommend them enough.
Furthermore, all the programming knowledge I gained in such a short time would not have happened without Lambda School. Thank you/recommend them very much.
Thanks for reading! 😊 If you enjoyed it, test how many times can you hit 👏 in 5 seconds. It’s great cardio for your fingers AND will help other people see the story. Thanks for reading! 😊 If you like it, test how many times you can hit it in 5 seconds. 👏 It’s a great cardio workout for your fingers and will also help others see this story.
TIPS
I learned how to use Instrument this week and am going to translate the latest official documents. I have already translated a small part of the first chapter: https://dandan2009.github.io/2018/10/26/Instruments-chinese-translation/
Share
Today I learned a few new terms: “clear network”, “dark network”, “deep network”, and shadow network. Clearnet refers to the network we usually use. “Dark Web”, “Deep Web”, “Clear Web”, Shadow Web. “Dark Web”, “Deep Web”, and Shadow Web all refer to networks that are beyond the reach of ordinary people and cannot be accessed through conventional methods. Most of these networks contain illegal information.
The following content comes from the Internet:
“Dark Web” DarkWeb and DeepWeb DeepWeb is a wide range of Internet content that cannot be indexed by search engines So what is the Darknet (English: Darknet or Dark Web)? The Darknet is a network that can only be connected using special software, special authorization, or special computer settings. Server addresses and data transmission on the dark web are usually anonymous and invisible. In contrast, the commonly used Internet is called “Clearnet” or “Clearnet” (English: Clearnet) because it can track its true geographical location and the identity of the person communicating. The Onion Network is currently recognized as a better method for anonymous Internet communication.
Using Tor Using Tor is not difficult. If you have access to Google, just log in to the Tor website http://www.theonionrouter.com/下载Tor和Tor浏览器即可~
https://www.mushroomnetworks.com/
house of cards The old man in the movie “Sin City”
In fact, the term “Shadow Web” only appeared at the beginning of this year, and the origin of this term comes from a post on Reddit (similar to the Hong Kong Gordon Forum). This is also the story I want to introduce to you today… a terrible warning.Like all technologies, there are good and evil sides. When the network plays its role in sharing information to benefit mankind, it also has a structural layering similar to the black and white in society, giving birth to three brothers called the clear network, the deep network, and the dark network.
The origin of the dark web
So, when did these websites begin to develop? Ironically, like the source of most technologies, the initiator must be mentioned here - the US military.
In 1996, scientists from the U.S. Naval Research Institute submitted a paper titled “Hidden Path Information” and proposed the idea of building a stealth system that would allow any user to remain anonymous in real time when connecting to the Internet without revealing their identity to the server. The construction of this system is very necessary. First, it can protect political dissidents in various countries, escape the authoritarian oppression of various countries, and popularize universal democracy in the eyes of Americans; second, it can provide a safe place for U.S. intelligence personnel to exchange information.
In October 2003, this idea began to be officially implemented to provide users with a free anonymous online place. Because the passwords protecting the data were wrapped like layers of an onion, the system was eventually called Tor (The Onion Router). https://www.ufochn.com/article-205-1.html
https://www.aqniu.com/industry/37816.html
https://parrotsec-cn.org/t/topic/50
http://blog.sina.com.cn/s/blog_63296ead0102x95x.html
http://www.theonionrouter.com/about/torusers.html.en#normalusers
The following websites are some of the darknet websites that Rocket found on the famous thehiddenwiki.org/ website. Be sure to use Tor to access the dark web (websites ending in .onion) Be sure to use https Do not use Tor to log in to any website (such as Baidu Netdisk, Weibo, Zhihu, etc.) Do not send any unsolicited personal information about yourself
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。