查看服务器上的网站,网络营销推广招聘广告,发布外链的步骤,网站微信建设运维培训班文章目录 数学_简单13_罗马数字转整数66_ 加一9_回文数70_爬楼梯69_x的平方根509_斐波那契数列2235_两整数相加67_二进制求和415_字符串相加2413_最小偶倍数2469_温度转换704_二分查找(重点) 数组_简单1_两数之和88_合并两个有序数组 链表_简单21_合并两个有序链表203_移除链表… 文章目录 数学_简单13_罗马数字转整数66_ 加一9_回文数70_爬楼梯69_x的平方根509_斐波那契数列2235_两整数相加67_二进制求和415_字符串相加2413_最小偶倍数2469_温度转换704_二分查找(重点) 数组_简单1_两数之和88_合并两个有序数组 链表_简单21_合并两个有序链表203_移除链表元素 字符串_简单125_验证回文串 哈希表_简单169_多数元素242_有效的字母异位词 双指针_简单28_找出字符串中第一个匹配项的下标344_反转字符串 递归_简单206_反转链表 栈_简单20_有效的括号232. 用栈实现队列 队列_简单225_用队列实现栈 树_简单104_二叉树的最大深度144_二叉树的前序遍历 以下汇总都是高出题频率题 按照以下顺序刷题 先简单再中等 数学 数组 链表 字符串 哈希表 双指针 递归 栈 队列 树 刷了多轮后再刷 图与回溯算法 贪心 动态规划 练熟了之后不能再开智能模式刷题了,一些细节关注不到 数学_简单
13_罗马数字转整数
class Solution {MapCharacter, Integer symbolValues new HashMapCharacter, Integer() {{put(I, 1);put(V, 5);put(X, 10);put(L, 50);put(C, 100);put(D, 500);put(M, 1000);}};public int romanToInt(String s) {// I1// IV4// V5// IX9// X10// XL40// L50// XC90// C100// CD400// D500// CM900// M1000int sum 0;for(int i0;is.length();i){int value symbolValues.get(s.charAt(i));//如果这个字符代表的数比后一个数大就//反之则if(is.length()-1 valuesymbolValues.get(s.charAt(i1))){//这里用双,也保证当运行到第[s.length()-1]轮时,不执行后面的判断条件,就不会报错sum-value;}else{sumvalue;}}return sum;}
}66_ 加一
class Solution {public int[] plusOne(int[] digits) {for (int i digits.length - 1; i 0; i--) {if (digits[i] 9) {digits[i] 0;} else {digits[i] 1;return digits;}}//如果所有位都是进位则长度1digits new int[digits.length 1];digits[0] 1;return digits;}
}
//千万不要想着将数组变为整数再计算,太麻烦9_回文数
class Solution {//暴力解法public boolean isPalindrome(int x) {String reversedStr (new StringBuilder(x)).reverse().toString();//StringBuilder是创建了一个StringBuilder对象,但是要转成string对象要toString()return (x).equals(reversedStr);//return (x)reversedStr;不能这么比,因为这样比的是地址值}
}class Solution {// 数学解法public boolean isPalindrome(int x) {//如何是负数不可能是回文//末位是0不可能是回文,除非X0if (x 0 || x % 10 0 x ! 0) {return false;}//让x代表前半段,reversex代表后半段//以上判断末位0正好除去了这里无法实现的翻转情况int reversex 0;while (x reversex) {reversex reversex * 10 x % 10;x x / 10;}return reversex x || reversex / 10 x;//两种情况,位数为偶数和奇数}
}70_爬楼梯
class Solution {public int climbStairs(int n) {//首先本题观察数学规律可知是斐波那契数列,但那逼公式谁记得//用另一种方法//爬到n-1层时,还有一节就到了//爬到n-2层时.还有两节就到了//所以methodNum[n]method[n-1]method[n-2]int[] methodNum new int[n1];methodNum[0] 1;methodNum[1] 1;for (int i 2; i methodNum.length; i) {methodNum[i] methodNum[i-1]methodNum[i-2];}return methodNum[n];}
}69_x的平方根
class Solution {public int mySqrt(int x) {// 非负整数// 二分查找,直到逼近满足k**2x的最大kint l 0, r x, ans -1;while (l r) {int mid (r l) / 2;if ((long) mid * mid x) {ans mid;l mid 1;}else {r mid - 1;}}return ans;}
}509_斐波那契数列
class Solution {public int fib(int n) {int[] F new int[n1];F[0] 0;if(n0){F[1]1;}for (int i 2; i F.length; i) {F[i] F[i-1]F[i-2];}return F[n];}
}2235_两整数相加
class Solution {public int sum(int num1, int num2) {return num1num2;}
}67_二进制求和
class Solution {public String addBinary(String a, String b) {//StringBuffer是可变的字符串类,String 是不可变的对象StringBuffer ans new StringBuffer();//取两个字符串中最大长度的字符串的长度//carry为计算记录,可算出当前位值和进位值int n Math.max(a.length(), b.length()), carry 0;for (int i 0; i n; i) {//比如1-0,两个字符串相减就是ascii码整数差值//从末尾位向前计算//当超过较短字符串长度的位计算,补零计算carry i a.length() ? (a.charAt(a.length() - 1 - i) - 0) : 0;carry i b.length() ? (b.charAt(b.length() - 1 - i) - 0) : 0;//添加本位的计算结果ans.append((char) (carry % 2 0));//记录进位值,可能为0,可能为1carry / 2;}//最后的进位还是1,再进位if (carry 0) {ans.append(1);}//翻转过来,因为计算是先低位再高位,但是显示应该是先高位再低位ans.reverse();//返回值要返回字符串类型return ans.toString();}
}415_字符串相加
//思路与二进制求和相同
class Solution {public String addStrings(String num1, String num2) {StringBuffer ans new StringBuffer();int carry 0;int maxLen Math.max(num1.length(),num2.length());for (int i 0; i maxLen; i) {carryinum1.length() ? num1.charAt(num1.length()-1-i)-0:0;carryinum2.length() ? num2.charAt(num2.length()-1-i)-0:0;ans.append(carry%10);carry /10;}if(carry!0){ans.append(carry);}ans.reverse();return ans.toString();}
}2413_最小偶倍数
class Solution {public int smallestEvenMultiple(int n) {if(n%20){return n;}else{return 2*n;}}
}2469_温度转换
class Solution {public double[] convertTemperature(double celsius) {double[] ans new double[2];ans[0] celsius273.15;ans[1] celsius*1.8032.00;return ans;}
}704_二分查找(重点)
class Solution {public int search(int[] nums, int target) {Integer l 0;Integer r nums.length-1;while(lr){Integer mid (lr)/2;if(nums[(lr)/2]target){//新的右边界一定要是mid-1//边界的更新一定要精确,需要思考最后的极端情况//如果不精确,最后就无法收敛到目标值//或者无法因为数组中不包含目标值,而不能跳出lr的满足条件,不精确将一直满足lrr mid-1;}else if(nums[(lr)/2]target){//新的左边界一定要是mid1l mid1;}else{return mid;}}return -1;}
}数组_简单
1_两数之和
class Solution {public int[] twoSum(int[] nums, int target) {//建立一个哈希表,存放数值(key)和下标(value)//使用Map接口作为类型相比使用HashMap更加灵活MapInteger,Integer hashtable new HashMapInteger,Integer();for (int i 0; i nums.length; i) {//每次与哈希中比对,保证不重复利用一个数值,因为此数值还没存放到表中if(hashtable.containsKey(target-nums[i])){return new int[]{hashtable.get(target-nums[i]),i};}//没有满足的配对,再将此值放入哈希表中hashtable.put(nums[i], i);}return null;}
}88_合并两个有序数组
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {//逆双指针int p1 m-1,p2 n-1; for (int i 0; i nums1.length; i) {//从后面向nums1中插入值,不会覆盖nums1含值的位置if(p10p20){if(nums1[p1]nums2[p2]){//nums1的含值尾值大,插入num1的尾部nums1[nums1.length-1-i] nums1[p1--];}else{//nums2的含值尾值大,插入num1的尾部nums1[nums1.length-1-i] nums2[p2--];}}else if(p10){nums1[nums1.length-1-i] nums2[p2--];}else if(p10){nums1[nums1.length-1-i] nums1[p1--];}}return;}
}链表_简单
21_合并两个有序链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode prehead new ListNode(-1);ListNode prev prehead;//此时 prehead和prev只是同一个节点的不同声明,不要将prehead和prev当作两个节点while(list1 !null list2!null){if(list1.val list2.val){prev.nextlist1;list1 list1.next;}else{prev.next list2;list2 list2.next;}prev prev.next;}prev.next list1 null?list2:list1;return prehead.next;}
}203_移除链表元素
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode newhead head;ListNode ptr newhead;while (ptr!null) {if(newhead.val val ptr newhead){//这是我自己的解法,但是其实官方迭代的思路是在head节点之前//链接一个newhead.next head,就简单多了,不用嵌套的逻辑了newhead newhead.next;ptr newhead;}else{while(ptr.next !null ptr.next.val val){ptr.next ptr.next.next;}ptr ptr.next;}}return newhead;}
}字符串_简单
125_验证回文串
解1
class Solution {public boolean isPalindrome(String s) {//先去除除了字母和数字的特殊字符.放入sgood//将sgood和sgood.reverse对比,相等则回文StringBuffer sgood new StringBuffer();int length s.length();for (int i 0; i length; i) {char ch s.charAt(i);if(Character.isLetterOrDigit(ch)){sgood.append(Character.toLowerCase(ch));}}StringBuffer reverse new StringBuffer(sgood).reverse();return sgood.toString().equals(reverse.toString());}
}解2
class Solution {public boolean isPalindrome(String s) {//在原字符串上比对//Time O(n),space O(1)int l 0;int r s.length()-1;while(lr){while(lr !Character.isLetterOrDigit(s.charAt(l))){l;}while(lr !Character.isLetterOrDigit(s.charAt(r))){r--;}if(lrCharacter.toLowerCase(s.charAt(l))!Character.toLowerCase(s.charAt(r))){return false;}l;r--;}return true;}
}哈希表_简单
哈希表的作用
统计一系列成员的数量
169_多数元素
import java.util.Map.Entry;
class Solution {public int majorityElement(int[] nums) {//集合只支持放引用数据类型HashMapInteger,Integer hashMap new HashMap();for (Integer i 0; i nums.length; i) {Integer num nums[i];if(!hashMap.containsKey(num)){hashMap.put(num, 1);}else{Integer count hashMap.get(num);count;hashMap.put(num, count);}}Integer maxCount 0;Integer maxValue null;for (EntryInteger,Integer entrySet : hashMap.entrySet()) {if(maxCount entrySet.getValue()){maxCount entrySet.getValue();maxValue entrySet.getKey();}}return maxValue;}
}242_有效的字母异位词
class Solution {public boolean isAnagram(String s, String t) {HashMapCharacter,Integer sHashMap new HashMap();HashMapCharacter,Integer tHashMap new HashMap();Character sCh;Character tCh;//我这里理解起来比较容易//官方只用了一个hashmap,比较优雅//注意,HashMap的泛型是Character也不严谨,并不完全适用于unicode//Character只存占两字节的字符,而unicode有超过100000个不同的字符//远超65535个,官方也是Character,我觉得也不严谨//所以最正确的方法应该是先强转成Integer型(4字节)再存入hashmapif(s.length()!t.length()){return false;}for (int i 0; i s.length(); i) {sCh s.charAt(i);if(!sHashMap.containsKey(sCh)){sHashMap.put(sCh, 1);}else{Integer count sHashMap.get(sCh);sHashMap.put(sCh, count1);}tCh t.charAt(i);if(!tHashMap.containsKey(tCh)){tHashMap.put(tCh, 1);}else{Integer count tHashMap.get(tCh);tHashMap.put(tCh, count1);}}return sHashMap.equals(tHashMap);}
}双指针_简单
28_找出字符串中第一个匹配项的下标
class Solution {public int strStr(String haystack, String needle) {//双指针//一个指针用来匹配//另一个指针如果在另一个指针匹配时,留在疑似匹配串的头部Integer head 0;for (Integer idx 0; idx haystack.length(); ) {if(haystack.charAt(idx)needle.charAt(idx-head)){if(idx-head1 needle.length()){return head;}idx;}else{head;idx head;}}return -1;}
}344_反转字符串
class Solution {public void reverseString(char[] s) {Integer len s.length;Integer i 0;//意识不到数组的最后一个元素的索引是len-1也是老毛病了while(i(len/2-1)){Character temp s[i];s[i] s[len-1-i];s[len-1-i]temp;i;}}
}递归_简单
206_反转链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {//递归思想//先用递归方法之前的程序,递归到最后一层(最后一个节点)//再用递归方法之后的程序翻转指针//为什么要加headnull的判断条件,//为什么headnull在前,head.nextnull在后//因为如果链表为[],直接报错,触发空指针异常if(headnull||head.nextnull){return head;}ListNode newHead reverseList(head.next);head.next.next head;head.next null;//递归到最后一层的时候防止1-2互相指,1-2-3-4-5return newHead; }
}栈_简单
20_有效的括号
class Solution {public boolean isValid(String s) {//栈思想//栈的接口//Deque是双端队列,是接口,此接口实现了queue队列//LinkedList实现了deque双端队列接口//deque双端队列可以作为栈(push()/pop())或队列(offer()/poll())使用//pop(),从栈顶移除一个元素//peek(),查看栈顶元素//push(),放入栈顶//push和pop都是在队头添加和删除DequeCharacter deque new LinkedList();//Deque为队列,可以作为栈使用for (int i 0; i s.length(); i) {Character ch s.charAt(i);//有左括号就在栈中放入对应的右括号if(ch (){deque.push());}else if (ch [) {deque.push(]);}else if (ch {) {deque.push(});}//没循环完,且左括号就遍历完,就为空说明有余下的右括号//匹配不上也falseelse if(deque.isEmpty()||deque.peek()!ch){return false;}else{deque.pop();}}// 完美匹配上,栈应该为空return deque.isEmpty();}
}232. 用栈实现队列
class MyQueue {DequeInteger inStack;DequeInteger outStack;//两个栈,一个作为入队列,一个作为出队列public MyQueue() {inStack new LinkedList();outStack new LinkedList();}public void push(int x) {inStack.push(x);}public int pop() {//在出队列的时候才将inStack的数据移到outStack,如果在入队列的时候,每一次移动时间复杂度都将是O(n)//只有outStack为空,才能将inStack移到outStack,不然inStack的新数据将把outStack中的旧数据压到栈底while(outStack.isEmpty()){//移动直到inStack为空while(!inStack.isEmpty()){outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {//与pop()操作同理while(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {if(inStack.isEmpty() outStack.isEmpty()){return true;}return false;}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/队列_简单
225_用队列实现栈
class MyStack {//LinkedList是类,LinkedList中实现了deque接口//Queue队列是一个接口,deque双端队列中实现了queue接口QueueInteger queue1;QueueInteger queue2;public MyStack() {queue1 new LinkedListInteger();queue2 new LinkedListInteger();}public void push(int x) {queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}QueueInteger temp queue1;queue1 queue2;queue2 temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/树_简单
104_二叉树的最大深度
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int maxDepth(TreeNode root) {//递归思想if(root null){return 0;}else{int lDepth maxDepth(root.left);int rDepth maxDepth(root.right);return Math.max(lDepth,rDepth) 1;}}
}144_二叉树的前序遍历
import com.sun.source.tree.Tree;/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root ! null){list.add(root.val);if(root.left ! null){ListInteger left preorderTraversal(root.left);list.addAll(left);}if(root.right ! null){ListInteger right preorderTraversal(root.right);list.addAll(right);}}return list;}
}
