赞
踩
此系列文章是关于LeetCode 精选 TOP 面试题 的题解文章,共136个题(不包括会员题),每篇 10 题。共十四篇文章。
LeetCode 精选 TOP 面试题链接
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解题思路:遍历数组,并查找,该值之前的数组有没有与之对应的值之和为 目标值
class Solution {
public int[] twoSum(int[] nums, int target){
HashMap<Integer,Integer> map = new HashMap<>(nums.length-1);
map.put(nums[0],0);
for (int i = 1;i<nums.length;i++) {
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]),i};
}
map.put(nums[i],i);
}
return null;
}
}
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
解题思路:使用一个变量记录进位标志,在做加法的时候,加上这个进位标志。
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode t = new ListNode(0); ListNode result = t; int c = 0; int sum; while(l1!=null || l2!=null){ result.next = new ListNode(0); result = result.next; sum = (l1 == null?0:l1.val) + (l2==null?0:l2.val) + c; c = sum / 10; result.val = sum % 10; l1 = l1!=null?l1.next:null; l2 = l2!=null?l2.next:null; } if(c == 1){ result.next = new ListNode(1); } return t.next; } }
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
解题思路:遍历字符串,记录字符出现的最后位置,如果前面已经出现,则回退到上一次出现的位置+1的位置,同时记录子串的大小。等待字符串遍历完成之后,就能得到最长子串的大小
class Solution { public int lengthOfLongestSubstring(String s) { int[] last = new int[128]; // 记录字符最后出现的位置。 for(int i = 0;i<128;i++){ last[i] = -1; } int result = 0; // 记录最大子串的长度 int t = 0; // 记录子串的起始位置 int index; // 下标 for (int i = 0; i < s.length(); i++){ index = s.charAt(i); t = (last[index] + 1) > t? (last[index] + 1):t; result = result>(i - t + 1)?result:(i - t + 1); last[index] = i; } return result; } }
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
解题思路:
使用二分查找确定两个有序数组的「分割线」,中位数就由分割线左右两侧的元素决定;
分割线满足这样的性质:左右两边元素个数相等(这里忽略两个数组长度之和奇偶性的差异);
分割线左边所有元素 小于等于 分割线右边所有元素;
由于分割线两边元素个数相等,挪动分割线就会有「此消彼长」的现象,所以使用二分去定位。
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 数组长度最短,在二分的时候,最快找到分割线。 if (nums1.length > nums2.length) { int[] t = nums1; nums1 = nums2; nums2 = t; } int m = nums1.length; int n = nums2.length; // 整个数组分割线边的元素个数。 // 如果 m+n是偶数,+1 为奇数,对值没有影响 // 如果 m+n是奇数,+1 为偶数,则值 + 1; // 保证分割线左边的个数比右边多一个,保证中位数在左边。 int totalLeft = (m + n + 1)/2; int left = 0; int right = m; int i,j; // 对 nums1 进行二分查找 while (left < right) { // i为数组nums1的分割线位置 // j为数组nums2的分割线位置 i = left + (right - left + 1)/2; j = totalLeft - i; // i-1为 分割线左边的第一个元素,j-1为 分割线左边的第一个元素 // 使得所有分割线左边的元素小于右边,即 nums1[i-1]<=nums2[j],nums2[j-1]>= nums[i] if(nums1[i-1]>nums2[j]){ // 新的区间查找 [0,i-1] right = i - 1; }else{ // [i,right] left = i; } } // 上面循环出来,就找到正确的分割线位置 i = left; j = totalLeft - i; // 分别考虑 分割线两边的四个元素,求出中位数 int nums1_MAX = i==0?Integer.MIN_VALUE:nums1[i-1]; int nums1_MIN = i == m?Integer.MAX_VALUE:nums1[i]; int nums2_MAX = j==0?Integer.MIN_VALUE:nums2[j-1]; int nums2_MIN = j == n?Integer.MAX_VALUE:nums2[j]; // 根据数组的长度奇偶数 if((m+n)%2==0){ // 数组长度为偶数,为左边最大值和右边最小值的和除以2 return (Math.max(nums1_MAX,nums2_MAX)+Math.min(nums1_MIN,nums2_MIN))*1.0/2; }else{ // 数组长度为奇数,中位数为左边元素的最大值。 return Math.max(nums1_MAX,nums2_MAX); } }
给你一个字符串 s,找到 s 中最长的回文子串。
解题思路:对于每一个字符,考虑两种情况,回文串是奇数个,回文串是偶数个,做中心扩展,判断是否为回文串,并记录长度。
中心扩散法:
public String longestPalindrome(String s) { int start = 0; int length = 1; int tLength; int l,r; for(int i = 0; i<s.length()-1;i++){ // 考虑回文串可能是偶数 l = i; r = i + 1; while(l >= 0 && r < s.length() && s.charAt(r) == s.charAt(l)){ r++; l--; } tLength = r - l - 1; //记录长度 // 考虑回文串可能是奇数 l=i-1; r=i+1; while((l >= 0) && (r < s.length())&&s.charAt(l) == s.charAt(r)){ r++; l--; } // 判断是否更新回文串 if(tLength>length || r-l-1 >length){ length = tLength>r-l-1?tLength:r-l-1; start = i - (length - 1) / 2; } } return s.substring(start,start + length); }
动态规划法:
对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后,它仍然是个回文串。
根据这样的思路,我们就可以用动态规划的方法解决本题。用P(i,j) 表示字符串 s的第 i 到 j 个字母组成的串是否为回文串;
P(i,j) 是回文串,那么 P(i+1,j-1)也是回文串。
P(i,j) 不是回文串,分为两种情况,P(i+1,j-1)不是回文串,i > j,不合法。
动态规划的状态转移方程:
P(i,j)=P(i+1,j−1)∧(S[i] == s[j])
动态规划的边界条件:
P(i,i) = true , P(i,i+1) = (S[i] == S[ i+1])
图解
单个字符的串一定是回文,标记为true,然后从左向下,再向右,依次填表。
public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 boolean[][] dp = new boolean[len][len]; // 初始化:所有长度为 1 的子串都是回文串 for (int i = 0; i < len; i++) { dp[i][i] = true; } char[] charArray = s.toCharArray(); // 递推开始 // 先枚举子串长度 for (int j = 1; j < len; j++) { // 枚举左边界,左边界的上限设置可以宽松一些 for (int i = 0; i < j; i++) { if (charArray[i] != charArray[j]) { dp[i][j] = false; } else { if (j - i < 3) { // 回文串长度是2,3的情况,直接可以判断是回文 dp[i][j] = true; } else { // 参考已有的结果 dp[i][j] = dp[i + 1][j - 1]; } } //只要dp[i][j] == true,并且长度大于已有的最大回文串,记录回文长度和起始位置 if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); }
给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。
public int reverse(int x) {
int reversex = 0;
while(x!=0) {
if(Integer.MIN_VALUE/10 > reversex || Integer.MAX_VALUE/10 < reversex){
return 0;
}
reversex = reversex * 10 + (x % 10);
x = x / 10;
}
return reversex;
}
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下:
解题思路:可以出现的前导符号空格,符号位(只能出现一次),然后就必须是数字(0-9),直到读取到其他字符,读取结束,同时判断是否溢出。
public int myAtoi(String s) { int x = 0; int i = 0; int f = 0; char[] cs = s.toCharArray(); int length = cs.length; while(i < length && cs[i] == ' '){ i++; } if(i < length && cs[i] == '-'){ f = -1; i++; } if(i < length && cs[i] == '+'){ if(f != 0) return 0; f = 1; i++; } for(;i<length;i++){ if(cs[i]>='0' && cs[i]<='9'){ if(x > Integer.MAX_VALUE / 10 || x == Integer.MAX_VALUE / 10 && (cs[i] - '0') > Integer.MAX_VALUE % 10){ if(f == 1 || f == 0){ return Integer.MAX_VALUE; }else{ return Integer.MIN_VALUE; } } x = x*10 + cs[i]-'0'; }else{ break; } } return x*(f!=0?f:1); }
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
. 匹配任意单个字符
*匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖整个字符串 s的,而不是部分字符串。
解题思路:
题目中的匹配是一个「逐步匹配」的过程:我们每次从字符串 p 中取出一个字符或者「字符 + 星号」的组合,并在 s 中进行匹配。对于 p 中一个字符而言,它只能在 s 中匹配一个字符,匹配的方法具有唯一性;而对于 p 中 [ 字符 + 星号 ] 的组合而言,它可以在 s 中匹配任意自然数个字符,并不具有唯一性。
f [i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。
在进行状态转移时,我们考虑 p 的第 j 个字符的匹配情况:
如果 p 的第 j 个字符是一个小写字母,那么我们必须在 s 中匹配一个相同的小写字母。
字母 + 星号的组合在匹配的过程中,本质上只会有两种情况:
在任意情况下,只要 p[j] 是 .,那么 p[j]一定成功匹配 s 中的任意一个小写字母。
动态规划的边界条件为 f[0][0] = true,即两个空字符串是可以匹配的。最终的答案即为 f[m][n],其中 m 和 n 分别是字符串 s 和 p 的长度。
根据以上三种情况的状态转移方程
代码:
public boolean isMatch(String s, String p) { int m = s.length(); int n = p.length(); boolean[][] f = new boolean[m + 1][n + 1]; f[0][0] = true; for(int j = 1;j<=n;j++){ if (j > 1) { if (p.charAt(j-1) == '*') { f[0][j] = f[0][j-2]; } } else { if (p.charAt(j-1) == '*') { f[0][j] = true; } } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if(p.charAt(j-1) == '.'||p.charAt(j-1) == s.charAt(i-1)){ f[i][j] = f[i-1][j-1]; }else if(p.charAt(j-1) == '*'){ if (j > 1) { if (f[i][j-2]) { f[i][j] = true; }else if(p.charAt(j-2) == '.' || p.charAt(j-2) == s.charAt(i-1)){ f[i][j] = f[i-1][j]; } } } } } return f[m][n]; }
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
就是求两点组成的面积最大。
解题思路:一开始想到的是暴力法,提交超时,就换成双指针法。将指针分别指向首尾两个元素,此时容器的底为最大,如果想让面积最大,只需要移动指向高较短的元素的指针。直到扫描完整个数组元素。
public int maxArea(int[] height) {
int i = 0;
int j = height.length-1;
int area = 0;
while(i < j) {
area = Math.max(Math.min(height[i],height[j])*(j-i),area);
if(height[i]>height[j]){
j--;
}else{
i++;
}
}
return area;
}
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例:
解题思路:建立映射表,如果罗马数字中小的数字在大的右边,则减去小的数字。
public int romanToInt(String s) { Map<Character,Integer> map = new HashMap<>(); map.put('I',1); map.put('V',5); map.put('X',10); map.put('L',50); map.put('C',100); map.put('D',500); map.put('M',1000); int result = 0; int x; for(int i= 0;i < s.length();i++){ x = map.get(s.charAt(i)); if(i < s.length()-1 && map.get(s.charAt(i+1)) > x){ result -= x; }else{ result += x; } } return result; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。