HashMap
hashmap的原理这里不再讲述，不知道的小伙伴可以看这篇文章。Hash与HashMap
hashmap数据结构的引入能帮助我们将O(n)的时间复杂度降低为O（1）的时间复杂度，代价是使用了O（n）的空间复杂度。这么一看好像功过参半。但是如果我们原来的时间复杂度是O（n^2）,使用了hashmap后时间复杂度变为o（n），而只是空间复杂度变为O（n），那么还是很划算的。
力扣第一题，两数之和：
如果我们用单纯的二维遍历做的话
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
第一种方法时间高原因是，对于每一个第一层遍历的i，我们都需要再次遍历数组找到target - i。
如果我们用hashmap将数组元素值及对应下标存入hashmap里，我们就可以直接获得target - i对应下标值，而不需要第二次遍历。
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];
}
遇到的实际题目是三数之和，给一个数组和一个目标值，在这个数组中找到三个数相加为目标值，如果找得到返回true，如果找不到返回false。三数之和就可以使用hashmap将三层循环降为两层循环，其他跟两数之和相似。
动态规划
基本思想：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
某音公司笔试题，力扣原题改编
思路是依次确定是否能到达第i个位置。到达第i个位置的要求是能到达第j个位置（i>j）并能从第j个位置直接跳跃至第i个位置。
public boolean canJump(int[] nums) {
// 边界判断
if (nums.length == 1) {
return true;
}
boolean[] dp = new boolean[nums.length];
int i;
// 从第1个下标可以直接到达的地方标记为可到达。
for (i = 0; i < nums[0] + 1 && i < nums.length; i++) {
dp[i] = true;
}
// 其余标记为不可达
for (; i < nums.length; i++) {
dp[i] = false;
}
// 对于每一个位置i，确定是否能能到达第j个位置（i>j）并能从第j个位置直接跳跃至第i个位置
for (i = nums[0] + 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && j + nums[j] >= i) {
dp[i] = true;
break;
}
}
}
return dp[nums.length -1];
}
当然这只是一种思路，这题还有更快更好的方法。
力扣139题：单词拆分
遇上题相同思路，不过在判断一个单词是否在数组中时使用hashmap判断即可。
这题也可以使用字典树来实现，有兴趣的小伙伴可以搜索什么是字典树。
贪心算法
基本思想：贪心算法并不从整体最优上加以考虑，它所做的选择只是在某种意义上的局部最优解。
某公司面试题，力扣原题改编：
看起来很简单，但是思考起来没想到最优解。因为买入的天数一定小于卖出的天数，那么买入天数的价格一定是卖出天数到第一天里所有价格的最小值。解题思想是依次假设第i天是卖出那天，找第i天的之前最小价格那天价格，维护最大利润。
public int maxProfit(int[] prices) {
if (prices.length <= 1)
return 0;
int min = prices[0], profit = 0;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
profit = Math.max(profit, prices[i] - min);
}
return profit;
}其他
某音笔试有一道核心是判断否是双端队列的问题，就是一个队列只能从两端进。一次放入n个数，给一个数组判断是否是双端队列。6 3 1 2 4 5 7 8
笔试过程中想复杂了，后边看到其实就是找到最小数，然后判断最小数到头尾是否是递增序列。其实在学数据结构的时候做过类似的选择题，但是不需要代码实现。对于平常的思想落实到代码实现很重要。
应试技巧
在网上看见说算法题通过率*本题分数为最后得分。对于一些输出True或False的题不会做可以直接输出结果，或者输出最小次数的题也可以直接输出3或4或5。
