欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-28 20:02:16
找了一段时间的实习,总结一下leetcode上面试出现频率比较高的题,只总结一部分,后续还会继续更新。 一、two sum 题意是给出一个数组,输出和为k的两个数。数组为无序的。 这道题的解题思路是...

找了一段时间的实习,总结一下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,减少计算的次数。
代码说话:

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 generateparenthesis(int n) {
        arraylist alist = new arraylist();
        if(n <= 0){
            return null;
        }
         getlist(n,n,"",alist);
         return alist;

    }
    public static void getlist(int left,int right,string curstr,list 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);
    }

就到这吧,整理的好累,其实leetcode刷了有一些了,但常见的笔试面试题也就那么几类,个人觉得应该不会出太难。