算法

Hot100 贪心算法 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 class Solution { public int maxProfit(int[] prices) { if(prices.length==0){ return 0; } int max=0,len=prices.length; int pre=prices[0]; for(int p:prices){ if(p<pre){ pre=p; } max=Math.max(max,p-pre); } return max; } } 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false class Solution { public boolean canJump(int[] nums) { int n = nums.length; int farthest = 0; for (int i = 0; i < n - 1; i++) { // 不断计算能跳到的最远距离 farthest = Math....

数据结构 数据结构知识 具体内容 数组：数组的内存空间是连续的，随机访问的时间复杂度是O1，适用于需要按索引访问元素的场景，但是插入和删除元素较慢，时间复杂度是On 链表：链表是由节点组成，节点之间是分散存储的，内存不连续，每个节点存储数据和指向下一个节点的指针。适用于频繁插入和删除元素的场景，随机访问元素较慢 栈：栈是一种后进先出的数据结构，只允许在栈顶进行插入和删除操作 队列：队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首删除元素 树：树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。树适用于表示层次关系的场景，例如文件系统、组织结构等 数组与链表区别？ 访问效率，插入和删除操作效率，缓存命中率 应用场景：数组适合静态大小、频繁访问元素的场景，而链表适合动态大小、频繁插入、删除操作的场景 平衡二叉树 二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质： 非空左子树的所有键值小于其根结点的键值。 非空右子树的所有键值大于其根结点的键值。 左、右子树都是二叉搜索树。 二叉树搜索树的目的：缩短插入、删除、修改和查找节点的时间 一棵理想的二叉搜索树所有操作的时间可以缩短到 O(logn) 一棵每个结点只有右孩子的二叉搜索树，那么性质就和链表一样 平衡树将二叉查找树平衡均匀地分布，好处就是可以减少二叉查找树的深度 平衡二叉树平衡的特性： 左右两个子树的高度差（平衡因子）的绝对值不超过1 左右两个子树都是一棵平衡二叉树 红黑树 每个节点要么是红色，要么是黑色。 根节点是黑色。 每个叶子节点（NIL节点）是黑色。 如果一个节点是红色，则其子节点必须是黑色。 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。 二叉查找树 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n) 平衡二叉查找树 每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) B+树 B+树是一种自平衡的多路查找树，所有叶节点都位于同一层，保证了树的平衡，使得搜索、插入和删除操作的时间复杂度为对数级别的 非叶节点仅包含索引信息，不存储具体的数据记录，用来引导搜索到正确的叶节点 所有数据记录都存储在叶节点中，且叶节点中的数据是按关键字排序的。叶节点包含实际的数据和关键字，是数据存储和检索的实体单元。叶节点之间通过指针相互链接，形成一个链表，便于范围查询和顺序遍历 B+树与B-树 检索路径：B树在查找数据时，可能在非叶子节点找到目标数据，路径长度不固定。B+树中所有数据都在叶子节点，查找数据时必须走到叶子节点，路径长度固定（均等）。即查找总是要到叶子节点结束 叶子节点结构：B树中叶子节点之间没有特别的链接，彼此独立。B+树中叶子节点通过指针连接，形成一个有序链表，便于范围查询和顺序访问 非叶子节点内容：B树中非叶子节点存储数据和索引。B+树中非叶子节点只存储索引，不存储实际数据。当数据量比较大时，相对于B树，B+树的层高更少，查找效率也就更高。 **高效地范围查询：**B+树叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树在进行范围查询时需要进行中序遍历，性能较差 堆 堆是一颗完全二叉树，实现的堆也被称为二叉堆。堆中节点的值都大于等于（或小于等于）其子节点的值，堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于等于其子节点的值，我们将其称为小顶堆 排序算法 冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）。时间复杂度：最好情况下O(n)，最坏情况下O(n^2)，平均情况下O(n^2)。，空间复杂度：O(1) //冒泡排序 public static void bubbleSort(int[] arr) { int temp;//临时变量 boolean flag;//是否交换的标志 for (int i = 0; i < arr....

Hot100 回溯 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案 class Solution { List<List<Integer>>res; int len=0; public List<List<Integer>> permute(int[] nums) { this.res=new LinkedList<>(); this.len=nums.length; dfs(nums,new LinkedList<>(),new boolean[len]); return res; } public void dfs(int[] nums,LinkedList path,boolean[]p){ if(path.size()==len){ res.add(new LinkedList<>(path)); return; } for(int i=0;i<len;i++){ if(p[i]){ continue; } p[i]=true; path.add(nums[i]); dfs(nums,path,p); p[i]=false; path.remove(path.size()-1); } } } 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集 class Solution { List<List<Integer>>res=new LinkedList<>(); LinkedList<Integer>track=new LinkedList<>(); public List<List<Integer>> subsets(int[] nums) { backtracking(nums,0); return res; } public void backtracking(int[] nums,int start){ res....

以前写的总结 框架思维： 数据结构的存储方式：数组和链表 任何数据结构无非遍历和访问，在不同的场合高效增删改查 而遍历分为线性和非线性（for/while和递归） 算法心得： 算法的本质就是无穷举 数组/单链表常用：双指针，二分搜索，滑动窗口，回文子串，前缀和，差分数组 二叉树常用：1.遍历一遍二叉树(递归函数无返回值) 2.分解问题计算答案(递归函数有返回值) 二叉树： void traverse(TreeNode root) { if (root == null) { return; } // 前序位置 :进入结点的时候 traverse(root.left); // 中序位置 traverse(root.right); // 后序位置 :离开结点的时候 } 层序遍历：竖while横for 链表：双指针 设置虚拟结点，用指针来进行变化，同时新建链表注意指明最后一个结点 回溯算法： 回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」 我们通过保证元素之间的相对顺序来防止出现重复子集—-用start变量 标记那些元素可以被选择—–用used数组 重复元素中找可能解—-先排序，用num[i]==num[i-1]来减枝 重复元素的全排列—-先排序，用num[i]==num[i-1]&&!used[i-1]固定相同数值位置来减枝（规则：相同则前一个必走过），且used[i]标记该数值是否被使用 子集/组合问题必须用start，排列问题必用used数组 数组： 双指针 一维前缀和：preSum[i] 记录 nums[0..i-1] 的累加和 二维前缀和：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和 对于前缀和问题：申请新数组范围是n+1，数组实际从索引1开始 差分数组：差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。 后面数据靠前面的差值，diff[i] 就是 nums[i] 和 nums[i-1] 之差 如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：...

Hot100 二叉树 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stk = new Stack<TreeNode>(); while (root != null || !stk.isEmpty()) { while (root != null) { stk.push(root); root = root.left; } root = stk.pop(); res.add(root.val); root = root.right; } return res; } } 思考中序过程就行 给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 class Solution { public int maxDepth(TreeNode root) { return Depth(root); } public int Depth(TreeNode root){ if(root==null){ return 0; } int left=Depth(root....

Hot100 哈希 两数之和 class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer>map=new HashMap<>(); int len=nums.length; for(int i=0;i<len;i++){ int p=target-nums[i]; if(map.containsKey(p)){ return new int[]{i,map.get(p)}; } map.put(nums[i],i); } return new int[]{0,0}; } } 字母异位分组 class Solution { public List<List<String>> groupAnagrams(String[] strs) { HashMap<String,LinkedList<String>>cur=new HashMap<>(); for(String str:strs){ char[] c1=str.toCharArray(); Arrays.sort(c1); String s=String.valueOf(c1); if(!cur.containsKey(s)){ cur.put(s,new LinkedList<>()); cur.get(s).add(str); }else{ cur.get(s).add(str); } } return new LinkedList(cur.values()); } } 最长连续序列：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度 class Solution { public int longestConsecutive(int[] nums) { int ans = 0; Set<Integer> st = new HashSet<>(); for (int num : nums) { st....

数据结构 数组 ArrayList`<Integer>`arr=new ArrayList<>();int[]c=new int[3];数组建立 arr.add(99);数组增加 arr.toArray(a);集合变成数组类型 arr.add(3,99);数组插入 arr.get(3);获得元素值 arr.set(3,22);改变元素值 arr.remove(3);移除某索引的元素 Collections.reverse(arr);反转一个arr arr.size();长度 普通数组长度为：length arr.contains(99);是否含有某元素 Collections.sort(arr);集合类的排序 Arrays.sort(c);普通排序 Arrays.fill(c, 1);填充数组c的所有值为1 二维数组排序：第一列按升序排列，第一列相同，则第二列按升序排列 compare方法返回值int类型，返回值大于0，交换两数，小于零，排序正确，等于0，两数相等 Arrays.sort(arr, new Comparator<int[]>() { public int compare(int[] e1, int[] e2) { // 如果第一列元素相等，则比较第二列元素 if (e1[0]==e2[0]) return e1[1]-e2[1]; // e1[1]-e2[1]表示对于第二列元素进行升序排序 return e1[0]-e2[0]; } Arrays.sort(intervals,new Comparator<int[]>(){//两数相减或相加会产生int值溢出，因此通过比较后，直接返回-1，0，1 public int compare(int[]e1,int[]e2){// e1[0]-e2[0]表示对于第一列元素进行升序排序 if(e1[0]>e2[0]){ return 1; }else if(e1[0]==e2[0]){ return 0; }else{ return -1; } } }); Arrays.sort(intervals, (e1, e2) -> Integer.compare(e1[0], e2[0]));//上面可简写 Arrays.sort(strings,(s1,s2)-> (s1+s2).compareTo(s2+s1)); Collections....