T1-将句子排序

方法1

• 思路：双指针 + 排序
• 利用双指针把每个空格之间的子串切出来，并且对索引以及单词进行排序，最后依次拼接即可（Java也可以用split方法）

class Solution {
    public String sortSentence(String s) {
        int n = s.length();
        TreeMap<Integer,String> map = new TreeMap<>();
        for(int i = 0; i < n; i++){
            int j = i;
            String str = "";
            while(j < n && Character.isLetter(s.charAt(j))) {
                str += s.charAt(j++);
            }
            map.put(s.charAt(j) - '0', str);
            i = j + 1;
        }
        String res = "";
        for(String v: map.values()){
            res += v + " ";
        }
        return res.substring(0, res.length() - 1);
    }
}

• 时间复杂度：$O(n \times \log n)$
• 空间复杂度：$O(n)$

方法2

• 思路：内置函数 + 排序

class Solution {
    public String sortSentence(String s) {
        String[] str = s.split(" ");
        TreeMap<Integer,String> map = new TreeMap<>();
        for(String x: str){
            String a = x.substring(0, x.length()-1);
            int b = x.charAt(x.length()-1) - '0';
            map.put(b, a);
        }
        String res = "";
        for(String x: map.values()){
            res += x + " ";
        }
        return res.substring(0, res.length()-1);
    }
}

• 时间复杂度：$O(n \times \log n)$
• 空间复杂度：$O(n)$

T2-增长的内存泄露

• 思路：模拟

class Solution {
    public int[] memLeak(int m1, int m2) {
        int cur = 1;
        while(m1 >= cur || m2 >= cur){
            if(m1 >= m2) m1 -= cur;
            else m2 -= cur;
            cur++;
        }
        return new int[]{cur, m1, m2};
    }
}

• 时间复杂度：$O(\sqrt{m_1 + m_2})$
• 空间复杂度：$O(1)$

T3-旋转盒子

• 思路：模拟
• 直接把盒子旋转90°，然后考虑每一个石头的位置：
  • 如果石头下面是障碍物或盒子底部，直接跳过
  • 如果石头下面是空位置，往下掉落到第一个能卡住石头的位置，路过的位置全部置为空位置

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int n = box.length, m = box[0].length;
        char[][] res = new char[m][n];
        for(int j = 0; j < m; j++){
            for(int i = n-1, k = 0; i >= 0; i--, k++){
                res[j][k] = box[i][j];
            }
        }

        for(int j = n-1; j >= 0; j--){
            for(int i = m-1; i >= 0; i--){
                if(res[i][j] == '*' || res[i][j] == '.') continue;
                else{
                    while(i + 1 < m && res[i+1][j] == '.'){
                        res[i+1][j] = '#';
                        res[i][j] = '.';
                        i++;
                    }
                } 
            }
        }
        return res;
    }
}

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(n \times m)$

T4-向下取整数对和

• 思路：前缀和 + 枚举
• 数据范围为1e5，如果挨个枚举i和j会超时，但是注意到nums[i]和nums[j]的范围也都是1e5，说明floor(j / i)的范围是[0, 1e5]，我们枚举这个整除的结果，并计算每个结果对答案带来的贡献即可，贡献为k * j的出现频次。
• 对于floor(j / i) = k，j的最小值为i * k，最大值为(i + 1) * k - 1，我们需要统计这个范围内j的出现次数，先统计j在[1, 1e5]的出现频次，再利用出现频次计算j的频次前缀和，从而快速获取范围内的j的出现频次
• 特别地，枚举的过程中如果i不存在，就不用计算对应的j所带来的贡献

class Solution {
    public int sumOfFlooredPairs(int[] nums) {
        int n = 100000;
        int mod = (int)1e9 + 7;
        int[] cnt = new int[n + 1];
        int[] s = new int[n + 1];
        for(int x: nums) cnt[x]++;
        for(int i = 1; i <= n; i++) s[i] = s[i-1] + cnt[i];
        // floor(j/i) = k
        int res = 0;
        for(int i = 1; i <= 100000; i++){
            for(int k = 1; k * i <= 100000; k++){
                if(cnt[i] == 0) continue;
                int j1 = k * i, j2 = Math.min(100000, (k + 1) * i - 1);
                int sum = (int)((long)(s[j2] - s[j1 - 1]) * k % mod);
                res = (res + sum * cnt[i]) % mod;
            }
        }
        return res;
    }
}

• 时间复杂度：$O(n \times \log n)$，循环执行的次数为调和级数
• 空间复杂度：$O(n)$