---
title: Easy Problems
tags: Leetcode
---
# 7. Reverse Integer
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/reverse-integer/
---
### Description
Given a 32-bit signed integer, reverse digits of an integer.
#### Example 1:
```
Input: 123
Output: 321
```
#### Example 2:
```
Input: -123
Output: -321
```
#### Example 3:
```
Input: 120
Output: 21
```
#### Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [$−2^{31}$, $2^{31} − 1$]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
---
### My code (Go language)
```go
func reverse(x int) int {
ans := 0
for ; x != 0;{
ans = ans * 10 + x % 10
x = x / 10
}
if ans > 0x7fffffff || ans < -1 * 0x80000000{
return 0
}
return ans
}
```
---
# 9. Palindrome Number
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/palindrome-number/
---
### Description
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
#### Example 1:
```
Input: 121
Output: true
```
#### Example 2:
```
Input: -121
Output: false
```
#### Example 3:
```
Input: 10
Output: false
```
---
### My code (Go language)
```go
func isPalindrome(x int) bool {
temp := []byte(strconv.Itoa(x))
for head, tail:= 0, len(temp) - 1; head < tail; head, tail = head + 1, tail - 1{
temp[head], temp[tail] = temp[tail], temp[head]
}
if string(temp) == strconv.Itoa(x){
return true
}
return false
}
```
---
### Solution (Go language)
```go
func isPalindrome(x int) bool {
s := strconv.Itoa(x)
r := []rune(s)
for i, j := 0, len(r) - 1; i < j; i, j = i + 1, j - 1 {
if r[i] != r[j] {return false}
}
return true
}
```
---
# 13. Roman to Integer
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/roman-to-integer/
---
### Description
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
```
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
```
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
#### Example 1:
```
Input: "III"
Output: 3
```
#### Example 2:
```
Input: "IV"
Output: 4
```
#### Example 3:
```
Input: "IX"
Output: 9
```
#### Example 4:
```
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
```
#### Example 5:
```
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```
---
### Idea
- Build a map
- Left number is larger right number?
---
### My code (Go language)
```go
func romanToInt(s string) int {
//Build a map
m := make(map[string]int)
m["I"] = 1
m["V"] = 5
m["X"] = 10
m["L"] = 50
m["C"] = 100
m["D"] = 500
m["M"] = 1000
ans := 0
//Left number is larger right number?
for i:=0; i < len(s) - 1; i++{
if m[s[i:i+1]] < m[s[i+1:i+2]]{
ans = ans - m[s[i:i+1]]
} else{
ans = ans + m[s[i:i+1]]
}
}
ans = ans + m[s[len(s)-1:len(s)]]
return ans
}
```
---
### Solution (Go language)
```go
import "strings"
func romanToInt(s string) int {
var number int = 0
var carry int = 0
hashT := map[string]int{
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
for _, v := range strings.Split(s, "") {
if carry < hashT[v] {
number = number - (carry * 2) + hashT[v]
} else {
number = number + hashT[v]
}
carry = hashT[v]
}
return number
}
```
---
# 14. Longest Common Prefix
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/reverse-integer/
---
### Description
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
#### Example 1:
```
Input: ["flower","flow","flight"]
Output: "fl"
```
#### Example 2:
```
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
```
#### Note:
All given inputs are in lowercase letters a-z.
---
### Idea
- 一個一個字比對
- 確定字串長度
---
### My code (Go language)
```go
func longestCommonPrefix(strs []string) string {
if len(strs) == 0{
return ""
}else if len(strs) == 1{
return strs[0]
}
ans := make([]byte,0)
var temp byte
for N:=0; N < len(strs[0]); N++{
temp= strs[0][N]
for idx:= 1; idx < len(strs); idx++{
if N >= len(strs[idx]){
return string(ans)
}else if strs[idx][N] != temp{
return string(ans)
}
}
ans = append(ans,temp)
}
return string(ans)
}
```
---
### Solution (Go language)
```go
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for _, el := range strs {
prefix = lcpHelper(prefix, el)
}
return prefix
}
func lcpHelper(s1, s2 string) string{
result := make([]byte, 0)
for i := 0; i < len(s1) && i < len(s2); i++ {
if s1[i] != s2[i] {
break;
}
result = append(result, s1[i])
}
s := string(result)
return s
}
```
---
# 20. Valid Parentheses
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/valid-parentheses/
---
### Description
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
#### Example 1:
```
Input: "()"
Output: true
```
#### Example 2:
```
Input: "()[]{}"
Output: true
```
#### Example 3:
```
Input: "(]"
Output: false
```
#### Example 4:
```
Input: "([)]"
Output: false
```
---
### My code (Go language)
```go
func isValid(s string) bool {
Map := map[string]string{
"(": ")",
"[": "]",
"{": "}",
}
stack := make([]string,0)
for i:=0; i < len(s); i++{
fmt.Println(s[i:i+1])
switch s[i:i+1]{
case "(":
stack = append(stack, "(")
case "[":
stack = append(stack, "[")
case "{":
stack = append(stack, "{")
default:
if len(stack)==0{
return false
}else if Map[stack[len(stack)-1]] != s[i:i+1]{
return false
}else{
stack = stack[0:len(stack) - 1]
}
}
}
if len(stack) > 0{
return false
}
return true
}
```
---
### solution
```go
func isValid(s string) bool {
stack := []rune{}
bracketsMaps := map[rune]rune{
')': '(',
'}': '{',
']': '[',
}
for _, v := range s {
if len(stack) == 0 {
stack = append(stack, v)
continue
}
if bracketsMaps[v] == stack[len(stack)-1] {
stack = stack[:len(stack)-1]
} else {
stack = append(stack, v)
}
}
return len(stack) == 0
}
```
---
# 21. Merge Two Sorted Lists
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/merge-two-sorted-lists/
---
### Description
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 1:
```
Input: 2->5, 1->3->4
Output: 1->2->3->4->5
```
---
### My code (Go language)
```go
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
//基本判斷
if l1 == nil && l2 == nil {
return nil
}
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var cur *ListNode
var head *ListNode
if l1.Val < l2.Val {
cur = l1
l1 = l1.Next
}else{
cur = l2
l2 = l2.Next
}
head = cur
for l1 != nil || l2 != nil {
if l1 == nil{
cur.Next = l2
return head
}else if l2 == nil{
cur.Next = l1
return head
}
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
return head
}
```
---
### solution
```go
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
var newList = &ListNode{}
var out = newList
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
newList.Next = l1
l1 = l1.Next
newList = newList.Next
}else{
newList.Next = l2
l2 = l2.Next
newList = newList.Next
}
}
if l1 != nil {
newList.Next = l1
}else if l2 != nil {
newList.Next = l2
}
return out.Next
}
```
---
# 67. Add Binary
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/add-binary/
---
### Description
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
#### Example 1:
```
Input: a = "11", b = "1"
Output: "100"
```
#### Example 2:
```
Input: a = "1010", b = "1011"
Output: "10101"
```
---
### My code (Go language)
```go
func addBinary(a string, b string) string {
if a == ""{
return b
}else if b==""{
return a
}
ans := ""
sign := 0
for max(len(a),len(b)) > 0{
if len(a) > 0{
sign = sign + int(a[len(a) - 1] - '0')
a = a[0:len(a) - 1]
}
if len(b) > 0{
sign = sign + int(b[len(b) - 1] - '0')
b = b[0:len(b) - 1]
}
if sign > 2{
ans = string(sign + '0' - 2) + ans;
sign = 1
}else{
ans = string(sign + '0') + ans;
sign = 0;
}
}
if sign == 1{
ans = "1" + ans}
return ans
}
```
---
# 69. Sqrt(x)
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/sqrtx/
---
### Description
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
#### Example 1:
```
Input: 4
Output: 2
```
#### Example 2:
```
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
```
---
### My code (Go language)
```go
func mySqrt(x int) int {
i:= 0
for i * i < x{
i = i + 1
}
if i*i == x{
return i
}else{
return i - 1
}
}
```
---
# 107. Binary Tree Level Order Traversal II
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
---
### Description
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
#### Example:
```
Given binary tree [3,9,20,null,null,15,7],
1 3
/ \
2 9 20
/ \
3 15 7
Output：
[
[15,7],
[9,20],
[3]
]
```
---
### My code (Go language)
```go
func levelOrderBottom(root *TreeNode) [][]int {
ans := [][]int{}
next := []*TreeNode{root}
temp := DFS(next, [][]int{}, 0)
for i:=len(temp)-1; i>=0 ;i--{
ans = append(ans, temp[i])
}
return ans
}
func DFS(cur []*TreeNode, ans [][]int, level int) [][]int {
next := []*TreeNode{}
for i:=0; i<len(cur);i++{
if cur[i] != nil{
if len(ans) <= level{
ans = append(ans,[]int{})
}
ans[level] = append(ans[level], cur[i].Val)
next = append(next, cur[i].Left)
next = append(next, cur[i].Right)
}
}
if len(next) == 0{
return ans
}
return DFS(next, ans, level + 1)
}
```
---
# 108. Convert Sorted Array to Binary Search Tree
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
---
### Description
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
#### Example:
```
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
```
---
### My code (Go language)
```go
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums)==0{
return nil
}
mid:=len(nums)/2
return &TreeNode{
Val:nums[mid],
Left:sortedArrayToBST(nums[0:mid]),
Right:sortedArrayToBST(nums[mid+1:])}
}
```
---
# 121. Best Time to Buy and Sell Stock
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
---
### Description
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
#### Example1:
```
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
```
#### Example2:
```
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
```
---
### My code (Go language)
```go
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
low := prices[0]
profit := 0
for _ , price := range prices {
if price < low {
low = price
}else if price - low > profit{
profit = price - low
}
}
return profit
}
```
---
# 122. Convert Sorted Array to Binary Search Tree
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
---
### Description
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
#### Example1:
```
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
```
#### Example2:
```
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
```
#### Example3:
```
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
```
---
### My code (Go language)
```go
func maxProfit(prices []int) int {
if(len(prices) == 0){
return 0}
profit := 0
low := prices[0]
peak := prices[0]
valley := prices[0]
for _,price:= range prices{
if p := price - low; p > 0{
profit += p
low = price
}else if low > price{
low = price
}
if valley > price {valley = price}
if peak < price {peak = price}
}
if profit < valley - peak{
return valley - peak
}
return profit
}
```
```go
func maxProfit(prices []int) int {
var ret int
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
ret += prices[i] - prices[i-1]
}
}
return ret
}
```
```c++
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
```
```c++
class Solution {
public int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
}
}
```
---
# 155. Min Stack
<!-- Put the link to this slide here so people can follow -->
Web link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
---
### Description
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
#### Example1:
```
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
```
---
### My code (Go language)
```go
type MinStack struct {
arr []int
}
func Constructor() MinStack {
return MinStack{
arr:[]int{}}
}
func (this *MinStack) Push(x int) {
this.arr = append(this.arr, x)
}
func (this *MinStack) Pop() {
this.arr = this.arr[:len(this.arr)-1]
}
func (this *MinStack) Top() int {
return this.arr[len(this.arr)-1]
}
func (this *MinStack) GetMin() int {
min := this.arr[0]
for i:=1; i < len(this.arr); i++{
if this.arr[i] < min{
min = this.arr[i]
}
}
return min
}
```
```go
type MinStack struct {
arr []int
sorted []int
}
func Constructor() MinStack {
return MinStack{
arr:[]int{},
sorted:[]int{},
}
}
func (this *MinStack) Push(x int) {
if len(this.sorted) == 0 || x <= this.GetMin() {
this.sorted = append(this.sorted, x)
}
this.arr = append(this.arr, x)
}
func (this *MinStack) Pop() {
if this.arr[len(this.arr)-1] == this.sorted[len(this.sorted)-1] {
this.sorted = this.sorted[:len(this.sorted)-1]
}
this.arr = this.arr[:len(this.arr)-1]
}
func (this *MinStack) Top() int {
return this.arr[len(this.arr)-1]
}
func (this *MinStack) GetMin() int {
return this.sorted[len(this.sorted)-1]
}
```
---
# 160. Intersection of Two Linked Lists
```go
func getIntersectionNode(headA, headB *ListNode) *ListNode {
size_a := getLen(headA);
size_b := getLen(headB);
for size_a != size_b{
if size_a > size_b{
headA = headA.Next
size_a--
}else if size_b > size_a{
headB = headB.Next
size_b--
}
}
for headA != nil && headB != nil && headA != headB {
headA = headA.Next
headB = headB.Next
}
return headA
}
func getLen(head *ListNode) int{
if head==nil{
return 0
}
return getLen(head.Next) + 1
}
```
```go
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
// --first loop
// p=[4,1,8,4,5 + 5,0,1,8,4,5]
// q=[5,0,1,8,4,5 + 4,1,8,4,5]
p, q := headA, headB
for p != nil || q != nil { // break loop if p==q(nil)
if p == q {
return p
}
if p == nil {
p = headB
q = q.Next
continue
}
if q == nil {
q = headA
p = p.Next
continue
}
p = p.Next
q = q.Next
}
return nil
}
```
# 198. House Robber
---
### Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
#### Example1:
```
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
```
#### Example2:
```
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
```
---
### My code (Go language)
[1 3 7 5 1]
1 天
3 天 -> rob1 3, rob2 1 -> 1 + 7 = 8 (temp), 3
4 天 -> rob1 8, rob2 3 ->
```go
func rob(nums []int) int {
rob_1 := nums[0] //rob left house
rob_2 := 0 //not rob left house
for idx:=1; idx < len(nums); idx++{
temp:=rob_2 + nums[idx]
if temp > rob_1{
rob_2 = rob_1
rob_1 = temp
}else{
rob_2 = rob_1
}
}
if rob_2 > rob_1{
return rob_2
}else{
return rob_1
}
}
```
---
# 202. Happy Number
---
### Description
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
#### Example1:
```
Input: 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 02 = 1
```
---
### My code (Go language)
```go
func isHappy(n int) bool {
nums:= []int{n}
for true{
temp := 0
for n!=0{
temp += (n % 10) * (n % 10)
n /= 10
}
if temp == 1{
return true
}else{
for _,v := range nums{
if v == temp{
return false
}
}
nums = append(nums, temp)
n = temp
}
}
return false
}
```
---
# 203. Remove Linked List Elements
---
### Description
Remove all elements from a linked list of integers that have value val.
#### Example1:
```
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
```
---
### My code (Go language)
```go
func removeElements(head *ListNode, val int) *ListNode {
pivot := &ListNode{Val:0, Next:head}
for cur := pivot; cur.Next!=nil;{
if cur.Next.Val == val{
cur.Next = cur.Next.Next
continue
}
cur = cur.Next
}
return pivot.Next
}
```
---
# 204. Count Primes
---
### Description
Count the number of prime numbers less than a non-negative number, n.
#### Example1:
```
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
```
---
### My code (Go language)
```go
func countPrimes(n int) int {
prime := []int{}
n_prime := make([]bool, n)
ans:=0
for tmp:=2; tmp < n;tmp++{
if n_prime[tmp]{
continue
}
if isPrime(tmp, prime){
prime = append(prime, tmp)
for idx:=tmp * 2; idx < n; idx+=tmp{
n_prime[idx] = true
}
ans++
}
}
return ans
}
func isPrime(n int, prime []int) bool {
for _,v := range prime{
if n % v == 0{
return false
}else if v * v > n{
return true
}
}
return true
}
----------------------------------------
func countPrimes(n int) int {
prime := make([]bool, n)
ans:=0
for tmp:=2; tmp < n;tmp++{
if !prime[tmp]{
for idx:=tmp * 2; idx < n; idx+=tmp{
prime[idx] = true
}
ans++
}
}
return ans
}
```
---
# 231. Power of Two
---
### Description
Given an integer, write a function to determine if it is a power of two.
#### Example 1:
```
Input: 1
Output: true
Explanation: 2^0 = 1
```
#### Example 2:
```
Input: 218
Output: false
```
---
### My code (Go language)
```go
func isPowerOfTwo(n int) bool {
tmp := 1
for{
if tmp == n{
return true
}else if tmp > n{
return false
}
tmp *= 2
}
}
func isPowerOfTwo(n int) bool {
// 檢查 n 是否為一負數
if n < 0 {
return false
}
count:=0 // 計算 2 的冪次方個數
for i := 0; i<32 ;i++{
if n&1 == 1{
count++
}
if count > 1 {
return false
}
n >>= 1
}
return count == 1
}
```
---
# 232. Implement Queue using Stacks
---
### Description
Implement the following operations of a queue using stacks.
* push(x) -- Push element x to the back of queue.
* pop() -- Removes the element from in front of queue.
* peek() -- Get the front element.
* empty() -- Return whether the queue is empty.
#### Example1 1:
```
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
```
---
### My code (Go language)
```go
type MyQueue struct {
stack []int
}
func Constructor() MyQueue {
return MyQueue{
stack: []int{},
}
}
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
this.stack = append(this.stack, x)
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
var reverse []int
size:= len(this.stack)
for idx:=0; idx < size; idx++{
reverse = append(reverse, this.stack[len(this.stack) - 1])
this.stack = this.stack[0:len(this.stack) - 1]
}
ans:= reverse[size - 1]
reverse= reverse[0:size - 1]
size = len(reverse)
for idx:=0; idx < size; idx++{
this.stack = append(this.stack, reverse[len(reverse) - 1])
reverse = reverse[0:len(reverse) - 1]
}
return ans
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
return this.stack[0]
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
if len(this.stack) == 0{
return true
}else{
return false
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/
```
---
# 278. First Bad Version
---
### Description
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.
#### Example 1:
```
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
```
---
### My code (Go language)
```go
func firstBadVersion(n int) int {
head := 1
tail := n
for head != tail{
mid := (head + tail) / 2
if isBadVersion(mid){
tail = mid
}else{
head = mid + 1
}
}
return tail
}
```
---
# 283. Move Zeroes
---
### Description
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.
#### Example 1:
```
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
```
#### Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
---
### My code (Go language)
```go
[0, 1, 0, 3, 12]
-> [1,0,0,3,12] , head=0, next=1 V
^ O
// => [1,0,0,3,12], head=0, next=2
=> [1,0,0,3,12], head=0, next=2
^ O
// => [1,0,3,0,12], head=0, next=3 V
=> [3,0,0,1,12], head=0, next=3 V
^ O
// => [1,0,3,12,0], head=0, next=4 V
0 1 2 3 4
=> [12,0,0,1,3], head=0, next=4 V
^ O
-> [12,0,0,1,3] , head=1, next=2
^ O
=> [12,1,0,0,3], head=1, next=3
^ O
=> [12,3,0,0,1], head=1, next=4
^ O
-> [12,3,0,0,1] , head=2, next=3
^ O
=> [12,3,1,0,0], head=2, next=4
^ O
func moveZeroes(nums []int) {
for head:= 0; head < len(nums); head++{
if nums[head] == 0{
for next:= head + 1; next < len(nums); next++{
if nums[next] != 0{
nums[head], nums[next] = nums[next], nums[head]
break
}
}
}
}
}
// [1,2,0,3,0,1] <- origin
// 0 1 2 3 4 5
// first for loop [1-2-3-1 .. 0, 1] ... 蓋掉原本的[1,2,0,3]位置，改成[1,2,3,1]
// 0 1 2 3 4 5
func moveZeroes(nums []int) {
k := 0
for i := 0; i < len(nums); i++ {
//把非0的數字直接往前蓋掉
if nums[i] != 0 {
nums[k] = nums[i]
k++
}
}
// [0,1]
// 4 5
// => [0, 0]
for i := k; i < len(nums); i++ {
nums[i] = 0
}
}
```
---
# 349. Intersection of Two Arrays
---
### Description
Given two arrays, write a function to compute their intersection.
#### Example 1:
```
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
```
#### Example 2:
```
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
```
---
### My code (Go language)
```go
func intersection(nums1 []int, nums2 []int) []int {
m := map[int]int{}
ans := []int{}
for _, v:= range nums1{
m[v]++
}
for _, v:= range nums2{
if m[v] > 0{
ans = append(ans, v)
delete(m, v)
}
}
return ans
}
```
---
# 350. Intersection of Two Arrays II
---
### Description
Given two arrays, write a function to compute their intersection.
#### Example 1:
```
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
```
#### Example 2:
```
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
```
---
### My code (Go language)
```go
func intersection(nums1 []int, nums2 []int) []int {
m := map[int]int{}
ans := []int{}
for _, v:= range nums1{
m[v]++
}
for _, v:= range nums2{
if m[v] > 0{
ans = append(ans, v)
m[v]--
}
}
return ans
}
```
---
# 392. Is Subsequence
---
### Description
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
#### Example 1:
```
s = "abc", t = "ahbgdc"
Return true.
```
#### Example 2:
```
s = "axc", t = "ahbgdc"
Return false.
```
---
### My code (Go language)
```go
func isSubsequence(s string, t string) bool {
m := []rune(s)
idx, max := 0, len(s)
for _, v := range(t){
if idx == max{
return true
}
if v == m[idx]{
idx++
}
}
return idx == max
}
```
---
# 401. Binary Watch
---
### Description
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
#### Example 1:
```
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
```
---
### My code (Go language)
```go
func readBinaryWatch(num int) []string {
hours := [][]string{
{"0"},
{"1", "2", "4", "8"},
{"3", "5", "6", "9", "10"},
{"7", "11"},
}
minutes := [][]string{
{"00"},
{"01", "02", "04", "08", "16", "32"},
{"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"},
{"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"},
{"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"},
{"31", "47", "55", "59"},
}
h := num
m := 0
ans := []string{}
if h > 3{
h = 3
m = num - 3
}
for h >= 0 && m <= 5{
for _, hour := range(hours[h]){
for _, minute := range(minutes[m]){
output := fmt.Sprintf("%s:%s", hour, minute)
ans = append(ans, output)
}
}
h--
m++
}
return ans
}
```
```go
func readBinaryWatch(num int) []string {
res := []string{}
for h := 0; h < 12; h++ {
for m := 0; m < 60; m++ {
if helper(h)+helper(m) == num {
s := fmt.Sprintf("%d:%02d", h, m)
res = append(res, s)
}
}
}
return res
}
func helper(n int) int {
res := 0
for n > 0 {
res += n % 2
n /= 2
}
return res
}
```
---
```go
// https://leetcode.com/problems/binary-watch/discuss/280914/0-ms100-GO-solution
func readBinaryWatch(num int) []string {
if num == 0 {
return []string{"0:00"}
}
dic := getDic()
var ret = make([]string, 0)
for i := 0; i <= num; i++ {
hours := generateHour(i, dic)
minutes := generateMinutes(num-i, dic)
for _, hv := range hours {
for _, mv := range minutes {
ret = append(ret, hv+":"+mv)
}
}
}
return ret
}
func generateHour(num int, dic map[int][]int) []string {
if num == 0 {
return []string{"0"}
}
ret := make([]string, 0)
slice := dic[num]
for _, v := range slice {
if v < 12 {
ret = append(ret, strconv.Itoa(v))
}
}
return ret
}
func generateMinutes(num int, dic map[int][]int) []string {
if num == 0 {
return []string{"00"}
}
ret := make([]string, 0)
slice := dic[num]
for _, v := range slice {
if v < 10 {
sv := strconv.Itoa(v)
sv = "0" + sv
ret = append(ret, sv)
} else {
ret = append(ret, strconv.Itoa(v))
}
}
return ret
}
func getDic() map[int][]int {
var dic = make(map[int][]int)
for i := 1; i < 60; i++ {
str := strconv.FormatInt(int64(i), 2)
c := strings.Count(str, "1")
//fmt.Println(str, c)
_, hasKey := dic[c]
if hasKey {
dic[c] = append(dic[c], i)
} else {
newSlice := make([]int, 0)
newSlice = append(newSlice, i)
dic[c] = newSlice
}
}
return dic
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
