2024.1.22力扣每日一题——最大交换

题目来源

力扣每日一题；题序：670

我的题解

方法一 暴力法

直接暴力对数字中的每两个位置进行交换，然后记录交换后生成数字的最大值

时间复杂度：O(${\log }^{3}m$)。m是数字num，num的位数是$\log m$
空间复杂度：O(KaTeX parse error: Undefined control sequence: \logm at position 1: \̲l̲o̲g̲m̲)

public int maximumSwap(int num) {
    
    String s=""+num;
    int n=s.length();
    int res=num;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            char ch1=s.charAt(i);
            char ch2=s.charAt(j);
            int t=Integer.parseInt(s.substring(0,i)+ch2+s.substring(i+1,j)+ch1+s.substring(j+1,n));
            res=Math.max(res,t);
        }
    }
    return res;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法一 哈希表+贪心

• 先将数字转为字符串s，然后使用哈希表分别记录每个字符在哪些位置出现，由于后续需要对哈希表的key进行排序（降序），因此选择TreeMap
• 再依次遍历s，若当前值与哈希表中的第一个key相同，则计数count加1，若count的值与第一个key对应的列表长度一致，删除第一个key对应的Node,并将count置为0
• 知道哈希表为空或者遍历位置的值与哈希表第一个key不同时退出循环。
  最后，若哈希表为空，则返回原始数字；否则将 遍历的位置和当前哈希表的第一个Node中list的最后一个值对应的数字交换，得到最终交换后的数字

时间复杂度：O(n)
空间复杂度：O(n)

 public int maximumSwap(int num) {
 	String s=""+num;
    TreeMap<Character,List<Integer>> map=new TreeMap<>((a,b)->b-a);
    for(int i=0;i<s.length();i++){
        char ch=s.charAt(i);
        List<Integer> list=map.getOrDefault(ch,new ArrayList<>());
        list.add(i);
        map.put(ch,list);
    }
    int index=0;
    int count=0;
    //这里要注意采用new的方式获取第一个key对应的list，不然会出问题
    List<Integer> list=new ArrayList<>(map.get(map.firstKey()));
    while(!map.isEmpty()&&s.charAt(index)==map.firstKey()){
        list.remove((Integer)index);
        index++;
        count++;
        if(count==map.get(map.firstKey()).size()){
            map.pollFirstEntry();
            count=0;
            //注意删除Node后哈希表为空
            if (!map.isEmpty())
                list=new ArrayList<>(map.get(map.firstKey()));
        }
    }
    if(map.isEmpty()){
        return num;
    }

    count=list.get(list.size()-1);
    return Integer.parseInt(s.substring(0,index)+s.charAt(count)+s.substring(index+1,count)+s.charAt(index)+s.substring(count+1,s.length()));


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

方法三 贪心

参考官方题解。

数字num可以表示为下面：
${\sum }_{i=0}^{n-1}{d}_i\ast 10^i$
假设交换的i和j位上的数字，0<=i<j<n，则最后交换的值为：

所以若要使交换后的数字最大，交换的两个数字di,dj,0<i<j<n,需要满足以下条件：

1. dj>di
2. 在同样大小数字di时，应该使得dj越大才能使得val越大
3. 在同样大小数字dj时，应使得j的索引值越大才能使得val越大
4. 在满足1的情况下，应该使得i的索引的越小才能使val越大

因此，具体操作：

• 将从右向左扫描数字数组，并记录当前已经扫描过的数字的最大值的索引为 maxId 且保证 maxId 越靠近数字的右侧，此时则说明 charArray[maxId]则为当前已经扫描过的最大值。
• 如果检测到当前数字 charArray[i]<charArray[maxId]，此时则说明索引 i 的右侧的数字最大值为 charArray[maxId]，此时可以尝试将 charArray[i] 与 charArray[maxId]进行交换即可得到一个比 num更大的值。尝试记录当前可以交换的数对 (i,maxId)，根据贪心法则，此时最左边的 iii 构成的可交换的数对进行交换后形成的整数值最大。

时间复杂度：O($\log m$)
空间复杂度：O($\log m$)

public int maximumSwap(int num) {
    char[] charArray = String.valueOf(num).toCharArray();
    int n = charArray.length;
    int maxIdx = n - 1;
    int idx1 = -1, idx2 = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (charArray[i] > charArray[maxIdx]) {
            maxIdx = i;
        } else if (charArray[i] < charArray[maxIdx]) {
            idx1 = i;
            idx2 = maxIdx;
        }
    }
    if (idx1 >= 0) {
        swap(charArray, idx1, idx2);
        return Integer.parseInt(new String(charArray));
    } else {
        return num;
    }
}

public void swap(char[] charArray, int i, int j) {
    char temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

自己也想到了贪心思想，但是在实际实现的过程中还是火候不到位

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