数据结构与算法

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....

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....