LeetCode最常见的面试笔试题总结

78 阅读 0 评论 52 点赞

我是靠谱客的博主独特荔枝，最近开发中收集的这篇文章主要介绍LeetCode最常见的面试笔试题总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

找了一段时间的实习，总结一下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<length-1&&array[i] == array[i+1]){
continue;
}
int num = k-array[i];
printK(array,i,length-1,array[i],num);
}
}
public static void printK(int[] array,int start,int end, int num,int k){
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(num+" "+array[start]+" "+array[end]);
start ++;
}
if(array[start]+array[end] < k){
start++;
}
if(array[start]+array[end] > 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 <head2.val){
head = head1;
head1 = head1.next;
}else{
head = head2;
head2 = head2.next;
}
//ListNode head = head1.val < head2.val?head1:head2;
ListNode result = head;
//head1 = head1.next;
while(head1!=null && head2 !=null){
if(head1.val < head2.val){
head.next = head1;
head1 = head1.next;
head = head.next;
}else{
head.next = head2;
head2 = head2.next;
head = head.next;
}
}
if(head1 != null){
head.next = head1;
}
if(head2 != null){
head.next = head2;
}
return result;
}

五、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]<nums2[index2]){
nums1[index--] = nums2[index2--];
}else{
nums1[index--] = nums1[index1--];
}
}
while(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<end&&!isAlpha(s.charAt(start))){
start++;
}
while(start<end&&!isAlpha(s.charAt(end))){
end--;
}
if(s.charAt(start)!=s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
public static boolean isAlpha(char s){
if(s>='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<Character> stack = new Stack<Character>();
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，减少计算的次数。
代码说话：

public class Main {
public static void main(String[] args){
System.out.println(pow(2,2));
}
public static double pow(double d,int n){
boolean flag = false;
boolean zhisuFlag = false;
int e = n;
if(n<0){
e = -n;
zhisuFlag = true;
if(d == 0.0){
return 0;
}
}
if(n%2==1&&d<0){
flag = true;//负数
}
double result = power(d, e);
if(zhisuFlag){
result = 1/result;
}
if(flag){
result = -result;
}
return result;
}
public static double power(double d,int n){
if(n == 1){
return d;
}
if(n == 0){
return 1;
}
double
result = d;
int k = 1;
int pn = n;
while (n/2>0) {
n = n/2;
result = result*result;
k = k*2;
}
result =result * power(pn, n-k);
return result;
}
}

九 Generate Parentheses

题意：给一个整数n，输出n对小括号所能组成的所有正常闭合的组合。如给出整数3，则输出 “((()))”, “(()())”, “(())()”, “()(())”, “()()()”。
思路：用递归实现所有情况，先定义left存左括号的个数，right存右括号数，首先输出一个“（”，如果剩余右括号多于左括号，可以输出右括号，否则只能输出左括号。
代码如下：

public class Main {
public static void main(String[] args){
generateParenthesis(1);
}
public static List<String> generateParenthesis(int n) {
ArrayList<String> aList = new ArrayList<String>();
if(n <= 0){
return null;
}
getList(n,n,"",aList);
return aList;
}
public static void getList(int left,int right,String curStr,List<String> aList){
if(left > right){
return;
}
if(left == 0&&right == 0){
aList.add(curStr);
}
if(left > 0){
getList(left-1, right, curStr+"(", aList);
}
if(right > 0){
getList(left, right-1, curStr+")", aList);
}
}
}

十、Validate Binary Search Tree

题意：判断一棵树是不是BST树。即判断一棵树的左节点是否全比根节点小，所有右节点是否全比根节点大。
思路一：最直接的方法是用中序遍历，发现不是有序的就不是BST，如果是有序那就是BST。
代码如下：

public static boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
boolean a = isValidBST(root.left);
pre = cur;
cur = root;
if(pre!=null&&pre.val>=cur.val){//要考虑到与子节点相同的情况
return false;
}
boolean b = isValidBST(root.right);
return a&&b;
}

思路二：递归遍历子节点，在遍历过程中分别给左子树和右子树设置左屏障和右屏障，什么意思呢？就是保证左子树的右屏障为根节点，也就是最大值小于等于根节点。右子树左屏障为根节点的值，即最小值大小等于根节点的值。
代码如下：

 public static boolean isValidBST(TreeNode root) {
int left = Integer.MIN_VALUE;
int right = Integer.MAX_VALUE;
if(root == null){
return true;
}
if(root.left == null&&root.right==null){
return true;
}
return validBinary(root, left, right);
}
public static boolean validBinary(TreeNode head,int left,int right){
if(head == null){
return true;
}
if(head.val<=left)
{
return false;
}
if(head.val>=right)
{
return false;
}
return validBinary(head.left,left,head.val)&&validBinary(head.right,head.val,right);
}