资讯专栏INFORMATION COLUMN

《程序员面试金典》部分题目

DC_er / 638人阅读

摘要:程序员面试金典题目字符串确定两个字符串同构的字符重新排列后,能否变成详细第一步先判断两个字符串的长度是否相等字符串的长度为有括号数组清除二维数组行列将数组中所有为的元素所在的行列都置为读数据和写数据必须分开。

《程序员面试金典》 题目 1.3 字符串 确定两个字符串同构

StringA的字符重新排列后,能否变成StringB 详细

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        if(stringA.length()!=stringB.length())
            return false;
        int[] recoder = new int[256];
        for(int i=0;i

tips:

第一步先判断两个字符串的长度是否相等

字符串的长度为.length()有括号

1.7 数组 清除二维数组行列

将数组中所有为0的元素所在的行列都置为0

import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[n];
        for(int i=0;i

tips

读数据和写数据必须分开。

1.8字符串 翻转子串

检查string2是否为sting1旋转而成

public boolean checkReverseEqual(String s1, String s2) {
        // write code here
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        return (s1+s1).contains(s2);
    }

tips

旋转问题:先将string1 收尾拼接,再检查新的字符串是否含有s2.

2.2链表 链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点

public ListNode FindKthToTail(ListNode head,int k) {
        //需不需要new???
        //ListNode headp = new ListNode(-1);
        if(head == null||k<1) return null;
        ListNode tailp = head;
        ListNode headp = head;
        for(int i=1;i

tips

new一个obj1对象,然后obj1 = obj2 ,错错错

核心思想:两个指针,相差k-1,tail指到尾,则前指针正好找到想要的位置。

另外一种思路是采用递归,head==null时,将count置零,之后count++。

2.3链表 访问单个节点的删除

删除单向链表中间的某个结点,并且只能访问该结点

public boolean removeNode(ListNode pNode) {
        // write code here
        if(pNode == null || pNode.next == null)
            return false;
        pNode.val = pNode.next.val;
        pNode.next = pNode.next.next;
        return true;
    }

tips

只能访问该节点,则不能删除该节点,因为删除之后则链表与前面断开链接,所有只能修改该节点的值为下一节点的值,再指向下下节点。

2.5链表 链式A+B

链表头为个位,A{1,2,3},B{3,2,1},则返回{4,4,4}

public ListNode plusAB(ListNode a, ListNode b) {
        // write code here
        int flag = 0;
        ListNode result = new ListNode(-1);
        ListNode phead = result;
        while(a!=null || b!=null || flag!=0){
            int sum = flag;
            if(a!=null){
                sum+=a.val;
                a = a.next;
            }
            if(b!=null){
                sum+=b.val;
                b = b.next;
            }
            int val = sum%10;
            flag = sum/10;
            result.next = new ListNode(val);
            result = result.next;
        }
        return phead.next;
    }

tips

之前有一个想法就是先相加公共部分,然后处理多出来的部分,这样处理起来非常麻烦。

如果链表头为高位,则采用栈方法处理。先对两个链表分别压栈,最后弾栈,直至两个都为空并且进位等于0。

2.7链表 回文链表

检查链表是否为回文,{1,2,3,2,1},返回true

 public boolean isPalindrome(ListNode pHead) {
        // 快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        Stack stack = new Stack<>();
        while(fast != null && fast.next != null){
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;     
        }
        if(fast != null)
              slow = slow.next;
        while(slow != null){
            if(slow.val != stack.pop())
                return false;
            slow = slow.next;
        }
        return true;      
    }
    
    public boolean isPalindrome(ListNode pHead) {
        //双栈
        if(pHead == null || pHead.next == null)
            return true;
        Stack stack1 = new Stack();        
        Stack stack2 = new Stack();

        while(pHead!=null){
            stack1.push(pHead.val);
            pHead = pHead.next;    
        }
        while(stack1.size()>stack2.size()){
            stack2.push(stack1.pop());
        }
        if(stack2.size()>stack1.size()){
            stack2.pop();
        }
        while(!stack1.empty() && !stack2.empty()){
            if(stack1.pop() != stack2.pop())
                return false;
        }
        return true;
            
    }

tips

方案1:用快慢指针,当快指针指向链表尾部时,慢指针正好指向中部,并且将慢指针压栈,这里要注意奇偶数的区别。

方案2:先将所有链表数据压到栈1,然后弹出一半到栈2,两者再进行比较。不过该方法显然没有方法一效率高。

3.5栈和队列 用两个栈实现队列
public class Solution {
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new RuntimeException("the queue is empty!");
        }
        if(stack2.isEmpty()){
          while(!stack1.isEmpty()){
              stack2.push(stack1.pop());
          }
        }
        return stack2.pop();
         
    }
}

tips

throw new RuntimeException("the queue is empty!");下次可以用

3.6栈和队列 双栈排序

要求只有一个缓存栈,并且排好序的栈最大元素在栈顶。

 public ArrayList twoStacksSort(int[] numbers) {
        // write code here
        ArrayList arrayList = new ArrayList();
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
         
        for(int i=0;itemp){
                stack1.push(stack2.pop());
            }
            stack2.push(temp);
        }
         
        while(!stack2.isEmpty()){
            arrayList.add(stack2.pop());
        }
        return arrayList;
    }

tips

while(!stack2.isEmpty() && stack2.peek()>temp){
        stack1.push(stack2.pop());
     }
stack2.push(temp);

代码的简洁性!思维不要太僵硬,可以多层条件一起考虑,不必非要一层一层考虑分析。

不要先考虑stack2是否为空,再嵌套考虑栈顶是否大于temp。。。

4.1 树 检查二叉树是否平衡

树的平衡指左右高度相差不能大于1

public boolean isBalance(TreeNode root) {
        // 遍历整个树的所有节点
        if(root == null)return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        int cha = Math.abs(left-right);
        if(cha>1)return false;
        else return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right)+1;
    }

