所以说不要怕算法,简单的题反而出现的频率最高,不一定非要写个几百道才面试
给定一个整数数组 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;
}
}
?
?
?
你知道如果没有它,浏览器在渲染页面的时候会使用怪异模式;你知道各个浏览器在...
本文转载自微信公众号「SH的全栈笔记」,作者SH。转载本文请联系SH的全栈笔记公...
[Ctrl+A 全选 注: 引入外部Js需再刷新一下页面才能执行 ] 原文链接:https://m.j...
grep (缩写来自Globally search a Regular Expression and Print)是一种强大的...
目录 主要思路 效果 ?核心代码 解码 SDL初始化 视频帧渲染 完整工程?? ? 主要思...
在最近的项目中 使用了jsp+servlet来开发项目,但是由于后台的不太熟练 导致了困...
问题描述 由于之前在安装VSCODE的时候,没注意详细阅读提示,而且第一次安装比较...
前言 有时候我们的应用需要系统级的权限来实现一些功能(如静默安装),这时候需...
废话不多说了,直接给大家贴代码了,具体代码如下所示: !DOCTYPE htmlhtmlheadm...
判断目标字符串中是否 可能 含这个字符。 假如待匹配字符串包含指定字符串并且匹...