输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

func merge(nums1 []int, m int, nums2 []int, n int) {
	//不额外占用空间，所以就是在num1上原地修改
	ptr1, ptr2, ptr := m-1, n-1, m+n-1
	for ;ptr1 >=0 && ptr2 >= 0;{
        if nums1[ptr1]>nums2[ptr2]{
            nums1[ptr] = nums1[ptr1]
            ptr--
            ptr1--
        }else{
            nums1[ptr] = nums2[ptr2]
            ptr--
            ptr2--
        }
	}
    for ;ptr2>=0;{
        nums1[ptr] = nums2[ptr2]
        ptr--
        ptr2--
    }
}

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

func removeElement(nums []int, val int) int {
    lst := len(nums)-1
    for i := 0; i<=lst; i++{
        if nums[i] != val {
            continue
        }
        for {
            if lst>=0&&nums[lst]==val{
                lst--
            }else{
                break
            }
        }
        if i<lst{
            tmp := nums[i]
            nums[i] = nums[lst]
            nums[lst] = tmp
        }
    }
    return lst+1;
}

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

func removeDuplicates(nums []int) int {
    //特例，额外处理
    if len(nums)<=1{
        return len(nums)
    }
    //有效数字
    start := 0
    for ptr := 1; ptr<len(nums); ptr++{
        if nums[ptr]!=nums[start]{
            start++
            nums[start] = nums[ptr]
        }
    }
    return start+1
}

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

func removeDuplicates(nums []int) int {
    if len(nums)<=2{
        return len(nums)
    }
    start := 1
    for ptr := 2; ptr<len(nums); ptr++{
        //这个对比的是start-1,不可以是ptr-2
        if nums[ptr] != nums[start-1]{
            start++
            nums[start] = nums[ptr]
        }
    }
    return start+1

}

输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

func majorityElement(nums []int) int {
    res := -1
    count := 0
    for _,val := range nums{
        if val==res{
            count++;
        }else{
            if count==0{
                res = val
                count++
            }else{
                count--
            }
        }
    }
    return res
}

输入: nums = [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]

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

func reverse(nums []int, start int, end int){
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}
func rotate(nums []int, k int)  {
    k = k%len(nums)
    reverse(nums,0,len(nums)-1)
    reverse(nums,0,k-1)
    reverse(nums,k,len(nums)-1)
}

func rotate(nums []int, k int)  {
    n := len(nums)
    if n<=1{
        return
    }
    k = k%n
    start := 0
  	//记录安置好的元素个数
    count := 0
  	//从第一个开始安置
    ptr := start
    for count<len(nums){
        ptr = (ptr+k)%n
        if ptr == start{
          	//第start圈循环的最后一个，安置到start位置
          	//记得安置完数目+1
            count++
            start++
            ptr = start
            continue
        }
        tmp := nums[start]
        nums[start] = nums[ptr]
        nums[ptr] = tmp
        count++
    }
}

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

func maxProfit(prices []int) int {
    preMin := math.MaxInt
    res := math.MinInt
    for _,value := range prices{
        if value<preMin{
            preMin = value
        }
        if res<value-preMin{
            res = value-preMin
        }
    }
    return res
}

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

func max(num1, num2 int) int{
    if num1>num2 {
        return num1
    }else{
        return num2
    }
}

func maxProfit(prices []int) int {
    //只初始化了第一维，每个子数组其实还是nil，第一次使用的时候要手动初始化
    dp := make([][]int,len(prices))
    dp[0] = make([]int,2)
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    res := 0
    for i := 1; i<len(prices); i++{
        dp[i] = make([]int,2)
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
        res = max(dp[i][0],res)
    }
    return res
}

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

func canJump(nums []int) bool {
    max := 0
    for pre :=0; pre<=max&&pre<len(nums); pre++{
        if pre + nums[pre] > max {
            max = pre + nums[pre]
        }
    }
    return max>=len(nums)-1
}

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

