Problem

796. Rotate String

Java

my solution - brute method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public boolean rotateString(String A, String B) {
        final int len_A = A.length();
        final int len_B = B.length();
        if (len_A != len_B)
            return false;
        if (A.isEmpty() && B.isEmpty())
            return true;
        for(int i=0; i<len_A; i++) {
            A = A.substring(1)+A.charAt(0);
            if (B.equals(A))
                return true;
        }
        return false;
    }
}

Submission Detail

• 45 / 45 test cases passed.
• Runtime: 5 ms, faster than 9.75% of Java online submissions for Rotate String.
• Memory Usage: 38.4 MB, less than 32.29% of Java online submissions for Rotate String.

trick method

© 20+ basic Algorithms Problems from Coding Interviews 19. How to check if two String is rotations of each other?

There is a simple trick to solve this problem, just concatenate the String with itself and check if the rotation exists there. You can do that by using indexOf or substring method. If the concatenated String contains rotation then given String is a rotation of former.

1
2
3
4
5
6
7
8
9
10

class Solution {
    public boolean rotateString(String A, String B) {
        final int len_A = A.length();
        final int len_B = B.length();
        if (len_A != len_B)
            return false;
        String s = A + A;
        return s.indexOf(B) != -1;
    }
}

Submission Detail

• 45 / 45 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate String.
• Memory Usage: 37.2 MB, less than 75.85% of Java online submissions for Rotate String.

Problem

507. Perfect Number

Java

my solution

There is one fact that odd perfect numbers are greater than \( 10^{1500} \) if exist. By Euclid–Euler theorem, there is a one-to-one relationship between even perfect numbers and Mersenne primes. Even perfect number have the form as \( 2^{p−1}(2^p−1) \).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean checkPerfectNumber(int num) {
		if ((num & 1) == 1)
			return false;
		else {
			if (num == 0)
				return false;
			int n = num;
			int p = 0;
			for (; (n & 1) == 0; p++) {
				n = n >> 1;
			}
			int x = (2 << (p - 1)) * ((2 << p) - 1);
			return num == x;
		}
    }
}

Submission Detail

• 156 / 156 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Perfect Number.
• Memory Usage: 37.7 MB, less than 23.24% of Java online submissions for Perfect Number.

Problem

392. Is Subsequence

Java

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isSubsequence(String s, String t) {
        boolean b = true;
        final int len_s = s.length();
        if (len_s > 0) {
            int i = t.indexOf(s.charAt(0));
            if (i != -1)
                return isSubsequence(s.substring(1), t.substring(++i));
            else
                return false;
        }
        return b;
    }
}

Submission Detail

• 15 / 15 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Is Subsequence.
• Memory Usage: 37.5 MB, less than 62.77% of Java online submissions for Is Subsequence.

Iterative

© JAVA clean, quick, concise solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isSubsequence(String s, String t) {
        final int len_s = s.length();
        final int len_t = t.length();
        if (len_s > len_t)
            return false;
        int i = 0;
        for (int j = 0; j < len_t && i < len_s; ) {
            if (s.charAt(i) == t.charAt(j)) i++;
            j++;
        }
        return i >= len_s;        
    }
}

Submission Detail

• 15 / 15 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Is Subsequence.
• Memory Usage: 37.1 MB, less than 39.06% of Java online submissions for Is Subsequence.

It is in Apple’s DNA that technology alone is not enough — it’s technology married with liberal arts, married with the humanities, that yields us the results that make our heart sing. — Steve Jobs

You’ve all been in a bar, right?

(Laughter)

But have you ever gone to a bar and come out with a $200 million business? That’s what happened to us about 10 years ago. We’d had a terrible day. We had this huge client that was killing us. We’re a software consulting firm, and we couldn’t find a very specific programming skill to help this client deploy a cutting-edge cloud system. We have a bunch of engineers, but none of them could please this client. And we were about to be fired.

So we go out to the bar, and we’re hanging out with our bartender friend Jeff, and he’s doing what all good bartenders do: he’s commiserating with us, making us feel better, relating to our pain, saying, “Hey, these guys are overblowing it. Don’t worry about it.” And finally, he deadpans us and says, “Why don’t you send me in there? I can figure it out.” So the next morning, we’re hanging out in our team meeting, and we’re all a little hazy …

(Laughter)

and I half-jokingly throw it out there. I say, “Hey, I mean, we’re about to be fired.” So I say, “Why don’t we send in Jeff, the bartender?”

(Laughter)

And there’s some silence, some quizzical looks. Finally, my chief of staff says, “That is a great idea.”

