至少是其他数字两倍的最大数
题目：在一个给定的数组nums中，总是存在一个最大元素 。查找数组中的最大元素是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的索引，否则返回-1。
示例 1:
输入: nums = [3, 6, 1, 0]
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
示例 2:
输入: nums = [1, 2, 3, 4]
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.
提示:
nums 的长度范围在[1, 50].
每个 nums[i] 的整数范围在 [0, 100].
思路：这道题怕不是太简单吧？不是只要知道最大值和第二大值之间是否差两倍就行了么？至于性能问题我自己遍历一遍还不行么？不用额外空间，时间复杂度O（n）,空间复杂度0.我去写写试试。
这道题其实很简单的，我直接贴代码吧：
class Solution {
public int dominantIndex(int[] nums) {
int max = 0;
int index = -1;
int max1 = 0;//第二大值
for(int i=0;i<nums.length;i++ ){
if(nums[i]>=max){
max1 = max;
max = nums[i];
index = i;
}else if(nums[i]>max1){
max1 = nums[i];
}
}
return max>=max1*2?index:-1;
}
}
因为性能也超过百分之九十九了，所以直接下一题。
最短完整词
题目：如果单词列表（words）中的一个单词包含牌照（licensePlate）中所有的字母，那么我们称之为完整词。在所有完整词中，最短的单词我们称之为最短完整词。单词在匹配牌照中的字母时不区分大小写，比如牌照中的 "P" 依然可以匹配单词中的 "p" 字母。我们保证一定存在一个最短完整词。当有多个单词都符合最短完整词的匹配条件时取单词列表中最靠前的一个。牌照中可能包含多个相同的字符，比如说：对于牌照 "PP"，单词 "pair" 无法匹配，但是 "supper" 可以匹配。
示例 1：
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
说明：最短完整词应该包括 "s"、"p"、"s" 以及 "t"。对于 "step" 它只包含一个 "s" 所以它不符合条件。同时在匹配过程中我们忽略牌照中的大小写。
示例 2：
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
说明：存在 3 个包含字母 "s" 且有着最短长度的完整词，但我们返回最先出现的完整词。
注意:
牌照（licensePlate）的长度在区域[1, 7]中。
牌照（licensePlate）将会包含数字、空格、或者字母（大写和小写）。
单词列表（words）长度在区间 [10, 1000] 中。
每一个单词 words[i] 都是小写，并且长度在区间 [1, 15] 中。
思路：思路就是暴力解法。获取牌照中的小写字母。然后去挨个和字符串比较（前提是字符串长度大于牌照中的）。然后获取字符串中最短的那个。
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
char[] c = licensePlate.toCharArray();
char[] word = new char[c.length];
int i = 0;
for(char j : c){
//大写字母
if(j>=65 && j<=90){
word[i] = (char)(j+32);
i++;
}else if(j>=97 && j<=122){
word[i] = j;
i++;
}
}
String res = "";
for(String str : words){
if(str.length()>=i){
String ss = str;
for(int k = 0;k<i;k++){
if(ss.indexOf(word[k])==-1) {
break;
}
if(k==i-1){
if(res == ""){
res = str;
}else{
res = res.length()>str.length()?str:res;
}
}
ss = ss.replaceFirst(word[k]+"","");
}
}
}
return res;
}
}
不得不说，执行速度着实可怜，但是内存消耗超过百分百也是第一次。这道题麻烦倒是不麻烦，但是真的处理起来很墨迹，我直接去看性能第一的代码吧。
感觉差不多思路，也没省事多少。反而处理起来更麻烦了。大概思路是把牌照作为一个26个元素的数组，每有一个小写字母则那个字母对应的位置的元素+1、最后得出来的数组元素就是牌照上需要的字母数。
然后把每一个单词拆成一个26元素的int数组，同样方法判断得出一个数组。
最终如果单词的数组中每一个元素都大于牌照的说明这个单词是包含了牌照上所有的字母的。在所有符合条件的单词中选出一个最短的就好了，贴代码：
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] license = new int[26];
for (char c : licensePlate.toCharArray()) {
if (c >= 'a' && c <= 'z') {
license[c - 'a']++;
} else if (c >= 'A' && c <= 'Z') {
license[c - 'A']++;
}
}
String res = null;
for (String word : words) {
if (isContains(license, word)) {
if (res == null || word.length() < res.length()) {
res = word;
}
}
}
return res;
}
private boolean isContains(int[] license, String word) {
int[] ans = new int[26];
for (char c : word.toCharArray()) {
if (c >= 'a' && c <= 'z') {
ans[c - 'a']++;
} else if (c >= 'A' && c <= 'Z') {
ans[c - 'A']++;
}
}
for (int i = 0; i < 26; i++) {
if (ans[i] < license[i]) {
return false;
}
}
return true;
}
}
这道题其实难是不难，就是很墨迹，这道题就这样吧，下题。
二进制表示中质数个计算置位
题目:给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
示例 1:
输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
示例 2:
输入: L = 10, R = 15
输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
注意:
L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000。
思路：这道题除了一个数一个数的判断，我还真没啥好想法。就先暴力法试试吧。大概思路写一个方法判断一个数二进制1个个数是不是质数（因为二进制int最大32位，所以只要列出32以内的质数就行了。没必要用代码逻辑判断。），是则add进结果集。然后遍历l到r。我去实现了。
好了，思路没问题，就是性能不满意，先贴上代码：
class Solution {
private int sum;
public int countPrimeSetBits(int L, int R) {
//2、3、5、7、11、13、17、19、23、29、31
for(int i =L;i<=R;i++){
isPrimeSetBits(i);
}
return sum;
}
public void isPrimeSetBits(int n){
int count = 0;
while(n>0){
if(n%2==1) count++;
n = n/2;
}
if(count==2 || count==3 || count==5 || count==7 || count==11 || count==13
|| count==17 || count==19) sum++;
}
}
这道题其实我觉得还是很简单的，我也布吉岛为啥性能这么差啊。我去试着优化优化。直接看了排名第一的代码。
我这里是多个判断是不是质数、但是其实可以用一个数组就表示了。
而且10^6最多19位。所以只需要判断20以内的质数就行。另外直接有个方法判断一个数二进制中有多少个1 的、直接贴代码：
class Solution {
public int countPrimeSetBits(int L, int R) {
int[]primes=new int[]{0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0};
int ans=0;
for(int i=L;i<=R;i++){
int tmp=Integer.bitCount(i);
ans+=primes[tmp];
}
return ans;
}
}
托普利茨矩阵
题目：如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
示例 1:
输入:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是True。
示例 2:
输入:
matrix = [
[1,2],
[2,2]
]
输出: False
解释:
对角线"[1, 2]"上的元素不同。
说明:
matrix 是一个包含整数的二维数组。
matrix 的行数和列数均在 [1, 20]范围内。
matrix[i][j] 包含的整数在 [0, 99]范围内。
进阶:
如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？
思路：讲真，如果不考虑进阶要求这道题我觉得还是很好做的。至于进阶要求，先放放吧。抛出去进阶要求剩下的其实就是要斜着比较而已。二维数组。在范围内i+1 j+1.简单来讲就这样，具体的实现我去写了。
我都没想到！一次就过了，而且性能贼好。
其实做出来是应该的，但是直接超过百分百的执行速度，内存消耗也超过百分之九十九就是意外惊喜了，我还以为我处理的方式比较啰嗦呢！
说了这么多直接上代码：
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
//第一个元素 0 0 然后 1 0 /2 0 /3 0 ...到 matrix.lenght--1 0
//还有 0 1 /0 2 /0 3 .... 到 0 matrix[0].lenght-1
int i = 0;
int j = 1;
while(i<matrix.length){
int ii =i;
int jj =0;
int x = matrix[i][0];
while(ii<matrix.length &&jj<matrix[0].length){
if(matrix[ii][jj]!=x) return false;
ii++;
jj++;
}
i++;
}
while(j<matrix[0].length){
int ii =0;
int jj =j;
int x = matrix[0][j];
while(ii<matrix.length &&jj<matrix[0].length){
if(matrix[ii][jj]!=x) return false;
ii++;
jj++;
}
j++;
}
return true;
}
}
其实这个我是用图的形式来理解的，画圈圈的是标准值。判断这一排的值是不是都和标准值一样，如果不是说明不是托普利茨矩阵，返回false，如果是则继续往下比较，每一排都比较完了都没false说明是，返回true。
image.png
因为这个涉及到竖着每一排第一个都是标准点，横着每一个元素都是标准点、所以是两个while循环。然后这道题就这样了。顺便显摆一下这个题性能好：
image.png
有点受打击，这个题是个人都能百分百，而且人家的代码更短小优雅，，，其实思路是差不多的思路，只不过人家写的更加优雅而已，其实本来我也试图写双循环的，但是后来静不下心来去想怎么写，所以直接拆开了，附上人家的简洁代码
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
for (int r = 0; r < matrix.length; ++r)
for (int c = 0; c < matrix[0].length; ++c)
if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
return false;
return true;
}
}
宝石与石头
题目： 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
注意:
S 和 J 最多含有50个字母。
J 中的字符不重复。
思路：这道题解法很多，主要是题目很简单。暴力法就可以，但是我觉得如果考虑性能的话，我是想玩个花板子，用数组下标代表元素。就为了性能能不错。跟上面的质数那个异曲同工吧。我先去写出来再说。
只能说没预计错，这个方法可行并且性能很不错，直接贴代码：
class Solution {
public int numJewelsInStones(String J, String S) {
int[] ar = new int[123];
for(char i: J.toCharArray()){
ar[i] = 1;
}
int res = 0;
for(char i:S.toCharArray()){
if(ar[i]==1) res++;
}
return res;
}
}
然后这道题就这样了。下一题。
二叉搜索树节点最小距离
题目：给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
题目截图
思路：这道题我又觉得好像是做过啊！眼熟的很，我去直接撸代码了。
回来了，这道题确实做过，不过当时是用的无脑的遍历节点，排序，然后找到的最小值。既然都二遍做题了，怎么也要做到更好啊，所以这里用了中序遍历。
其实也正好借着这个机会好好复习了前序遍历，中序遍历和后序遍历！因为我也没有系统的学过这些，都是做题遇到了然后才去理解，使用或者直接摸着测试熟悉。今天好好的看了几者的区别。
前序：如其名，先当前节点，然后左节点，右节点。
中序：如其名，先左节点，当前节点，右节点。
后序：如其名，先左节点，然后右节点，最后当前节点。
用三张图表示
前序遍历
中序遍历
后序遍历
然后这些基础知识就复习到这里，接下来是这个题的解法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int min;
//前一个节点
private Integer pre;
public int minDiffInBST(TreeNode root) {
min = 101;
minDiff(root);
return min;
}
public void minDiff(TreeNode root){
if(root==null || min==1) return;
minDiff(root.left);
if(pre!=null) {
min = Math.min(min,root.val-pre);
}
pre = root.val;
minDiff(root.right);
}
}
然后这道题用中序就是最优解，性能超过百分百的那种。所以就到这。最后一题。
字母大小写全排列
题目：给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]
注意：
S 的长度不超过12。
S 仅由数字和字母组成。
思路：讲真，如果这道题是输出可能的个数我觉得好多了！！！这个规律我见过。可能大写可能小写，不就是2的n次可能么。这个n是字母的个数。一个两个三四个还好说。。。这，这么多目前想法绝对是循环递归啥的，总不能一个个情况去写吧？我照着这个思路去写代码了！
这个题循环暂时没想好怎么处理！因为是个乘方次的解法。我目前知道的唯一解法就是递归。正好昨天看动态规划的视频的时候说这种有重复子问题的题目适合用动态规划解决！！
然而我并没有找到动态规划的解法，所以只能回复到递归（说来说去都是知识储量不够！）。
原谅我直接看了题解！然后在leetcode并没有提交，今天先把解法看仔细明白，明天再自己凭记忆写代码实现。
这里有个知识点很新颖：
大小写字母相差32,又因为异或重要特性:不进位加法,所以大写字母和(1<<5)异或变成变成小写字母,小写字母和(1<<5)异或变成大写字母。
对的，这个知识点真的很重要，咱们继续往下说这道题。其实这个代码我是贴在编译器里，然后debug模式一遍一遍跑出来的，这就是一个笛卡尔积的模式：
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> ans = new ArrayList<String>();
dg(S.toCharArray(),0,ans);
return ans;
}
public void dg(char[] s,int i,List<String> ans){
if(i==s.length){
ans.add(String.valueOf(s));
return;
}
dg(s,i+1,ans);
if(s[i]<'0'||s[i]>'9'){
s[i]^=(1<<5);
dg(s,i+1,ans);
}
}
}
每一个单词对应着大写小写全部走一遍。剩下的明天续上。今天就到这。因为笛卡尔积这块真的是一脸懵逼，我再去努力理解理解，自己理清思路了再补上。
网友评论