刷题参考：[Leetcode 题解-CyC2018](https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode 题解 - 目录.md)算法思想分类： [双指针](# 双指针) 排序 贪心思想 二分查找 分治 搜索 动态规划 数学 双指针 [167] 两数之和 II - 输入有序数组 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明:返回的下标值（i...
题目原文 42. 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9 提示：n == height.length 0 <= n <= 3 * 104 0 <= height[i] <= 105 ...
前言 现在几乎所有大厂的软件岗位面试都会有算法题的面试，那么该如何准备算法面试呢？ 什么是算法面试？ 算法面试只是技术面试的一部分，大家要意识到算法只是技术的一部分，技术还包括计算机基础知识、项目中的经验，解决问题的思路等等，因此不要把算法面试当作技术面试的全部。不要一提到软件岗位就是刷题。 如何准备算法面试 要多关注基础的数据结构与算法，基础的算法设计思想。面试中的题目不会特别难。高级数据结构除非特定...
107. 二叉树的层次遍历 II题目 题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 例如： 给定二叉树 [3,9,20,null,null,15,7],3/ 9 20/ 15 7返回其自底向上的层次遍历为： [[15,7],[9,20],[3] ]解题思路思路：广度优先搜索（BFS） 先看题目，题目要求返回...
查找表：考虑的基本数据结构 第一类： 查找有无--set 元素a是否存在，通常用set：集合 set只存储键，而不需要对应其相应的值。 set中的键不允许重复 第二类： 查找对应关系(键值对应)--map 元素a出现了几次：dict-->字典 dict中的键不允许重复 第三类： 改变映射关系--map 通过将原有序列的关系映射统一表示为其他349 两个数组的交集 题目描述： 给定两个数组，编写一个函数来计算它们的交集。 示例 1：输入：nums1 = [1,2,2,1], n...
字母异位词分组 题目链接：https://leetcode-cn.com/problems/group-anagrams/ class Solution { public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, int> hashmap;vector<vector<string>> res;for(auto str : strs){auto tmp = str;sort(tmp.begin(), tmp.end());if(hashmap.count(tmp)){res[hashmap[tmp]].push_back(str);}else{hashmap[tmp] = res.size();res.push_back({str});}}retu...
和为K的子数组 题目链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/ 哈希 class Solution { public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();int cnt = 0;int sum = 0;unordered_map<int, int> hashmap;hashmap[0] = 1;for(int i = 0; i < n; i++){sum += nums[i];if(hashmap[sum - k]) cnt += hashmap[sum - k];hashmap[sum]++;}return cnt;} };
78. 子集 题目链接：https://leetcode-cn.com/problems/subsets/ class Solution { public:vector<vector<int>> res;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return res;}void dfs(vector<int>& nums, int u){res.push_back(path);for(int i = u; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back();}} };90. 子集II 题目链接：https://leetcode-cn.com/pr...
39. 组合总数 题目链接：https://leetcode-cn.com/problems/combination-sum/ class Solution { public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(candidates, target, 0, 0);return res;}void dfs(vector<int>& candidates, int target, int u, int sum){if(sum == target) {res.push_back(path);ret...
leetcode 46题： 给定一个 没有重复 数字的序列，返回其所有可能的全排列。输入: [1,2,3] 输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ] 思路就是按照这张图进行穷举 class Solution {private List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) { List<Integer> path = new ArrayList<>();backTrack(path, nums);return res;}private void backTrack(List<Integer...
我在研究该算法题的时候是先经过最笨的方法，然后慢慢优化得到计算量相对较少的算法。在研究该算法中断断续续的花了10个小时吧，基本都是晚上思考，白天为找工作准备。晚上思考算法并进行代码实现。 我也看了官方的答案，官方给的答案没有考虑数组中是否有重复的数。所以我这给了考虑重复的数的答案。如不准确还请告知。谢谢。 题目是： 给定一个整数数组 A ，考虑 A 的所有非空子序列。 对于任意序列 S ，设 S 的宽度是 S 的最大元...
这个层序遍历要求返回每层的节点，正常的BFS从队列中弹出一个节点后就判断其有没有左子树和右子树，所以直接用BFS实现的话无法分层输出。 需要记录每层的节点数目，增加一个for循环就可以了。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public List<List<Integer>> levelOrder(TreeNode...
本来想写完递归再写这个专栏的，但是老师给了一个贪心的题目，没办法只能开一个板块了 简介 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。 与这个局部最优解相对应的全局最优解会在动态规划里面展现出来。例题 先来一道经典的贪心热热手，跳跃游戏就算是一个比较经典的贪心题思路 一开始看到这个题目不知不觉开始用动态规划在写了 (ー〃) 仔细一看返...
题目： 数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。(难度：简单) 示例 1: 输入: cost = [10, 15, 20]输出: 15解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 ...
一、题目 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama"输出: true示例 2: 输入: "race a car"输出: false 二、解题思路 做过回文的题目，我比较喜欢用的方法，就是直接将字符串中的特殊字符啥的直接删除，然后将字符串中的字母转化为小写或者大写，之后使用StringBuffer将字符串的顺序颠...