(Laughter)

“Jeff is wicked smart. He’s brilliant. He’ll figure it out. Let’s send him in there.”

Now, Jeff was not a programmer. In fact, he had dropped out of Penn as a philosophy major. But he was brilliant, and he could go deep on topics, and we were about to be fired. So we sent him in. After a couple days of suspense, Jeff was still there. They hadn’t sent him home. I couldn’t believe it. What was he doing?

Here’s what I learned. He had completely disarmed their fixation on the programming skill. And he had changed the conversation, even changing what we were building. The conversation was now about what we were going to build and why. And yes, Jeff figured out how to program the solution, and the client became one of our best references.

Back then, we were 200 people, and half of our company was made up of computer science majors or engineers, but our experience with Jeff left us wondering: Could we repeat this through our business? So we changed the way we recruited and trained. And while we still sought after computer engineers and computer science majors, we sprinkled in artists, musicians, writers … and Jeff’s story started to multiply itself throughout our company. Our chief technology officer is an English major, and he was a bike messenger in Manhattan. And today, we’re a thousand people, yet still less than a hundred have degrees in computer science or engineering. And yes, we’re still a computer consulting firm. We’re the number one player in our market. We work with the fastest-growing software package to ever reach 10 billion dollars in annual sales. So it’s working.

Meanwhile, the push for STEM-based education in this country – science, technology, engineering, mathematics – is fierce. It’s in all of our faces. And this is a colossal mistake. Since 2009, STEM majors in the United States have increased by 43 percent, while the humanities have stayed flat. Our past president dedicated over a billion dollars towards STEM education at the expense of other subjects, and our current president recently redirected 200 million dollars of Department of Education funding into computer science. And CEOs are continually complaining about an engineering-starved workforce. These campaigns, coupled with the undeniable success of the tech economy – I mean, let’s face it, seven out of the 10 most valuable companies in the world by market cap are technology firms – these things create an assumption that the path of our future workforce will be dominated by STEM.

I get it. On paper, it makes sense. It’s tempting. But it’s totally overblown. It’s like, the entire soccer team chases the ball into the corner, because that’s where the ball is. We shouldn’t overvalue STEM. We shouldn’t value the sciences any more than we value the humanities. And there are a couple of reasons.

Number one, today’s technologies are incredibly intuitive. The reason we’ve been able to recruit from all disciplines and swivel into specialized skills is because modern systems can be manipulated without writing code. They’re like LEGO: easy to put together, easy to learn, even easy to program, given the vast amounts of information that are available for learning. Yes, our workforce needs specialized skill, but that skill requires a far less rigorous and formalized education than it did in the past.

Number two, the skills that are imperative and differentiated in a world with intuitive technology are the skills that help us to work together as humans, where the hard work is envisioning the end product and its usefulness, which requires real-world experience and judgment and historical context. What Jeff’s story taught us is that the customer was focused on the wrong thing. It’s the classic case: the technologist struggling to communicate with the business and the end user, and the business failing to articulate their needs. I see it every day. We are scratching the surface in our ability as humans to communicate and invent together, and while the sciences teach us how to build things, it’s the humanities that teach us what to build and why to build them. And they’re equally as important, and they’re just as hard.

It irks me … when I hear people treat the humanities as a lesser path, as the easier path. Come on! The humanities give us the context of our world. They teach us how to think critically. They are purposely unstructured, while the sciences are purposely structured. They teach us to persuade, they give us our language, which we use to convert our emotions to thought and action. And they need to be on equal footing with the sciences. And yes, you can hire a bunch of artists and build a tech company and have an incredible outcome.

Now, I’m not here today to tell you that STEM’s bad. I’m not here today to tell you that girls shouldn’t code.

(Laughter)

Please. And that next bridge I drive over or that next elevator we all jump into – let’s make sure there’s an engineer behind it.

(Laughter)

But to fall into this paranoia that our future jobs will be dominated by STEM, that’s just folly. If you have friends or kids or relatives or grandchildren or nieces or nephews … encourage them to be whatever they want to be.

(Applause)

The jobs will be there. Those tech CEOs that are clamoring for STEM grads, you know what they’re hiring for? Google, Apple, Facebook. Sixty-five percent of their open job opportunities are non-technical: marketers, designers, project managers, program managers, product managers, lawyers, HR specialists, trainers, coaches, sellers, buyers, on and on. These are the jobs they’re hiring for. And if there’s one thing that our future workforce needs – and I think we can all agree on this – it’s diversity. But that diversity shouldn’t end with gender or race. We need a diversity of backgrounds and skills, with introverts and extroverts and leaders and followers. That is our future workforce. And the fact that the technology is getting easier and more accessible frees that workforce up to study whatever they damn well please.

