每天坚持两道题，整理数据结构与算法相关代码.zip

# 记录和总结数据结构与算法相关内容 ###主要实践为leetcode，剑指offer，各大公司笔试，面试题。 本仓库主要用于学习数据结构与算法，同时作为笔试、面试刷题积累，主要用于提升自身的编程能力。在自己思考的基础之上融入高手们的编程思想，做好详细记录。 ## 如何写出正确的程序？ ## - 明确变量的含义 - 循环不变量 - 小数据量调试 - 大数据量的测试 ## 时间复杂度分析与空间复杂度分析 增加一个文件夹leetcode，用于记录数据结构与算法相关的完成代码。主要分为Array，链表，栈，队列，二叉树，图，排序，递归，贪心，分治，动态规划，回溯。 # 一、数组 # 数组是一种**线性表数据结构**，用一组**连续的内存空间**来存储一组具有**相同类型**的数据。其最大特点是**支持随机访问**，但删除，插入操作低效。 数组在定义时需要预先指定大小，因为需要分配连续的内存空间。 Java中的ArrayList支持动态扩容，当存储空间不够时，其空间自动扩容为1.5倍大小。 数组和链表的区别？ 数组按照下标访问时，其时间复杂度是O(1),插入元素的时间复杂度是O(n),链表适合插入和删除数据，时间复杂度为O(1)。 ## 数组的基本操作 ## - Insert--在指定索引插入一个元素 - Get--返回指定索引的元素 - Delete--删除指定索引位置的元素 - Size--数组所有元素的数量 ## 数组常见问题 ## - 二分查找，注意二分查找的实现 - 寻找数组中的第二小的元素 - 找到数组中第一个不重复出现的整数 - 合并两个有序数组 - 重新排列数组中的正值和负值 - 连续子数组的和 - 顺时针打印矩阵 leetcode 283. Move Zeroes leetcode 27. Remove Element leetcode 26. Remove Duplicates from Sorted letcode 80. Remove Duplicates from Sorted Array II leetcode 75. Sort Colors leetcode 88. Merge Sorted Array leetcode 215. Kth Largest Element in an Array leetcode 125. Valid Palindrome leetcode 345. Reverse Vowels of a String leetcode 11. Container With Most Water 34. 在排序数组中查找元素的第一个和最后一个位置 ## 双索引技术 ## 15. 三数之和 class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<=nums.length-2;i++){ if(i>0 && nums[i]==nums[i-1]){ continue; } //设置双指针 int left = i+1; int right = nums.length-1; while(left<right){ if(nums[i] + nums[left] +nums[right] < 0){ left++; } else if(nums[i] + nums[left] +nums[right] > 0){ right--; } else{ res.add(Arrays.asList(nums[i],nums[left],nums[right])); //防止相等元素，导致结果重复 while(left < nums.length-1 && nums[left] == nums[left+1]){ left++; } //防止相等元素，导致结果重复 while(right > 0 && nums[right] == nums[right-1]){ right--; } left++; right--; } } } return res; } } leetcode 209. Minimum Size Subarray Sum ## 滑动窗口法。 leetcode 3. Longest Substring Without leetcode 438.Find All Anagrams in a String leetcode 76. Minimum Window Substring ## 二分查找(运行效率还不如for循环) 34. 在排序数组中查找元素的第一个和最后一个位置 public int[] searchRange(int[] nums, int target) { if(nums.length==0||nums == null){ return new int[]{-1,-1}; } int start = findFirst(nums,target); if( start == -1){ return new int[]{-1,-1}; } return new int[]{start,findLast(nums,start,target)}; } public int findFirst(int[] nums,int target){ int left = 0; int right = nums.length-1; while(left < right){ int mid = left + (right-left)/2; if(nums[mid]==target){ right = mid; } else if(nums[mid]<target){ left = mid+1; }else{ right = mid-1; } } return nums[left] == target? left:-1; } public int findLast(int[] nums,int num,int target){ int left = num; int right = nums.length-1; while(left < right){ int mid = left + (right-left+1)/2; if(nums[mid]==target){ left = mid; } else if(nums[mid]<target){ left = mid+1; }else{ right = mid-1; } } return nums[left] == target? left:-1; } class Solution { public int[] searchRange(int[] nums, int target) { int first = -1; int i = 0; for(;i<nums.length;i++){ if(nums[i] == target){ first = i; break; } } if(first == -1){ return new int[]{-1,-1}; } int count = -1; for(int j = i;j<nums.length;j++){ if(nums[j] == target){ count++; } } return new int[]{first,first+count}; } } # 二、链表 # 链表包括单链表、双向链表以及循环链表 ## 链表的基本操作 ## - InsertAtEnd 在链表的尾部插入指定元素 - InsertAtHead 在链表的头部插入指定元素 - Delete 从链表删除指定元素 - DeleteAtHead 删除链表的第一个元素 - Search 从链表中返回指定元素 - isEmpty 如果链表为空，则返回true ## 链表常见问题 ## - 1.反转链表 - 2.检查链表中的循环 - 3.返回链表中倒数第N个节点 - 4.删除链表中的重复项 -5合并两个排序的链表 # 三、查找表 # map+set 350. 两个数组的交集 II 242. 有效的字母异位词 202. 快乐数 290. 单词模式 205. 同构字符串 451. 根据字符出现频率排序 1. 两数之和 15. 三数之和 16. 最接近的三数之和 454. 四数相加 II 18. 四数之和 49. 字母异位词分组 447. 回旋镖的数量 ## 滑动窗口+查找表 219. 存在重复元素 II 217. 存在重复元素 220. 存在重复元素 III # 四、栈 # LIFO(后进先出) ## 栈的基本操作 ## - Push 在栈顶插入一个元素 - Pop 返回并移除栈顶元素 - isEmpty 若栈为空，则返回true - Top 返回顶部元素，但并不移除 ## 栈常见问题 ## - 1.使用栈计算后缀表达式 - 2.对栈元素进行排序 - 3.判断表达式是否括号平衡 - 4.包含min函数的栈 -5 栈的压入和弹出 # 五、队列 # FIFO(先进先出) ## 队列的基本操作 ## - Enqueue 在队列尾部插入元素 - Dequeue 在移除队列头部的元素 - isEmpty 如果队列为空则返回true - Top 返回队列第一个元素 ## 队列常见问题 ## - 1.使用队列表示栈 - 2.对队列的前K个元素倒序 - 3.使用队列生成1~n的二进制数 - 4.用两个栈实现队列 ##附加：跳表(Redis利用跳表实现有序集合Sorted Set) # 六、树 # 树形结构是一种层次式的数据结构，由顶点和边组成，但不存在回路 ## 树形结构的主要类型包括 ## - N元树 - 平衡树 高度差小于1 ## 二叉树 114. 二叉树展开为链表 class Solution { TreeNode prev = null; public void flatten(TreeNode root) { if(root == null){ return; } flatten(root.right);//先递归到最右边，在回溯 flatten(root.