找了一段时间的实习,总结一下LeetCode上面试出现频率比较高的题,只总结一部分,后续还会继续更新。
一、Two Sum
题意是给出一个数组,输出和为k的两个数。数组为无序的。
这道题的解题思路是先把数组排序,再用两个指针,分别指向头和尾,并算出头和尾的和s,再把s与k比较,如果s小于k,头指针往后移,如果s大小k,尾指针往前移。直到找到为止。如果头尾指针相遇还没找到,则证明不存在。
代码如下:
public class Main {
public static void main(String[] args){
int[] a = {1,3,2,1,4,5};
printK(a,5);
}
public static void printK(int[] array,int k){
if(array == null||array.length<=0){
return ;
}
int length = array.length;
Arrays.sort(array);
int start = 0;
int end = length - 1;
while(start < end){
while(array[start] == array[start+1]){
start++;
}
while(array[end] == array[end-1]){
end--;
}
if(array[start] + array[end] == k){
System.out.println(start+" "+end);
start ++;
}
if(array[start]+array[end] < k){
start++;
}
if(array[start]+array[end] > k){
end--;
}
}
//System.out.println("can't find");
}
}
二,3Sum
题意:从给定的数组中找三个数,让它们的和为0。输出所有可能。
如[1,3,-1,0,-3],那么输出[1,-1,0],[3,0,-3]。
思路:这个其实是以第一个题目为基础,首先进行排序。然后从数组第一位开始遍历,如第一位为1,在剩余后面的数组[3,-1,0,-3]中找出和为-1的两个数。用的就是第一题的思路。
代码:
public class Main {
public static void main(String[] args){
int[] array = {-1, 0,1,2,-1,-4};
print3Num(array, 0);
}
public static void print3Num(int[] array,int k){
Arrays.sort(array);
int length = array.length;
if(array == null||array.length<=0){
return ;
}
for(int i = 0;i < length;i++){
if(i
k){ end--; } } } }
三、Climbing Stairs
题意:有n级楼梯,你一次可以爬一级或两级,问爬上n级楼梯有多少种爬法。这是我一个同学面腾讯时被问到的问题。典型的斐波那契数列。
思路:因为一次你能爬一级或两级,所以除去第一次,n级的爬法f(n)可以等于f(n-1)+f(n-2)。求的就是斐波那契数列。
代码:
public class Main {
public static void main(String[] args){
System.out.print(climbStair(5));
}
//递归
public static int climbStairs(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return climbStairs(n-1)+climbStairs(n-2);
}
//非递归
public static int climbStair(int n) {
int num1 = 1;
int num2 = 2;
int sum = 0;
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
for(int i = 2;i < n;i++){
sum = num1+num2;
num1 = num2;
num2 = sum;
}
return sum;
}
}
分别实现了递归和非递归两种方式。
四,Merge Two Sorted Lists
题意:合并两个排序的链表
思路:先选出头小的节点作为新链表的起点,然后开始比较两个链表,那个值小就把链表指向它,被指向的链表往下移一位,新链表也要指向当前最后一个节点。当有一个链表遍历完了,就把另一个链表剩余部分全部赋到新链表的尾部,直接看代码更清晰。
public static ListNode merge(ListNode head1,ListNode head2){
if(head1 == null&& head2 == null){
return null;
}
if(head1 == null){
return head2;
}
if(head2 == null){
return head1 ;
}
ListNode head = null;
if(head1.val
五、Merge Sorted Array
题意:给两个数组n1[1,2,3],n2[3,4,5],把n2合并到n1中去,n1长度>=n1.length+m.length。
思路:这道题是不允许多用空间的。最后我想出的方法是从尾部开始比较,大的放到n1数组的最后一位。并把大数所在的数组尾部指针往前移,直到比较结束后,所有数就自然的在n1中排序了。
代码如下:
public class Main { public static void main(String[] args){ int[] a = {0}; int[] b = {1}; merge(a,0,b,1); for(int i = 0;i < a.length;i++) System.out.print(a[i]+" "); } public static void merge(int[] nums1, int m, int[] nums2, int n) { if(nums1==null||nums2==null||m<0||n<0){ return; } int index = m+n-1; int index1 = m-1; int index2 = n-1; while(index1>=0&&index2>=0){ if(nums1[index1]
=0){ nums1[index--] = nums1[index1--]; } while(index2>=0){ nums1[index--] = nums2[index2--]; } } }
六、Valid Palindrome
题意:验证一个字符串是否为回文,只看字母(忽略其它字符),不分大小写。如“A man, a plan, a canal: Panama”就是一个回文,从头读和从尾往前读读出来是一样的。
思路:这道题思路其实很直接,就是两个指针,一个指向头部一个指向尾部,头部依次往后走,尾部依次往前走,一个个比,如果有不同就不是回文,否则如果两指针相遇了还没有不同的,就是回文。
代码:
public class Main { public static void main(String[] args){ System.out.println(isPalindrome("......a.....")); System.out.println(isPalindrome("09")); } public static boolean isPalindrome(String s) { s = s.toLowerCase(); if(s.length()<=1){ return true; } int length = s.length(); int start = 0; int end = length-1; while(start < end){ while(start
='a'&&s<'z'||s>='0'&&s<='9'){ // s=(char)(s-'a'+'A'); return true; } else{ return false; } } }
七 Valid Parentheses
题意:验证括号是否能正常闭合,如“()[]{}”是可以正常闭合的,但“(]”就是不正常的。
思路:用一个栈,如果是左括号入栈,如果是右括号,则出栈与右括号比,如果最后栈空了,也没的右括号了,则证明正确。
代码写得有点傻,可以继续优化:
public class Main { public static void main(String[] args){ System.out.println(valid("[")); } public static boolean valid(String str){ if(str.length() <= 0){ return false; } Stack
stack = new Stack
(); int length = str.length(); for(int i = 0;i < length;i++){ if(str.charAt(i) == '{'||str.charAt(i) == '['||str.charAt(i)=='('){ stack.push(str.charAt(i)); } if(str.charAt(i)==')'){ if(!stack.isEmpty()){ char c = stack.pop(); if(c != '('){ return false; } }else{ return false; } } if(str.charAt(i)=='}'){ if(!stack.isEmpty()){ char c = stack.pop(); if(c != '{'){ return false; } }else{ return false; } } if(str.charAt(i)==']'){ if(!stack.isEmpty()){ char c = stack.pop(); if(c != '['){ return false; } }else{ return false; } } } if(stack.isEmpty()) return true; else{ return false; } } }
八 Pow(x, n)
题意:就是实现一个Pow(x,n)乘方函数。
思路:首先要注意负数和倒数的问题。其次就是要合理的利用己经算出来的值来算下一个,如计算2^4,我们计算了2*2=4之后,就可以用4*4来计算2^4,减少计算的次数。
代码说话:
pu