Thank you.

(Applause)

Steve Jobs: “Technology Alone Is Not Enough”

by Jonathan Coulton

Verse 1

Code Monkey get up, get coffee
Code Monkey go to job
Code Monkey have boring meeting
With boring manager Rob
Rob say Code Monkey very diligent
But his output stink
His code not “functional” or “elegant”
What do Code Monkey think?

Pre-Chorus 1

Code Monkey think maybe manager want to write god-damned login page himself
Code Monkey not say it out loud
Code Monkey not crazy, just proud

Chorus

Code Monkey like Fritos
Code Monkey like Tab and Mountain Dew
Code Monkey very simple man
With big warm fuzzy secret heart
Code Monkey like you
Code Monkey like you

Verse 2

Code Monkey hang around at front desk
Tell you sweater look nice
Code Monkey offer buy you soda
Bring you cup, bring you ice
You say no thank you for the soda cause
Soda make you fat
Anyway you busy with the telephone
No time for chat

Pre-Chorus 2

Code Monkey have long walk back to cubicle
He sit down pretend to work
Code Monkey not thinking so straight
Code Monkey not feeling so great

Chorus

Code Monkey like Fritos
Code Monkey like Tab and Mountain Dew
Code Monkey very simple man
With big warm fuzzy secret heart
Code Monkey like you
Code Monkey like you a lot

Verse 3

Code Monkey have every reason
To get out this place
Code Monkey just keep on working
See your soft pretty face
Much rather wake up, eat a coffee cake
Take bath, take nap
This job “fulfilling in creative way”
Such a load of crap

Pre-Chorus 3

Code Monkey think someday he have everything
Even pretty girl like you
Code Monkey just waiting for now
Code Monkey say someday, somehow

Chorus

Code Monkey like Fritos
Code Monkey like Tab and Mountain Dew
Code Monkey very simple man
With big warm fuzzy secret heart
Code Monkey like you
Code Monkey like you

• Code Monkey (song)
• Code Monkey
• Code Monkey/Lyrics

concepts

The repository holds all versions of the content, while the working directory is the place where you modify the code. You checkout code from the repository to the working directory and commit changes you’ve made in this working directory back into a new version of the content in the repository.

The main principle of Git

First, Git handles content in snapshots, one for each commit, and knows how to apply or roll back the change sets between two snapshots. This is an important concept. In my opinion, understanding the concept of applying and rolling back change sets makes Git much easier to understand and work with. This is the real basic principle. Anything else follows from this.

Naming

Snapshots are the main elements in Git. They are named with the commit ID, which is a hash ID like “c69e0cc32f3c1c8f2730cade36a8f75dc8e3d480” for example.

Note that the term commit, is used both as verb for creating a snapshot and as name for the resulting snapshot.

Normally you don’t have to work with the commit IDs; instead you work with branches.

In Git, a stream of changes is an ordered list of change sets as they are applied one after another to go from one snapshot to the next. A branch in Git is only a named pointer to a specific snapshot. It notes the place where new changes should be applied to when this branch is used. When a change is applied to a branch, then also the branch label moves to the new commit.

How does Git know where to put the change from a workspace? That is where HEAD points. The HEAD of the development is where you last checked out your workspace and, more importantly, where to commit the changes. It usually points to the branch you last checked out.

The tag command names a commit and allows you to address the individual commit with a readable name. Basically, a tag is an alias for a commit ID but commits can also be addressed with some shortcuts.

gitrevisions is a revision parameter typically, but not necessarily, names a commit object.

Because names like tags or branch names are references to commits, they are called refnames. A reflog shows what has been changed during the lifetime of the name, from when it was created (usually by a branch) until the current state.

Branching

The concept behind branching is that each snapshot can have more than one child. Applying a second change set to the same snapshot creates a new, separate stream of development. And if it is named, it is called a branch.

Branches are created with the git branch <branch name> command on the current HEAD, or git branch <branch name> <commit id> on any valid snapshot version. This creates a new branch pointer in the repository. Be careful, branching this way leaves your workspace at the old branch. You need to checkout the new branch first. With git checkout -b <branch name> the new branch is created, and your workspace is also moved to the new branch.

Two other commands are rather useful:

• git diff <branch> -- <path> as already mentioned above prints a diff of the given path (file or directory) between the current working directory and the specified branch.
• git checkout <branch> -- <path> checks out files from a different branch into the working directory, so you can pick changes from another branch.

