2017年12月26日 星期二

[LeetCode] 447. Number of Boomerangs

轉自LeetCode

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Example:
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
<Solution>

2017年12月21日 星期四

[LeetCode] 443. String Compression

轉自LeetCode

Given an array of characters, compress it in-place.
The length after compression must always be smaller than or equal to the original array.
Every element of the array should be a character (not int) of length 1.
After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:
Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
Example 2:
Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.
Example 3:
Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.
Note:
  1. All characters have an ASCII value in [35, 126].
  2. 1 <= len(chars) <= 1000.
<Solution>

2017年12月18日 星期一

[LeetCode] 414. Third Maximum Number

轉自LeetCode

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
<Solution>

[LeetCode] 437. Path Sum III

轉自LeetCode

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
<Solution>

[LeetCode] 434. Number of Segments in a String

轉自LeetCode

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
<Solution>

2017年12月17日 星期日

[LeetCode] 409. Longest Palindrome

轉自LeetCode

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
<Solution>

2017年12月16日 星期六

[LeetCode] 405. Convert a Number to Hexadecimal

轉自LeetCode

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
Note:
  1. All letters in hexadecimal (a-f) must be in lowercase.
  2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
  3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
  4. You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:
Input:
26

Output:
"1a"
Example 2:
Input:
-1

Output:
"ffffffff"
<Solution>

[LeetCode] 404. Sum of Left Leaves

轉自LeetCode

Find the sum of all left leaves in a given binary tree.
Example:
    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
<Solution>

[LeetCode] 400. Nth Digit

轉自LeetCode

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3

Output:
3
Example 2:
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
<Solution>

[LeetCode] 389. Find the Difference

轉自LeetCode

Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.
<Solution>

[LeetCode] 387. First Unique Character in a String

轉自LeetCode

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
<Solution>

2017年12月15日 星期五

[LeetCode] 383. Ransom Note

轉自LeetCode

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>

[LeetCode] 371. Sum of Two Integers

轉自LeetCode

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
<Solution>

[LeetCode] 633. Sum of Square Numbers

轉自LeetCode

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False
<Solution>

[LeetCode] 367. Valid Perfect Square

轉自LeetCode

Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
<Solution>

2017年12月14日 星期四

[LeetCode] 350. Intersection of Two Arrays II

轉自LeetCode

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2, 2].
Note:
  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.
<Solution>

[LeetCode] 349. Intersection of Two Arrays

轉自LeetCode

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].
Note:
  • Each element in the result must be unique.
  • The result can be in any order.
<Solution>

2017年12月13日 星期三

[LeetCode] 557. Reverse Words in a String III

轉自LeetCode

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>

[LeetCode] 345. Reverse Vowels of a String

轉自LeetCode

Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
<Solution>

2017年12月11日 星期一

[LeetCode] 541. Reverse String II

轉自LeetCode

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Restrictions:
  1. The string consists of lower English letters only.
  2. Length of the given string and k will in the range [1, 10000]
<Solution>

[LeetCode] 303. Range Sum Query - Immutable

轉自LeetCode

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.
<Solution>

2017年12月10日 星期日

[LeetCode] 290. Word Pattern

轉自LeetCode

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
<Solution>

2017年12月9日 星期六

[LeetCode] 374. Guess Number Higher or Lower

轉自LeetCode

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-11, or 0):
-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.
<Solution>

[LeetCode] 278. First Bad Version

轉自LeetCode

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
<Solution>

[LeetCode] 257. Binary Tree Paths

轉自LeetCode

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:
["1->2->5", "1->3"]
<Solution>

2017年12月6日 星期三

[LeetCode] 438. Find All Anagrams in a String

轉自LeetCode

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
<Solution>

2017年12月4日 星期一

[LeetCode] 242. Valid Anagram

轉自LeetCode

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
<Solution>

2017年12月2日 星期六

