Fizz Buzz
题目：写一个程序，输出从 1 到 n 数字的字符串表示。1. 如果 n 是3的倍数，输出“Fizz”；2. 如果 n 是5的倍数，输出“Buzz”；3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
示例：
n = 15,
返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
思路:这个题怎么说呢。应该是很简单的啊，没坑的话一个循环搞定，是3,5的倍数输出FizzBuzz，是3倍数输出Fizz是5倍数输出Buzz，不是输出字符串本身。我去做做看坑在哪里
class Solution {
public List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<String>();
for(int i=1;i<=n;i++){
if(i%3==0 && i%5==0){
res.add("FizzBuzz");
}else if(i%3==0){
res.add("Fizz");
}else if(i%5==0){
res.add("Buzz");
}else{
res.add(i+"");
}
}
return res;
}
}
额，有点尴尬，一次做完，都没发现有坑，我可能是让LeetCode坑的有了被害妄想症了。因为这个性能也不错，所以直接这样了，下一题。
第三大的数
题目：给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。
思路：这道题第一反应排序，估计直接sort之类的有点问题，我先理理思路：大体上分两种情况，有第三大的返回第三大的。没第三大的返回最大的。其实又有那个想法了：不考虑性能的话怎么都能做出来！不管是list，map，还是数组都可以做到。就是里面三个不同元素，遍历数组每一个比较大小，小于已有的三个则继续往下，大于已有的三个依次比较，保证存储的元素是最大的三个就行了。我觉得这个思路可以实现，就是不知道性能怎么样，我去试试。
事实证明刚刚的想法是可行的，就是性能确实不怎么地，先上代码：
class Solution {
public int thirdMax(int[] nums) {
Map<Integer,Long> map = new HashMap<Integer,Long>();
map.put(1,-3000000000l);
map.put(2,-3000000000l);
map.put(3,-3000000000l);
for(int i = 0 ;i<nums.length;i++){
if(nums[i]>map.get(3)){
if(map.get(1)<nums[i]){
map.put(3,map.get(2));
map.put(2,map.get(1));
map.put(1,(long)nums[i]);
}else if(map.get(2)<nums[i] && nums[i]!=map.get(1)){
map.put(3,map.get(2));
map.put(2,(long)nums[i]);
}else if(map.get(3)<nums[i] && nums[i]!=map.get(2) && nums[i]!=map.get(1)){
map.put(3,(long)nums[i]);
}
}
}
return map.get(3)==-3000000000l?map.get(1).intValue():(int)map.get(3).intValue();
}
}
啰里啰嗦的，事实证明我还年轻，所以没想到测试案例第三的值会是int的最小值，卡了好久。
然后我这用的map，但是我估计数组，list 都可以，具体哪个性能好也不知道，但是我觉得应该是数组比较好，我去试试：
class Solution {
public int thirdMax(int[] nums) {
long[] res = new long[3];
res[0] = -3000000000l;
res[1] = -3000000000l;
res[2] = -3000000000l;
for(int i = 0 ;i<nums.length;i++){
if(nums[i]>res[2]){
if(res[0]<nums[i]){
res[2] = res[1];
res[1] = res[0];
res[0] = nums[i];
}else if(res[1]<nums[i] && nums[i]!=res[0]){
res[2] = res[1];
res[1] = nums[i];
}else if(res[2]<nums[i] && nums[i]!=res[1] && nums[i]!=res[0]){
res[2] = nums[i];
}
}
}
return res[2]==-3000000000l?(int)res[0]:(int)res[2];
}
}
嗯，换了数组确实性能一下子上来了，超过百分之九十九的用户，所以这道题就这样，下一题吧。
字符串相加
题目:给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
思路：很好，又没看懂题目，这个不能使用BigInteger可以理解，还不能转化整数是什么意思？for循环每一个字符相加不行么？有点费解，我去用测试案例试试什么意思
很好，明白题意了，就是从最后一位开始两个字符串一个个字符相加。而且题目简直有毛病。长度5100以内，还用特意声明不转化成int？也得能转化才行啊。其实这样看思路清晰多了，我去撸代码了。
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int carry = 0;
int i = num1.length()-1;
int j = num2.length()-1;
while(i >= 0 || j >= 0 || carry != 0){
if(i>=0) carry += num1.charAt(i--)-'0';
if(j>=0) carry += num2.charAt(j--)-'0';
sb.append(carry%10);
carry /= 10;
}
return sb.reverse().toString();
}
}
在多次循环并且越写越墨迹以后，我选择了直接嫖大神代码：对，就是如图所示，简单易懂，我就很纳闷同样的大脑为啥思路差这么多呢（手动滑稽）。
反正如图，做的很好，如果进位了，carry/10还会是1，这样自动进位了，不然不足10会是0，相当于重置计算下一位数字。
而且大神说了，适用于十进制，二进制，任何进制（只不过参数要改，但是思路不变。前提是不考虑负数）。
反正方法就是这么个方法，代码也就是这么几行代码。我是存在u盘里了，觉得真的挺经典的，除了膜拜没啥说的。继续往下吧，现在一篇目标5+题。
字符串中的单词数
题目：统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: "Hello, my name is John"
输出: 5
思路:这个题说真的，类似的做了好多好多遍了，好像是不能直接用split？我忘了有啥潜含的要求了，反正我现在贼烦这种题目上看不出来的限制。我就按照我自己的想法做一遍，通过了的话剩下题解见吧。对了这个题好像也可以是所有莫名其妙的符号转换成空格。比如什么逗号句号问号啥的，我先去做做再说
很好，这个题很清新脱俗不拘一格别出心裁反正完全让人意想不到。大概讲一下几个坑：关于这个空格，不是空字符串，是space这个空格，关于这两个是有区别的：
然后继续往下，这个, , ,这算是三个单词，出题人脑回路6666.然后一开始split不行，换了个思路，我直接上代码:
class Solution {
public int countSegments(String s) {
char [] ch = s.toCharArray();
int res = 0;
int temp = 0;
for(int i=0;i<s.length();i++ ){
if(!Character.isSpace(ch[i])){
temp++;
}else{
if(temp!=0) {
res += 1;
}
temp=0;
}
}
return temp==0?res:res+1;
}
}
说实话判断逻辑挺无脑的，就是有不是空格的就计数，遇到空格说明总数+1.如果遇到空格发现计数为0说明多个空格在一起了，不算是单词。一直遍历到最后，判断最后计数上是不是0，是0说明空格结尾，之前有多少单词返回多少，不是0说明最后的单词还没算，所以要+1.
整体逻辑就这样，因为直接性能百分百，所以直接下一题。
路径总和三
题目：给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
思路：二叉树的题，主思路递归/迭代。我习惯性递归。首先判断例子可以看出几点1.树节点不唯一。2.树节点没有规律，什么左小右大都没有，正负也是。 3.本来我预计的是某条线到了给定数字就清0从来，但是现在看不行，很有可能到了给定数字然后往下加个正数减个负数啥的又变成了这个数字。这就有点问题了，暂时没有啥思路，我去理理
好吧，没理出来，虽然知道是递归但是具体怎么做一点思路没有，所以直接看了官方的题解,不得不说看了题解豁然开朗,然后我先把题解大概说一下：
- 路径的开头可以不是根节点，结束也可以不是叶子节点，是不是有点复杂？
如果问题是这样：找出以根节点为开始，任意节点可作为结束，且路径上的节点和为 sum 的路径的个数； - 是不是前序遍历一遍二叉树就可以得到所有这样的路径？是的；
如果这个问题解决了，那么原问题可以分解成多个这个问题； - 是不是和数线段是同一个问题，只不过线段变成了二叉树；
在解决了以根节点开始的所有路径后，就要找以根节点的左孩子和右孩子开始的所有路径，三个节点构成了一个递归结构； - 递归真的好简单又好难；
然后看了这个题的解释豁然开朗，我去试着写写代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root==null) return 0;
return pathNode(root,sum)+pathSum(root.right,sum)+pathSum(root.left,sum);
}
public int pathNode(TreeNode root,int sum){
if(root==null) return 0;
int res = 0;
if(root.val==sum) res += 1;
return res+pathNode(root.right,sum-root.val)+pathNode(root.left,sum-root.val);
}
如图所示，两个递归。要调试疯了，反正没技术，没技巧，我就一点点打印调试。等做出来了才发现其实也没那么简单。就是每一个节点的符合条件的路径数，然后再递归把所有的加在一起。但是我这么写性能不咋地，我去看看性能好的写法：
算了看了性能好的写法有点看不懂，而且刚刚不断调试那个双递归也头晕，换下一道题换个心情吧。能自己做出来我就挺满意了，不追求完美了。
排列硬币
题目：你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
思路：很喜欢这种一个简单一个难的题目啊，这道题又是送分题，不就是判断一个数字拆成1，2，3，。。最多能拆到几么。我去写代码了
class Solution {
public int arrangeCoins(int n) {
int i = 1;
while(n>=i){
n=n-i;
i++;
}
return i-1;
}
}
一次搞定，虽然性能不行。不过在写的时候就有了隐隐约约的貌似有什么规律的感觉。第一行+倒数第二行是倒数第一行（这里忽略了不满的最后一行）第二行加倒数第三行也是最后一行，第三行加倒数第四行。。以此类推，肯定是有规律的，我去“看”规律了！
算了，手头没笔和纸，还是在这里打字吧：第n行，前面有n-1除2的n，如果是偶数还会有个中间的二分之n的数，再加上本身的 第n行，嗯嗯，有道理，我还是直接看题解吧。哈哈，觉得没啥必要非要手算，知道有规律就行了我觉得。
诺，如图，我还是喜欢拿现成的。
今天的笔记就做到这里，如果稍微帮到你了记得点个喜欢点个关注呦!也祝大家工作顺顺利利！顺便说个题外话，力扣1298道题，到了今天我终于把尾数做完了，开心~~虽然我知道以后中等难度和困难难度肯定不会做的这么快了，但还是觉得有奔头！嘿嘿