useful commands concerning to branch

• git branch — creates a new branch from the current HEAD (working directory).
• git checkout -b — creates a new branch from the current HEAD, and switches the working directory to the new branch.
• git diff – — shows the difference of between the working directory and the given branch.
• git checkout – — checks out files from the given branch into the working directory.
• git merge — merges the given branch into the current branch.
• git merge -abort — aborts a merge that resulted in conflicts.

Merging

When you implemented your new feature, you checked it into the repository, for example, on your “feature” branch. When the feature is finished, you need to merge it back into the master branch. You do this by checking out the master branch, and use git merge <branch name>. Git then merges the changes from the given branch into the checked out branch. What Git does to achieve this is it applies all of the change sets from the feature branch onto the tip of the master branch.

Depending on the type of changes in the two branches, and possible conflicts, there are three possibilities that can happen.

• Fast forward merge
• No-conflict merge
• Conflicting merge

merge conflict

如何消除对合并时出现冲突的恐惧心理？

• 首先可以放心的是，你随时可以撤销一个合并操作，并且返回到冲突发生之前的状态。
• 只要在命令行界面中键入 git merge --abort 命令，你的合并操作就会被安全的撤销。
• 当你解决完冲突，并且在合并完成后发现一个错误，仍然还有机会来简单地撤销它。你只须键入 git reset --hard 命令，系统就会回滚到那个合并开始前的状态

git status 显示 unmerged paths，表明存在冲突

发生冲突的文件的内容

• Git 会非常友好地把文件中那些有问题的区域在 <<<<<<< HEAD 和 >>>>>>> other/branch/name 之间标记出来。

• 第一个标记后的内容源于当前分支。在尖括号之后，Git 会告诉我们这些改动是从哪里（哪个分支）来的。然后有冲突的改动会被 ======= 分割起来。

• 使用一个专门的合并工具可以使清理这些冲突变得更容易，你可以通过 git config 命令来设置这个合并工具给 Git。之后当发生合并冲突时，你可以使用 git mergetool 命令来调用这个工具。

• 手动处理冲突，你必须手动地将文件标记为已解决状态（通过执行命令 git add <filename>）。最终，当所有的冲突被解决后，你必须通过一个正常的提交操作来完成这个清理合并冲突的工作。

resources

• 了解 Git 的工作方式，而不仅仅是了解命令
• CS Visualized: Useful Git Commands
• Learn the workings of Git, not just the commands
• Learn git concepts, not commands

by Muriel Rukeyser

I

Whoever despises the clitoris despises the penis
Whoever despises the penis despises the cunt
Whoever despises the cunt despises the life of the child.

Resurrection music, silence, and surf.

II

No longer speaking
Listening with the whole body
And with every drop of blood
Overtaken by silence

But this same silence is become speech
With the speed of darkness.

III

Stillness during war, the lake.
The unmoving spruces.
Glints over the water.
Faces, voices. You are far away.
A tree that trembles.

I am the tree that trembles and trembles.

IV

After the lifting of the mist
after the lift of the heavy rains
the sky stands clear
and the cries of the city risen in day
I remember the buildings are space
walled, to let space be used for living
I mind this room is space
this drinking glass is space
whose boundary of glass
lets me give you drink and space to drink
your hand, my hand being space
containing skies and constellations
your face
carries the reaches of air
I know I am space
my words are air.

V

Between between
the man : act exact
woman : in curve senses in their maze
frail orbits, green tries, games of stars
shape of the body speaking its evidence

VI

I look across at the real
vulnerable involved naked
devoted to the present of all I care for
the world of its history leading to this moment.

VII

Life the announcer.
I assure you
there are many ways to have a child.
I bastard mother
promise you
there are many ways to be born.
They all come forth
in their own grace.

VIII

Ends of the earth join tonight
with blazing stars upon their meeting.
These sons, these sons
fall burning into Asia.

IX

Time comes into it.
Say it. Say it.

The universe is made of stories,
not of atoms.

X

Lying
blazing beside me
you rear beautifully and up—
your thinking face—
erotic body reaching
in all its colors and lights—
your erotic face
colored and lit—
not colored body-and-face
but now entire,
colors lights the world thinking and reaching.

XI

The river flows past the city.

Water goes down to tomorrow
making its children I hear their unborn voices
I am working out the vocabulary of my silence.

XII

Big-boned man young and of my dream
Struggles to get the live bird out of his throat.
I am he am I? Dreaming?
I am the bird am I? I am the throat?

