十大排序算法冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法
它重复地遍历要排序的数列,一次比较两个元素,如果顺序错误就把它们交换过来
遍历的最终结果是会把最大的数冒泡地沉到最底下,最小的数会像鱼泡一样被冒泡地推到最上面来
算法步骤
比较相邻的元素。如果第一个比第二个大,就交换它们两个
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
针对所有的元素重复以上的步骤,除了最后一个
重复步骤 1~3,直到排序完成
图解算法
实现代码1234567891011121314151617181920212223242526272829/** * 冒泡排序 * * @param nums 待排序数组 */public static void BubbleSort(int[] nums) { // 初始化两个指针,slow和fast int slow = 0, fast = 1; // 外层循环,遍历整个数组 for (int i = 0; i < nums.length; i++) & ...
KMP算法KMP 算法是一个快速查找匹配串的算法,它的作用其实就是本题问题:如何快速在「原字符串」中找到「匹配字符串」在朴素解法中,不考虑剪枝的话复杂度是 O(m∗n) 的,而 KMP 算法的复杂度为 O(m+n)KMP 之所以能够在O(m+n) 复杂度内完成查找,是因为其能在「非完全匹配」的过程中提取到有效信息进行复用,以减少「重复匹配」的消耗
匹配过程前缀: 对于字符串 abc…efg,我们称 abc 属于 ab…efg 的某个前缀后缀: 对于字符串 abc…efg,我们称 efg 属于 ab…efg 的某个后缀
假设原串为 abeababeabf,匹配串为 abeabf
朴素匹配不使用 KMP,采用最朴素的暴力匹配方法首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置首次匹配的「发起点」是第一个字符 a 显然,后面的 abeab 都是匹配的,两个指针会同时往右移动(黑标)在都能匹配上 abeab 的部分,「朴素匹配」和「KMP」并无不同
直到出现第一个不同的位置(红标):接下来,正是「朴素匹配」和「KMP」出现不同的地方:先看下「朴素匹配」逻辑:将原串的指针移动至本 ...
12345678910111213141516171819public int binarySearch(int[] nums, int target) { // 二分查找 int left = 0, right = nums.length - 1; int mid = 0; while (left <= right) { mid = left + ((right - left) >> 1); if (nums[mid] == target) { return mid; } // 二分查找的模板 if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { ...
有效的括号LeetCode 第 20 题 简单题
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例1
输入:s = “()”输出:true
示例2
输入:s = “()[]{}”输出:true
示例3
输入:s = “(]”输出:false
查看提示
1 <= s.length <= 104s 仅由括号 '()[]{}' 组成
栈解题思路
用 map 去记录对应的括号匹配情况循环字符串栈为空,或 top 元素不为对应的匹配值,将这个括号压入栈top 元素和当前括号匹配上就出栈栈为空就说明括号是闭合的,不为空说明不匹配,有可能是顺序问题,也可能是数量问题
...
1234567891011121314151617class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 边界条件设置 if (list1 == null) { return list2; } else if (list2 == null) { return list1; } else if (list1.val < list2.val) { // list1 的 val 小于 liste2,将 list1 节点的下一个节点指向递归后合并的链表 list1.next = mergeTwoLists(list1.next, list2); return list1; } else { ...
两数之和LeetCode 第 1 题 简单题
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
输入:nums = [2,7,11,15], target = 9输出:[0,1]解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例2
输入:nums = [3,2,4], target = 6输出:[1,2]
示例3
输入:nums = [3,3], target = 6输出:[0,1]
查看提示
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案
1234567891011121314151617clas ...
回文数LeetCode 第 9 题 简单题
给一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例1
输入:x = 121输出:true
示例2
输入:x = -121输出:false解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例3
输入:x = 10输出:false解释:从右向左读, 为 01 。因此它不是一个回文数。
查看提示
-231 <= x <= 231 - 1
反转一半数字 反转一半数字解题思路
先考虑处理临界情况所有负数都不可能是回文最低位和最高位不为 0通过 while 循环去反转这个数判断条件就是反转之后的数是否大于当前的数如果大于说明反转完成如果小于就说明还需要去反转,就将反转后的数字 * 10,并将 x 的最 ...
多数元素 IILeetCode 第 229 题 中等题
给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例1
输入:nums = [3,2,3]输出:[3]
示例2
输入:nums = [1]输出:[1]
示例3
输入:nums = [1,2]输出:[1,2]
查看提示
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
HashMap 法 HashMap法解题思路
遍历整个数组,对记录每个数值出现的次数(利用 HashMap,其中 key 为数值,value 为出现次数)再去遍历这个 HashMap ,如果这个数值出现的次数 > ⌊ n/3 ⌋ 的话,那这个数值就是要寻找的值出现的数值最终要 ...
多数元素ILeetCode 第169题 简单题
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例1
输入:nums = [3,2,3]输出:3
示例2
输入:nums = [2,2,1,1,1,2,2]输出:2
查看提示
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
HashMap法 HashMap法解题思路
遍历整个数组,对记录每个数值出现的次数(利用 HashMap,其中 key 为数值,value 为出现次数)再去遍历这个 HashMap ,如果这个数值出现的次数 > ⌊ n/2 ⌋ ...
