给定两个数组，编写一个函数计算他们的交集
示例1：
输入： nums1 = [1, 2, 2, 1], num2 = [2, 2]
输出： [2,2]
示例2：
输入： nums1 = [4, 9, 5], num2 = [9, 4, 9, 8, 4]
输出： [4, 9]
说明: 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。 我们可以不考虑输出结果的顺序。 进阶: 如果给定的数组已经排好序呢?将如何优化你的算法呢? 思路:设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一 起向后移动,并且将相等的元素放入空白数组。
优秀解答
// 解法一， 针对所有列表
func intersect1(nums1 []int, nums2 []int) []int {
m0 := map[int]int{}
for _, v := range nums1{
m0[v] += 1
}
k := 0
for _, v := range nums2{
if m0[v] > 0{
m0[v] -= 1
nums2[k] = v
k++
}
}
return nums2[0:k]
}
// 解法二: 针对有序的列表
func intersect2(nums1 []int, nums2 []int) []int {
i, j, k := 0, 0, 0
sort.Ints(nums1)
sort.Ints(nums2)
for i < len(nums1) && j < len(nums2){
if nums1[i] > nums2[j] {
j++
} else if nums1[i] < nums2[j]{
i++
} else {
nums1[k] = nums1[j]
i++
j++
k++
}
}
return nums[:k]
}编写一个函数来查找数组中最长的公共前缀，如果不存在公共前缀，则返回“”
示例1：
输入: ["flower","flow","flight"]
输出: "fl"
示例2：
输入: ["dog","racecar","car"]
输出: ""
教程里面用到了go的strings.Index（返回子串seq在字符串s中第一次出现的位置，没有返回-1）
拿第一个字符串全部字符去对每一个字符串，没有找到公共前缀那么就字符串从末尾切片，一个一个的切片，直到找到公共前缀或者没有
func longestCommonPrefix(strs []string) string{
if len(strs) < 1{
return ""
}
prefix := strs[0]
for _,k := range strs {
for strings.Index(k, prefix) != 0{
if len(prefix) == 0 {
return ""
}
prefix = prefix[: len(prefix) - 1]
}
}
return prefix
}第122题:买卖股票的最佳时机 II
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的 最大利润。注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格= 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2:
输入: [1,2,3,4,5]
输出: 4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 -1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路:
- 不能参与多笔交易。只能买进一笔，卖出后才能再次买进
- 尽可能的多进行交易。
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
dp := make([][2]int, len(prices))
dp[0][0] = 0
dp[0][1] = -prices[0]
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][0]- prices[i], dp[i-1][1])
}
return dp[len(prices) - 1][0]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
题目扩展
图解的方式其实在各种算法题中,屡见不鲜。而我们通过图解的方式,也可以抽丝剥茧一样,一层一层 剥掉算法题目的外壳,寻找到最直观的解题思路,直捣黄....咳咳,直奔核心。那我们又如何用图解的观 察方式,来对本系列的其他题目寻找到一种通用解法,来规避题目中的陷阱呢?浩仔讲算法,我们下期 再见喽!
题目189: 旋转数组
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例1：
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
- 向右旋转 1 步: [7,1,2,3,4,5,6]
- 向右旋转 2 步: [6,7,1,2,3,4,5]
- 向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
- 向右旋转 1 步: [99,-1,-100,3]
- 向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。
这道题如果不要求原地翻转的话,其实相当简单。但是原地翻转的方法却并不容易想到,我们直接看题解。
题目图解
这个方法基于这个事实:若我们需要将数组中的元素向右移动 k 个位置, 那么 k%l (l为数组长度) 的尾部元素会被移动到头部,剩下的元素会被向后移动。
思路：
先将整个数组反转，然后将前面k个元素反转，再将l-k个元素反转
func rotate(nums []int, k int){
reverse(nums)
reverse(nums[:k%len(nums)])
reverse(nums[k%len(nums):])
}
func reverse(arr []int){
for i := 0; i < len(arr)/2; i ++{
arr[i], arr[len(arr)-i -1] = arr[len(arr)-i -1], arr[i]
}
}