ip地址无效化
题目：给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。
示例 1：
输入：address = "1.1.1.1"
输出："1[.]1[.]1[.]1"
示例 2：
输入：address = "255.100.50.0"
输出："255[.]100[.]50[.]0"
提示：
给出的 address 是一个有效的 IPv4 地址
思路：额，，这道题我又不知道是不是我审题没明白，感觉就是一个replace的事，哪怕不这样split根据. 然后再加上[.]也没问题吧？我还是先去试试看这个题有什么坑吧。
我完全get不到这个题的考点啊？算了算了，还是尽量看看能不能提升下性能。
好了，性能百分百了，直接贴代码:
class Solution {
public String defangIPaddr(String address) {
char[] c = address.toCharArray();
StringBuffer sb = new StringBuffer();
for(char i:c){
if(i=='.'){
sb.append("[.]");
}else{
sb.append(i);
}
}
return sb.toString();
}
}
按序打印
题目：我们提供了一个类：
public class Foo {
public void one() { print("one"); }
public void two() { print("two"); }
public void three() { print("three"); }
}
三个不同的线程将会共用一个 Foo 实例。
线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法
请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。
示例 1:
输入: [1,2,3]
输出: "onetwothree"
解释:
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。
正确的输出是 "onetwothree"。
示例 2:
输入: [1,3,2]
输出: "onetwothree"
解释:
输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。
正确的输出是 "onetwothree"。
注意:
尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。
你看到的输入格式主要是为了确保测试的全面性。
思路：好的吧，leetcode还有多线程的题目，我也是才知道。其实这道题不是很复杂，大概题意就是有三个方法，无论谁先执行要求输出语句必须的first，two，three。也就是说调用的顺序不重要，重要的是三个线程的执行顺序一定的1，2，3.这就要求三个方法在执行的时候要按照顺序执行。其实实现的方法也是多样的，比如先决条件啊，就是设置两个变量，在前一个执行完这个变量值会改变，后面的方法不断去判断这个变量值直到为改变后的值（也就说前面的执行完了）才会执行。但是我感觉如果用这种方法有点过分了，毕竟一个两三三个线程能这样，但是如果N多条都这么一直while判断？剩下的就是一些辅助类了，我这里用的是比较常见的计数器CountDownLatch。这个类初始化必须输入一个初始计数值。有个方法是计数值-1的countDown。还有一个方法是将次线程挂起，直到计数为0才开始执行的await。本题只要用的高这两个方法就行了。
我直接贴代码：我感觉处理的没什么问题啊。可是性能可怜的很，，我再试试别的
class Foo {
private CountDownLatch c2;
private CountDownLatch c3;
public Foo() {
c2 = new CountDownLatch(1);
c3 = new CountDownLatch(1);
}
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
c2.countDown();
}
public void second(Runnable printSecond) throws InterruptedException {
c2.await();
printSecond.run();
c3.countDown();
}
public void third(Runnable printThird) throws InterruptedException {
c3.await();
printThird.run();
}
}
第二种方法暴力法，这种没锁，就用一个volatile保证可见性就ok了，其实这里有个问题，之前我不用volatile提交超时，但是本地测试是ok的，我觉得可能和leetcode设置的超时时间有关。这种办法的执行时间比上个还要快。：
class Foo {
volatile boolean flag1=true;
volatile boolean flag2=true;
public Foo() {
}
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
flag1=false;
}
public void second(Runnable printSecond) throws InterruptedException {
while(flag1);
printSecond.run();
flag2=false;
}
public void third(Runnable printThird) throws InterruptedException {
while(flag2);
printThird.run();
}
}
其实应该还有别的解法，但是其实多线程这块我并不熟，所以就暂时这样吧。下一题了。
数组的相对排序
题目：给你两个数组，arr1 和 arr2，arr2 中的元素各不相同.arr2 中的每个元素都出现在 arr1 中.对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
思路：思路就是一个个元素排序？这个1有2没有的元素可以顺序往1-2的长度替换。暂时只有一个隐约的思路，我去完善看看。
心疼我自己，审题总马虎，辛辛苦苦两个for循环写完了才发现做了一般无用功。我以为没出现在2的1中数要按照本来的顺序排序，结果不对我才看了下，是按照升序排序就行。。简直给自己添加难度！马虎的下场~~哎，我去改改。
第一版本代码出来了，2ms，性能只超过了百分之五十，我先贴出来再寻思优化：
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int l1 = arr1.length;
int n = 0;
for(int i : arr2){
for(int j = 0;j<l1;j++){
if(arr1[j]==i){
int temp = arr1[n];
arr1[n] = arr1[j];
arr1[j] = temp;
n++;
}
}
}
for(int i = n;i<l1;i++){
int min = 1001;
int index = 0;
for(int j = i;j<l1;j++){
if(min>arr1[j]) {
index = j;
min = arr1[j];
}
}
int temp = arr1[i];
arr1[i] = arr1[index];
arr1[index] = temp;
}
return arr1;
}
}
怎么说呢，我看了性能排行第一的代码，可能这道题真的是我有误区了，我一直以为要返回的是arr1呢，所以一直原数组操作。。不过看了人家的代码，用新数组，一个计数，一个用来最后的排序，性能好多了，简单易懂，我直接贴出来瞻仰吧
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] nums = new int[1001];
int[] res = new int[arr1.length];
//遍历arr1,统计每个元素的数量
for (int i : arr1) {
nums[i]++;
}
//遍历arr2,处理arr2中出现的元素
int index = 0;
for (int i : arr2) {
while (nums[i]>0){
res[index] = i;
nums[i]--;
index++;
}
}
//遍历nums,处理剩下arr2中未出现的元素
for (int i = 0; i < 1001; i++) {
while (nums[i]>0){
res[index] = i;
nums[i]--;
index++;
}
}
return res;
}
}
等价多米诺骨牌对数量
题目：给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
示例：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1
提示：
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
思路：这道题怎么说呢，感觉暴力法应该是可以解决。并且这里注意 1，2 等于 2，1后，这个2，1就不能等于1，2了。所以说如果暴力解法要记得除2.不过我总在看这个大于1小于9。感觉这个条件应该能用到啊。我去琢磨琢磨。
好了，到底是有点良心，没用暴力法（主要是我怕暴力法超时），然后用二维数组做的，刚刚我就觉得这个大于1下于9可能有用处，这个时候数组下标代替数值的概念就生成了，但是第一张牌，第二张牌是两个概念，所以用的数组型数组做的。我先贴代码：
class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
int[][] a = new int[9][9];
for(int[] i :dominoes){
a[i[0]-1][i[1]-1]++;
}
int sum = 0;
int sum1 = 0;
for(int i = 0;i<9;i++){
for(int j=0;j<9;j++){
if(a[i][j]>0){
if(i==j){
sum += a[i][j]*(a[i][j]-1)/2;
}else{
if(a[j][i]!=0 && a[i][j]!=0){
//因为这里如果是两边都有数会重复计算，所以除4
int n = a[i][j] + a[j][i];
sum1 += n*(n-1)/2;
}else{
sum += a[i][j]*(a[i][j]-1)/2;
}
}
}
}
}
return sum+sum1/2;
}
}
这里比较麻烦的点就是1，2 和2，1应该是一样的，但是一起算的话，遍历完1.2还会遍历2，1这样就重复了。可是比如1，1这种还不能双方相加，所以分两种情况，是不是不同的牌。不同的牌又分两种情况，一种是一种有，另一种没有。。还有一种是两种都有。
但是代码还算是简单，而且逻辑清楚。
这个代码超越了百分之九十八的人，所以就这样我也看题解了，这个题就过吧。
第N个泰波纳契数列
题目：泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
思路：这个题，这个泰波纳契数列怕不是斐波那契数列的哥哥？有点意思啊。关于这道题几乎就是送分题，具体怎么做参考斐波那契数列就ok了。我先去实现下。
class Solution {
public int tribonacci(int n) {
if(n==0 ||n==1) return n;
if(n==2) return 1;
int f = 0;
int s = 1;
int t = 1;
int i = 2;
while(i<n){
int temp = f;
f = s;
s = t;
t = temp+f+s;
i++;
}
return t;
}
}
这个题其实可以用动态规划来理解，我写的比较麻烦，其实递归可以使代码更简洁。但是要注意递归的时间复杂度是O（n方）而这样从前往后算时间复杂度是O（n）；
（ps：如果理解不了或者不太清楚或者想了解的更多建议看下我另一篇文章
动态规划 ——用数组记录中间过程的递归）
然后这道题也就这样了。
一年中的第几天
题目：给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。
示例 1：
输入：date = "2019-01-09"
输出：9
示例 2：
输入：date = "2019-02-10"
输出：41
示例 3：
输入：date = "2003-03-01"
输出：60
示例 4：
输入：date = "2004-03-01"
输出：61
提示：
date.length == 10
date[4] == date[7] == '-'，其他的 date[i] 都是数字。
date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日。
思路：这道题不知道怎么说，是不是现有的api都不能调用？纯数字计算？就当是吧，我都不知道这道题要怎么写了。是每个月的天数列出来相加？还是换成毫秒除每天的毫秒数?主要是题意是什么意思啊？我真不知道有什么潜含的规则啊
好了，写完了，就是生算的。性能超过百分百，直接贴代码:
class Solution {
public int dayOfYear(String date) {
int[] a = new int[]{0,31,59,90,120,151,181,212,243,273,304,334};
int y = (date.charAt(0)-'0')*1000+(date.charAt(1)-'0')*100+(date.charAt(2)-'0')*10+(date.charAt(3)-'0');
int m = (date.charAt(5)-'0')*10+(date.charAt(6)-'0');
int d = a[m-1] + (date.charAt(8)-'0')*10+(date.charAt(9)-'0');
return y%4==0&& y%100!=0 && m>2 ?d+1:d;
}
}
只能说复习闰年了，我以前以为能被4整除就是闰年了，现在才知道还不能被100整除。。得了得了。这个题过了。
拼写单词
题目：给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。注意：每次拼写时，chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1：
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
示例 2：
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
提示：
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母
思路：类似的题感觉做过。反正思路是创建一个方法，把词汇表化成数组。然后挨个单词判断是否含这个单词，含有返回true，然后结果res会把这个单词的长度加上，否则不加。遍历一遍就ok了，我去实现了。
好了，思路没问题，代码运行效率也行，超过百分之九十五的人，我直接贴代码：
class Solution {
public int countCharacters(String[] words, String chars) {
int[] d = new int[26];
for(char c:chars.toCharArray()){
d[c-'a']++;
}
int res = 0;
for(String s :words){
if(isContains(d,s)) res += s.length();
}
return res;
}
public boolean isContains(int[] d,String s){
int[] dd = new int[26];
for(int i = 0;i<26;i++){
dd[i] = d[i];
}
for(char c : s.toCharArray()){
int i = c-'a';
dd[i]--;
if(dd[i]<0) return false;
}
return true;
}
}
其实这道题比较简单，很多类似的题目，比如大小写字母就要用char操作，然后在有限范围的选值（比如0-9，a-z之类的）用数组下标代替值，数组值代替次数也很好，反正这些小技巧用着用着就习惯了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注~另外祝大家工作顺顺利利，周末愉快！
