莆田做外贸网站十大互联网平台

当前位置： 首页 > news >正文

莆田做外贸网站,十大互联网平台,网页模板免费下载网站,app开发公司有哪些坑文章目录 引言复习堆堆——前K个高频元素个人实现复习实现二参考实现 新作单词搜索个人实现参考实现 分割回文串个人实现参考实现 环形链表II个人实现参考实现 两个有序链表个人实现 总结 引言 又是充满挑战性的一天#xff0c;继续完成我们的任务吧#xff01;继续往下刷继续完成我们的任务吧继续往下刷一场面试三个构成八股、项目和算法都得抓住加油今天复习一下堆然后把回溯剩下的题目全部做完然后的继续往下做链表 复习 堆 对顶堆——数据流的中位数 front是大顶堆back是小顶堆
堆——前K个高频元素 题目链接第一次练习链接第二次练习链接虽然已经做了两次但是一点都想不起来应该怎么做 个人实现 这道题可以通过设置不同的数据结构实现通过key-value改变记录每一个数字出现的频率然后通过PriorityQueue来实现根据频率进行排序这样效率就快很多那么怎么实现自定义排序就很重要 class Solution {class Item implements ComparableItem{int val;int freq;Item(int value,int frequency){val value;freq frequency;}// override the compareTo functionOverridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueueItem pq new PriorityQueue(Comparator.reverseOrder());MapInteger,Item map new HashMap();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp map.get(x);temp.freq temp.freq 1;System.out.println(map.get(x).freq);}else{Item temp new Item(x,1);map.put(x,temp);pq.add(temp);}}// traverse the front k elementsint[] res new int[k];//System.out.println(pq.peek().val);for(int i 0;i k;i )res[i] pq.poll().val;return res;} }问题 如何重写对象compare方法 要实现Comparable接口compareTo方法是接受当前类型的变量进行的比较compareTo方法返回的是一个int类型的变量实现comparable接口需要实现compareTo方法
class Item implements ComparableItem {int val;int freq;Item(int value, int frequency) {val value;freq frequency;}// override the compareTo functionOverridepublic int compareTo(Item o) {return Integer.compare(o.freq, this.freq); // descending order} }致命问题PriorityQueue并不会自动重新排序需要每次更新都要插入和删除对应的元素不然会出问题 复习实现二 这里不知道自己着了什么魔这个题目为啥要想的那么复杂不就是先统计频率然后再根据频率进行排序吗为什么要想那么多 class Solution {class Item implements ComparableItem{int val;int freq;Item(int value,int frequency){val value;freq frequency;}// override the compareTo functionOverridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueueItem pq new PriorityQueue(Comparator.reverseOrder());MapInteger,Item map new HashMap();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp map.get(x);temp.freq temp.freq 1;}else{map.put(x,new Item(x,1));}}// traverse the values int the for(Item x:map.values()){pq.add(x);}// traverse the front k elementsint[] res new int[k];//System.out.println(pq.peek().val);for(int i 0;i k;i )res[i] pq.poll().val;return res;} }问题 这里Map的相关方法使用起来还是带有试验的性质很多方法当时写了就错了编译器提醒没有这种方法才知道应该换这里再复习一遍加入元素 put(K key,V value)如果存在旧值会将其替换注意没有set方法那是list才有的 获取对应的value get(Object key)如果不含有对应的key就返回null 删除对应的元素 remove(Object key) 判定是否含有对应的元素 containsKeyObejct key是containsKeycontains是Set的方法 判定是否为空 isEmpty不是Empty每次都写错 获取所有value values这里是返回所有的values不是valueset 获取所有的key keySet不是keys
参考实现 使用计数排序 将所有出现的频次记录在对应的数组中然后根据索引进行遍历减少遍历的时间 这里就不记录了如果感兴趣就自己去看 限定堆使用的大小 如果直接将所有的元素加入到堆中进行排序需要消耗很多时间这里只要前K个元素所以只需要维护一个大小为K的堆就行了 class Solution {class Item implements ComparableItem{int val;int freq;Item(int value,int frequency){val value;freq frequency;}// override the compareTo functionOverridepublic int compareTo(Item o){return Integer.compare( this.freq,o.freq);}}public int[] topKFrequent(int[] nums, int k) {// define map to store the key-value item ,priorityqueue to sort the itemPriorityQueueItem pq new PriorityQueue();MapInteger,Item map new HashMap();// traverse all the elementsfor(int x :nums){if(map.containsKey(x)){Item temp map.get(x);temp.freq temp.freq 1;}else{map.put(x,new Item(x,1));}}// traverse the values int the for(Item x:map.values()){if(pq.size() k)pq.add(x);else{if(pq.peek().freq x.freq){pq.poll();pq.add(x);}}}// traverse the front k elementsint[] res new int[k];//System.out.println(pq.peek().val);for(int i 0;i k;i )res[i] pq.poll().val;return res;} }新作 单词搜索 题目链接 注意 整个二维矩阵的大小可能是一个单元格仅仅只有一个字母可能是边界情况需要特殊处理。目标单词的长度是遍历的深度也就是遍历树的高度然后上下左右是四个方向是每一层遍历的宽度。 个人实现 这道题是典型的回溯回溯的要素设定如下 idx 界限值是 单词的长度每一层遍历的宽度是上下左右四个方向需要维护一个exist数组标记每一个元素的访问情况。
class Solution {// define the global string to store the mid situationStringBuilder str new StringBuilder();// exist matrix to store the attendenceboolean[][] exist ;//boolean res false;int[][] step {{1,0},{0,1},{-1,0},{0,-1}};boolean dfs(char[][] board,String word,int idx,int x,int y){if(idx word.length()){return true;}for(int i 0;i 4;i ){int xNext x step[i][0];int yNext y step[i][1];if(xNext 0 xNext board.length ){if(yNext 0 yNext board[0].length){if(!exist[xNext][yNext] board[xNext][yNext] word.charAt(idx)){exist[xNext][yNext] true;if(dfs(board,word,idx 1,xNext,yNext)) return true;exist[xNext][yNext] false;}}}}return false;}public boolean exist(char[][] board, String word) {//define row and col of the matrixint row board.length;int col board[0].length;exist new boolean[row][col];// traverse the board to find the first charfor(int i 0;i board.length;i ){for(int j 0;j board[0].length;j ){if(board[i][j] word.charAt(0)){//System.out.println(first board[i][j]);exist[i][j] true;if(dfs(board,word,1,i,j)) return true;exist[i][j] false;}}}return false;} }代码量真多不过还是在规定时间内完成了 参考实现 这里可以将融合到原来的数组中通过修改特殊的字符然后判定当前位置是否已经访问过 分割回文串 题目链接 注意 回文串逆序和顺序都是一样的仅由小写字母构成不用担心字母大小写变换长度是1到16可能有边界情况需要特殊考虑 个人实现 这道题是一个组合体找到所有的组合然后在判断一下是否是回文就行了。总结一下回溯的几个要素 树的深度总的元素数量节点的宽度每一个节点放或者不放两种情况。
错误这里审错题目了是分割字符串应该然后分割之后每一个字串都是回文 修改一下回溯的几个要素 树的深度分割的位置总的元素数减一每一个元素都有一个分割点节点的宽度是否在当前点进行分割
class Solution {ListString list new ArrayList();ListListString res new ArrayList();boolean judge(String str){str str.trim();StringBuilder sb new StringBuilder(str);sb.reverse();return str.equals(sb.toString());}void dfs(StringBuilder s,int idx,int len){if(idx len ){if(judge(s.toString())){list.add(s.toString());res.add(new ArrayList(list));list.remove(list.size() - 1);}return;}// cutint subIdx len - s.length();String temp s.substring(0,idx - subIdx);//System.out.print(idx: idx temp: s.substring(0,idx - subIdx));if(judge(temp)){list.add(temp);//System.out.println( subtemp: s.substring(idx - subIdx));dfs(new StringBuilder(s.substring(idx - subIdx)),idx 1,len);list.remove(list.size() - 1);}// not cutdfs(s,idx 1,len);}public ListListString partition(String s) {dfs(new StringBuilder(s),1,s.length());return res;} }问题 StringBuilder获取子串是substring没有大写而且也没有简称不是subString不是subStr 都不是是substring substring(strat_idx:从start_idx到末尾substring(start_idx,end_idx):从start_idx到end_idx这段子串 ,不包括end_idx,相当于在end_idx前面一个字符做的分割点 String去除空格 str.trim()去除前后空格str.replace “,”;正则表达式replaceAll(“\s”, “”) 我这里回溯的角度可能有问题导致时间上有很多耗费
参考实现 暴力搜索 迭代优化 暴力搜索 这里举得是区间长度也就是区间起点然后列举区间的终点不同于我们列举每一个分割点迭代深度 每一区间的起点的位置 单次迭代的宽度 * 迭代优化 利用了回文字符串的中间子串也一定是回文字符串的特性具体如下图 for(int j 0;j n;j ){for(int i 0;i j;i ){if(i j) f[i][j] true;else if(s[i] s[j]){if(i 1 j -1 || f[i 1][j - 1]) f[i][j] true;}} }具体实现代码 class Solution {boolean[][] f;ListString list new ArrayList();ListListString res new ArrayList();void dfs(String s,int idx){int m s.length();if(idx m){res.add(new ArrayList(list));return ;}for(int i idx ;i m; i){if(f[idx][i]){//System.out.println(idx: idx i i substr:s.substring(idx,i1));list.add(s.substring(idx,i 1));dfs(s,i1);list.remove(list.size() - 1);}}}public ListListString partition(String s) {int m s.length();f new boolean[m][m];for(int j 0;j m;j ){for(int i 0;i j;i ){if(i j) f[i][j] true;else if(s.charAt(i) s.charAt(j)){if(i 1 j - 1 || f[i 1][j - 1]) f[i][j] true;}}}dfs(s,0);return res;} }确实更快那个回文推导的得稍微记一下 环形链表II 题目连接 注意pos表示-1或者有效索引不用担心数字越界空间复杂度要求是O1 个人实现 这个明显是用快慢指针首先判定是否有环然后在有环的情况下判定出对应环的起始点难点在第二步不过感觉这个环的起始点之前好像做过。感觉快慢节点在有环的情况下应该有特殊情况 这里还是不知道怎么推导出来的这题挂了 如果不强制要求空间复杂度的话只需要一次遍历就能实现 这里就不写了没什么意思 参考实现 这里推导的比较绕我看了很多遍总结起来就是一句话 快慢指针相遇的地方和链表的头节点分别同时触发一个速度为1的节点遍历相遇点就是入点
先套一个快慢指针的模板 while(f ! null){f f.next;s s.next;if(f null) return false;f f.next;if(f s) return true; }最终实现代码 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public ListNode detectCycle(ListNode head) {if(head null || head.next null) return null;ListNode s head;ListNode f head.next;// judge whether contains circlewhile(f ! null){f f.next;s s.next;if(f null) return null;f f.next;if(f s){s head;f f.next;while(s ! f) {s s.next;f f.next;}return s;}}return null;} }两个有序链表 题目链接 第一次练习连接 个人实现 这个题目第二次做了而且是个简单题直接遍历就行了 /** 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 head1 list1;ListNode head2 list2;ListNode dummy new ListNode();ListNode temp dummy;while(head1 ! null head2 ! null){if(head1.val head2.val){temp.next head1;head1 head1.next;temp temp.next;}else{temp.next head2;head2 head2.next;temp temp.next;}}temp.next (head1 null ? head2:head1);return dummy.next;} }题目很简单但是让我想到了某一次字节的面试面试官觉得我代码写的太差了那道题是一个大数加法使用链表表示的我最后写的太差了毕竟我已经换了三道题感觉完蛋了 总结 今天状态不得行刷到了第三题我就厌烦的不行不过还是得调整一下真的是每天刷题刷的恶心恶心的不行后续还是得加油又搞到好晚我要睡了明天面试百度加油