[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

轉自LeetCode

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
<Solution>

[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree

轉自LeetCode

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
<Solution>

2017年12月1日 星期五

[LeetCode] 234. Palindrome Linked List

轉自LeetCode

Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
<Solution>

2017年11月30日 星期四

2017年11月27日 星期一

[LeetCode] 237. Delete Node in a Linked List

轉自LeetCode

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
<Solution>

[LeetCode] 283. Move Zeroes

轉自LeetCode

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.
<Solution>

2017年11月25日 星期六

[LeetCode] 220. Contains Duplicate III

轉自LeetCode

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

<Solution>

2017年11月24日 星期五

[LeetCode] 219. Contains Duplicate II

轉自LeetCode

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

<Solution>

2017年11月19日 星期日

[LeetCode] 217. Contains Duplicate

轉自LeetCode

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

<Solution>

[LeetCode] 204. Count Primes

轉自LeetCode

Description:
Count the number of prime numbers less than a non-negative number, n.
<Solution>

2017年10月12日 星期四

[LeetCode] 203. Remove Linked List Elements

轉自LeetCode

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
<Solution>

[LeetCode] 653. Two Sum IV - Input is a BST

轉自LeetCode

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
Example 2:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

<Solution>

2017年6月20日 星期二

[Kotlin] 學習筆記(2) - Basic Concept

在開始之前,附上一篇文章 17位Google Android 工程師對 Kotlin 的看法

來了解一下各方對 Kotlin 的見解

然後也提供一下學習資源 : Kotlin官方文檔

本篇大部分內容都是參考 Kotlin 的官方文檔來的,可以去該網站多挖挖寶

以下開始一些基礎介紹
  • Variables
有兩個關鍵字,val 和 var。val 就是 java 裡的 final,var 是可以重新賦值的變數

var 也有上面的宣告方式,差別在於 var 可以重新賦值

在 Kotlin,變數預設是 non-null type,也就是不能是 null

Kotlin 的一大特色就是能盡量減少 NullPointerException 發生的機率

以下是關於變數 null safety 的介紹
型態轉換也有 null safety 可以使用
如果今天有一個 class 的 property,我們不希望為 null,但也不想在 construtor 去初始化,該怎麼做呢?
lateinit 的用法有一些限制
(1) 只能用在 var 變數
(2) 不能用在 primitive type (Int, Float, ...) 
(3) 該變數不能有客製化的 setter 和 getter
  • Functions
有兩個 Int 的 parameters,回傳 type 是 Int
如果沒有 return value,用 Unit 表示,也可以把 Unit 省略
如果一個函式的參數比較多,這時候可以使用 named arguments 來增加可讀性
function 也可以使用 variable number of arguments

使用 vararg 有幾點注意事項
  1. function 只能有一個 parameter 被標示為 vararg
  2. vararg parameter 通常要放在 parameter list 的最後一個。如果不是最後一個,則在使用的時候,必須搭配 named argument 來使用
  • Class
在 Kotlin,如果 class 沒有指明父類別的話,都會是從 Any 這個例別衍生出來的

class 的基本宣告方式如下
Kotlin 有個和 Java 不一樣的地方是,Kotlin 沒有 new 這個 keyword
每個 class 都會有一個 primary constructor
primary constructor 是不能寫 code 的,必須使用 initializer block 來達到這個目的
Kotlin 還有提供 secondary constructor,一個 class 可以有多個 secondary constructor
在 Kotlin,function 和 constructor 的 arguments 都可以有 default value,這可以簡化原本 Java 的寫法
在繼承 class 的時候,constructor 的寫法有下列兩種情況
以下示範 derived class 如何複寫 function
當 derived class 繼承或實現多個 base class or interface 的情況呢
可以看到因為有 doAction() 的 supertype 不只一個,所以在 Derived class 就一定得用 override 去複寫這個函式

而在這種情況下,要指定使用哪個 supertype 的 doAction(),就可以使用 super<BaseName> 來指定

至於 showMsg() 和 power(),因為來源都只有一個,所以不會被強迫要求用 override 複寫

  • What's Next
本篇介紹一些 Kotlin 基礎的語法,可以看出來 Kotlin 有簡化一些 Java 語法,並且引入一些新的概念

不過也可以看出來,Kotlin 在某些部分也有一些限制,像是為了 null safety,programmer 必須在寫 code 的時候遵從一些語法才行

下一篇會繼續介紹 Kotlin 的基礎語法,讓各位更熟悉 Kotlin