删列造序
题目：给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。删除 操作的定义是：选出一组要删掉的列，删去 A 中对应列中的所有字符，形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。比如，有 A = ["abcdef", "uvwxyz"]，要删掉的列为 {0, 2, 3}，删除后 A 为["bef", "vyz"]， A 的列分别为["b","v"], ["e","y"], ["f","z"]。你需要选出一组要删掉的列 D，对 A 执行删除操作，使 A 中剩余的每一列都是 非降序 排列的，然后请你返回 D.length 的最小可能值。
示例 1：
输入：["cba", "daf", "ghi"]
输出：1
解释：
当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。
示例 2：
输入：["a", "b"]
输出：0
解释：D = {}
示例 3：
输入：["zyx", "wvu", "tsr"]
输出：3
解释：D = {0, 1, 2}
提示：
1 <= A.length <= 100
1 <= A[i].length <= 1000
思路：审了三四遍题才看懂，我可能是没救了。咱们继续说这个题，他说的非降序排列，其实就是升序排列！！！明明白白的说升序不行么？还非要说什么非降序，真的是。。。就是如题，把A中升序排列的列留着，不是升序排列的都删除了。最坏的结果不过就是全都删了得了。做起来应该很简单。我去实现了。
行了，一次通过，性能超过百分之八十，但是我知道我为什么性能不好~~先贴第一版代码：
class Solution {
public int minDeletionSize(String[] A) {
int res = 0;
//外圈是列，里圈是行
for(int i = 0;i<A[0].length();i++){
for(int j = 0; j<A.length-1;j++){
if(A[j].charAt(i)-A[j+1].charAt(i)>0){
res++;
break;
}
}
}
return res;
}
}
有点奇怪啊，我以为性能不好是因为字符串的操作。换成数组性能更低了。然后看了排行第一的代码。就是把我的双层for循环变成了for+方法。性能就上来了。。不懂为什么。我先贴出来共享下吧：
class Solution {
public int minDeletionSize(String[] A) {
int len = A[0].length();
int count = 0 ;
for(int i = 0; i < len; i++){
count += isIncreasing(A, i);
}
return count;
}
private int isIncreasing(String [] A, int idx){
char start = A[0].charAt(idx);
for(int i = 1 ; i < A.length; i++){
if ( start > A[i].charAt(idx))
return 1;
start = A[i].charAt(idx);
}
return 0 ;
}
}
给定数字能组成的最大时间
题目：给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
示例 1：
输入：[1,2,3,4]
输出："23:41"
示例 2：
输入：[5,5,5,5]
输出：""
提示：
A.length == 4
0 <= A[i] <= 9
思路：现在对于每一个能看懂的题目都心怀感恩~~好了，说一下这个题的思路：首先从“时”来讲，最大23.也就是第一位最大2.第二位可以是0-9，但是如果第一位是2的前提下只能0-3。接下来“分”，第一位最大6.在第一位是6的情况下第二位只能是0，第一位小于6时取值范围0-9.然后要分情况判断，我去理理思路直接写代码。
这个题我好像是 做麻烦了？反正性能百分百，直接贴代码：
class Solution {
public String largestTimeFromDigits(int[] A) {
int max = 0;
int max1 = 0;
int min = 10;
int min1 = 10;
for(int i:A){
if(i<=min){
min1 = min;
min = i;
}else if(i<min1){
min1= i;
}
if(i>=max){
max1 = max;
max = i;
}else if(i>max1){
max1 = i;
}
}
A[0] = min;
A[1] = min1;
A[2] = max1;
A[3] = max;
//组成不了时间
if(min>2 || min1>6) return "";
for(int i=3; i>=0; i--){
if(A[i]>2) continue;
for(int j=3; j>=0; j--) {
if (j==i || A[i]==2 && A[j]>3) continue;
for (int k=3; k>=0; k--) {
if (k==i || k==j || A[k]>5) continue;
return "" + A[i] + A[j] + ':' + A[k] + A[6-i-j-k];
}
}
}
return "";
}
}
看了题解，人家都是直接排序的、但是因为我一开始没准备用数组。而且单个数字拆分，所以手动获取最大第二大最小第二小的值的，后来思路转换过来也没推翻重写。反正情况就是这么个情况。虽然代码的可读性间接性上说不如直接一个Arrays.sort（），但是既然性能差不多也就这样了。
我尝试使用了排序，结果性能反而下降了，所以说代码麻烦还是对于性能提升有帮助的。下一题。
验证外星语词典
题目：某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
示例 1：
输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
示例 2：
输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
示例 3：
输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。
思路：这道题的思路很清晰，就是怎么操作的问题。保证前面字符串第一个字符所在下标小于等于后面的，如果是等于则继续往下判断。感觉麻烦点就是差不多的字符串要不断往后比较，我去尝试实现看看
好了，第一版本做完了，性能不是那么好，但是可优化的地方很多，我直接贴代码：
class Solution {
public boolean isAlienSorted(String[] words, String order) {
for(int i = 0;i<words.length-1;i++){
if(!isAlienSort(words[i],words[i+1],order)) return false;
}
return true;
}
public boolean isAlienSort(String a,String b,String order){
int s = a.length()<b.length()?a.length():b.length();
int i = 0;
while(i<s){
if(order.indexOf(a.charAt(i))>order.indexOf(b.charAt(i))) {
return false;
}else if(order.indexOf(a.charAt(i))<order.indexOf(b.charAt(i))){
return true;
}else {
i++;
}
}
//前面ab一样，但是a还有字母b没有了
if(a.length()>b.length()) return false;
return true;
}
}
就是如图，主要是三个判断点：
1，第一个字母顺序对则下一个。
2，第一个字母顺序不对直接false；
3，第一个字母一样则判断第二个字母。。
然后我这个1ms，只超过百分之八十，也是醉了。感觉优化点在于各种细节处理，我一点点去优化。很好，我觉得我这个性能消耗不好的就是哪怕第一个字符就有结果了还要判断长度啥的，所以把这个判断提到前面去了。然后就性能百分百了，虽然代码更墨迹了。贴代码：
class Solution {
public boolean isAlienSorted(String[] words, String order) {
for(int i = 0;i<words.length-1;i++){
if(!isAlienSort(words[i],words[i+1],order)) return false;
}
return true;
}
public boolean isAlienSort(String a,String b,String order){
if(order.indexOf(a.charAt(0))>order.indexOf(b.charAt(0))) {
return false;
}else if(order.indexOf(a.charAt(0))<order.indexOf(b.charAt(0))){
return true;
}
int al = a.length();
int bl = b.length();
int s = al<bl?al:bl;
int i = 1;
while(i<s){
if(order.indexOf(a.charAt(i))>order.indexOf(b.charAt(i))) {
return false;
}else if(order.indexOf(a.charAt(i))<order.indexOf(b.charAt(i))){
return true;
}else {
i++;
}
}
//前面ab一样，但是a还有字母b没有了
if(al != s ) return false;
return true;
}
}
重复N次的元素
题目：在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。返回重复了 N 次的那个元素。
示例 1：
输入：[1,2,3,3]
输出：3
示例 2：
输入：[2,1,2,5,3,2]
输出：2
示例 3：
输入：[5,1,5,2,5,3,5,4]
输出：5
提示：
4 <= A.length <= 10000
0 <= A[i] < 10000
A.length 为偶数
思路：这个题又是似曾相识啊。没有任何进阶提示，最简单无脑粗暴的办法就是map计数。然后value是n的就是答案，还有就是除了这个重复的剩下不会有重复元素，所以只要出现重复元素就是这个值。不过为了这个性能，我决定还是用数组下表代替数值。我直接去写代码了。
好吧，思路没问题，写着也就几行，但是性能八十九。逼死强迫症么？到就是我就放过自己了，太低自己就想着看人家的代码了。结果89？？算了，先贴上第一版本的代码：
class Solution {
public int repeatedNTimes(int[] A) {
int [] a = new int[10000];
a[0] = -1;
for(int i :A){
if(a[i]==i) return i;
a[i] = i;
}
return 0;
}
}
我都快怀疑我看错题了，性能第一的大哥着实nb啊，这么一道题写了俩方法。我贴出来分享下，我个人就不改动了：
class Solution {
private int res = 0;
public int repeatedNTimes(int[] A) {
if(devide(A,0,A.length-1)){
return res;
}
return -1;
}
public boolean devide(int[] arr, int start, int end){
if(start < end){
int mid = (start + end) / 2;
if(devide(arr,start,mid)){
return true;
}else if(devide(arr,mid+1,end)){
return true;
}
return merge(arr,start,mid,end);
}
return false;
}
public boolean merge(int[] arr, int start, int mid, int end){
for(int i = start; i <= mid; i++){
for(int j = mid + 1; j <= end; j++){
if(arr[i] == arr[j]){
res = arr[i];
return true;
}
}
}
return false;
}
}
单值二叉树
题目：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
思路：这道题我目前思路很简单啊，取根节点数值，遍历树，等于根节点返回true，不是返回false。有一个false则停止遍历，不然就遍历整棵树。我去实现了。
嗯，这个题就是这么简单，也没啥特别的技巧，性能百分百，我直接贴上然后下一题了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isUnivalTree(TreeNode root) {
//题目说最少有一个节点，所以这里不判空了
int rv = root.val;
return isUnival(root,rv);
}
public boolean isUnival(TreeNode root,int rv){
if(root==null) return true;
if(root.val != rv) return false;
return isUnival(root.left,rv) && isUnival(root.right,rv);
}
}
强整数
题目：给定两个正整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。返回值小于或等于 bound 的所有强整数组成的列表。你可以按任何顺序返回答案。在你的回答中，每个值最多出现一次。
示例 1：
输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释：
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2
示例 2：
输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]
提示：
1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6
思路：这个要从异或开始说了吧？------神踏马异或！！我怎么看怎么不对，然后忍不住审题半小时看了题解，这个是次方的意思。x的i次方，y的j次方，，，，心累，越简单的问题描述越不说人话。哪怕打不出来次方的样式起码写个汉字好伐???，话题转回来吧，这道题还是很简单的，就是某一个数是不是某两个数的次方和。
好了，这个题其实只要明白题意还是很简单的。我直接贴代码:
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 1;i<bound;i *= x){
for(int j = 1;j<bound;j *=y){
if(i+j<=bound) set.add(i+j);
if(i+j>bound || y==1) break;
}
if(x==1) break;
}
List<Integer> res = new ArrayList<Integer>();
for(int i : set){
res.add(i);
}
return res;
}
}
这里注意，如果x=1或者y=1.然后就会一直做无用的循环判断，所以在循环里判断x或y等不等于1.注意放的位置。比如x 的判断要在走完一圈y以后，剩下的就没什么了。这道题其实不难，就是之前的异或半小时让我心态炸裂。我再去看看大神的代码吧。
排名第一的和我差不多思路，可能处理起来略微优雅？但是神奇的是一样的代码我写出来运行还是只能超过百分之八十七的人。。。。针对我吧？
算了算了，贴上代码这道题过：
class Solution {
public List<Integer> powerfulIntegers(int x, int y, int bound) {
Set<Integer> set = new HashSet<>();
for (int a = 1; a < bound; a *= x) {
for (int b = 1; a + b <= bound; b *= y) {
set.add(a + b);
if (y == 1) break;
}
if (x == 1) break;
}
return new ArrayList<>(set);
}
}
三角形的最大周长
题目：给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。
示例 1：
输入：[2,1,2]
输出：5
示例 2：
输入：[1,2,1]
输出：0
示例 3：
输入：[3,2,3,4]
输出：10
示例 4：
输入：[3,6,2,3]
输出：8
提示：
3 <= A.length <= 10000
1 <= A[i] <= 10^6
思路：这道题我做过类似的，不就是两边之和大于第三边么？最偷懒的办法：排序，从最后往前数，满足两边和大于第三边返回周长，不满足往前进一位判断。重点是这个排序是sort还是手写。。。想了想还是直接sort吧。。我去实现了
emmm...标准的算上return四行代码:
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);
for(int i = A.length-1;i>=2;i--){
if(A[i]<A[i-1]+A[i-2]) return A[i]+A[i-1]+A[i-2];
}
return 0;
}
}
反正是实现了。性能还超过百分之九十五的人，这道题我就直接过了。
好吧，我手贱，又看了眼性能第一的代码。。其实实现的方式不难，就是愿意费事就行，贴下代码吧：
class Solution {
public int largestPerimeter(int[] A) {
int result = 0;
int maxA = max(A);
int maxB = max(A);
int maxC = max(A);
while (maxC != 0) {
if (maxB + maxC > maxA) {
result = maxA + maxB + maxC;
break;
} else {
maxA = maxB;
maxB = maxC;
maxC = max(A);
}
}
return result;
}
public int max(int[] A) {
int max = 0;
int maxIndex = -1;
for (int i = 0; i < A.length; i++) {
if (max < A[i]) {
max = A[i];
maxIndex = i;
}
}
if (maxIndex != -1) A[maxIndex] = -1;
return max;
}
}
另外吐个槽，虽然这么说有点过分，但是感觉这个性能应该和测试案例有关系。如果大量测试案例都是最大的组不成三角形，感觉这种方式肯定更麻烦。过了过了。下一题。
有序数组的平方
题目：给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
思路：这道题怎么说呢？实现属于是个人就能实现，但是怎么实现的优雅简单快捷就各显神通了。最无脑的做法每个数字平方存一个数组，最后sort。然后稍微有点技术含量的办法就是在计算平方的同时就排好序。首先找出第一个非负的下标。然后以此位左指针右指针的基，比较左右绝对值（或平方）然后放一个比较一次。放一个比较一次。我可能表述的不明白，但是我思路很清楚，我去代码实现了。
坚持用了点技巧，虽然墨迹很多，但是不得不说性能很满意啊，超过百分之九十九的人，直接贴代码：
class Solution {
public int[] sortedSquares(int[] A) {
int len = A.length;
int idx = -1;
for(int i = 0;i<len;i++){
if(A[i]>=0) {
idx = i;
break;
}
}
int[] res = new int[len];
if(idx==-1){
int j = 0;
for(int i = len-1;i>=0;i--){
res[j] = A[i]*A[i];
j++;
}
return res;
}
int l = idx-1;
int r = idx;
//偷懒，不想新建了，反正idx值用完了。
idx = 0;
while(l>=0 && r<len){
//负数较大则先放正数平方，否则放负数平方
if(Math.abs(A[l])>A[r]){
res[idx] = A[r]*A[r];
idx++;
r++;
}else if(Math.abs(A[l])<A[r]){
res[idx] = A[l]*A[l];
idx++;
l--;
}else{
res[idx] = A[r]*A[r];
res[idx+1] = A[l]*A[l];
idx += 2;
r++;
l--;
}
}
if(l>-1){
for(int i = l;i>=0;i--){
res[idx] = A[i]*A[i];
idx++;
}
} else{
for(int i = r; i<len;i++){
res[idx] = A[i]*A[i];
idx++;
}
}
return res;
}
}
其实我觉得还可以优化优化，但是确实是懒惰主导了我，有点写的没耐心了。这道题就这样吧，毕竟已经及格了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！
