LeetCode - Algorithms - 260. Single Number III

Problem

260. Single Number III

Java

XOR with bitmask

In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word etc. can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation.

A bit mask is a predefined set of bits that is used to select which specific bits will be modified by subsequent operations.

the bit mask blocks the bitwise operators from touching bits we don’t want modified, and allows access to the ones we do want modified.

© https://leetcode.com/problems/single-number-iii/discuss/982092/Python3-XOR-with-bitmask

© https://www.bookstack.cn/read/solve-leetcode-problems/problems-Single%20Number%20III.md

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] singleNumber(int[] nums) {
int xorResult = 0, firstNum = 0, secondNum = 0;
for (int num : nums) {
xorResult ^= num;
}

int bitMask = xorResult & (~xorResult + 1);

for (int num : nums) {
if ((bitMask & num) != 0)
firstNum ^= num;
else
secondNum ^= num;
}

return new int[]{firstNum, secondNum};
}
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 1 ms, faster than 96.24% of Java online submissions for Single Number III.
  • Memory Usage: 42 MB, less than 5.92% of Java online submissions for Single Number III.

Mask (computing)

Quotes - Isaac Newton

Nature and nature’s laws lay hid in night;
God said “Let Newton be” and all was light.
(Alexander Pope)

It could not last; the Devil shouting “Ho!
Let Einstein be!” restored the status quo.
(J. C. Squire)


Plato is my friend — Aristotle is my friend — but my greatest friend is truth.

If I have seen further it is by standing on the shoulders of giants.

tis due to nothing but industry and a patient thought.

I have not been able to discover the cause of those properties of gravity from phenomena, and I frame no hypotheses; for whatever is not deduced from the phenomena is to be called a hypothesis, and hypotheses, whether metaphysical or physical, whether of occult qualities or mechanical, have no place in experimental philosophy.

To explain all nature is too difficult a task for any one man or even for any one age. ‘Tis much better to do a little with certainty, & leave the rest for others that come after you, than to explain all things by conjecture without making sure of any thing.

I keep the subject constantly before me, and wait ‘till the first dawnings open slowly, by little and little, into a full and clear light.

I do not know what I may appear to the world, but to myself I seem to have been only like a boy playing on the sea-shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.

In default of any other proof, the thumb would convince me of the existence of a God.

It is the perfection of God’s works that they are all done with the greatest simplicity. He is the God of order and not of confusion.

As in Mathematicks, so in Natural Philosophy, the Investigation of difficult Things by the Method of Analysis, ought ever to precede the Method of Composition.

By this way of Analysis we may proceed from Compounds to Ingredients, and from Motions to the Forces producing them; and in general, from Effects to their Causes, and from particular Causes to more general ones, till the Argument end in the most general. This is the Method of Analysis: and the Synthesis consists in assuming the Causes discover’d, and establish’d as Principles, and by them explaining the Phænomena proceeding from them, and proving the Explanations.

Godliness consists in the knowledge love & worship of God, Humanity in love, righteousness & good offices towards man.


Isaac Newton, a posthumous child, born with no father on Christmas Day 1642, was, as Maynard Keynes has aptly written, “the last wonder child to whom the Magi could do sincere and appropriate homage.”

One of the most remarkable aspects of Newton’s most remarkable life is the explosive outburst of his genius. He was not an infant prodigy; and it is probable that when he went to Cambridge in 1661, he knew little more than elementary arithmetic. And it must be remembered that the new outlook on scientific thought that we associate with the names of Galileo, Kepler, and Descartes had hardly yet penetrated the walls of Oxford and Cambridge. Nevertheless, by 1664, when Newton was in his twenty-third year, his genius seems to have flowered. Thus, Newton recalled in his old age that he had “found the method of Infinite Series at such time (1664-65).”

By the summer of 1665, when Cambridge was evacuated on account of the plague and Newton had gone to Woolsthorpe, his genius was fully in flower. It manifested itself in a manner unsurpassed in the history of scientific thought.

An account of a philosophical discovery – which I doubt not but will prove much more grateful than the communication of that instrument, being in my judgement the oddest, if not the most considerable detection, which has hitherto been made in the operation of nature. (January 18, 1672)

I should like to draw your attention especially to the words, “the oddest, if not the most considerable detection.” This is the first and the only time that Newton expresses a trace of enthusiasm with respect to any of his discoveries.