输入: nums = [2,3,0,1,4]
输出: 2

func jump(nums []int) int {
    end := 0
    maxPos := 0
    res := 0
    for index, value := range nums{
        if index + value > maxPos {
            maxPos = index + value
        }
        if index == end && index<len(nums)-1 {
            end = maxPos
            res++
        }
    }
    return res
}

class Solution {
    public int jump(int[] nums) {
        int res[] =new int[nums.length];
        res[0]=0;
        int j=0;
        for(int i=1;i<nums.length;i++){
            while(nums[j]+j<i){
                j++;
            }
            res[i]=res[j]+1;
        }
        return res[nums.length-1];
    }
}

func jump(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = 0
    start := 0
    for i:=1;i<len(nums);i++{
        for start+nums[start]<i{
            start++;
        }
        dp[i] = dp[start]+1
    }
    return dp[len(nums)-1]
}

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

输入：citations = [1,3,1]
输出：1 

func hIndex(citations []int) int {
    sort.Slice(citations,func(i, j int) bool{
        return citations[i] < citations[j]
    });
  	//当然也可以这么写
  	//sort.Ints(citations)
  	//假设全部论文都满足引用大于n，然后从头开始删除
    pre := len(citations)
    for _, value := range citations{
        if value < pre{
            pre--
        }
    }
    return pre
}

func min(num1, num2 int) int{
    if num1>num2 {
        return num2
    }
    return num1
}
func hIndex(citations []int) int {
    index := make([]int, len(citations)+1)
    n := len(citations)
    for _,value := range citations{
        index[min(value,n)]+=1
    }
    sum := 0
    for i:=n; i>=0; i--{
        sum += index[i]
        if sum>= i{
            return i
        }
    }
    return 0;
}	

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

type RandomizedSet struct {
    nums []int
    hash map[int]int
}


func Constructor() RandomizedSet {
    return RandomizedSet{[]int{},map[int]int{}}
}


func (this *RandomizedSet) Insert(val int) bool {
    if _, exist := this.hash[val]; exist {
        return false
    }
    this.hash[val] = len(this.nums)
    this.nums = append(this.nums, val)
    return true
}


func (this *RandomizedSet) Remove(val int) bool {
    if value, exist := this.hash[val]; exist{
        lst := len(this.nums)-1
        this.nums[value] = this.nums[lst]
        this.hash[this.nums[value]] = value
        delete(this.hash, val)
        this.nums = this.nums[:lst]
        return true
    }
    return false
}


