13 Jul 2024
Leetcode Top Interview 150 的其中一題
題目描述
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
範例
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
解法
專注於我們目前能到達的最遠 index 。從前面哪個 index 到這個最遠的index並不重要。
從 index 0 開始遍歷 nums，使用 canArrive 變數來記錄我們能到達的最遠 index。如果 i + nums[i] > canArrive，這表示我們可以到達更遠的 index，更新canArrive的值。如果 i < canArrive，這表示我們無法抵達剩餘的index，返回 false。
func maximumGain(s string, x int, y int) int {
remove := func(str string, removestr string, val int) int {
count := 0
stack := make([]byte, 0)
for i:=0; i<len(str); i++ {
stack = append(stack, str[i])
l := len(stack)
if l >= 2 && stack[l-1]==removestr[1] && stack[l-2]==removestr[0] {
count += val
stack = stack[:l-2]
}
}
s = string(stack)
return count
}
if x > y {
return remove(s, "ab", x) + remove(s, "ba", y)
} else {
return remove(s, "ba", y) + remove(s, "ab", x)
}
return 0
}
Time complexity : O(n)
Space complexity : O(1)
12 Jul 2024
Leetcode Top Interview 150 的其中一題
題目描述
Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this path into its simplified canonical path.
In Unix-style file system context, a single period '.' signifies the current directory, a double period ".." denotes moving up one directory level, and multiple slashes such as "//" are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like "...") as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
It must start with a single slash '/'.
Directories within the path should be separated by only one slash '/'.
It should not end with a slash '/', unless it’s the root directory.
It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
範例
Example 1:
Input: path = "/home/"
Output: "/home"
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation:
Multiple consecutive slashes are replaced by a single one.
Example 3:
Input: path = "/../"
Output: "/"
Explanation:
Going one level up from the root directory is not possible.
Constraints:
- 1 <= path.length <= 3000
- path consists of English letters, digits, period
'.', slash '/' or '_'.
- path is a valid absolute Unix path.
解法
func simplifyPath(path string) string {
if len(path) == 1 { return path }
folders := make([]string, 0)
path += "/"
bytes := make([]byte, 0)
for i:=1; i<len(path); i++ {
if path[i] != '/' {
bytes = append(bytes, path[i])
continue
}
if len(bytes) == 0 { continue }
if len(bytes) == 1 && bytes[0] == '.' {
bytes = []byte{}
continue
}
if len(bytes) == 2 && bytes[0] == '.' && bytes[1]=='.' {
if len(folders) > 0 { folders = folders[:len(folders) - 1] }
bytes = []byte{}
continue
}
folders = append(folders, string(bytes))
bytes = []byte{}
}
res := ""
for _, s := range folders {
res += "/"
res += s
}
if len(res) == 0 { return "/"}
return res
}
12 Jul 2024
Leetcode Top Interview 150 的其中一題
題目描述
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
範例
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
Follow Up
Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with $O(1)$ extra space?
解法
方法：檢查每個數字現在是否等於 val，是的話改成 100001，這樣排序後就會在最後面，不在列入檢查的陣列前面
func rotate(nums []int, k int) {
k = k % len(nums)
new := make([]int, 0)
for i:= len(nums) - k; i<len(nums); i++ {
new = append(new, nums[i])
}
for i:=0; i<len(nums)-k; i++ {
new = append(new, nums[i])
}
copy(nums, new)
}
Time complexity : O(n)
Space complexity : O(n)
12 Jul 2024
2024/07/12 的每日一題！
題目描述
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
- Remove substring
"ab" and gain x points.
- For example, when removing
"ab" from "cabxbae" it becomes "cxbae".
- Remove substring
"ba" and gain y points.
- For example, when removing
"ba" from "cabxbae" it becomes "cabxe".
Return the maximum points you can gain after applying the above operations on s.
範例
Example 1:
Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.
Example 2:
Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20
Constraints:
- 1 <= s.length <= 10^5
- 1 <= x, y <= 10^4
s consists of lowercase English letters.
解法
方法：寫一個叫做 remove 的方法，該方法利用 stack 消除所有 removestr，並將每個 removestr 作為 val 值加總在一起並回傳。
針對題目字串，如果ｘ較大，我們就先處理 ab，如 y 較大，處理 ba。
func maximumGain(s string, x int, y int) int {
remove := func(str string, removestr string, val int) int {
count := 0
stack := make([]byte, 0)
for i:=0; i<len(str); i++ {
stack = append(stack, str[i])
l := len(stack)
if l >= 2 && stack[l-1]==removestr[1] && stack[l-2]==removestr[0] {
count += val
stack = stack[:l-2]
}
}
s = string(stack)
return count
}
if x > y {
return remove(s, "ab", x) + remove(s, "ba", y)
} else {
return remove(s, "ba", y) + remove(s, "ab", x)
}
return 0
}
Time complexity : O(n)
Space complexity : O(n)
11 Jul 2024
Leetcode Top Interview 150 的其中一題
題目描述
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
範例
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
解法
方法：檢查每個數字現在是否等於 val，是的話改成 100001，這樣排序後就會在最後面，不在列入檢查的陣列前面
func removeElement(nums []int, val int) int {
count := 0
for i:=0; i<len(nums); i++ {
if nums[i] == val {
nums[i] = 101
count++
}
}
sort.Ints(nums)
return len(nums)-count
}
Time complexity : O(nlogn)