By now Newton’s mathematical genius seems to have been fully aroused, and Newton appears to have been caught in its grip. Newton now entered upon a period of the most intense mathematical activity. Against his will and against his preferences, Newton seems to have been propelled inexorably forward, by the pressure of his own genius, till, at last, he had accomplished the greatest intellectual feat of his life, the greatest intellectual feat in all of science.

By Newton’s own account, he began writing the Principia towards the end of December 1684, and he sent the completed manuscript of all three Books of the Principia to the Royal Society in May 1686, that is, in seventeen months. He had solved two of the propositions in the first Book in 1679, and he had also proved eight of the propositions in the second Book in June and July 1685. There are ninety-eight propositions in the first Book; fifty-three in the second; and forty-two in the third. By far the larger proportion of them was, therefore, enunciated and proved during the seventeen consecutive months that Newton was at work on the three Books. It is this rapidity of execution, besides the monumental scale of the whole work, that makes this achievement incomparable. If the problems enunciated in the Principia were the results of a lifetime of thought and work, Newton’s position in science would still be unique. But that all these problems should have been enunciated, solved, and arranged in logical sequence in seventeen months is beyond human comprehension. It can be accepted only because it is a fact: it just happens to be so!

It is only when we observe the scale of Newton’s achievement that comparisons, which have sometimes been made with other men of science, appear altogether inappropriate both with respect to Newton and with respect to the others. In fact, only in juxtaposition with Shakespeare and Beethoven is the consideration of Newton appropriate.

No account of Newton’s life, however brief, can omit some indication of the manner of man he was. The subject is a complex and a controversial one. But this much can fairly be said: Newton seems to have been remarkably insensitive: impervious to the arts, tactless, and with no real understanding of others.

Newton’s most remarkable gift was probably his powers of concentration. As Keynes wrote:

His peculiar gift was the power of holding continuously in his mind a purely mental problem until he had seen straight through it. I fancy his pre-eminence is due to his muscles of intuition being the strongest and most enduring with which a man has ever been gifted… I believe that Newton could hold a problem in his mind for hours and days and weeks until it surrendered to him its secret.

Besides, as De Morgan has said, he was:

…So happy in his conjectures as to seem to know more than he could possibly have any means of proving.

But the central paradox of Newton’s life is that he deliberately and systematically ignored his supreme mathematical genius and through most of his life neglected the one activity for which he was gifted beyond any man. This paradox can be resolved only if we realize that Newton simply did not consider science and mathematics as of any great importance;

I do not know what I may appear to the world, but to myself I seem to have been only like a boy playing on the sea-shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.

In view of Newton’s insensitiveness to others, doubts have sometimes been raised about the sincerity of this statement. I do not believe that such doubts are warranted: only someone, like Newton, who can view knowledge from his height, can have the vision of an “ocean of undiscovered truth.” As an ancient proverb of India says, “Only the wise can plumb the wells of wisdom.”

(Shakespeare, Newton, and Beethoven: Or, Patterns of Creativity, a talk by Subrahmanyan Chandrasekhar)


LeetCode - Algorithms - 674. Longest Continuous Increasing Subsequence

Problem

674. Longest Continuous Increasing Subsequence

Java

Sliding Window

Sliding Window problems are a subset of dynamic programming problems, though the approach to solving them is quite different from the one used in solving tabulation or memoization problems.

© Approach 1: Sliding Window

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int findLengthOfLCIS(int[] nums) {
int maxLen = 0;
int anchor = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] <= nums[i - 1]) anchor = i;
maxLen = Math.max(maxLen, i - anchor + 1);
}
return maxLen;
}
}

Submission Detail

  • 36 / 36 test cases passed.
  • Runtime: 1 ms, faster than 98.29% of Java online submissions for Longest Continuous Increasing Subsequence.
  • Memory Usage: 39.7 MB, less than 70.15% of Java online submissions for Longest Continuous Increasing Subsequence.

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int findLengthOfLCIS(int[] nums) {
final int N = nums.length;
if (N < 2)
return N;
int len = 1, tempLen = 1;
for (int i = 1; i < N; i++) {
if (nums[i] > nums[i - 1]) {
tempLen++;
} else {
if (tempLen > len)
len = tempLen;
tempLen = 1;
}
}
if (tempLen > len)
len = tempLen;
return len;
}
}

Submission Detail

  • 36 / 36 test cases passed.
  • Runtime: 1 ms, faster than 98.29% of Java online submissions for Longest Continuous Increasing Subsequence.
  • Memory Usage: 39.9 MB, less than 41.25% of Java online submissions for Longest Continuous Increasing Subsequence.