另一种解法:一边检查高度一边检查是否平衡

public boolean isBalance(TreeNode root) {
        // write code here
        if(root == null)return true;
        if(getHeight(root) == -1)return false;
        return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        if(left == -1) return -1;
        int right = getHeight(root.right);
        if(right == -1) return -1;
        if(Math.abs(left-right)>1) return -1;
        else return Math.max(left,right)+1;
    }

tips

这样的改进的好处在于不用遍历所有的树节点

4.3最小二叉查找树

给定一个元素各不相同的升序数组,生成一个最小二叉查找树

public TreeNode creatBST(int[] arr,int start,int end){
    if(start>end)return null;
    int mid = (start+end)>>1;
    TreeNode n = new TreeNode(arr[mid]);
    n.left = creatBST(arr,start,mid-1);
    n.right = creatBST(arr,mid+1;end);
    return n;
}

tips

二叉查找树:数组的中间值为根,根的左子树元素值全部小于根节点值,根的右子树大于根节点。

4.4 树 输出单层节点

给定一颗二叉树,创建含有某一深度上所有结点的链表。

 private ListNode result= new ListNode(-1);
    public ListNode getTreeLevel(TreeNode root, int dep) {
        // write code here
        ListNode list = result;
        getTree(root,dep,1);
        return list.next;
        
    }
    public void getTree(TreeNode root,int dep,int i){
        if(root == null) return;
        if(i == dep){
            result.next = new ListNode(root.val);
            result = result.next;
        }else{
            getTree(root.left,dep,i+1);
            getTree(root.right,dep,i+1);
        }
            
    }
4.5 树 检查是否为BST(二叉查找树)
int former = Integer.MIN_VALUE;
    public boolean checkBST(TreeNode root){
        if(root == null) return true;
        if(!checkBST(root.left)) return false;
        if(root.val <= former) return false;
        former = root.val;
        if(!checkBST(root.right)) return false;
        return true;
    }

tips

先序遍历:左中右顺序,这样保证每一个元素值比上一个元素值大即可。

对上一层返回数据的处理:if语句

Integer.MIN_VALUE即min-value是Integer类里面的变量值。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/65268.html

相关文章

  • 我的阿里之路+Java面经考点

    摘要:我的是忙碌的一年,从年初备战实习春招,年三十都在死磕源码,三月份经历了阿里五次面试,四月顺利收到实习。因为我心理很清楚,我的目标是阿里。所以在收到阿里之后的那晚,我重新规划了接下来的学习计划,将我的短期目标更新成拿下阿里转正。 我的2017是忙碌的一年,从年初备战实习春招,年三十都在死磕JDK源码,三月份经历了阿里五次面试,四月顺利收到实习offer。然后五月怀着忐忑的心情开始了蚂蚁金...

    姘搁『 评论0 收藏0
  • 大厂难进?(来自双非 非科班 应届生的自述信)

    摘要:关于自己届毕业生一本双非学校,非科班可能和很多人一样,因为小时候喜欢打游戏,所以大学一直想学编程,但因为种种原因,自己来到了一个硬件相关专业,但由于现实和兴趣,自己又从事了软件相关的工作。找实习实习对于之后的秋招来说,是非常非常重要的。 ...

    jerryloveemily 评论0 收藏1
  • ⭐算法入门⭐《二叉树 - 二叉搜索树》简单05 —— LeetCode 897. 递增顺序搜索树

    文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   给你一棵二叉搜索树,请按 中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。  样例输入: [5,3,6,2,4,null,8,1,null,null,nu...

    Soarkey 评论0 收藏0
  • 开开心心做几道JavaScript机试题 - 01

    摘要:碰到这种面试官,你只有是个题霸,再加上眼缘够才能顺利入围。只要按照我题目的思路,甚至打出来测试用例看看,就能实现这个题目了。答案根据的,对答案做出修正。另我的答案绝不敢称最佳,随时欢迎优化修正。但了解总归是好的。 我们在长期的面试过程中,经历了种种苦不堪言,不诉苦感觉不过瘾(我尽量控制),然后主要聊聊常见JavaScript面试题的解法,以及面试注意事项 忆苦 面试第一苦,面试官的土 ...

    liujs 评论0 收藏0
  • 前端该如何准备数据结构和算法?

    摘要:很多前端同学在看到数据结构和算法后会有一定的抵触心理,或者尝试去练习,但是被难倒,从而放弃。本文选择的数据结构和算法的类别均是出现频率最高,以及应用最广的类别。面试这是非常现实的一点,也是很多前端学习数据结构和算法的原因。 一、导读 据我了解,前端程序员有相当一部分对数据结构和算法的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。 实际上,当你了解了数据结构和...

    simon_chen 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<