Weekly #6

@Date : 2019-04-29 11:18:11

@Author : Lewis Tian (taseikyo@gmail.com)

@Link : https://taseikyo.github.io

@Range : 2019/05/05 - 2019/05/12

Photo by Ray Hennessy on Unsplash

algorithm
review
tip
share

algorithm

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Solution

Because 'The majority element is the element that appears more than ⌊ n/2 ⌋ times.', we can sort the list and just return the value at [n/2]

nums.sort()
return nums[len(nums)//2]

Python

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution

This problem is interesting. I came up with 2 solutions: sorting and set(). But the requirements mention that the list is read only. So I had to resort to Solution. Surprisingly, the author proposed 3 approachs; #1, #2 were sorting and set() hahah. So I look through the #3.

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = nums[0]
        hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break

        # Find the "entrance" to the cycle.
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]

        return ptr1

And Discuss gave the same solution: Can it get any shorter? 2 c++ solutions. Using O(1) space without modifying-space-without-modifying)

Basically we treat the array elements as an index to another element, this produces a kind of linked list starting at the first element. As each element is in the range [1, n] and there are n + 1 elements, each element will point to a valid index. A cycle will be created when two (or more) duplicates point to the same element. All that remains is to find the start of the cycle.

@BITQinDynasty explained: 'The second phase will not be trapped into an endless loop. Here are the intuitive explanation. In the first phase, the distance tortoise traveled is t=x1+x2 , where x1 is the distance from the start point to the entrance of the loop and x2 is the distance traveled in the loop by tortoise, while the distance hare traveled is h=2t=2(x1+x2)=x1+x2+nC, where C is the length of the loop. Hence, we get that x1+x2 = nC, which means that the distance traveled by tortoise is a multiple of C. In the second phase, ptr1 and ptr2 begin at start point and the position of tortoise respectively. By moveing one step forward, the will finally meet and overlap with each other. The first time they overlap happens at the entrance point definitly.'

Python

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Solution

Use a queue to store nodes at each level.

Python

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution

I'm fucking Stupid!

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution

Quite easy to note that: F(1) = 1 F(2) = 2 F(n) = F(n-1) + F(n-2)

917. Reverse Only Letters

Given a string S, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S doesn't contain \ or "

Solution

Two pointers.

Python

557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Solution

Easy in Python.

Python

848. Shifting Letters

We have a string S of lowercase letters, and an integer array shifts.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.

Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.

Return the final string after all such shifts to S are applied.

Example 1:

Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters of S by 3, we have "dbc".
After shifting the first 2 letters of S by 5, we have "igc".
After shifting the first 3 letters of S by 9, we have "rpl", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Solution

520. Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital if it has more than one letter, like "Google".

Otherwise, we define that this word doesn't use capitals in a right way.

Example 1:

Input: "USA"
Output: True
Example 2:
Input: "FlaG"
Output: False
Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

Solution

383. Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note: You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution

Pretty interesting. My solution is similar to that of 100%, whereas my solution is 16.75%.

Maybe it is the magic of the pointers.

100%

bool canConstruct(char * ransomNote, char * magazine){
    int count[256] = {0};
    while(*magazine != '\0'){
        ++count[*magazine] ;
        ++magazine;
    }
    while(*ransomNote != '\0'){
        if(--count[*ransomNote] <0){
            return false;
        }
        ++ransomNote;
    }
    return true;
}

mine

bool canConstruct(char * ransomNote, char * magazine){
  int tab[26] = {0};
  int i;

  if (strlen(ransomNote) > strlen(magazine)) {
    return false;
  }

  for (i = 0; i < strlen(magazine); ++i) {
    ++tab[magazine[i]-'a'];
  }

  for (i = 0; i < strlen(ransomNote); ++i) {
    if(tab[ransomNote[i]-'a'] == 0) {
      return false;
    }
    --tab[ransomNote[i]-'a'];
  }
  return true;
}

review

This article talks about 996 - 9 a.m. to 9 p.m., six days a week.

996 is not new, and it is not a primarily Chinese problem. Japan has long suffered from this issue, and Japanese create a word 'Karōshi'.

tip

Go fmt Printf tricks

[ASPLOS'19] HawkEye: efficient Fine-grained OS Support for Huge Pages

Transparent huge page management is essential but complex. Effective and efficient algorithms are required in the OS to automatically balance the tradeoffs and provide performant and stable system behavior.

The authors expose some important subtleties related to huge page management in existing proposals, and propose a new set of algorithms to address them in HawkEye.

201905W1

Weekly #6

Table of Contents

algorithm

169. Majority Element

Solution

287. Find the Duplicate Number

Solution

102. Binary Tree Level Order Traversal

Solution

21. Merge Two Sorted Lists

Solution

70. Climbing Stairs

Solution

917. Reverse Only Letters

Solution

557. Reverse Words in a String III

Solution

848. Shifting Letters

Solution

520. Detect Capital

Solution

383. Ransom Note

Solution

review

tip

results matching ""

No results matching ""

Weekly #6

Table of Contents

algorithm

169. Majority Element

Solution

287. Find the Duplicate Number

Solution

102. Binary Tree Level Order Traversal

Solution

21. Merge Two Sorted Lists

Solution

70. Climbing Stairs

Solution

917. Reverse Only Letters

Solution

557. Reverse Words in a String III

Solution

848. Shifting Letters

Solution

520. Detect Capital

Solution

383. Ransom Note

Solution

review

tip

share

results matching ""

No results matching ""