What we're learning from online education - Daphne Koller - TEDGlobal 2012 - Transcript

Like many of you, I’m one of the lucky people. I was born to a family where education was pervasive. I’m a third-generation PhD, a daughter of two academics. In my childhood, I played around in my father’s university lab. So it was taken for granted that I attend some of the best universities, which in turn opened the door to a world of opportunity.

Unfortunately, most of the people in the world are not so lucky. In some parts of the world, for example, South Africa, education is just not readily accessible. In South Africa, the educational system was constructed in the days of apartheid for the white minority. And as a consequence, today there is just not enough spots for the many more people who want and deserve a high quality education. That scarcity led to a crisis in January of this year at the University of Johannesburg. There were a handful of positions left open from the standard admissions process, and the night before they were supposed to open that for registration, thousands of people lined up outside the gate in a line a mile long, hoping to be first in line to get one of those positions. When the gates opened, there was a stampede, and 20 people were injured and one woman died. She was a mother who gave her life trying to get her son a chance at a better life.

But even in parts of the world like the United States where education is available, it might not be within reach. There has been much discussed in the last few years about the rising cost of health care. What might not be quite as obvious to people is that during that same period the cost of higher education tuition has been increasing at almost twice the rate, for a total of 559 percent since 1985. This makes education unaffordable for many people.

Finally, even for those who do manage to get the higher education, the doors of opportunity might not open. Only a little over half of recent college graduates in the United States who get a higher education actually are working in jobs that require that education. This, of course, is not true for the students who graduate from the top institutions, but for many others, they do not get the value for their time and their effort.

Tom Friedman, in his recent New York Times article, captured, in the way that no one else could, the spirit behind our effort. He said the big breakthroughs are what happen when what is suddenly possible meets what is desperately necessary. I’ve talked about what’s desperately necessary. Let’s talk about what’s suddenly possible.

What’s suddenly possible was demonstrated by three big Stanford classes, each of which had an enrollment of 100,000 people or more. So to understand this, let’s look at one of those classes, the Machine Learning class offered by my colleague and cofounder Andrew Ng. Andrew teaches one of the bigger Stanford classes. It’s a Machine Learning class, and it has 400 people enrolled every time it’s offered. When Andrew taught the Machine Learning class to the general public, it had 100,000 people registered. So to put that number in perspective, for Andrew to reach that same size audience by teaching a Stanford class, he would have to do that for 250 years. Of course, he’d get really bored.

So, having seen the impact of this, Andrew and I decided that we needed to really try and scale this up, to bring the best quality education to as many people as we could. So we formed Coursera, whose goal is to take the best courses from the best instructors at the best universities and provide it to everyone around the world for free. We currently have 43 courses on the platform from four universities across a range of disciplines, and let me show you a little bit of an overview of what that looks like.

(Video) Robert Ghrist: Welcome to Calculus.

Ezekiel Emanuel: Fifty million people are uninsured.

Scott Page: Models help us design more effective institutions and policies. We get unbelievable segregation.

Scott Klemmer: So Bush imagined that in the future, you’d wear a camera right in the center of your head.

Mitchell Duneier: Mills wants the student of sociology to develop the quality of mind …

RG: Hanging cable takes on the form of a hyperbolic cosine.

Nick Parlante: For each pixel in the image, set the red to zero.

Paul Offit: … Vaccine allowed us to eliminate polio virus.

Dan Jurafsky: Does Lufthansa serve breakfast and San Jose? Well, that sounds funny.

Daphne Koller: So this is which coin you pick, and this is the two tosses.

Andrew Ng: So in large-scale machine learning, we’d like to come up with computational …

(Applause)

DK: It turns out, maybe not surprisingly, that students like getting the best content from the best universities for free. Since we opened the website in February, we now have 640,000 students from 190 countries. We have 1.5 million enrollments, 6 million quizzes in the 15 classes that have launched so far have been submitted, and 14 million videos have been viewed.

But it’s not just about the numbers, it’s also about the people. Whether it’s Akash, who comes from a small town in India and would never have access in this case to a Stanford-quality course and would never be able to afford it. Or Jenny, who is a single mother of two and wants to hone her skills so that she can go back and complete her master’s degree. Or Ryan, who can’t go to school, because his immune deficient daughter can’t be risked to have germs come into the house, so he couldn’t leave the house. I’m really glad to say – recently, we’ve been in correspondence with Ryan – that this story had a happy ending. Baby Shannon – you can see her on the left – is doing much better now, and Ryan got a job by taking some of our courses.

