超硬核！我统计了BAT笔试面试出现频率最高的五道题，学会了总能碰到一道

秒速五厘米 2022-11-19 04:06 113阅读 0赞

> 所以说不要怕算法，简单的题反而出现的频率最高，不一定非要写个几百道才面试

# 两数之和 #

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

思路：

遇到的数字装到hashmap中，遇到的新数字查找有没有答案int dif = target - nums\[i\];

class Solution {
        public int[] twoSum(int[] nums, int target) {
            HashMap<Integer,Integer> map = new HashMap<>();
            int[] res = new int[2];
            for (int i = 0; i < nums.length; i++) {
                int dif = target - nums[i];
                if (map.get(dif) != null) {
                    res[0] = map.get(dif);
                    res[1] = i;
                    return res;
                }
                map.put(nums[i],i);
            }
            return res;
        }
    }

# 反转链表 #

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

经典题，一i个循环做那四个经典操作，自己拿纸笔画一画就懂啦。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    }

# 有效的括号 #

给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"  
输出: true  
示例 2:

输入: "()\[\]\{\}"  
输出: true  
示例 3:

输入: "(\]"  
输出: false  
示例 4:

输入: "(\[)\]"  
输出: false  
示例 5:

输入: "\{\[\]\}"  
输出: true

思路：

初始化栈 。一次处理表达式的每个括号。

1.  如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它。
2.  如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则表达式无效。

如果到最后我们剩下的栈中仍然有元素，那么表达式无效。

class Solution {
      // Hash table that takes care of the mappings.
      private HashMap<Character, Character> mappings;
      // Initialize hash map with mappings. This simply makes the code easier to read.
      public Solution() {
        this.mappings = new HashMap<Character, Character>();
        this.mappings.put(')', '(');
        this.mappings.put('}', '{');
        this.mappings.put(']', '[');
      }
    
      public boolean isValid(String s) {
    
        // Initialize a stack to be used in the algorithm.
        Stack<Character> stack = new Stack<Character>();
    
        for (int i = 0; i < s.length(); i++) {
          char c = s.charAt(i);
    
          // If the current character is a closing bracket.
          if (this.mappings.containsKey(c)) {
    
            // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
            char topElement = stack.empty() ? '#' : stack.pop();
    
            // If the mapping for this bracket doesn't match the stack's top element, return false.
            if (topElement != this.mappings.get(c)) {
              return false;
            }
          } else {
            // If it was an opening bracket, push to the stack.
            stack.push(c);
          }
        }
        // If the stack still contains elements, then it is an invalid expression.
        return stack.isEmpty();
      }
    }

# 爬楼梯/跳台阶 #

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

找递推关系：

1）跳一阶，就一种方法

2）跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种

3）三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。

它跳一阶来到这里，说明它上一次跳到n-1阶，

同理，它也可以从n-2跳过来

f（n）为跳到n的方法数，所以，f(n)=f(n-1)+f(n-2)  
![20210414105609291.png][]

class Solution {
        public int climbStairs(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

# 合并链表 #

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = \[1,2,4\], l2 = \[1,3,4\]  
输出：\[1,1,2,3,4,4\]  
示例 2：

输入：l1 = \[\], l2 = \[\]  
输出：\[\]  
示例 3：

输入：l1 = \[\], l2 = \[0\]  
输出：\[0\]

提示：

两个链表的节点数目范围是 \[0, 50\]  
\-100 <= Node.val <= 100  
l1 和 l2 均按 非递减顺序 排列

思路：归并的思想，一直比较两边的大小并且插入。

class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode prehead = new ListNode(-1);
    
            ListNode prev = prehead;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
            // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
            prev.next = l1 == null ? l2 : l1;
    
            return prehead.next;
        }
    }

[20210414105609291.png]: /images/20221022/edd6c0ddaaf94bc8b364ad471175f6d2.png