襄阳建设局网站,wordpress 资源文件,酒店网站做的比较好的,WordPress最顶部的文章目录 17.01 不用加号的加法17.04 消失的数字17.05字母与数字17.06 2出现的次数17.07 婴儿名字17.08 马戏团人塔17.09 第k个数17.10 主要元素17.11 单词距离17.12 BiNode17.13 恢复空格#xff08;未做#xff0c;字典树dp#xff09;17.14 最小K个数17.15 最长单词17.16… 文章目录 17.01 不用加号的加法17.04 消失的数字17.05字母与数字17.06 2出现的次数17.07 婴儿名字17.08 马戏团人塔17.09 第k个数17.10 主要元素17.11 单词距离17.12 BiNode17.13 恢复空格未做字典树dp17.14 最小K个数17.15 最长单词17.16按摩师17.17 多次搜索17.18 最短超串17.19 消失的两个数17.20 连续中值17.21 接雨水后面的太难了不想写了换书刷了17.22 单词转换17.23最大黑方阵17.24 最大子矩阵17.25 单词矩阵17.26 稀疏相似度 17.01 不用加号的加法 好像是计算机组成原理的知识完全不会。
class Solution {public static int add(int a, int b) {int sum 0, carry 0;while(b ! 0) {sum a ^ b; // 异或计算未进位的部分carry (a b) 1; // 进位部分a sum; // 保存未进位部分再次计算b carry; // 保存进位部分再次计算}return a; // 最后无进位异或的结果即加法结果}
}17.04 消失的数字 异或运算利用xx0x0xx^y y^x的性质简单说就是一个萝卜一个坑下标和数组里的数然后找没有萝卜的那个坑。
int missingNumber(vectorint nums)
{int sum 0;for (int i 0; i nums.size(); i){sum ^ i;sum ^ nums[i];}sum ^ nums.size();return sum;
}17.05字母与数字 定义一个差分数组diff, 后面直接对diff数组进行操作。来确定截取范围。
class Solution {public String[] findLongestSubarray(String[] array) {int[] diffnew int[array.length1];HashMapInteger,Integer firstnew HashMap();for(int i0;iarray.length;i){diff[i1](array[i].charAt(0)6 1 )*2-1 diff[i];}int start0,end0;for(int i0;idiff.length;i){int jfirst.getOrDefault(diff[i],-1);if(j0){first.put(diff[i],i);}else if(i-jend-start){startj;endi;}}String[] ansnew String[end-start];System.arraycopy(array, start, ans, 0, ans.length);return ans;}
}17.06 2出现的次数 class Solution {public int numberOf2sInRange(int n) {if (n 2) return 0;int high n, pow 1, low 0;while (high 9) {low high % 10 * pow;pow * 10;high / 10;}if (high 1) return numberOf2sInRange(pow - 1) numberOf2sInRange(low);if (high 2) return numberOf2sInRange(2 * pow - 1) numberOf2sInRange(low) low 1;return pow high * numberOf2sInRange(pow - 1) numberOf2sInRange(low);}
}n358 high3 low58 pow100 ans1003func(99)func(58) 200多里面的2 0-99里面的3 201-258里面的2
17.07 婴儿名字 使用并查集而不是让所有都指向一个祖宗。
class Solution {public String[] trulyMostPopular(String[] names, String[] synonyms) {HashMapString,Integer map new HashMap();HashMapString,String unionmapnew HashMap();for(int i0;inames.length;i){ //对names进行简单处理int idx1names[i].indexOf(();int idx2names[i].indexOf());int frequencyInteger.valueOf(names[i].substring(idx11,idx2));map.put(names[i].substring(0,idx1),frequency);}for(String pair:synonyms){int idxpair.indexOf(,);String name1pair.substring(1,idx);String name2pair.substring(idx1,pair.length()-1);//找祖宗节点while(unionmap.containsKey(name1)){name1unionmap.get(name1);}while(unionmap.containsKey(name2)){name2unionmap.get(name2);}if(!name1.equals(name2)){int frequencymap.getOrDefault(name1,0)map.getOrDefault(name2,0);String s1 name1.compareTo(name2)0 ? name1:name2;String s2name1.compareTo(name2)0 ?name2:name1;unionmap.put(s2,s1);map.remove(s2);map.put(s1,frequency);}}String[] ansnew String[map.size()];int index0;for(String name:map.keySet()){StringBuilder s1new StringBuilder(name);s1.append(();s1.append(map.get(name));s1.append(()));ans[index]s1.toString();}return ans;}
}17.08 马戏团人塔 关于Arrays.binarySearch 要理解为什么先按身高升序排再按体重降序排。 height[] 1 2 2 3 4 weight[] 1 4 3 5 7 这样从前到后先输入4然后输入3最后在dp[]中定格的是3
class Solution {public int bestSeqAtIndex(int[] height, int[] weight) {int len height.length;int[][] person new int[len][2];for (int i 0; i len; i)person[i] new int[]{height[i], weight[i]};Arrays.sort(person, (a, b) - a[0] b[0] ? b[1] - a[1] : a[0] - b[0]);int[] dp new int[len];int res 0;for (int[] pair : person) {int i Arrays.binarySearch(dp, 0, res, pair[1]);if (i 0)i -(i 1);dp[i] pair[1];if (i res)res;}return res;}
}17.09 第k个数 三指针问题三个指针然后分别进行操作取最小值即可。
public int getKthMagicNumber(int k) {int [] result new int[k];result[0] 1;// 定义三个 指针分别表示 resultA、B、C 的下标int point3 0;int point5 0;int point7 0;for (int i 1; i k; i) {int resultN Math.min(Math.min(result[point3] * 3, result[point5] * 5), result[point7] * 7);if (resultN % 3 0) {point3;}if (resultN % 5 0) {point5;}if (resultN % 7 0) {point7;}result[i] resultN;}return result[k - 1];}
}17.10 主要元素
数组中占比超过一半的元素称之为主要元素。 先用摩尔投票法筛出一个元素然后再判断这个元素的占比是否大于一半。
17.11 单词距离
单纯遍历一遍记录即可
17.12 BiNode 中序遍历过程中将当前节点的左节点置空并将当前节点置为上一结点的右节点。pre始终指向当前节点的上一结点在遍历时不断的移动。 一定要把pre声明出一个变量。
class Solution {TreeNode prenull;public TreeNode convertBiNode(TreeNode root) {if(rootnull) return null;TreeNode ansroot;while(ans.left!null) ansans.left;inorder(root);return ans;}public void inorder(TreeNode root){if(rootnull) return;inorder(root.left);root.leftnull;if(pre!null) pre.rightroot;preroot;inorder(root.right);}}17.13 恢复空格未做字典树dp 字典树插入时要逆序插入。这样遍历sentence的时候方便向前查找
class Solution {public int respace(String[] dictionary, String sentence) {int n sentence.length();Trie root new Trie();for (String word: dictionary) {root.insert(word);}int[] dp new int[n 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for (int i 1; i n; i) {dp[i] dp[i - 1] 1;Trie curPos root;for (int j i; j 1; --j) {int t sentence.charAt(j - 1) - a;if (curPos.next[t] null) {break;} else if (curPos.next[t].isEnd) {dp[i] Math.min(dp[i], dp[j - 1]);}if (dp[i] 0) {break;}curPos curPos.next[t];}}return dp[n];}
}class Trie {public Trie[] next;public boolean isEnd;public Trie() {next new Trie[26];isEnd false;}public void insert(String s) {Trie curPos this;for (int i s.length() - 1; i 0; --i) {int t s.charAt(i) - a;if (curPos.next[t] null) {curPos.next[t] new Trie();}curPos curPos.next[t];}curPos.isEnd true;}
}作者LeetCode-Solution 链接https://leetcode.cn/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
17.14 最小K个数 1.用最大堆
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueueInteger q new PriorityQueue((a,b)-b-a);int[] ans new int[k];if (k 0) return ans;for (int i : arr) {if (q.size() k q.peek() i) continue;if (q.size() k) q.poll();q.add(i);}for (int i k - 1; i 0; i--) ans[i] q.poll();return ans;}
}2.用快速排序的思想因为题目要求是返回无序的数组即可。
17.15 最长单词 先排序按字符串长度从大到小然后按字典序。 全塞进set集合里不停的remove并且判断。
public class Solution {public static String longestWord(String[] words) {Arrays.sort(words, new ComparatorString() {Overridepublic int compare(String o1, String o2) {if(o1.length()o2.length()){return o1.compareTo(o2);}else{return Integer.compare(o2.length(),o1.length());}}});//参数要collection,所以用了Arrays.asList()进行转换SetStringsetnew HashSet(Arrays.asList(words));for(String word:words){set.remove(word);if(find(set,word)) return word;}return ;}public static boolean find(SetStringset,String word){if(word.length() 0)return true;for(int i 0; i word.length(); i){if(set.contains(word.substring(0,i1)) find(set,word.substring(i1)))return true;}return false;}public static void main(String[] args) {Scanner scnew Scanner(System.in);ArrayListString array1new ArrayList();//使用hasNext的重载方法让其停下。while(!sc.hasNext(#)){String s1sc.nextLine();array1.add(s1);}String[] s1array1.toArray(new String[array1.size()]);String anslongestWord(s1);System.out.println(ans);}
}17.16按摩师 直接动态规划可以将数组压成常数。
public class Solution {public int massage(int[] nums) {if(nums.length0) return 0;int nnums.length;int[][] dpnew int[n][2];dp[0][0]0;dp[0][1]nums[0];for(int i1;in;i){dp[i][0]Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1]nums[i]dp[i][0];}return Math.max(dp[n-1][0],dp[n-1][1]);}
}17.17 多次搜索 前缀树Trie; 思路 trie中记录smalls中的字符串末尾记录字符串方便后面遍历。 trie中的search用于搜索字符串将搜索到的字符串存入返回值中。 遍历big长字符串将其与trie匹配。 按smalls顺序输出最终结果
17.18 最短超串 labuladong算法小抄里面滑动窗口C解法的java版。 1.把[left,right]称为一个窗口 2.先右移右指针扩大窗口直到窗口中的数字满足small数组要求 3.满足要求时停止增加right转而增加left缩小窗口直到不满足要求 4.重复2,3步直到right走到big尽头
17.19 消失的两个数 两个数先算出一个数 方法一求和算出ab的和然后在[1,(ab)/2] 中可以找到一个数然后用(ab)减去这个数即可 方法二用位运算算出ta^b,然后用difft (-t)可以找出a和b所相差的二进制最低位不一样的位数则可以根据此将输入数组和[1.n2]分为两组。比如一组这一位都是0则这一组全异或输入数组和[1,n2]中这一位全是0的则可以获得a,然后bt ^ a;
17.20 连续中值 利用一个大顶堆一个小顶堆中位数可以看作是隔开两个数组的分位线这样左端用大顶堆右端用小顶堆最后两个堆奇数个是一个的peek求平均即可。
class MedianFinder {PriorityQueueInteger left, right;boolean isLeft;/** initialize your data structure here. */public MedianFinder() {left new PriorityQueue((x, y) - y - x);right new PriorityQueue();}public void addNum(int num) {//注意这一行不能省略目的是为了维护左边的值永远小于右边的值所以要先扔进左堆再拿出来放进右堆left.offer(num);right.offer(left.poll());if (left.size() right.size())left.offer(right.poll());}public double findMedian() {if (left.size() right.size())return left.peek();return (left.peek() right.peek()) / 2.0;}
}17.21 接雨水 复杂度O(N)
解题思路只有凹的地方能存水存水量遵循短板原则所以用每个位置左右两侧最大值中的较小者减当前位置的值即可得到当前位置储水量。
解题方法先倒叙遍历用数组记录每个位置其右侧最大值max右再正序遍历时刻记录并更新当前位置左侧的最大值max左然后当前位置存水量cMin(max左max右)-当前值如果c0则表示没有水抛弃即可最后每个位置的c累加一起的和即为总储水量。
class Solution {public int trap(int[] height) {int size1height.length;if(size10) return 0;int []maxRightnew int[size1];int []maxLeftnew int[size1];maxLeft[0]height[0];for(int i1;isize1;i){maxLeft[i]Math.max(height[i],maxLeft[i-1]);}maxRight[size1-1]height[size1-1];for(int isize1-2;i0;i--){maxRight[i]Math.max(height[i],maxRight[i1]);}int ans0;for(int i1;isize1-1;i){ansMath.min(maxLeft[i],maxRight[i])-height[i];}return ans;}
}后面的太难了不想写了换书刷了
17.22 单词转换 17.23最大黑方阵 17.24 最大子矩阵 17.25 单词矩阵 17.26 稀疏相似度