So what made these courses so different? After all, online course content has been available for a while. What made it different was that this was real course experience. It started on a given day, and then the students would watch videos on a weekly basis and do homework assignments. And these would be real homework assignments for a real grade, with a real deadline. You can see the deadlines and the usage graph. These are the spikes showing that procrastination is global phenomenon.

(Laughter)

At the end of the course, the students got a certificate. They could present that certificate to a prospective employer and get a better job, and we know many students who did. Some students took their certificate and presented this to an educational institution at which they were enrolled for actual college credit. So these students were really getting something meaningful for their investment of time and effort.

Let’s talk a little bit about some of the components that go into these courses. The first component is that when you move away from the constraints of a physical classroom and design content explicitly for an online format, you can break away from, for example, the monolithic one-hour lecture. You can break up the material, for example, into these short, modular units of eight to 12 minutes, each of which represents a coherent concept. Students can traverse this material in different ways, depending on their background, their skills or their interests. So, for example, some students might benefit from a little bit of preparatory material that other students might already have. Other students might be interested in a particular enrichment topic that they want to pursue individually. So this format allows us to break away from the one-size-fits-all model of education, and allows students to follow a much more personalized curriculum.

Of course, we all know as educators that students don’t learn by sitting and passively watching videos. Perhaps one of the biggest components of this effort is that we need to have students who practice with the material in order to really understand it. There’s been a range of studies that demonstrate the importance of this. This one that appeared in Science last year, for example, demonstrates that even simple retrieval practice, where students are just supposed to repeat what they already learned gives considerably improved results on various achievement tests down the line than many other educational interventions.

We’ve tried to build in retrieval practice into the platform, as well as other forms of practice in many ways. For example, even our videos are not just videos. Every few minutes, the video pauses and the students get asked a question.

(Video) SP: … These four things. Prospect theory, hyperbolic discounting, status quo bias, base rate bias. They’re all well documented. So they’re all well documented deviations from rational behavior.

DK: So here the video pauses, and the student types in the answer into the box and submits. Obviously they weren’t paying attention.

(Laughter)

So they get to try again, and this time they got it right. There’s an optional explanation if they want. And now the video moves on to the next part of the lecture. This is a kind of simple question that I as an instructor might ask in class, but when I ask that kind of a question in class, 80 percent of the students are still scribbling the last thing I said, 15 percent are zoned out on Facebook, and then there’s the smarty pants in the front row who blurts out the answer before anyone else has had a chance to think about it, and I as the instructor am terribly gratified that somebody actually knew the answer. And so the lecture moves on before, really, most of the students have even noticed that a question had been asked. Here, every single student has to engage with the material.

And of course these simple retrieval questions are not the end of the story. One needs to build in much more meaningful practice questions, and one also needs to provide the students with feedback on those questions. Now, how do you grade the work of 100,000 students if you do not have 10,000 TAs? The answer is, you need to use technology to do it for you. Now, fortunately, technology has come a long way, and we can now grade a range of interesting types of homework. In addition to multiple choice and the kinds of short answer questions that you saw in the video, we can also grade math, mathematical expressions as well as mathematical derivations. We can grade models, whether it’s financial models in a business class or physical models in a science or engineering class and we can grade some pretty sophisticated programming assignments.

Let me show you one that’s actually pretty simple but fairly visual. This is from Stanford’s Computer Science 101 class, and the students are supposed to color-correct that blurry red image. They’re typing their program into the browser, and you can see they didn’t get it quite right, Lady Liberty is still seasick. And so, the student tries again, and now they got it right, and they’re told that, and they can move on to the next assignment. This ability to interact actively with the material and be told when you’re right or wrong is really essential to student learning.

Now, of course we cannot yet grade the range of work that one needs for all courses. Specifically, what’s lacking is the kind of critical thinking work that is so essential in such disciplines as the humanities, the social sciences, business and others. So we tried to convince, for example, some of our humanities faculty that multiple choice was not such a bad strategy. That didn’t go over really well.

So we had to come up with a different solution. And the solution we ended up using is peer grading. It turns out that previous studies show, like this one by Saddler and Good, that peer grading is a surprisingly effective strategy for providing reproducible grades. It was tried only in small classes, but there it showed, for example, that these student-assigned grades on the y-axis are actually very well correlated with the teacher-assigned grade on the x-axis. What’s even more surprising is that self-grades, where the students grade their own work critically – so long as you incentivize them properly so they can’t give themselves a perfect score – are actually even better correlated with the teacher grades. And so this is an effective strategy that can be used for grading at scale, and is also a useful learning strategy for the students, because they actually learn from the experience. So we now have the largest peer-grading pipeline ever devised, where tens of thousands of students are grading each other’s work, and quite successfully, I have to say.

