如何做网站小编,自媒体运营怎么学,站群管理系统,wordpress迁移安装所以说不要怕算法#xff0c;简单的题反而出现的频率最高#xff0c;不一定非要写个几百道才面试 两数之和
给定一个整数数组 nums 和一个目标值 target#xff0c;请你在该数组中找出和为目标值的那 两个 整数#xff0c;并返回他们的数组下标。
你可以假设每种输入只会… 所以说不要怕算法简单的题反而出现的频率最高不一定非要写个几百道才面试 两数之和
给定一个整数数组 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) {HashMapInteger,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 HashMapCharacter, Character mappings;// Initialize hash map with mappings. This simply makes the code easier to read.public Solution() {this.mappings new HashMapCharacter, Character();this.mappings.put(), ();this.mappings.put(}, {);this.mappings.put(], [);}public boolean isValid(String s) {// Initialize a stack to be used in the algorithm.StackCharacter stack new StackCharacter();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 doesnt match the stacks 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跳过来
fn为跳到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;}
}
