大地保险网站,宿州网站建设哪家公司好,依波手表价格 官方网站,wordpress index.txt1.两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。
你可以按…1.两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
class Solution {public int[] twoSum(int[] nums, int target) {int n nums.length;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums[i] nums[j] target) {return new int[]{i, j};}}}return new int[0];}
}
方法二哈希表
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。
使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
这样我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer hashtable new HashMapInteger, Integer();for (int i 0; i nums.length; i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}2.回文数
给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。
回文数是指正序从左向右和倒序从右向左读都是一样的整数。例如121 是回文而 123 不是。 答案
class Solution {public boolean isPalindrome(int x) {// 特殊情况// 如上所述当 x 0 时x 不是回文数。// 同样地如果数字的最后一位是 0为了使该数字为回文// 则其第一位数字也应该是 0// 只有 0 满足这一属性if (x 0 || (x % 10 0 x ! 0)) {return false;}int revertedNumber 0;while (x revertedNumber) {revertedNumber revertedNumber * 10 x % 10;x / 10;}// 当数字长度为奇数时我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如当输入为 12321 时在 while 循环的末尾我们可以得到 x 12revertedNumber 123// 由于处于中位的数字不影响回文它总是与自己相等所以我们可以简单地将其去除。return x revertedNumber || x revertedNumber / 10;}
}3.罗马数字转整数 方法一模拟
思路
通常情况下罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况那么可以将每个字符视作一个单独的值累加每个字符对应的数值即可。
若存在小的数字在大的数字的左边的情况根据规则需要减去小的数字。对于这种情况我们也可以将每个字符视作一个单独的值若一个数字右侧的数字比它大则将该数字的符号取反。
class Solution {MapCharacter, Integer symbolValues new HashMapCharacter, Integer() {{put(I, 1);put(V, 5);put(X, 10);put(L, 50);put(C, 100);put(D, 500);put(M, 1000);}};public int romanToInt(String s) {int ans 0;int n s.length();for (int i 0; i n; i) {int value symbolValues.get(s.charAt(i));if (i n - 1 value symbolValues.get(s.charAt(i 1))) {ans - value;} else {ans value;}}return ans;}
}4.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。
class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}String prefix strs[0];int count strs.length;for (int i 1; i count; i) {prefix longestCommonPrefix(prefix, strs[i]);if (prefix.length() 0) {break;}}return prefix;}public String longestCommonPrefix(String str1, String str2) {int length Math.min(str1.length(), str2.length());int index 0;while (index length str1.charAt(index) str2.charAt(index)) {index;}return str1.substring(0, index);}
}public static String re(String[] str){if(str.length0){return ;}String str1str[0];for (int i 1; i str.length; i) {str1 bj(str1, str[i]);if (str1.length()0){break;}//当第一个没有比对上时直接用break结束循环减少时间。}if (str1.length()0){return ;}return str1;
}private static String bj(String str2, String str3) {int min Math.min(str2.length(), str3.length());int index0;while (indexminstr2.charAt(index)str3.charAt(index)){index;}//用while比for循环次数更少return str2.substring(0,index);
}public static void main(String[] args) {String[] strnew String[]{moyon,molon,moxue};String result re(str);System.out.println(result);
}5.删除有序数组中的重复项
给你一个有序数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 答案
解法 双指针
首先注意数组是有序的那么重复的元素一定会相邻。
要求删除重复元素实际上就是将不重复的元素移到数组的左侧。
考虑用 2 个指针一个在前记作 p一个在后记作 q算法流程如下
1.比较 p 和 q 位置的元素是否相等。
如果相等q 后移 1 位
如果不相等将 q 位置的元素复制到 p1 位置上p 后移一位q 后移 1 位
重复上述过程直到 q 等于数组长度。
返回 p 1即为新数组长度。public int removeDuplicates(int[] nums) {if(nums null || nums.length 0) return 0;int p 0;int q 1;while(q nums.length){if(nums[p] ! nums[q]){nums[p 1] nums[q];p;}q;}return p 1;
}6.移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
答案
方法一双指针
思路及算法由于题目要求删除数组中等于val 的元素因此输出数组的长度一定小于等于输入数组的长度我们可以把输出的数组直接写在输入数组上。可以使用双指针右指针 right 指向当前将要处理的元素左指针 left 指向下一个将要赋值的位置。如果右指针指向的元素不等于 val它一定是输出数组的一个元素我们就将右指针指向的元素复制到左指针位置然后将左右指针同时右移如果右指针指向的元素等于val它不能在输出数组里此时左指针不动右指针右移一位。整个过程保持不变的性质是区间 [0,left) 中的元素都不等于val。当左右指针遍历完输入数组以后left 的值就是输出数组的长度。这样的算法在最坏情况下输入数组中没有元素等于 val左右指针各遍历了数组一次。class Solution {public int removeElement(int[] nums, int val) {int n nums.length;int left 0;for (int right 0; right n; right) {if (nums[right] ! val) {nums[left] nums[right];left;}}return left;}
}
另一种写法
class Solution {public int removeElement(int[] nums, int val) {int ans 0;for(int num: nums) {if(num ! val) {nums[ans] num;ans;}}return ans;}
}方法二双指针优化
思路如果要移除的元素恰好在数组的开头例如序列 [1,2,3,4,5][1,2,3,4,5]当 val 为 11 时我们需要把每一个元素都左移一位。注意到题目中说「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 55 移动到序列开头取代元素 11得到序列 [5,2,3,4][5,2,3,4]同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。实现方面我们依然使用双指针两个指针初始时分别位于数组的首尾向中间移动遍历该序列。算法如果左指针 left 指向的元素等于 val此时将右指针 right 指向的元素复制到左指针 left 的位置然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val可以继续把右指针 right 指向的元素的值赋值过来左指针left 指向的等于 val 的元素的位置继续被覆盖直到左指针指向的元素的值不等于 val 为止。当左指针 left 和右指针 right 重合的时候左右指针遍历完数组中所有的元素。这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是方法二避免了需要保留的元素的重复赋值操作。class Solution {public int removeElement(int[] nums, int val) {int left 0;int right nums.length;while (left right) {if (nums[left] val) {nums[left] nums[right - 1];right--;} else {left;}}return left;}
}7.字符串出现位置
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串出现的第一个位置下标从 0 开始。如果不存在则返回 -1 如果needle字符串为空则返回0。
public static int strStr(String haystack, String needle) {if (needle.equals()){return 0;}int indexneedle.length();for(int i0;indexhaystack.length();i,index){String temphaystack.substring(i,index);if (temp.equals(needle)){return 1;}}return -1;
}public static void main(String[] args) {String ahello;String bll;int num strStr(a, b);System.out.println(num);
}8.搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
答案
「二分查找」作为一种基础算法本不该很难所以希望借这道题的讲解和大家谈谈如何学习算法「二分查找」就那么几行代码我们完全有理由充分掌握它而不可以用记忆模板、背例题的方式
「二分查找」虽然看起来有很多种写法「递归」和「非递归」「非递归」又有好几种写法while (left right)、while (left right)、while (left 1 right)。但核心的思想就一个逐渐缩小问题规模。我们在学习和练习的时候需要 首先着眼于掌握算法的思想而不该去纠结二分的几种写法的区别和细节这样会让自己更乱
在面对问题的时候应该将主要精力放在 如何分析利用单调性绝大多数二分查找问题利用的是单调性也有一些例外或者题目本身蕴含的可以逐渐缩小问题规模的特性解决问题而不应该纠结在「二分查找」该怎么写。
class Solution {public int search(int[] nums, int target) {int len nums.length;int left 0;int right len - 1;// 在 [left..right] 里查找 targetwhile (left right) {// 为了防止 left right 整形溢出写成这样int mid left (right - left) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] target) {// 下一轮搜索区间[left..mid - 1]right mid - 1;} else {// 此时nums[mid] target下一轮搜索区间[mid 1..right]left mid 1;}}return -1;}
}9.最大子序和
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 答案
一
这道题用动态规划的思路并不难解决比较难的是后文提出的用分治法求解但由于其不是最优解法所以先不列出来
动态规划的是首先对数组进行遍历当前最大连续子序列和为 sum结果为 ans
如果 sum 0则说明 sum 对结果有增益效果则 sum 保留并加上当前遍历数字
如果 sum 0则说明 sum 对结果无增益效果需要舍弃则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小将最大值置为ans遍历结束返回结果1.假如全是负数那就是找最大值即可因为负数肯定越加越大。 2.如果有正数则肯定从正数开始计算和不然前面有负值和肯定变小了所以从正数开始。 3.当和小于零时这个区间就告一段落了然后从下一个正数重新开始计算
class Solution {public int maxSubArray(int[] nums) {int ans nums[0];int sum 0;for(int num: nums) {if(sum 0) {sum num;} else {sum num;}ans Math.max(ans, sum);}return ans;}
}
二
class Solution {public int maxSubArray(int[] nums) {int pre 0, maxAns nums[0];for (int x : nums) {pre Math.max(pre x, x);maxAns Math.max(maxAns, pre);}return maxAns;}
}10.最后一个单词的长度
给你一个字符串 s由若干单词组成单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词请返回 0
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串
答案
标签字符串遍历
从字符串末尾开始向前遍历其中主要有两种情况
第一种情况以字符串Hello World为例从后向前遍历直到遍历到头或者遇到空格为止即为最后一个单词World的长度5
第二种情况以字符串Hello World 为例需要先将末尾的空格过滤掉再进行第一种情况的操作即认为最后一个单词为World长度为5
所以完整过程为先从后过滤掉空格找到单词尾部再从尾部向前遍历找到单词头部最后两者相减即为单词的长度
时间复杂度O(n)n为结尾空格和结尾单词总体长度
class Solution {public int lengthOfLastWord(String s) {int end s.length() - 1;while(end 0 s.charAt(end) ) end--;if(end 0) return 0;int start end;while(start 0 s.charAt(start) ! ) start--;return end - start;}11.加一
给定一个由 整数 组成的 非空 数组所表示的非负整数在该数的基础上加一。 最高位数字存放在数组的首位 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外这个整数不会以零开头
答案
根据题意加一没错就是加一这很重要因为它是只加一的所以有可能的情况就只有两种除 99 之外的数字加一
数字 99。
加一得十进一位个位数为 00 加法运算如不出现进位就运算结束了且进位只会是一。所以只需要判断有没有进位并模拟出它的进位方式如十位数加 11 个位数置为 00如此循环直到判断没有再进位就退出循环返回结果。然后还有一些特殊情况就是当出现 9999、999999 之类的数字时循环到最后也需要进位出现这种情况时需要手动将它进一位。
class Solution {public int[] plusOne(int[] digits) {for (int i digits.length - 1; i 0; i--) {digits[i];digits[i] digits[i] % 10;if (digits[i] ! 0) return digits;}digits new int[digits.length 1];digits[0] 1;return digits;}
}12.二进制求和
给你两个二进制字符串返回它们的和用二进制表示。
输入为 非空 字符串且只包含数字 1 和 0
Integer.toBinaryString()//十进制转换为二进制形式答案
整体思路是将两个字符串较短的用 00 补齐使得两个字符串长度一致然后从末尾进行遍历计算得到最终结果。本题解中大致思路与上述一致但由于字符串操作原因不确定最后的结果是否会多出一位进位所以会有 2 种处理方式第一种在进行计算时直接拼接字符串会得到一个反向字符需要最后再进行翻转
第二种按照位置给结果字符赋值最后如果有进位则在前方进行字符串拼接添加进位class Solution {public String addBinary(String a, String b) {StringBuilder ans new StringBuilder();int ca 0;for(int i a.length() - 1, j b.length() - 1;i 0 || j 0; i--, j--) {int sum ca;sum i 0 ? a.charAt(i) - 0 : 0;sum j 0 ? b.charAt(j) - 0 : 0;ans.append(sum % 2);ca sum / 2;}ans.append(ca 1 ? ca : );return ans.reverse().toString();}
}13.x的平方根
实现 int sqrt(int x) 函数。
Math.sqrt(int x)//求平方根计算并返回 x 的平方根其中 x 是非负整数。 由于返回类型是整数结果只保留整数的部分小数部分将被舍去。
答案
由于计算机无法存储浮点数的精确值浮点数的存储方法可以参考 IEEE 754这里不再赘述而指数函数和对数函数的参数和返回值均为浮点数因此运算过程中会存在误差。例如当 x 2147395600x2147395600 时的计算结果与正确值 4634046340 相差 10^{-11}10
−11这样在对结果取整数部分时会得到 4633946339 这个错误的结果。
因此在得到结果的整数部分 ans 后我们应当找出 ans 与 ans1 中哪一个是真正的答案
class Solution {public int mySqrt(int x) {if (x 0) {return 0;}int ans (int) Math.exp(0.5 * Math.log(x));return (long) (ans 1) * (ans 1) x ? ans 1 : ans;}
}14.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 答案
我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数考虑最后一步可能跨了一级台阶也可能跨了两级台阶所以我们可以列出如下式子f(x) f(x - 1) f(x - 2)
f(x)f(x−1)f(x−2)它意味着爬到第 xx 级台阶的方案数是爬到第 x - 1x−1 级台阶的方案数和爬到第 x - 2x−2 级台阶的方案数的和。很好理解因为每次只能爬 11 级或 22 级所以 f(x)f(x) 只能从 f(x - 1)f(x−1) 和 f(x - 2)f(x−2) 转移过来而这里要统计方案总数我们就需要对这两项的贡献求和。以上是动态规划的转移方程下面我们来讨论边界条件。我们是从第 00 级开始爬的所以从第 00 级爬到第 00 级我们可以看作只有一种方案即 f(0) 1f(0)1从第 00 级到第 11 级也只有一种方案即爬一级f(1) 1f(1)1。这两个作为边界条件就可以继续向后推导出第 nn 级的正确结果。我们不妨写几项来验证一下根据转移方程得到 f(2) 2f(2)2f(3) 3f(3)3f(4) 5f(4)5……我们把这些情况都枚举出来发现计算的结果是正确的。
class Solution {public int climbStairs(int n) {int p 0, q 0, r 1;for (int i 1; i n; i) {p q; q r; r p q;}return r;}
}15.合并两个有序数组
给你两个有序整数数组 nums1 和 nums2请你将 nums2 合并到 nums1 中使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m n这样它就有足够的空间保存来自 nums2 的元素。
答案
标签从后向前数组遍历
因为 nums1 的空间都集中在后面所以从后向前处理排序的数据会更好节省空间一边遍历一边将值填充进去
设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部从尾部值开始比较遍历同时设置指针 len 指向 nums1 的最末尾每次遍历比较值大小之后则进行填充
当 len10 时遍历结束此时 nums2 中海油数据未拷贝完全将其直接拷贝到 nums1 的前面最后得到结果数组class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int len1 m - 1;int len2 n - 1;int len m n - 1;while(len1 0 len2 0) {nums1[len--] nums1[len1] nums2[len2] ? nums1[len1--] : nums2[len2--];}}
}16.买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 答案
我们需要找出给定数组中两个数字之间的最大差值即最大利润。此外第二个数字卖出价格必须大于第一个数字买入价格。形式上对于每组 ii 和 jj其中 j iji我们需要找出 \max(prices[j] - prices[i])max(prices[j]−prices[i])。
public class Solution {public int maxProfit(int prices[]) {int maxprofit 0;for (int i 0; i prices.length - 1; i) {for (int j i 1; j prices.length; j) {int profit prices[j] - prices[i];if (profit maxprofit) {maxprofit profit;}}}return maxprofit;}
}
方法二动态规划
思路题目只问最大利润没有问这几天具体哪一天买、哪一天卖因此可以考虑使用 动态规划 的方法来解决。买卖股票有约束根据题目意思有以下两个约束条件条件 1你不能在买入股票前卖出股票
条件 2最多只允许完成一笔交易。
因此 当天是否持股 是一个很重要的因素而当前是否持股和昨天是否持股有关系为此我们需要把 是否持股 设计到状态数组中。状态定义dp[i][j]下标为 i 这一天结束的时候手上持股状态为 j 时我们持有的现金数。换种说法dp[i][j] 表示天数 [0, i] 区间里下标 i 这一天状态为 j 的时候能够获得的最大利润。其中j 0表示当前不持股
j 1表示当前持股。
注意下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息因此最后输出 dp[len - 1][0]。说明使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少卖出股票手上的现金数增加 这个事实
「现金数」等价于题目中说的「利润」即先买入这只股票后买入这只股票的差价
因此在刚开始的时候我们的手上肯定是有一定现金数能够买入这只股票即刚开始的时候现金数肯定不为 00但是写代码的时候可以设置为 0。极端情况下股价数组为 [5, 4, 3, 2, 1]此时不发生交易是最好的这一点是补充说明限于我的表达希望不要给大家造成迷惑。
推导状态转移方程dp[i][0]规定了今天不持股有以下两种情况昨天不持股今天什么都不做
昨天持股今天卖出股票现金数增加
dp[i][1]规定了今天持股有以下两种情况昨天持股今天什么都不做现金数与昨天一样
昨天不持股今天买入股票注意只允许交易一次因此手上的现金数就是当天的股价的相反数。public class Solution {public int maxProfit(int[] prices) {int len prices.length;// 特殊判断if (len 2) {return 0;}int[][] dp new int[len][2];// dp[i][0] 下标为 i 这天结束的时候不持股手上拥有的现金数// dp[i][1] 下标为 i 这天结束的时候持股手上拥有的现金数// 初始化不持股显然为 0持股就需要减去第 1 天下标为 0的股价dp[0][0] 0;dp[0][1] -prices[0];// 从第 2 天开始遍历for (int i 1; i len; i) {dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] prices[i]);dp[i][1] Math.max(dp[i - 1][1], -prices[i]);}return dp[len - 1][0];}
}17.买卖股票的最佳时机2
给定一个数组 prices 其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 答案
class Solution {public int maxProfit(int[] prices) {int ans 0;int n prices.length;for (int i 1; i n; i) {ans Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}18.验证回文串
给定一个字符串验证它是否是回文串只考虑字母和数字字符可以忽略字母的大小写。
**说明**本题中我们将空字符串定义为有效的回文串。
Character.isLetterOrDigit(char ch) 确定指定的字符是否为字母或数字。
字符被认为是字母或数字如果字符不是Character.isLetter(char ch)也不Character.isDigit(char ch) 则返回true
toLowerCase() 方法用于将大写字符转换为小写。 答案:
最简单的方法是对字符串 ss 进行一次遍历并将其中的字母和数字字符进行保留放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev只要这两个字符串相同那么sgood 就是回文串。
class Solution {public boolean isPalindrome(String s) {StringBuffer sgood new StringBuffer();int length s.length();for (int i 0; i length; i) {char ch s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}
}19.只出现一次的数字
给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
答案
方法一位运算
如果不考虑时间复杂度和空间复杂度的限制这道题有很多种解法可能的解法有如下几种。使用集合存储数字。遍历数组中的每个数字如果集合中没有该数字则将该数字 加入集合 如果集合中已经有该数字则将该数字 从集合中删除 最后剩下的数字就是只出现一次的数字。使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数并更新哈希表最后遍历哈希表得到只出现一次的数字。使用集合存储数组中出现的所有数字并计算数组中的元素之和。由于集合保证元素无重复因此计算集合中的所有元素之和的两倍即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次其余元素都出现两次因此用集合中的元素之和的两倍减去数组中的元素之和剩下的数就是数组中只出现一次的数字。上述三种解法都需要额外使用 O(n)O(n) 的空间其中 nn 是数组长度。如何才能做到线性时间复杂度和常数空间复杂度呢class Solution {public int singleNumber(int[] nums) {int single 0;for (int num : nums) { single ^ num; //异或运算}return single;}
}20.多数元素
给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 答案
方法一哈希表
思路我们知道出现次数最多的元素大于n/2 次所以可以用哈希表来快速统计每个元素出现的次数。算法我们使用哈希映射HashMap来存储每个元素以及出现的次数。对于哈希映射中的每个键值对键表示一个元素值表示该元素出现的次数。我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后我们遍历哈希映射中的所有键值对返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法维护最大的值这样省去了最后对哈希映射的遍历。
class Solution {private MapInteger, Integer countNums(int[] nums) {MapInteger, Integer counts new HashMapInteger, Integer();for (int num : nums) {if (!counts.containsKey(num)) {counts.put(num, 1);} else {counts.put(num, counts.get(num) 1);}}return counts;}public int majorityElement(int[] nums) {MapInteger, Integer counts countNums(nums);Map.EntryInteger, Integer majorityEntry null;for (Map.EntryInteger, Integer entry : counts.entrySet()) {if (majorityEntry null || entry.getValue() majorityEntry.getValue()) {majorityEntry entry;}}return majorityEntry.getKey();}
}答案2
方法二排序
思路如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序那么下标为n/2的元素下标从 0 开始一定是众数。
算法对于这种算法我们先将 nums 数组排序然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中第一个例子是 nn 为奇数的情况第二个例子是 nn 为偶数的情况。对于每种情况数组下面的线表示如果众数是数组中的最小值时覆盖的下标数组下面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况这条线会在这两种极端情况的中间。对于这两种极端情况它们会在下标为n/2的地方有重叠。因此无论众数是多少返回 n/2下标对应的值都是正确的。class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}21.颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
答案
方法一逐位颠倒
思路将 nn 视作一个长为 3232 的二进制串从低位往高位枚举 nn 的每一位将其倒序添加到翻转结果 \textit{rev}rev 中。代码实现中每枚举一位就将 nn 右移一位这样当前 nn 的最低位就是我们要枚举的比特位。当 nn 为 00 时即可结束循环。需要注意的是在某些语言如 \texttt{Java}Java中没有无符号整数类型因此对 nn 的右移操作应使用逻辑右移。
public class Solution {public int reverseBits(int n) {int rev 0;for (int i 0; i 32 n ! 0; i) {rev | (n 1) (31 - i);n 1;}return rev;}
}
22.判断能否形成等差数列
给你一个数字数组 arr 。
如果一个数列中任意相邻两项的差总等于同一个常数那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列请返回 true 否则返回 false 。 答案
方法一模拟
class Solution {public boolean canMakeArithmeticProgression(int[] arr) {Arrays.sort(arr);for (int i 1; i arr.length - 1; i) {if (arr[i] * 2 ! arr[i - 1] arr[i 1]) {return false;}}return true;}
}23.位1的个数
编写一个函数输入是一个无符号整数以二进制串的形式返回其二进制表达式中数字位数为 ‘1’ 的个数也被称为汉明重量。
答案
方法一循环检查二进制位
思路及解法我们可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。具体代码中当检查第 i位时我们可以让 n 与 2^i进行与运算当且仅当 n 的第 i 位为 1 时运算结果不为 0。
public class Solution public int hammingWeight(int n) {int ret 0;for (int i 0; i 32; i) {if ((n (1 i)) ! 0) {ret;}}return ret;}
}public class Solution {public int hammingWeight(int n) {int ret 0;while (n ! 0) {n n - 1;ret;}return ret;}
}24.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。 如果 可以变为 1那么这个数就是快乐数。 如果 n 是快乐数就返回 true 不是则返回 false 。 答案
方法一用哈希集合检测循环
算法算法分为两部分我们需要设计和编写代码。给一个数字 nn它的下一个数字是什么
按照一系列的数字来判断我们是否进入了一个循环。
第 1 部分我们按照题目的要求做数位分离求平方和。第 2 部分可以使用哈希集合完成。每次生成链中的下一个数字时我们都会检查它是否已经在哈希集合中。如果它不在哈希集合中我们应该添加它。
如果它在哈希集合中这意味着我们处于一个循环中因此应该返回 false。
我们使用哈希集合而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集合中需要 O(1)O(1) 的时间而对于其他数据结构则需要 O(n)O(n) 的时间。选择正确的数据结构是解决这些问题的关键部分。class Solution {private int getNext(int n) {int totalSum 0;while (n 0) {int d n % 10;n n / 10;totalSum d * d;}return totalSum;}public boolean isHappy(int n) {SetInteger seen new HashSet();while (n ! 1 !seen.contains(n)) {seen.add(n);n getNext(n);}return n 1;}
}25.存在重复元素
给定一个整数数组判断是否存在重复元素。
如果存在一值在数组中出现至少两次函数返回 true 。如果数组中每个元素都不相同则返回 false 。 答案
方法一排序
在对数字从小到大排序之后数组的重复元素一定出现在相邻位置中。因此我们可以扫描已排序的数组每次判断相邻的两个元素是否相等如果相等则说明存在重复的元素。class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int n nums.length;for (int i 0; i n - 1; i) {if (nums[i] nums[i 1]) {return true;}}return false;}
}
方法二哈希表
对于数组中每个元素我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中则说明存在重复的元素。class Solution {public boolean containsDuplicate(int[] nums) {SetInteger set new HashSetInteger();for (int x : nums) {if (!set.add(x)) {return true;}}return false;}
}26.存在重复元素II
给定一个整数数组和一个整数 k判断数组中是否存在两个不同的索引 i 和 j使得 nums [i] nums [j]并且 i 和 j 的差的 绝对值 至多为 k。 答案
方法一 线性搜索 【超时】
思路
将每个元素与它之前的 k2 个元素中比较查看它们是否相等。算法这个算法维护了一个 k 大小的滑动窗口然后在这个窗口里面搜索是否存在跟当前元素相等的元素。public boolean containsNearbyDuplicate(int[] nums, int k) {for (int i 0; i nums.length; i) {for (int j Math.max(i - k, 0); j i; j) {if (nums[i] nums[j]) return true;}}return false;
}
方法三 散列表 【通过】
思路用散列表来维护这个k大小的滑动窗口。算法在之前的方法中我们知道了对数时间复杂度的 搜索 操作是不够的。在这个方法里面我们需要一个支持在常量时间内完成 搜索删除插入 操作的数据结构那就是散列表。这个算法的实现跟方法二几乎是一样的。遍历数组对于每个元素做以下操作
在散列表中搜索当前元素如果找到了就返回 true。
在散列表中插入当前元素。
如果当前散列表的大小超过了 k 删除散列表中最旧的元素。
返回 false。public boolean containsNearbyDuplicate(int[] nums, int k) {SetInteger set new HashSet();for (int i 0; i nums.length; i) {if (set.contains(nums[i])) return true;set.add(nums[i]);if (set.size() k) {set.remove(nums[i - k]);}}return false;
}27.汇总区间
给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说nums 的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个范围但不属于 nums 的数字 x 。
答案
方法一一次遍历
我们从数组的位置 00 出发向右遍历。每次遇到相邻元素之间的差值大于 11 时我们就找到了一个区间。遍历完数组之后就能得到一系列的区间的列表。在遍历过程中维护下标 \textit{low}low 和 \textit{high}high 分别记录区间的起点和终点对于任何区间都有 \textit{low} \le \textit{high}low≤high。当得到一个区间时根据 \textit{low}low 和 \textit{high}high 的值生成区间的字符串表示。当 \textit{low}\textit{high}lowhigh 时区间的字符串表示为 \textit{low} \rightarrow \textit{high}‘‘low→high当 \textit{low}\textit{high}lowhigh 时区间的字符串表示为 \textit{low}‘‘low。
class Solution {public ListString summaryRanges(int[] nums) {ListString ret new ArrayListString();int i 0;int n nums.length;while (i n) {int low i;i;while (i n nums[i] nums[i - 1] 1) {i;}int high i - 1;StringBuffer temp new StringBuffer(Integer.toString(nums[low]));if (low high) {temp.append(-);temp.append(Integer.toString(nums[high]));}ret.add(temp.toString());}return ret;}
}28.有效的字母异位词
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。 答案
方法一排序
tt 是 ss 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 ss 和 tt 分别排序看排序后的字符串是否相等即可判断。此外如果 ss 和 tt 的长度不同tt 必然不是 ss 的异位词。
class Solution {public boolean isAnagram(String s, String t) {if (s.length() ! t.length()) {return false;}char[] str1 s.toCharArray(); //将字符串转化为字符数组char[] str2 t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2); //比较两个数组是否相同}
}
方法二哈希表
从另一个角度考虑t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母因此我们可以维护一个长度为 26 的频次数组table先遍历记录字符串 s 中字符出现的频次然后遍历字符串 t减去 table 中对应的频次如果出现 table[i]0则说明 t 包含一个不在 s 中的额外字符返回 false 即可。
class Solution {public boolean isAnagram(String s, String t) {if (s.length() ! t.length()) {return false;}int[] table new int[26];for (int i 0; i s.length(); i) {table[s.charAt(i) - a];}for (int i 0; i t.length(); i) {table[t.charAt(i) - a]--;if (table[t.charAt(i) - a] 0) {return false;}}return true;}
}29.各位相加
给定一个非负整数 num反复将各个位上的数字相加直到结果为一位数。
答案
除个位外每一位上的值都是通过 (91) 进位的过程得到的想一下 拨算盘进位
把整数 n 看成 n 样物品原本是以 10 个 1 份打包的现在从这些 10 个 1 份打包好的里面拿出 1 个让它们以 9 个为 1 份打包。
这样就出现了两部分的东西
原本 10 个现在 9 个 1 份的打包好的物品这些我们不用管
零散的物品它们还可以分成
从原来打包的里面拿出来的物品它们的总和 》 原来打包好的份数 》 10进制进位的次数 》 10 进制下除个位外其他位上的值的总和
以 10 个 1 份打包时打不进去的零散物品 》 10 进制个位上的值
如上零散物品的总数就是第一次处理 num 后得到的累加值
如果这个累加值 9那么如题就还需要将各个位上的值再相加直到结果为个位数为止。也就意味着还需要来一遍如上的过程。
那么按照如上的思路似乎可以通过 n % 9 得到最后的值
但是有1个关键的问题如果 num 是 9 的倍数那么就不适用上述逻辑。原本我是想得到 n 被打包成 10 个 1 份的份数打不进 10 个 1 份的散落个数的和。通过与 9 取模去获得那个不能整除的 1作为计算份数的方式但是如果可以被 9 整除我就无法得到那个 1也得不到个位上的数。
所以需要做一下特殊处理(num - 1) % 9 1
可以这么做的原因原本可以被完美分成 9 个为一份的 n 样物品我故意去掉一个那么就又可以回到上述逻辑中去得到我要的n 被打包成 10 个一份的份数打不进 10 个一份的散落个数的和。而这个减去的 1 就相当于从在 10 个 1 份打包的时候散落的个数中借走的本来就不影响原来 10 个 1 份打包的份数先拿走再放回来都只影响散落的个数所以没有关系。class Solution {public int addDigits(int num) {return (num - 1) % 9 1;}
}30.丑数
给你一个整数 n 请你判断 n 是否为 丑数 。如果是返回 true 否则返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。 答案
方法一数学
根据丑数的定义00 和负整数一定不是丑数。当 n0n0 时若 nn 是丑数则 nn 可以写成 n 2^a \times 3^b \times 5^cn2
a×3
b×5
c的形式其中 a,b,ca,b,c 都是非负整数。特别地当 a,b,ca,b,c 都是 00 时n1n1。为判断 nn 是否满足上述形式可以对 nn 反复除以2,3,5直到 nn 不再包含质因数 2,3,5。若剩下的数等于 11则说明 nn 不包含其他质因数是丑数否则说明 nn 包含其他质因数不是丑数。
class Solution {public boolean isUgly(int n) {if (n 0) {return false;}int[] factors {2, 3, 5};for (int factor : factors) {while (n % factor 0) {n / factor;}}return n 1;}
}31.丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
答案
方法一排序
分析如果数组是有序的那么就很容易知道缺失的数字是哪个了。算法首先我们对数组进行排序随后我们可以在常数时间内判断两种特殊情况0 没有出现在数组的首位以及 nn 没有出现在数组的末位。如果这两种特殊情况都不满足那么缺失的数字一定在 0 和 nn 之间不包括两者。此时我们可以在线性时间内扫描这个数组如果某一个数比它前面的那个数大了超过 1那么这两个数之间的那个数即为缺失的数字。
class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);// 判断 n 是否出现在末位if (nums[nums.length-1] ! nums.length) {return nums.length;}// 判断 0 是否出现在首位else if (nums[0] ! 0) {return 0;}// 此时缺失的数字一定在 (0, n) 中for (int i 1; i nums.length; i) {int expectedNum nums[i-1] 1;if (nums[i] ! expectedNum) {return expectedNum;}}// 未缺失任何数字保证函数有返回值return -1;}
}
