5.23号刷题

发表于 | 分类于 | 0 comments

第一题 244. Shortest Word Distance II

算法

利用一个HashMap存下对应的word的值和这个word的所有index出现的位置(出现位置用List进行存储)

自己的

自己的在遍历List的时候，时间复杂度是O(n^2)

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
public class WordDistance {
    HashMap<String, List<Integer>> wordsMap = new HashMap<String, List<Integer>>();
    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (wordsMap.containsKey(word)) {
                List indexes = wordsMap.get(word);
                indexes.add(i);
            } else {
                List<Integer> indexes = new ArrayList<>();
                indexes.add(i);
                wordsMap.put(word, indexes);
            }
        }
    }
    public int shortest(String word1, String word2) {
        List indexFirst = wordsMap.get(word1);
        List indexSed = wordsMap.get(word2);
        int minDs = Integer.MAX_VALUE;
        for (int i = 0; i < indexFirst.size(); i++)
            for (int j = 0; j < indexSed.size(); j++) {
                int distance = Math.abs((int) indexFirst.get(i) - (int) indexSed.get(j));
                if (distance < minDs) minDs = distance;
            }
        return minDs;
    }
}

改进

可以通过index的相互推进，算法效率可以获得更大的提高。但是实际情况，运行速度比上面的还要慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int shortest(String word1, String word2) {
    List indexFirst = wordsMap.get(word1);
    List indexSed = wordsMap.get(word2);
    int minDs = Integer.MAX_VALUE;
    
    for (int i = 0, j = 0; i < indexFirst.size() && j < indexSed.size(); ) {
        int indexA = (int) indexFirst.get(i);
        int indexB = (int) indexSed.get(j);
        if (indexA - indexB > 0) {
            minDs = Math.min(minDs, indexA - indexB);
            j++;
        } else {
            minDs = Math.min(minDs, indexB - indexA);
            i++;
        }
    }
    return minDs;
}

学到的东西

  • 如果初始化一个Map中的List。第一次出现的时候创建new ArrayList, 其他的时候直接添加即可
  • 在for 循环中，可以给出多个条件，例如本题中的i 和 j。在最后加的那一步，可以缺失。

第二题 245. Shortest Word Distance III

算法

在本题中，需要考虑新的情况，即当两个words相同时候如何处理，这个时候自己第一题中的两个if 判断就不能再继续使用了。
需要加入判断旗帜flag进行情况判断

自己的算法，快速但是丑陋
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
public int shortestWordDistance(String[] words, String word1, String word2) {
    int index1 = Integer.MAX_VALUE, index2 = Integer.MAX_VALUE, distance = Integer.MAX_VALUE;
    boolean flagEqual = false, flagFirst = true;
    if (word1.equals(word2)) flagEqual = true;
    if (flagEqual) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word.equals(word1) && flagFirst) {
                index1 = i;
                distance = Math.min(distance, Math.abs(index1 - index2));
                flagFirst = false;
            } else if (word.equals(word2)) {
                index2 = i;
                distance = Math.min(distance, Math.abs(index1 - index2));
                flagFirst = true;
            }
        }
    } else {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word.equals(word1)) {
                index1 = i;
                distance = Math.min(distance, Math.abs(index1 - index2));
            }
            if (word.equals(word2)) {
                index2 = i;
                distance = Math.min(distance, Math.abs(index1 - index2));
            }
        }
    }
    return distance;
}
别人的

这个算法容易理解，但是由于在O(n)的循环过程中，每一次都对distance进行了计算，所以效率较低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int shortestWordDistance2(String[] words, String word1, String word2) {
    long index1 = Integer.MAX_VALUE, index2 = -Integer.MAX_VALUE, distance = Integer.MAX_VALUE;
    boolean flag = false;
    if (word1.equals(word2)) flag = true;
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        if (word.equals(word1)) {
            if (flag) {
                index1 = index2;
                index2 = i;
            } else {
                index1 = i;
            }
        } else if (word.equals(word2)) {
            index2 = i;
        }
        distance = Math.min(distance, Math.abs((index1 - index2)));
    }
    return (int) distance;
}

学到的东西

有个非常重要的点，对于别人的算法的时候。在初始化的时候，如果用int进行定义，那么第一次两个相减的时候，由于定义的是Integer.MAX_VALUE那么相减之后会变成负的最大，所以需要定义为long类型。这点再以后的刷题中一定要注意。

第三题 238. Product of Array Except Self

算法

一个数的乘法和为其左边所有数相乘，然后再乘右边所有数相乘。我们可以用一个Array将其左边的值保存下来，然后同时再保存右边的值。这样就可以做到在不用除法的情况下计算出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * nums   = [1, 2, 3, 4]
 * output = product of nums[left of i] * product of nums[right of i]
 */
 public static int[] productExceptSelf2(int[] nums) {
     int[] result = new int[nums.length];
     for (int i = 0, tmp = 1; i < nums.length; i++) {
         result[i] = tmp;
         tmp *= nums[i];
     }
     for (int i = nums.length - 1, tmp = 1; i >=0; i--) {
         result[i] *= tmp;
         tmp *= nums[i];
     }
     return result;
 }

学到东西

如果使用除法，注意0这样特殊的点

第四题 167. Two Sum II - Input array is sorted

算法

由于Array是排序的，所以我们用两个pointer进行推进，最后肯定是能找到答案的。在这个算法中，有两个指针，分别指向最左端和最右端。之后根据sum的大小进行调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ppublic int[] twoSum2(int[] numbers, int target) {
    int[] result = new int[2];
    if (numbers.length < 2) return result;
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if ( sum == target) {
            result[0] = left + 1;
            result[1] = right + 1;
            break;
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return result;
}