But this is not just about students sitting alone in their living room working through problems. Around each one of our courses, a community of students had formed, a global community of people around a shared intellectual endeavor. What you see here is a self-generated map from students in our Princeton Sociology 101 course, where they have put themselves on a world map, and you can really see the global reach of this kind of effort.

Students collaborated in these courses in a variety of different ways. First of all, there was a question and answer forum, where students would pose questions, and other students would answer those questions. And the really amazing thing is, because there were so many students, it means that even if a student posed a question at 3 o’clock in the morning, somewhere around the world, there would be somebody who was awake and working on the same problem. And so, in many of our courses, the median response time for a question on the question and answer forum was 22 minutes. Which is not a level of service I have ever offered to my Stanford students.

(Laughter)

And you can see from the student testimonials that students actually find that because of this large online community, they got to interact with each other in many ways that were deeper than they did in the context of the physical classroom. Students also self-assembled, without any kind of intervention from us, into small study groups. Some of these were physical study groups along geographical constraints and met on a weekly basis to work through problem sets. This is the San Francisco study group, but there were ones all over the world. Others were virtual study groups, sometimes along language lines or along cultural lines, and on the bottom left there, you see our multicultural universal study group where people explicitly wanted to connect with people from other cultures.

There are some tremendous opportunities to be had from this kind of framework. The first is that it has the potential of giving us a completely unprecedented look into understanding human learning. Because the data that we can collect here is unique. You can collect every click, every homework submission, every forum post from tens of thousands of students. So you can turn the study of human learning from the hypothesis-driven mode to the data-driven mode, a transformation that, for example, has revolutionized biology. You can use these data to understand fundamental questions like, what are good learning strategies that are effective versus ones that are not? And in the context of particular courses, you can ask questions like, what are some of the misconceptions that are more common and how do we help students fix them?

So here’s an example of that, also from Andrew’s Machine Learning class. This is a distribution of wrong answers to one of Andrew’s assignments. The answers happen to be pairs of numbers, so you can draw them on this two-dimensional plot. Each of the little crosses that you see is a different wrong answer. The big cross at the top left is where 2,000 students gave the exact same wrong answer. Now, if two students in a class of 100 give the same wrong answer, you would never notice. But when 2,000 students give the same wrong answer, it’s kind of hard to miss. So Andrew and his students went in, looked at some of those assignments, understood the root cause of the misconception, and then they produced a targeted error message that would be provided to every student whose answer fell into that bucket, which means that students who made that same mistake would now get personalized feedback telling them how to fix their misconception much more effectively.

So this personalization is something that one can then build by having the virtue of large numbers. Personalization is perhaps one of the biggest opportunities here as well, because it provides us with the potential of solving a 30-year-old problem. Educational researcher Benjamin Bloom, in 1984, posed what’s called the 2 sigma problem, which he observed by studying three populations. The first is the population that studied in a lecture-based classroom. The second is a population of students that studied using a standard lecture-based classroom, but with a mastery-based approach, so the students couldn’t move on to the next topic before demonstrating mastery of the previous one. And finally, there was a population of students that were taught in a one-on-one instruction using a tutor. The mastery-based population was a full standard deviation, or sigma, in achievement scores better than the standard lecture-based class, and the individual tutoring gives you 2 sigma improvement in performance.

To understand what that means, let’s look at the lecture-based classroom, and let’s pick the median performance as a threshold. So in a lecture-based class, half the students are above that level and half are below. In the individual tutoring instruction, 98 percent of the students are going to be above that threshold. Imagine if we could teach so that 98 percent of our students would be above average. Hence, the 2 sigma problem.

Because we cannot afford, as a society, to provide every student with an individual human tutor. But maybe we can afford to provide each student with a computer or a smartphone. So the question is, how can we use technology to push from the left side of the graph, from the blue curve, to the right side with the green curve? Mastery is easy to achieve using a computer, because a computer doesn’t get tired of showing you the same video five times. And it doesn’t even get tired of grading the same work multiple times, we’ve seen that in many of the examples that I’ve shown you. And even personalization is something that we’re starting to see the beginnings of, whether it’s via the personalized trajectory through the curriculum or some of the personalized feedback that we’ve shown you. So the goal here is to try and push, and see how far we can get towards the green curve.

