刷leetCode算法题+解析（二十四）
有效的完全平方数
题目:给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
思路：这个思路怎么说呢，做出来容易。如何做好比较难的。最暴力的办法，从1开始平方，比给定num小就+1再平方，直到相等或大于。相等就是true，大于就是false。
很好，不出意外的这种暴力方法超出时间限制了，我觉得还是用技巧想想：双指针？二分法啥的现实一点。
好了回来了，这里就是刚刚的思路:最小是0，最大46340。如果一个数是平方数则平方根一定在这个范围内。二分法查找。对了，这里有个坑，就是因为left<right。所以当测试案例就是46340的平方时要单独处理。反正执行时间已经最优了，直接贴代码：
class Solution {
public boolean isPerfectSquare(int num) {
// if(num==2147395600) return true;
int left = 0;
//int范围内最大的平方根
int right = 46340;
int mid = left+(right-left)/2;
while(left<right){
if(mid*mid>num){
right = mid;
}
if(mid*mid<num){
left = mid+1;
}
if(mid*mid==num){
return true;
}
mid = left+(right-left)/2;
}
return false;
}
}
下一题
两整数之和
题目：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
思路：这个题有点蒙啊，不使用加减，那么二进制的运算总可以吧？但是二进制运算的过程中，也要一个位一个位的+啊。。感觉看上去很简单的一道题，但是题目都不明白，脑阔痛。
回来了，不出所料的二进制运算。用到的就是两个操作符：
按位与运算符（&）： 0 0 为0 ，1 1 为1 ，0 1 1 0都是0
异或运算符（^）： 0 0 为0 ， 1 1 为0， 0 1 1 0都是1
我们使用异或可以完成+运算，但是不考虑进位。
使用与运算可以完成进位。
两个相结合才能实现整个功能。
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
同样我们可以用三步走的方式计算二进制值相加： 5---101，7---111
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位进行与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步重复上述两步，各位相加 010^1010=1000，进位值为100=(010 & 1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
结束条件：进位为0，即a为最终的求和结果。
（ps：以上讲解出自官方题解，我觉得说的很清楚）
直接贴代码：
class Solution {
public int getSum(int a, int b) {
while(b!=0){
int temp = a^b;
b =(a&b)<<1;
a = temp;
}
return a;
}
}
猜数字大小
题目：我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：
-1 : 我的数字比较小
1 : 我的数字比较大
0 : 恭喜！你猜对了！
示例 :
输入: n = 10, pick = 6
输出: 6
思路：讲真，我也不知道这个题是怎么混进来的。既然出了就做吧。老规矩：1到n所以是二分法。根据大小判断（类似的题感觉做了N道了）甚至这道题和本篇第一道题大同小异，我直接上代码吧
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1;
int res = left+(n-left)/2;
while(left<n){
if(guess(res)==1){
left = res+1;
}else if(guess(res)==-1){
n = res;
}else{
return res;
}
res = left+(n-left)/2;
}
return n;
}
}
赎金信
题目：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
思路：首先这个提示说的从多个杂志搜索字母应该是说明调用频繁？所以性能要好？说的太隐蔽了吧。。然后这道题，是不是又不能用str的内置方法contains？哪怕不用我也觉得这道题似曾相识。先去撸代码了
image.png
好了，已经确定题目就是判断字符串的包含关系了，估计还不让用contains，我去实现了。又回来了，这个题的判断简直。。。丧心病狂！
刚刚不断测试发现我之前理解错了，不是包含关系 aabbcc 其中含有ac。这样的也属于true。aabbcc 不含有 aaac，因为只有两个c，这样的属于false。就是这么简单。第一版本做完了：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
for(int i = 0;i<ransomNote.length();i++){
if(magazine.indexOf(ransomNote.charAt(i))!=-1){
magazine = magazine.replaceFirst(ransomNote.charAt(i)+"","");
}else{
return false;
}
}
return true;
}
}
说实话我现在特别害怕这种要求不明细的题，很有可能就是研究半天做出来然后人家评论：我们做算法题不能用XXX。日狗的心都有了好塞？
还是继续优化：看了下题解中所谓大神的算法：一个套路，只不过我这里用的是string，而人家用的是StringBuffer。其实这块是应该想到、子串长了以后频繁的替换操作，StringBuffer却行性能比较好。
还有一种比较不错的思路：存map或者数组中。杂志的全存进去也不过就是26个元素（只考虑小写26字母）。然后密码一个个取出来，全能取出来就说明包含。有取不出来的说明不包含。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] words = new int[26];
for(int i = 0; i < ransomNote.length(); i++){
char cur = ransomNote.charAt(i);
words[cur-'a']++;
}
int len = ransomNote.length();
for(int i = 0; i<magazine.length()&&len>0; i++){
char cur = magazine.charAt(i);
if(words[cur-'a']!=0) {
len--;
words[cur-'a']--;
}
}
return len==0;
}
}
这种方法其实也不错，这个题办法比较多，我就说到这，继续下一题。
字符串中的第一个唯一字符
题目：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
注意事项：您可以假定该字符串只包含小写字母。
思路：这个题怎么说呢，不考虑性能，实现的方法大把大把的，但是跟上一个题一起做。我仍然比较喜欢map。我觉得这道题的重点是第一个唯一字符，所以在遍历是不是唯一的同时还要知道是第几个。去撸代码试试想法。
很好，我现在已经习惯于第一个版本惨不忍睹的性能了:
class Solution {
public int firstUniqChar(String s) {
String ss = s;
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i = 0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
ss = ss.replace(s.charAt(i)+"","");
}else{
map.put(s.charAt(i),1);
}
}
return ss.length()==0?-1:s.indexOf(ss.charAt(0));
}
}
说真的，这道题很简单，但是就是因为太简单了，所以思路较多，我再试试别的方法：
class Solution {
public int firstUniqChar(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i = 0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
map.put(s.charAt(i),Integer.MAX_VALUE);
}else{
map.put(s.charAt(i),i);
}
}
int res = Integer.MAX_VALUE;
for(Map.Entry<Character, Integer> j:map.entrySet()){
if(res>j.getValue()){
res = j.getValue();
}
}
return res==Integer.MAX_VALUE?-1:res;
}
}
只能说执行时间上进步很大，但是还是不够优化。还有一种是遍历字符串，如果第一次出现的下标和最后一次出现的下标一样，说明就是唯一一次出现：
class Solution {
public int firstUniqChar(String s) {
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (s.indexOf(ch) == s.lastIndexOf(ch)) {
return i;
}
}
return -1;
}
}
然后看了评论说数组和map性能差别很大，所以又用数组做了一遍：
class Solution {
public int firstUniqChar(String s) {
char[] chars = s.toCharArray();
if (chars.length == 0) {
return -1;
}
int[] map = new int[26];
for (char aChar : chars) {
map[aChar-'a'] += 1;
}
for (int i = 0; i < chars.length; i++) {
if (map[chars[i]-'a'] == 1) {
return i;
}
}
return -1;
}
}
好了好了，这个题就到这吧，下一题。
找不同
题目：给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。
示例
输入：
s = "abcd"
t = "abcde"
输出：
e
解释：
'e' 是那个被添加的字母。
思路：这道题，应该还是字符串比较的题，不说性能是个人就会。说起性能优化起来没完。初步思路相同就删除，遇到不同的就是那个添加的字母。就酱
刚刚做的时候灵机一动，想到了一个有意思的解决办法：反正都是小写字母，26位编码，只要判断哪个字母是多的就行了，直接两个字符串每个字符char相加，最后的差值就是多的那个char代表的数字，int转回char就ok了。上代码：
class Solution {
public char findTheDifference(String s, String t) {
int ss = 0;
int tt = 0;
for(int i = 0;i<s.length();i++){
ss += s.charAt(i);
tt += t.charAt(i);
}
tt += t.charAt(t.length()-1);
return (char)(tt-ss);
}
}
因为这个性能很不错，所以就不看题解了，下一题。
判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
思路：就是短的在长的里一个个字符查找，并且自动将之前的都截取掉，这样能保证顺序。
class Solution {
public boolean isSubsequence(String s, String t) {
for(int i = 0;i<s.length();i++){
int x = t.indexOf(s.charAt(i)+"");
if(x==-1){
return false;
}else{
t = t.substring(x+1);
}
}
return true;
}
}
额，实现起来其实很简单，但是性能上，怎么说呢，还是要想想怎么优化，之前我有想过StringBuffer，但是这个subString方法只有String支持，所以我直接看题解吧。
看了一个大神的思路：
大体思路和我差不多，但是细节优化了很多。
比如说我这里用的substring，但是人家根本不用。如下图，直接有个现成 的api，是从某下标开始存不存在某子串。所以我还是输在基础薄弱啊，哎，感觉常用的integer，string啥的用的很熟了，其实不会的也还多。
image.png
贴出超过百分百的代码瞻仰吧：
class Solution {
public boolean isSubsequence(String s, String t) {
int index = -1;
for(char c : s.toCharArray()) {
index = t.indexOf(c, index + 1);
if(index == -1) {
return false;
}
}
return true;
}
}
然后下一题。
二进制手表
题目：二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。如下图：
image.png
例如，上面的二进制手表读取 “3:25”。给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
案例:
输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
注意事项:
输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
思路：讲真这道题出的很奇葩啊，这种需要动脑的手表真的有人带么？其实拨开这么啰嗦的题目，就是二进制的转化问题。首先说小时：这里虽然1248，但是最多同时亮三个灯，因为同时四个灯就15小时了，所以不可能。然后这个分最多五个灯亮。同样6个灯就会超过60分钟了。所以这个整个题目中num最小是0最大是8.我去理理思路直接写代码了。
很喜欢评论的一句话，这道题是单纯的秀表吧？没啥说的，我喜欢暴力穷举法，不过没有现成的java版本，可惜了。就用一个遍历每个时间段的1的个数来表示这个题，直接贴代码，没什么好讲解的
class Solution {
public List<String> readBinaryWatch(int num) {
List<String> res = new LinkedList<>();
//直接遍历 0:00 -> 12:00 每个时间有多少1
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 60; j++) {
if (count1(i) + count1(j) == num)
res.add(i + ":" + (j < 10 ? "0" + j : j));
}
}
return res;
}
/**
* 计算二进制中1的个数
* @param n
* @return
*/
int count1(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}
左叶子之和
题目：
image.png
思路：这道题怎么说呢，还是似曾相识：以前做过类似的寻找所有叶子节点，到叶子节点的线之类的，这个也不过是变种。个人思路：循环或者递归。获取每一个左叶子并相加。我去写代码：
好了，回来了，这道题除了左右需要判断剩下和之前的差不多，无脑递归。直接上代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int sum = 0;
private void getSum(TreeNode root, boolean isLeft){
if(root != null){
if(isLeft && root.left == null && root.right == null){
sum += root.val;
}else{
getSum(root.left, true);
getSum(root.right, false);
}
}
}
public int sumOfLeftLeaves(TreeNode root) {
getSum(root, false);
return sum;
}
}
看一下就能知道思路：这个题是实际测试过的，跟节点不算是左叶子，所以是false。然后题目中左叶子节点才累加，右叶子节点布雷加。然后没到叶子节点就递归。就酱，下一题。
数字转化16进制数
题目：给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。注意:
十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1：
输入:
26
输出:
"1a"
示例 2：
输入:
-1
输出:
"ffffffff"
真的，力扣百分之十的题都没做完，但是感觉遇到差不多的题目好多啊，这个题很简单，就是进制转化的关系（隐隐感觉之前做过类似的）。只要明白进制之间的关系很容易做的，我去写代码
class Solution {
public String toHex(int num) {
if(num==0) return "0";
String hex="0123456789abcdef";
String res="";
while(num!=0&&res.length()<8){
res=hex.charAt(num&0xf)+res;
num>>=4;
}
return esr;
}
}
踩了好多的坑，首先这个负数补码占整个题目难度的百分之九十。
然后0-f一开始我想用switch -case。但是因为真的有点麻烦，所以就这样吧。
这个res是对结果的封装，然后注意这个顺序。不用res += 。因为每次生成的要放在前面。
num右移四位是四位二进制代表一位16进制。
至于判断条件的res.length()<8是最大的一个坑，因为如果是负数的话 没有这个条件就会一直循环下去。
提交了好几次才终于成功。
我到现在也觉得优化点可以是这个字符串charAt换成switch - case，不过我是真的懒得测试了，下一题吧。
最长回文串
题目：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路：我觉得这道题可以换个说法：该字符串有多少成对的字符串。因为回文串的构成就是成对的字母，可以+一个单个的当作中间的那个字符。判断字符串中成对出现的字符就容易得多，我第一反应就是map。我先去写出来。
额，写的时候发现map的value没什么意义，所以我用set代替了。一次通过:
class Solution {
public int longestPalindrome(String s) {
Set<Character> set = new HashSet<Character>();
int res = 1;
for(int i = 0;i<s.length();i++){
if(set.contains(s.charAt(i))){
res += 2;
set.remove(s.charAt(i));
}else{
set.add(s.charAt(i));
}
}
return set.size()>0?res:res-1;
}
}
在题解看到了一种做法：因为只有大小写字母，所以还是可以存数组，然后数组本身的下标就代表了那个字母。而下标数值则代表数组的个数，这样到时候可以根据双数回文串+2，思路就跟上面的类似了。
class Solution {
public int longestPalindrome(String s) {
if(s == null || s.length()==0)
return 0;
int[] map = new int[128];
char[] chs = s.toCharArray();
for(int i=0; i<chs.length; i++){
map[chs[i]]++;
}
int evenCount = 0, oddCount = 0;
for(int count:map){
if(count % 2 == 0)
evenCount += count;
else{
evenCount += count-1;
oddCount = count;
}
}
return oddCount>0 ? evenCount + 1 : evenCount;
}
}
其实不得不承认这种方法性能更好，而我属于惯性思维，没有第一时间想到这，因为之前做的题都是随机字符，其实像这种固定长度（大写字母，小写字母之类的类型很少的）都可以考虑数组。今天一天的题目好几个都是数组性能好了，下次要注意转换思维了。
今天的笔记就记录到这，如果稍微帮到你了记得点个喜欢点个关注呦~也祝大家工作顺顺利利！生活愉快！
