Java 集合与手动循环 - 编码挑战/面试最佳实践

Question

对于编码挑战/面试以及优化，使用集合到底好不好？例如，检查以下程序的回文运行时间

    import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Palindrome {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        if(isPalindrome(str)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

        if(isPalindromeUsingSet(str)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }

    public static boolean isPalindrome(String str) {
        final long startTime = System.nanoTime();
        final long duration;
        for (int i=0;i<str.length()/2;i++) {
            if(str.charAt(i) != str.charAt(str.length() -1 -i)) {
                duration = System.nanoTime() - startTime; 
                System.out.println("isPalindrome - " + duration);
                return false;
            } 
        }
        duration = System.nanoTime() - startTime; 
        System.out.println("isPalindrome - " + duration);

        return true;
    }

    public static boolean isPalindromeUsingSet(String str) {
    final long startTime = System.nanoTime();
    final long duration;
    Set<Character> charSet = new HashSet<>();
    for (int i=0;i<str.length()/2;i++) {
        if(charSet.add(str.charAt(i)) == false) {
            duration = System.nanoTime() - startTime; 
            System.out.println("isPalindromeUsingSet - " + duration);
            return false;
        } else {
            charSet.remove(str.charAt(i));
        }
    }
    duration = System.nanoTime() - startTime; 
    System.out.println("isPalindromeUsingSet - " + duration);
    return true;
}

}

计算的运行时间如下所示。

AMANAPLANACANALPANAMA
isPalindrome - 7788
YES
isPalindromeUsingSet - 745473
YES

我的几个问题是:

1. 所以 java 集合在各种 CRUD 中大多是安全和通用的操作，为什么不使用它们？
2. 为了编写更好的优化解决方案，我应该寻找一个循环吗执行，使用大量 O(1) 数据结构？

我学习优化代码的方法:

1. 对于每一个编码问题，解决我java和数据的粗略方式结构。
2. 稍后去研究最佳解决方案，计算时间和复杂性并逐渐适应我的解决方案。

背景:我已经编写 Java 代码几年了。现在学习拼图、算法和时间复杂度的编码，以应对更大的面试!

任何好的方向表示赞赏。

谢谢

Answer 1

让我们看一下HashSet.add的实现:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

在内部，HashSet 使用 HashMap。

现在，让我们看一下HashMap.put方法的实现:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

我们可以注意到，从计算的角度来说，将注册表放入 map 是一项“艰巨的任务”。有一个:

• 哈希算法
• for 循环
• 添加入口方法执行
• 等等...

因此，如果执行时间是您的场景中的一个问题，那么手动循环是比 Java 集合更好的选择。

现在，就可读性和可维护性而言，Collections 是最好的选择。