So, if this is so great, are universities now obsolete? Well, Mark Twain certainly thought so. He said that, “College is a place where a professor’s lecture notes go straight to the students’ lecture notes, without passing through the brains of either.”

(Laughter)

I beg to differ with Mark Twain, though. I think what he was complaining about is not universities but rather the lecture-based format that so many universities spend so much time on. So let’s go back even further, to Plutarch, who said that, “The mind is not a vessel that needs filling, but wood that needs igniting.” And maybe we should spend less time at universities filling our students’ minds with content by lecturing at them, and more time igniting their creativity, their imagination and their problem-solving skills by actually talking with them.

So how do we do that? We do that by doing active learning in the classroom. So there’s been many studies, including this one, that show that if you use active learning, interacting with your students in the classroom, performance improves on every single metric – on attendance, on engagement and on learning as measured by a standardized test. You can see, for example, that the achievement score almost doubles in this particular experiment. So maybe this is how we should spend our time at universities.

So to summarize, if we could offer a top quality education to everyone around the world for free, what would that do? Three things. First it would establish education as a fundamental human right, where anyone around the world with the ability and the motivation could get the skills that they need to make a better life for themselves, their families and their communities.

Second, it would enable lifelong learning. It’s a shame that for so many people, learning stops when we finish high school or when we finish college. By having this amazing content be available, we would be able to learn something new every time we wanted, whether it’s just to expand our minds or it’s to change our lives.

And finally, this would enable a wave of innovation, because amazing talent can be found anywhere. Maybe the next Albert Einstein or the next Steve Jobs is living somewhere in a remote village in Africa. And if we could offer that person an education, they would be able to come up with the next big idea and make the world a better place for all of us.

Thank you very much.

LeetCode - Algorithms - 137. Single Number II

Problem

137. Single Number II

Java

Bitwise

We can design the digital logic what we need so the only one can still be extracted.

© https://gist.githubusercontent.com/lenchen1112/77dfd4afae0098dbe3199e4b70fa6a2b/raw/ceb58d8d505ddab95b133eb527235eaa77be2a1a/137_single_number_II.py

1
2
3
4
5
6
7
8
9
10
class Solution {
public int singleNumber(int[] nums) {
int lowBits = 0, highBits = 0;
for (int num : nums) {
lowBits = ~highBits & (lowBits ^ num);
highBits = ~lowBits & (highBits ^ num);
}
return lowBits;
}
}

Submission Detail

  • 14 / 14 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number II.
  • Memory Usage: 38.8 MB, less than 49.17% of Java online submissions for Single Number II.

LeetCode - Algorithms - 27. Remove Element

Problem

27. Remove Element

javascript

Array.prototype.splice()

1

© 9 Ways to Remove Elements From A JavaScript Array - Plus How to Safely Clear JavaScript Arrays - Removing Array Items By Value Using Splice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
for(var i = 0; i < nums.length; i++){
if ( nums[i] === val) {
nums.splice(i, 1);
i--;
}
}
return nums.length;
};

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 76 ms, faster than 85.28% of JavaScript online submissions for Remove Element.
  • Memory Usage: 38.6 MB, less than 69.26% of JavaScript online submissions for Remove Element.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
var index=nums.indexOf(val);
while (index !== -1) {
index = nums.indexOf(val);
if (index!==-1)
nums.splice(index, 1);
}
return nums.length;
};

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 80 ms, faster than 65.29% of JavaScript online submissions for Remove Element.
  • Memory Usage: 38.6 MB, less than 48.89% of JavaScript online submissions for Remove Element.

3

© The Fastest Way to Remove a Specific Item from an Array in JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let index
while((index = nums.indexOf(val)) > -1)
{
nums.splice(index, 1)
}
return nums.length;
};

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 80 ms, faster than 65.29% of JavaScript online submissions for Remove Element.
  • Memory Usage: 38.9 MB, less than 18.66% of JavaScript online submissions for Remove Element.

Two Pointers

Translation of © Solution - Approach 1: Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
var i=0;
for(var j=0;j<nums.length;j++) {
if (nums[j]!=val) {
nums[i] = nums[j];
i++;
}
}
return i;
};

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 76 ms, faster than 85.28% of JavaScript online submissions for Remove Element.
  • Memory Usage: 38.7 MB, less than 48.89% of JavaScript online submissions for Remove Element.

Java

Two Pointers

1

© Solution - Approach 1: Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
}
return i;
}
}

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Element.
  • Memory Usage: 37.6 MB, less than 48.38% of Java online submissions for Remove Element.

