超硬核！我统计了BAT笔试面试出现频率最高的五道题，学会了总能碰到一道
所以说不要怕算法，简单的题反而出现的频率最高，不一定非要写个几百道才面试
两数之和
给定一个整数数组 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
思路：
初始化栈 。一次处理表达式的每个括号。
- 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它。
- 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则表达式无效。
如果到最后我们剩下的栈中仍然有元素，那么表达式无效。
-
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)
-
-
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;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/115693139
- 点赞
- 收藏
- 关注作者
评论（0）