A bird with a curved beak.
It could slit anything, the throat-bird.
Drawn up slowly. The curved blades, not large.
Bird emerges wet being born
Begins to sing.

XIII

My night awake
staring at the broad rough jewel
the copper roof across the way
thinking of the poet
yet unborn in this dark
who will be the throat of these hours.
No. Of those hours.
Who will speak these days,
if not I,
if not you?

• Muriel Rukeyser, “The Speed of Darkness” from The Collected Poems of Muriel Rukeyser. Copyright © 2006 by Muriel Rukeyser. Reprinted by permission of International Creative Management.
• Source: Out of Silence: Selected Poems (TriQuarterly Books, 1992)

• The Speed of Darkness
• Muriel Rukeyser

Problem

349. Intersection of Two Arrays

Java

brute force method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        final int len1 = nums1.length;
        final int len2 = nums2.length;

        Set<Integer> ret = new HashSet<Integer>();
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (nums1[i] == nums2[j])
                    ret.add(nums1[i]);
            }
        }
        int[] r = new int[ret.size()];
        int k = 0;
        for (Integer e : ret)
            r[k++] = e.intValue();
        return r;        
    }
}

Submission Detail

• 60 / 60 test cases passed.
• Runtime: 8 ms, faster than 11.36% of Java online submissions for Intersection of Two Arrays.
• Memory Usage: 39.9 MB, less than 54.69% of Java online submissions for Intersection of Two Arrays.

retainAll of HashSet in Java collections framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int i = 0; i < nums1.length; i++)
            set1.add(nums1[i]);
        for (int i = 0; i < nums2.length; i++)
            set2.add(nums2[i]);
        set1.retainAll(set2);
        int[] r = new int[set1.size()];
        int k = 0;
        for (Integer e : set1)
            r[k++] = e.intValue();
        return r;        
    }
}

Submission Detail

• 60 / 60 test cases passed.
• Runtime: 2 ms, faster than 99.40% of Java online submissions for Intersection of Two Arrays.
• Memory Usage: 39.4 MB, less than 90.00% of Java online submissions for Intersection of Two Arrays.

作者：文嘉

昨日歌

昨日兮昨日，
昨日何其好！
昨日過去了，
今日徒懊惱。
世人但知悔昨日，
不覺今日又過了。
水去日日流，
花落日日少，
成事立業在今日，
莫待明朝悔今朝。

今日歌

今日復今日，今日何其少！
今日又不為，此事何時了？！
人生百年幾今日，今日不為真可惜！
若言姑待明朝至，明朝又有明朝事。
為君聊賦《今日詩》，努力請從今日始！

明日歌

明日復明日，明日何其多！
我生待明日，萬事成蹉跎。
世人苦被明日累，春去秋來老將至。
朝看水東流，暮看日西墜，
百年明日能幾何？請君聽我《明日歌》。

I can solve some easy problem on leetcode directly without IDE now. A little bit better.

Problem

1470. Shuffle the Array

Java

1

1
2
3
4
5
6
7
8

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] r = new int[2 * n];
        for (int i = 0; i < 2 * n; i++)
            r[i] = (i & 1) == 1 ? nums[n + i / 2] : nums[i / 2];
        return r;
    }
}

Submission Detail

• 53 / 53 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Shuffle the Array.
• Memory Usage: 39.3 MB, less than 95.59% of Java online submissions for Shuffle the Array.

2

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] r = new int[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            if ((i & 1) == 1) {
                r[i] = nums[n + i / 2];
            } else {
                r[i] = nums[i / 2];
            }
        }
        return r;
    }
}

Submission Detail

• 53 / 53 test cases passed.
• Runtime: 0 ms
• Memory Usage: 39.7 MB, Your memory usage beats 47.43 % of java submissions.

3

1
2
3
4
5
6
7
8

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] r = new int[2 * n];
        for (int i = 0; i < 2 * n; i++)
            r[i] = nums[(i & 1) * n + i / 2];
        return r;
    }
}

Submission Detail

• 53 / 53 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Shuffle the Array.
• Memory Usage: 39.6 MB, less than 56.99% of Java online submissions for Shuffle the Array.

4

1
2
3
4
5
6
7
8

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] r = new int[2 * n];
        for (int i = 0; i < 2 * n; i++)
            r[i] = nums[((i & 1) == 1 ? n : 0) + i / 2];
        return r;
    }
}

Submission Detail

• 53 / 53 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Shuffle the Array.
• Memory Usage: 39.2 MB, less than 95.96% of Java online submissions for Shuffle the Array.