2

© Solution - Approach 2: Two Pointers - when elements to remove are rare

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
for (int i = 0; i < n; ) {
if (nums[i] == val) {
nums[i] = nums[n - 1];
n--;
} else
i++;
}
return n;
}
}

Submission Detail

  • 113 / 113 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Element.
  • Memory Usage: 37.7 MB, less than 48.38% of Java online submissions for Remove Element.

LeetCode - Algorithms - 1143. Longest Common Subsequence

Problem

1143. Longest Common Subsequence

The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

For the general case of an arbitrary number of input sequences, the problem is NP-hard. When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming.

The LCS problem has an optimal substructure: the problem can be broken down into smaller, simpler subproblems, which can in turn be broken down into simpler subproblems, and so on, until, finally, the solution becomes trivial. LCS in particular has overlapping subproblems: the solutions to high-level subproblems often reuse solutions to lower level subproblems. Problems with these two properties are amenable to dynamic programming approaches, in which subproblem solutions are memoized, that is, the solutions of subproblems are saved for reuse.

Java

Hunt–Szymanski algorithm

Translation of © Hunt-Szymanski Algorithm(Match-List, 1977)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
final int LEN1 = text1.length(), LEN2 = text2.length();
return huntSzymanski_lcs(text1.toCharArray(), text2.toCharArray(), LEN1, LEN2);
}

private int huntSzymanski_lcs(char[] stringA, char[] stringB, int m, int n) {
final int alphabet_size = 256;
int i, j, k, LCS, high, low, mid;
int[][] matchlist = new int[alphabet_size][];
int[] L;
for (i = 0; i < alphabet_size; i++) {
matchlist[i] = new int[n + 2];
}
L = new int[n + 1];

// make the matchlist
for (i = 0; i < m; i++) {
if (matchlist[stringA[i]][0] == 0) {
matchlist[stringA[i]][0] = 0;

for (k = 1, j = n - 1; j >= 0; j--) {
if (stringA[i] == stringB[j]) {
matchlist[stringA[i]][k] = j + 1;
k++;
}
matchlist[stringA[i]][k] = -1;
}
}
}

// finding the LCS
for (LCS = 0, i = 0; i < m; i++) {
for (j = 0; matchlist[stringA[i]][j] != -1; j++) {
// if the number bigger then the biggest number in the L, LCS + 1
if (matchlist[stringA[i]][j] > L[LCS]) {
LCS++;
L[LCS] = matchlist[stringA[i]][j];
}
// else, do the binary search to find the place to insert the number
else {
high = LCS;
low = 0;
k = 0;
while (true) {
mid = low + ((high - low) / 2);
if (L[mid] == matchlist[stringA[i]][j]) {
k = 1;
break;
}
if (high - low <= 1) {
mid = high;
break;
}
if (L[mid] > matchlist[stringA[i]][j]) {
high = mid;
} else if (L[mid] < matchlist[stringA[i]][j]) {
low = mid;
}
}
if (k == 0) {
L[mid] = matchlist[stringA[i]][j];
}
}
}
}
return LCS;
}
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 12 ms, faster than 32.13% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 39.2 MB, less than 92.10% of Java online submissions for Longest Common Subsequence.

Dynamic Programming

bottom-up approach

Oftentimes I found Wikipedia is helpful when doing leetcode algorithm problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
final int LEN1 = text1.length(), LEN2 = text2.length();
int[][] C = new int[LEN1 + 1][LEN2 + 1];
for (int i = 1; i <= LEN1; i++) {
for (int j = 1; j <= LEN2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
C[i][j] = C[i - 1][j - 1] + 1;
} else {
C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
}
}
}
return C[LEN1][LEN2];
}
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 18 ms, faster than 17.54% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 42.8 MB, less than 51.59% of Java online submissions for Longest Common Subsequence.

top-down approach (momoized version)

© https://www.techiedelight.com/longest-common-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
final int LEN1 = text1.length(), LEN2 = text2.length();
Map<String, Integer> map = new HashMap<String, Integer>();
return lcsLength(text1, text2, LEN1, LEN2, map);
}

private int lcsLength(String X, String Y, int m, int n, Map<String, Integer> lookup) {
// return if we have reached the end of either string
if (m == 0 || n == 0)
return 0;

// construct an unique map key from dynamic elements of the input
String key = m + "|" + n;

// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (!lookup.containsKey(key)) {
// if last character of X and Y matches
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
lookup.put(key, lcsLength(X, Y, m - 1, n - 1, lookup) + 1);

} else {
// else if last character of X and Y don't match
lookup.put(key, Integer.max(lcsLength(X, Y, m, n - 1, lookup), lcsLength(X, Y, m - 1, n, lookup)));
}
}

