[数据结构与算法]537. 复数乘法 / 220. 存在重复元素 III

537. 复数乘法【中等题】【每日一题】

思路：【模拟】

1. 定义一个函数splitNum用来取出字符串形式复数的实部和虚部，分别存入一个长度为2的int类型数组中，实部存第0个位置，虚部存第1个位置。
2. splitNum函数的实现思路为：遍历复数字符串，遇到 + 时记录当前 + 的下标 ch = i并退出for循环；实部就是复数字符串从0到ch-1位置的子串所表示的数，虚部就是复数字符串从ch+1到len-2位置的子串所表示的数，由于题目规定给的复数均为有效复数，且实部和虚部的值的范围均在[-100,100]之间，因此可以直接调用parseInt函数直接将子串转为int类型数据，分别存入数组第0和第1位返回。
3. 在complexNumberMultiply函数中，利用自定义的splitNum函数分别提取两个复数的实部和虚部，然后进行正常的复数相乘运算，得到的实部和虚部再给转为复数字符串形式返回即可。

代码：

class Solution {
    public String complexNumberMultiply(String num1, String num2) {
        int[] n1 = splitNum(num1),n2 = splitNum(num2);
        int practical = n1[0]*n2[0]-n1[1]*n2[1];
        int virtual = n1[1]*n2[0]+n1[0]*n2[1];
        return practical+"+"+virtual+"i";
    }
    public int[] splitNum(String num){
        int[] nums = new int[2];
        char[] chars = num.toCharArray();
        int ch = 0,len = chars.length;
        for (int i = 0; i < len; i++) {
            if (chars[i] == '+'){
                ch = i;
                break;
            }
        }
        nums[0] = Integer.parseInt(num.substring(0,ch));
        nums[1] = Integer.parseInt(num.substring(ch+1,len-1));
        return nums;
    }
}

用时：

220. 存在重复元素 III【中等题】

思路：【看题解】【桶排序+滑动窗口+哈希表】

1. 遍历数组，将当前元素用长度为t+1的桶装起来，每个桶都有一个固定的id（>=0的数，id即为当前数字/桶长度，<0 的数，id为 数先+1，除以桶长度之后再减1）。
2. 定义一个哈希表map用来装桶编号其对应的数组元素。
3. 定义当前遍历到的数组元素的桶编号为id，如果map中已经存在当前id，那么说明遇到了在同一个桶的元素，既然在同一个桶，那么必满足题意，于是直接返回true。如果map中存在当前id的相邻桶，即id+1或者id-1，那么此时如果当前元素和相邻桶对应的元素间的距离<=t，即小于t+1，也就是小于桶的长度，那么此时也存在符合题意的两个数，可以返回true。
4. 如果map中既不存在当前桶，也不存在相邻桶或者存在相邻桶但不符合题意，那么就在map中添加一个当前桶，对应当前元素。
5. 如果上述3、4步骤走完，此时i是大于k的，说明此时map中刚添加完当前元素nums[i]对应的桶，前i个元素对应的桶都存在，其都不符合题意，那么此时因为i>k，所以i-k位置元素对应的桶就失效了，因为不满足abs(i

• j) <= k ,此时需要将i-k位置元素对应的桶在map中移除。

6. 如果数组遍历完了都没有返回true，说明数组中不存在复合题意的元素对，此时返回false。

代码：

class Solution {
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Long,Long> map = new HashMap<>();
        long w = (long)t+1;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            long id = getId(nums[i],w);
            if (map.containsKey(id)){
                return true;
            }
            if (map.containsKey(id-1) && Math.abs(nums[i]-map.get(id-1)) < w){
                return true;
            }
            if (map.containsKey(id+1) && Math.abs(nums[i]-map.get(id+1)) < w){
                return true;
            }
            map.put(id,(long)(nums[i]));
            if (i>=k){
                map.remove(getId(nums[i-k],w));
            }
        }
        return false;
    }
    public static long getId(long cur_num,long w){
        if (cur_num>=0){
            return cur_num/w;
        }
        return (cur_num+1)/w-1;
    }
}