知识像个⚪，里面是我们所知的，外面是未知的。知道的越多，我们会发现未知的也越多。今日份自勉语句。
链表组件
题目：给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 G，该列表是上述链表中整型值的一个子集。返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
示例 1：
输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释:
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
提示：
如果 N 是给定链表 head 的长度，1 <= N <= 10000。
链表中每个结点的值所在范围为 [0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集.
思路：这个题的思路我暂时的想法就是把G用set记录。然後从头遍历链表。用一个计数器count来记录。如果当前节点G中存在则count+1。不存在并且count不为0则ans+1,且count归0。。暂时就是这样，我去代码实现试试.
好了,ac了,上第一版本代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] G) {
Set<Integer> set = new HashSet<Integer>();
for(int i : G) set.add(i);
int count = 0;
int ans = 0;
while(head != null) {
if(set.contains(head.val)) {
count++;
}else {
if(count != 0) ans++;
count = 0;
}
head = head.next;
}
if(count != 0) ans++;
return ans;
}
}
这个题怎么说呢,比较简单,简单难度撑死了,不知道怎么混到中等难度里的.然後一开始我忘记了结尾count不为0也要算所以wa了一次.我这个代码性能也还好,O(n)时间复杂度,O(1)空间复杂度.我去看看性能第一的代码,没什么大问题的话就过了:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] G) {
boolean hash[] = new boolean[10000];
for(int i = 0; i < G.length; i++){
hash[G[i]] = true;
}
int res = 0; //记录组件的个数
while(head != null){
if(hash[head.val]){
while(head.next != null && hash[head.val]){
head = head.next;
}
res++;
}
head = head.next;
}
return res;
}
}
这个用的空间换时间?反正用了hash数组,性能变好了能理解.这个题就这样吧.
单词的压缩编码
题目:单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.length
助记字符串 s 以 '#' 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等
给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
示例 1：
输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
示例 2：
输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。
提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 仅由小写字母组成
思路:这个题我觉得首先看单词之间的关系.比如time和me.这种time的结尾包含me的.但是因为单词总共2000个..所以这种包含关系我觉得还是挺不好算的.我打算先暴力法试试.首先第一个单词看有没有endwith第一个单词的,没有的话则先把第一个单词放这.然後一个字符一个字符的减.看后面有没有同等的单词,有的话直接算在这里.思路还算清楚.就是怕超时.我去试试代码了.又想出一些算是优化的措施:比如可以单词按照长度分组.
暴力法居然ac了,哈哈,我直接贴代码:
class Solution {
public int minimumLengthEncoding(String[] words) {
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
Set<String> set3 = new HashSet<String>();
Set<String> set4 = new HashSet<String>();
Set<String> set5 = new HashSet<String>();
Set<String> set6 = new HashSet<String>();
Set<String> set7 = new HashSet<String>();
for(String s : words) {
switch (s.length()) {
case 1: set1.add(s); break;
case 2: set2.add(s); break;
case 3: set3.add(s); break;
case 4: set4.add(s); break;
case 5: set5.add(s); break;
case 6: set6.add(s); break;
default: set7.add(s);
}
}
int ans = 0;
for(String s: set7) {
ans += 8;
set6.remove(s.substring(1, 7));
set5.remove(s.substring(2, 7));
set4.remove(s.substring(3, 7));
set3.remove(s.substring(4, 7));
set2.remove(s.substring(5, 7));
set1.remove(s.substring(6, 7));
}
for(String s: set6) {
ans += 7;
set5.remove(s.substring(1, 6));
set4.remove(s.substring(2, 6));
set3.remove(s.substring(3, 6));
set2.remove(s.substring(4, 6));
set1.remove(s.substring(5, 6));
}
for(String s: set5) {
ans += 6;
set4.remove(s.substring(1, 5));
set3.remove(s.substring(2, 5));
set2.remove(s.substring(3, 5));
set1.remove(s.substring(4, 5));
}
for(String s: set4) {
ans += 5;
set3.remove(s.substring(1, 4));
set2.remove(s.substring(2, 4));
set1.remove(s.substring(3, 4));
}
for(String s: set3) {
ans += 4;
set2.remove(s.substring(1, 3));
set1.remove(s.substring(2, 3));
}
for(String s: set2) {
ans += 3;
set1.remove(s.substring(1, 2));
}
for(String s: set1) {
ans += 2;
}
return ans;
}
}
思路和我上面说的差不多.然後重点是四个字符的单词可能包含3个的,2个的,1个的.但是不可能包含四个的(set自动去重,一样的不占用长度).所以说这个代码写的比较丑,但是思路还是挺清晰的.而且性能并没有我想的那么惨不忍睹.其实我现在觉得没必要分这么多set,应该一个也能搞定.我去试试代码:
class Solution {
public int minimumLengthEncoding(String[] words) {
Set<String> good = new HashSet<String>(Arrays.asList(words));
for (String word: words) {
for (int k = 1; k < word.length(); ++k) {
good.remove(word.substring(k));
}
}
int ans = 0;
for (String word: good) {
ans += word.length() + 1;
}
return ans;
}
}
下面我去看看性能第一的代码吧:
只能说不出所料,其实在做的时候我就想过字典树了,还寻思暴力法超时了就换..但是因为没超时,emmmm...总而言之思路就是每一个单词从后往前.最后一个字母是字典的开始.每次都从后往前遍历,如果找到一样的子分支了则说明当前的不需要额外加长.如果找到包含的子分支并且这个分支不够长,那么把之前的单词算在这个单词的一部分,所以要续上的是当前大于之前的那个长度.最后如果找不到类似的子分支则这个新挂在树上,思路还算好理解,下面是大佬的代码实现:
class Solution {
public int minimumLengthEncoding(String[] words) {
Trie trie = new Trie();
int ans = 0;
for (String word: words) {
ans += trie.insert(word);
}
return ans;
}
}
class TrieNode {
TrieNode[] next;
boolean end;
public TrieNode() {
this.next = new TrieNode[26];
this.end = false;
}
}
class Trie {
TrieNode node;
public Trie() {
this.node = new TrieNode();
}
public int insert(String word) {
char[] chs = word.toCharArray();
int len = chs.length;
TrieNode cur = this.node;
int ans = len + 1;
boolean update = false;
for (int i = len - 1; i >= 0; i--) {
int p = chs[i] - 'a';
if (cur.end) {
cur.end = false;
// common suffix
ans -= len - i;
}
if (cur.next[p] == null) {
cur.next[p] = new TrieNode();
update = true;
}
cur = cur.next[p];
}
if (update) {
cur.end = true;
return ans;
} else {
return 0;
}
}
}
这个题解出来不算难,但是怎么优雅的解出来还是挺不容易的.下一题.
翻转卡片游戏
题目:在桌子上有 N 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。
我们可以先翻转任意张卡片，然后选择其中一张卡片。如果选中的那张卡片背面的数字 X 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0。其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。
示例：
输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
输出：2
解释：假设我们翻转第二张卡片，那么在正面的数变成了 [1,3,4,4,7] ， 背面的数变成了 [1,2,4,1,3]。
接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，所以 2 就是我们想要的数字。
提示：
1 <= fronts.length == backs.length <= 1000
1 <= fronts[i] <= 2000
1 <= backs[i] <= 2000
思路:讲真,这个 题目我自己读了好几遍都没看懂,还是问了群里的人才算是理解题意了.本来我很奇怪为什么是2而不是1.后来发现是因为这个背面的值,要和正面所有的值都不同(包括自己这张的正面).所以1pass了.理解完题意以后说这个题的解题思路:首先正负面一样的元素直接pass.其次因为数字最大2千.我暂时的想法是2000个元素数组.然後正负面一样的直接false.剩下的从前往后一个个数判断.我去试试代码.
第一版本代码:
class Solution {
public int flipgame(int[] fronts, int[] backs) {
int[] d = new int[2001];//2是false。肯定不行了。1是有可能，可以试试。 0是不存在这个元素
for(int i = 0;i<fronts.length;i++) {
if(fronts[i] == backs[i]) {
d[fronts[i]] = 2;
}else {
if(d[fronts[i]] != 2) d[fronts[i]] = 1;
if(d[backs[i]] != 2) d[backs[i]] = 1;
}
}
int min = 2001;
for(int i = 0;i<2001;i++) {
if(d[i] == 0 || d[i] == 2) continue;
return i;
}
return 0;
}
}
说真的,我觉得这个题难度在于阅读理解吧?反正做出来挺容易的,比我想的还简单.然後性能也不错,我再去看看性能第一的代码:
class Solution {
public int flipgame(int[] fronts, int[] backs) {
int[] arr = new int[2000];
int i =0;
while(i < fronts.length){
if(fronts[i] == backs[i]){
arr[fronts[i]] = 1;
}
i++;
}
int j=0;
int min = Integer.MAX_VALUE;
while(j < fronts.length){
int test = fronts[j];
if(arr[test] ==0 && test < min){
min = test;
}
int test2 = backs[j];
if(arr[test2] ==0 && test2 < min){
min = test2;
}
j++;
}
if(min < Integer.MAX_VALUE){
return min;
}else{
return 0;
}
}
}
感觉这个代码的好处是不用多加很多无用的判断.比如我这边数组是2000个.但是如果最大数是4.可是5-2000我还要判断一遍的.然後这个解法就不用这个判断了.除了这个也没啥了.下一题吧.
带因子的二叉树
题目:给出一个含有不重复整数元素的数组，每个整数均大于 1。我们用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。满足条件的二叉树一共有多少个？返回的结果应模除 10 ** 9 + 7。
示例 1:
输入: A = [2, 4]
输出: 3
解释: 我们可以得到这些二叉树: [2], [4], [4, 2, 2]
示例 2:
输入: A = [2, 4, 5, 10]
输出: 7
解释: 我们可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示:
1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.
思路:这个题首先因为每个整数都大于1.因为不存在等于1的情况,所以我们可以从最高层开始找.虽然这个没有标签,但是我觉得应该可以用dp解决.每一个数字本身都可以单独作为一个树.所以开始就是1.然後比如4可以被2乘2来组成,所以4在1的基础上+1.也就是4的组成个数是2.所以2.4这个数组的答案是3.重点是如果三层树:20->4->2这种.4本身就两种可能,一种是单独的4一种是422.5的系数是1.20的结果就是20本身的1+(1乘2)乘2 = 5.之所以(1乘2)乘2是因为左右分支两种可能.如果是2,2或者4,4这种就不用再乘2了.大概思路是这样,我去代码试试.
第一版本代码:
class Solution {
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
Map<Integer, Long> map = new HashMap<Integer, Long>();
for(int i:arr) map.put(i, 1l);//都可以单独成树，所以是1
for(int i = 1;i<arr.length;i++) {
int temp = arr[i];
Set<Integer> set = new HashSet<>();
for(int j = i-1;j>=0;j--) {
int cur = arr[j];
if(set.contains(cur)) continue;
if(temp%cur == 0 && map.containsKey(temp/cur)) {
if(temp/cur == cur) {
map.put(temp, map.get(temp)+map.get(cur)*map.get(cur));
}else {
set.add(temp/cur);
map.put(temp,map.get(temp)+map.get(cur)*map.get(temp/cur)*2);
}
}
}
}
long ans = 0;
for(long i:map.values()) ans += i;
return (int)(ans%1000000007);
}
}
我只能说勉强过了.低空掠过.因为这个数据太大,我只想到了map.各种map,set查找.感觉性能是耗费在这里.但是优化一时半会儿想不出好办法...我直接去看看性能第一的代码:
class Solution {
public final static int MOD = 1000000007;
public int numFactoredBinaryTrees(int[] arr) {
Arrays.sort(arr);
Map<Integer,Integer> map = new HashMap<>() ;
for(int i = 0;i < arr.length;i++){
map.put(arr[i],i) ;
}
long[] dp = new long[arr.length] ;
long ans = 0 ;
for(int i = 0;i < arr.length;i++){
double sq = Math.sqrt(arr[i]) ;
dp[i] = 1 ;
for(int j = 0;j < i;j++){
if(arr[j] > sq){
break;
}
if(arr[i]%arr[j] == 0){
Integer other = map.get(arr[i]/arr[j]) ;
if(other != null){
dp[i] = (dp[i]+dp[j]*dp[other]%MOD)%MOD ;
if(other != j){
dp[i] = (dp[i]+dp[j]*dp[other]%MOD)%MOD ;
}
}
}
}
ans += dp[i] ;
}
return (int) (ans%MOD);
}
}
这个平方根,着实优秀!!都踏马是我知道的知识,看了人家的代码恍然大悟,自己就是没想起来..脑壳痛,反正这个题思路差不多就是这样.然後细节的处理优化在于平方根往上不用看了.因为如果有在这边较小的数字上也处理完了.这个题就这样了,下一题.
适龄的朋友
题目:人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。当满足以下任一条件时，A 不能给 B（A、B不为同一人）发送好友请求：
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
否则，A 可以给 B 发送好友请求。注意如果 A 向 B 发出了请求，不等于 B 也一定会向 A 发出请求。而且，人们不会给自己发送好友请求。 求总共会发出多少份好友请求?
示例 1：
输入：[16,16]
输出：2
解释：二人可以互发好友申请。
示例 2：
输入：[16,17,18]
输出：2
解释：好友请求可产生于 17 -> 16, 18 -> 17.
示例 3：
输入：[20,30,100,110,120]
输出：3
解释：好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.
提示：
1 <= ages.length <= 20000
1 <= ages[i] <= 120
首先说题目:我感觉这个题有点问题啊:感觉条件2和条件三重复了.当然这个不重要.继续说题目.我的想法是每个人只要看小于等于当前区间的.然後我打算年龄最大120.作为一个数组.然後下标代表年龄,值代表人数.直接计算.没啥好说的,我去写代码试试.
第一版本代码:
class Solution {
public int numFriendRequests(int[] ages) {
int[] d = new int[121];
for(int i :ages) d[i]++;
int ans = 0;
for(int i = 0;i<d.length;i++) {
if(d[i] == 0) continue;
if(d[i] > 1 && i>14) ans += d[i]*(d[i]-1);
double temp = 0.5*i+7;
for(int j = i-1;j>=0;j--) {
if(d[j] == 0) continue;
if(j<=temp) break;//太小了不合适
ans += d[i] * d[j];
}
}
return ans;
}
}
这个代码一开始i>14我没写,所以卡了一下,剩下的没啥特别难的.就是判断就行了,和预计的也差不读.这个题就这样了,因为性能已经不错了所以不看性能第一的代码啦.
本篇笔记就记到这里,如果稍微帮到你了记得点个喜欢点个关注,也祝大家工作顺顺利利!