// return the subproblem solution from the map
return lookup.get(key);
}
}

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 295 ms, faster than 5.04% of Java online submissions for Longest Common Subsequence.
  • Memory Usage: 167 MB, less than 5.04% of Java online submissions for Longest Common Subsequence.

javascript

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
var LEN1 = text1.length, LEN2 = text2.length;
var C = [];
for (var i = 0; i <= LEN1; i++) {
C.push([]);
for (var j = 0; j <= LEN2; j++) {
C[i].push(0);
}
}
for (var i = 1; i <= LEN1; i++) {
for (var j = 1; j <= LEN2; j++) {
if (text1[i - 1] == text2[j - 1]) {
C[i][j] = C[i - 1][j - 1] + 1;
} else {
C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
}
}
}
return C[LEN1][LEN2];
};

Submission Detail

  • 43 / 43 test cases passed.
  • Runtime: 116 ms, faster than 60.08% of JavaScript online submissions for Longest Common Subsequence.
  • Memory Usage: 53.4 MB, less than 22.63% of JavaScript online submissions for Longest Common Subsequence.

LeetCode - Algorithms - 703. Kth Largest Element in a Stream

Problem

703. Kth Largest Element in a Stream

Java

priority queue - Java collections framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.PriorityQueue;

class KthLargest {
private int k;
private PriorityQueue<Integer> minHeap;

public KthLargest(int k, int[] nums) {
this.k = k;
minHeap = new PriorityQueue<Integer>(k);
for(int i : nums) {
minHeap.offer(i);
if (minHeap.size()>k)
minHeap.poll();
}
}

public int add(int val) {
minHeap.offer(val);
if (minHeap.size()>k)
minHeap.poll();
return minHeap.peek();
}
}

/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 17 ms, faster than 49.28% of Java online submissions for Kth Largest Element in a Stream.
  • Memory Usage: 44.3 MB, less than 60.24% of Java online submissions for Kth Largest Element in a Stream.

On Hearing a Symphony of Beethoven

by Edna St. Vincent Millay

Sweet sounds, oh, beautiful music, do not cease!
Reject me not into the world again.
With you alone is excellence and peace,
Mankind made plausible, his purpose plain.
Enchanted in your air benign and shrewd,
With limbs a-sprawl and empty faces pale,
The spiteful and the stingy and the rude
Sleep like the scullions in the fairy-tale.
This moment is the best the world can give:
The tranquil blossom on the tortured stem.
Reject me not, sweet sounds; oh, let me live,
Till Doom espy my towers and scatter them,
A city spell-bound under the aging sun.
Music my rampart, and my only one.


  • On Hearing a Symphony of Beethoven
  • One of the most significant facts, for the understanding of Beethoven, is that his work shows an organic development up until the very end… The greatest music Beethoven ever wrote is to be found in the last string quartets, and the music of every decade before the final period was greater than its predecessor. (Shakespeare, Newton, and Beethoven: Or, Patterns of Creativity, a talk by Subrahmanyan Chandrasekhar)

LeetCode - Algorithms - 268. Missing Number

Problem

268. Missing Number

Java

leetcode solution

© Approach 3 Bit Manipulation

1
2
3
4
5
6
7
8
9
class Solution {
public int missingNumber(int[] nums) {
final int N = nums.length;
int r = N;
for (int i = 0; i < N; i++)
r ^= i ^ nums[i];
return r;
}
}

Submission Detail

  • 122 / 122 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Number.
  • Memory Usage: 47.8 MB, less than 5.40% of Java online submissions for Missing Number.

2

© Bitwise operators — Facts and Hacks - Compute XOR from 1 to n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int missingNumber(int[] nums) {
final int N = nums.length;
int x = computeXOR(N);
x = 0 ^ x;
int y = nums[0];
for (int i = 1; i < N; i++) {
y = y ^ nums[i];
}
return x ^ y;
}

private int computeXOR(int n) {
if (n % 4 == 0) return n;
if (n % 4 == 1) return 1;
if (n % 4 == 2) return n + 1;
else return 0;
}
}

Submission Detail

  • 122 / 122 test cases passed.
  • Runtime: 1 ms, faster than 40.83% of Java online submissions for Missing Number.
  • Memory Usage: 48 MB, less than 5.40% of Java online submissions for Missing Number.