func (this *RandomizedSet) GetRandom() int {
    return this.nums[rand.Intn(len(this.nums))]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

func productExceptSelf(nums []int) []int {
    //返回数组，接下来我们用它来保存左边的乘积
    res := make([]int, len(nums))
    res[0] = 1
    pre := nums[0]
    for i := 1; i< len(nums); i++ {
        res[i] = pre
        pre = pre * nums[i]
    }
    //接下来修改原数组，用原数组保存右边的乘积
    lst := nums[len(nums)-1]
    nums[len(nums)-1] = 1
    for i := len(nums)-2; i>=0; i-- {
        tmp := lst
        lst = lst * nums[i]
      	//这里不能写lst/nums[i]的原因主要是可能/0
        nums[i] = tmp
    }
    for i := 0; i<len(nums); i++ {
        res[i] *= nums[i]
    }
    return res
}

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

func canCompleteCircuit(gas []int, cost []int) int {
    //假设我们的起点是0
    start := 0
    n := len(gas)
    for start<n {
        end := start
        rest := gas[start]
        //只要油还够，就能往前走了
        for rest>= cost[end]{
            rest = rest - cost[end] + gas[(end+1)%n]
            end = (end + 1) % n
            //如果到达起点，证明能环绕
            if end==start{
                return start
            }
        }
        //如果到达点在起点前，就一定无法抵达了，因为从0到起点-1出发都是不不能环绕的，起点到n也是不能环绕的
        if end < start{
            return -1
        } else {
            //更换剪枝后的新起点
            start = end + 1
        }
    }
    return -1
}

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

func candy(ratings []int) int {
    //我个人喜欢定义一个数组走两遍，而不是定义俩数组
    res := make([]int, len(ratings))
    res[0] = 1
    for i := 1; i<len(ratings); i++{
        if ratings[i]>ratings[i-1]{
            res[i] = res[i-1]+1
        }else{
            res[i] = 1
        }
    }
    sum := res[len(ratings)-1]
    for i := len(ratings)-2; i>=0; i--{
        if ratings[i] > ratings[i+1] && res[i]<res[i+1]+1{
            res[i] = res[i+1]+1
        }
        sum += res[i]
    }
    return sum
}

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

输入：height = [4,2,0,3,2,5]
输出：9

func max(num1, num2 int) int{
    if num1<num2{
        return num2
    }
    return num1
}
func trap(height []int) int {
    left := 0
    right := len(height) - 1
    leftMax := 0
    rightMax := 0
    sum := 0
    for left<=right {
        if height[left]<=height[right]{
            leftMax = max(height[left],leftMax)
            sum += leftMax - height[left]
            left++
        }else{
            rightMax = max(height[right],rightMax)
            sum += rightMax - height[right]
            right--
        }
    }
    return sum
}

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

输入: s = "III"
输出: 3

输入: s = "IV"
输出: 4

输入: s = "IX"
输出: 9

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

func romanToInt(s string) int {
    res := map[byte]int{'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    sum := 0
    for i:= 0; i<len(s); i++{
        if i==len(s)-1 {
            sum+=res[s[i]]
            break
        }
        if res[s[i]]<res[s[i+1]]{
            sum -= res[s[i]]
        }else {
            sum += res[s[i]]
        }
    }
    return sum
}

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

50 = L
 8 = VIII

1000 = M
 900 = CM
  90 = XC
   4 = IV

func intToRoman(num int) string {
    //说实话，感觉这个题目纯是逆天题目
    //但是还有个细节要讲，这里不能定义map来存对应关系
    //因为go的map底层是真无序，也不能说无序，是按照hash序
    //严格来说，要么定义两个数组，要么定义一个结构体数组
    res := []struct{
        value int
        symbol string
    }{{1000,"M"},
        {900,"CM"},
        {500,"D"},
        {400,"CD"},
        {100,"C"},
        {90,"XC"},
        {50,"L"},
        {40,"XL"},
        {10,"X"},
        {9,"IX"},
        {5,"V"},
        {4,"IV"},
        {1,"I"}}
    str := ""
    for num>0 {
        for _,st := range res{
            for num>=st.value{
                num -= st.value
                str += st.symbol
            }
        }
    }
    return str
}

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

func lengthOfLastWord(s string) int {
    //这题其实是一个很简单的题，问题就是在于go有没有提供对string 的strip和slipt方法
    //strings包提供了一些操作，包括TrimSpace和Trim操作
    //同时strings也提供了Split方法
    s = strings.Trim(s, " ")
    sSplit := strings.Split(s," ")
    n := len(sSplit)-1
    return len(sSplit[n])
}

func lengthOfLastWord(s string) int {
    start := len(s)-1
    for s[start]==' '{
        start--
    }
    end := start
    for end>=0&&s[end]!=' '{
        end--
    }
    return start-end
}

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

func min(num1, num2 int) int{
    if num1 > num2 {
        return num2
    }
    return num1
}
func longestCommonPrefix(strs []string) string {
    res := ""
    n := math.MaxInt
    for _, str := range strs{
        n = min(n,len(str))
    }
    for i:=0;i<n;i++{
        b := strs[0][i]
        for _,str := range strs{
            if str[i] != b{
                return res
            }
        }
        res = res+string(b)
    }
    return res
}