关于算法:笔试算法题总结

44次阅读

共计 1691 个字符，预计需要花费 5 分钟才能阅读完成。

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 判断即可。
这题也能够应用字典树来实现，有趣味的小伙伴能够搜寻什么是字典树。

某音口试有一道外围是判断否是双端队列的问题，就是一个队列只能从两端进。一次放入 n 个数，给一个数组判断是否是双端队列。
6 3 1 2 4 5 7 8
口试过程中想简单了，后边看到其实就是找到最小数，而后判断最小数到头尾是否是递增序列。其实在学数据结构的时候做过相似的选择题，然而不须要代码实现。对于平时的思维落实到代码实现很重要。

在网上看见说算法题通过率 * 本题分数为最初得分。对于一些输入 True 或 False 的题不会做能够间接输入后果，或者输入最小次数的题也能够间接输入 3 或 4 或 5。

正文完