go面试题 最大交换

 题目：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。给定数字的范围是 [0, 108]

输入：
2736
1993
98368
2736
9973
115
 
输出：
7236 //交换数字2和数字7
9913
98863
7236
9973
511

题解：拿到该题后，我们可以快速想到的是比较数值中每一个数值的大小来解决来进行排序，排列出最大的一组。因此，我们可以把int类型转变为数组类型来进行操作。（提示：面试中，我们没有太多的时间来考虑算法的复杂度问问，我们需要快速的把题目完成出来。）

1.题目中给出了一个约束条件：至多可以交换一次数字中的任意两位。因此，我们可以快速想到从头开始判断该数值是否是后续中最大的。如果不是，我就记录该值为必须交换的，对比的值记录为可能交换的。如果是，我们就判断下一个值（如1993中，1要小于9，此时，我们可以记录下1是必须交换的和9是有可能交换的)。

2.接下来，我们要从可能交换的值后面选择到大于等于的数值。如果，有大于或等于，我们把该值认为是可能交换的数值。

3.我们将必须交换的值和可能要交换的值进行互换，得出最优解。

func maximumSwap(num int) int {
    ans := make([]int,0)
    sum, tmp := 0 , num 
    start, end := -1, -1
    fase := false
    max := 0
    for tmp != 0 {
        ans = append(ans,tmp%10)
        tmp /= 10
        sum++
    }
    for i := sum-1 ; i > 0 ; i-- {
        for j := i-1 ; j >= 0 ; j-- {
            if ans[i] < ans[j] {
                start = i
                end = j
                fase = true
                break
            }
        }
        if fase {
            break
        }
    }
 
    for i := end ; i >= 0 ; i-- {
        if ans[end] <= ans[i] {
            end = i
        }
    }
 
    if start != -1 {
        ans[start] , ans[end] = ans[end], ans[start]
    }
    
    for i := sum-1 ; i >= 0 ; i-- {
        max = max *10 +ans[i]
    }
    return max
}

进阶：为了由于该题难度不大，有可能会面临对时间复杂度进行要求的情况，因此我们对数据进行了优化。我们可以采用贪心算法对题目进行解题

func maximumSwap(num int) int {
    arr := []byte(strconv.Itoa(num))
    n := len(arr )
    maxIdx, i1, i2 := n-1, -1, -1
    for i := n - 1; i >= 0; i-- {
        if arr[i] > arr[maxIdx] {
            maxIdx = i
        } else if arr[i] < arr[maxIdx] {
            i1, i2 = i, maxIdx
        }
    }
    if i1 < 0 {
        return num
    }
    arr[i1], arr[i2] = arr[i2], arr[i1]
    v, _ := strconv.Atoi(string(arr))
    return v
}