#第二周学习笔记
切题目： 1.clarification 2.possible solutions ---> optimal (time & space) 3.code 4.test cases #本周作业 1、有效的字母异位词
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
2、两数字和
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
3.N叉树的前序遍历 由于递归实现 N 叉树的前序遍历较为简单，因此我们只讲解如何使用迭代的方法得到 N 叉树的前序遍历。
使用一个栈来帮助我们得到前序遍历，需要保证栈顶的节点就是我们当前遍历到的节点。我们首先把根节点入栈，因为根节点是前序遍历中的第一个节点。随后每次我们从栈顶取出一个节点 u，它是我们当前遍历到的节点，并把 u 的所有子节点逆序推入栈中。例如 u 的子节点从左到右为 v1, v2, v3，那么推入栈的顺序应当为 v3, v2, v1，这样就保证了下一个遍历到的节点（即 u 的第一个子节点 v1）出现在栈顶的位置。
public List<Integer> preorder(Node root) {
LinkedList<Node> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
output.add(node.val);
Collections.reverse(node.children);
for (Node item : node.children) {
stack.add(item);
}
}
return output;
}
4.前 K 个高频元素
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
5.N 叉树的层序遍历 递归思想
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if (root != null) traverseNode(root, 0);
return result;
}
private void traverseNode(Node node, int level) {
if (result.size() <= level) {
result.add(new ArrayList<>());
}
result.get(level).add(node.val);
for (Node child : node.children) {
traverseNode(child, level + 1);
}
}
6.丑叔 利用本周学习的小根堆
private int[] uglyNumber = {2,3,5};
public int nthUglyNumber(int n) {
//创建小根堆，每次出堆的都是最小值
Queue<Long> queue = new PriorityQueue<>();
queue.add(1L);
//记录出堆的个数，出堆的元素完全按照从小到大排序
int count = 0;
while (! queue.isEmpty()){
long cut = queue.poll();
//如果出堆的个数>=n,当前cut就是第n个丑数
if(++count >= n){
return (int) cut;
}
for(int num : uglyNumber){
//排除重复的数字
if(! queue.contains(num * cut)){
queue.add(num * cut);
}
}
}
return -1;
}
#每日一题 两个数组的交集 II
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
#HashMap 的实现原理？ HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的数据结构： 在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根绝hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。
需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) #树的面试题解法一般都是递归，为什么？ 对树的增删改查操作，都涉及到树的遍历，而树的结构特点，基本就是根据某个节点（根节点）来遍历左子树或者右子树，这样重复性的操作，比较适合递归操作来完成。