每日刷题记录，希望坚持。

导航

2019.11.2删除链表中的节点二叉树的最大深度反转字符串将有序数组转换为二叉搜索树 2019.11.3Excel表列序号反转链表杨辉三角只出现一次的数字 2019.11.4Fizz Buzz位数为1的个数 2019.11.5求众数合并两个有序链表移动零 2019.11.6有效的字母异位词买卖股票的最佳时机Ⅱ 2019.11.7快乐树 2019.11.8报数 2019.11.11缺失数字 2019.11.12买卖股票的最佳时机存在重复元素 2019.11.13两数之和 2019.11.20最大子序和

2019.11.2

删除链表中的节点

题目：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/ 【A-B-C-D】 思考：如果要删除节点B，一般是让节点A的next指向C。 因为此题参数只给了要删除的节点B，我们无法访问A，因此我们要把B换成C【即：A-C-C-D】，然后是C（原B）的next指向D【即：A-C-D】

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } }

二叉树的最大深度

题目：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/

思考：一般关于二叉树的遍历分为递归与非递归，求二叉树的最大深度要遍历二叉树，最后比较得出结果。

递归：DFS

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { if(root == null){ return 0; } else{ int left = maxDepth(root.left);//求左子树最大深度 int right = maxDepth(root.right);//求右子树最大深度 return java.lang.Math.max(left,right)+1;//比较并加上此时所在节点 } } }

非递归(1：利用栈将递归改为迭代，使用 DFS 策略访问每个结点，同时在每次访问时更新最大深度. (2:利用队列，使用BFS层序遍历每个节点

class Solution { public int maxDepth(TreeNode root) { if(root == null){ return 0; } Stack<TreeNode> stack = new Stack<>(); Stack<Integer> value = new Stack<>(); stack.push(root); value.push(1); int depth = 0; while(!stack.isEmpty()){ TreeNode node = stack.pop(); int tmp = value.pop(); depth = Math.max(depth,tmp); if(node.left != null){ stack.push(node.left); value.push(tmp+1); } if(node.right != null){ stack.push(node.right); value.push(tmp+1); } } return depth; } } class Solution { public int maxDepth(TreeNode root) { if(root == null){ return 0; } int depth = 0; Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while(!q.isEmpty()){ depth++; int size = q.size(); for(int i=0;i<size;i++){ TreeNode tmp = q.poll(); if(tmp.left != null){ q.offer(tmp.left); } if(tmp.right != null){ q.offer(tmp.right); } } } return depth; } }

反转字符串

题目：https://leetcode-cn.com/problems/reverse-string/comments/ 思考：除了毫无难度的双指针移动，学到了异或交换的用法。

//普通版本 public void reverseString(char[] s) { int len = s.length; for(int i = 0; i < len / 2; i++) { char temp = s[i]; s[i] = s[len - 1 -i]; s[len - 1 -i] = temp; } } 异或： public void reverseString(char[] s) { int n = s.length; for (int i = 0; i < n / 2; ++i) { int j = n - 1 - i; s[i] ^= s[j]; s[j] ^= s[i];//s[j]=原来的s[i] s[i] ^= s[j];//s[i]=原来的s[j] } }

将有序数组转换为二叉搜索树

题目：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/ 思考：

二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。【也方便查找】

利用这个性质中序遍历二叉搜索树刚好是一个升序数组。

class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sortedBST(nums,0,nums.length-1); } public TreeNode sortedBST(int[] nums,int s,int e){ if(s > e){ return null; } int mid = (int)(s+e)/2; TreeNode node = new TreeNode(nums[mid]); node.left = sortedBST(nums,s,mid-1); node.right = sortedBST(nums,mid+1,e); return node; } }

2019.11.3

Excel表列序号

题目：https://leetcode-cn.com/problems/excel-sheet-column-number/ 思考：仔细观察会发现26一个轮回，可以列出表达式。

public int titleToNumber(String s) { char[] string = s.toCharArray(); int res = 0; for(int i=0;i<string.length;i++){ res = res * 26 + (string[i] - 'A' + 1); } return res; }

反转链表

题目：https://leetcode-cn.com/problems/reverse-linked-list/ 思考：既可以递归，也可以迭代

递归： class Solution { public ListNode reverseList(ListNode head) { return reverse(null,head); } public ListNode reverse(ListNode pre,ListNode now){ if(now == null) return pre; ListNode next = now.next; now.next = pre; return reverse(now,next); } } 迭代： class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur!=null){ ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }

杨辉三角

题目：https://leetcode-cn.com/problems/pascals-triangle/ 思考：…怎么说，利用上一行的结果得出这一行的答案，然后记得特判一下。

class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> list = new ArrayList<>(); int[][] arr = new int[numRows][numRows]; for(int i=0;i<numRows;i++){ List<Integer> subList = new ArrayList<>(); for(int j=0;j<=i;j++){ if(j==0||j==i){ arr[i][j] = 1; } else{ arr[i][j] = arr[i-1][j-1]+arr[i-1][j]; } subList.add(arr[i][j]); } list.add(subList); } return list; } }

只出现一次的数字

题目：https://leetcode-cn.com/problems/single-number/ 思考：

1.交换律 a ^ b ^ c <=> a ^ c ^ b 2.任何数与0异或值为那个数本身 0 ^ n => n 3.相同的数异或值为0: n ^ n => 0

class Solution { public int singleNumber(int[] nums) { int res = 0; for(int i=0;i<nums.length;i++){ res = res ^ nums[i]; } return res; } }

2019.11.4

Fizz Buzz

题目：https://leetcode-cn.com/problems/fizz-buzz/ 思考：好像没什么可说的，将数字转换为字符串的方式:String.valueOf(a); Integer.toString(a);

class Solution { public List<String> fizzBuzz(int n) { List<String> list = new ArrayList<>(); for(int i=1;i<=n;i++){ if(i%3==0&&i%5==0) { list.add("FizzBuzz"); } else if(i%3==0){ list.add("Fizz"); } else if(i%5==0){ list.add("Buzz"); } else{ list.add(String.valueOf(i)); } } return list; } }

位数为1的个数

题目：https://leetcode-cn.com/problems/number-of-1-bits/ 思考：

使用 位掩码 来检查数字的第 i^{th}位。一开始，掩码m=1 因为 1 的二进制表示是 0000 0000 0000 0000 0000 0000 0000 0001 显然，任何数字跟掩码 1进行逻辑与运算，都可以让我们获得这个数字的最低位。检查下一位时，我们将掩码左移一位。 0000 0000 0000 0000 0000 0000 0000 0010 并重复此过程。

public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int res = 0; int mask = 1; for(int i=0;i<32;i++){ if((n&mask) != 0){ res++; } mask<<=1; } return res; } }

2019.11.5

求众数

题目：https://leetcode-cn.com/problems/majority-element/ 思考：求数组中出现次数大于 ⌊ n/2 ⌋ 的元素。除了 ①用憨憨的二重循环求找出那个数 ②利用排序Arrays.sort(nums);，然后求nums[nums.length / 2]外 ③还可以利用投票法：

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个

class Solution { public int majorityElement(int[] nums) { int count = 0; int ans = 0; for(int i=0;i<nums.length;i++){ if(count == 0){ ans = nums[i]; count++; } else{ if(nums[i] == ans){ count++; } else{ count--; } } } return ans; } }

合并两个有序链表

题目：https://leetcode-cn.com/problems/merge-two-sorted-lists/ 思考：比较大小，然后移动链表。注意细节比较重要。

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode ll = new ListNode(0); ListNode cur = ll; while(l1 != null && l2 != null){ if(l1.val < l2.val){ cur.next = l1; cur = cur.next; l1 = l1.next; } else{ cur.next = l2; cur = cur.next; l2 = l2.next; } } if(l1 == null){ cur.next = l2; } else{ cur.next = l1; } return ll.next; } } //差不多，但是思路有细微区别 class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null)return l2; if(l2 == null)return l1; ListNode cur = null; if(l1.val < l2.val){ cur = l1; l1 = l1.next; } else{ cur = l2; l2 = l2.next; } ListNode ans = cur; while(l1 != null && l2 != null){ if(l1.val < l2.val){ cur.next = l1; cur = cur.next; l1 = l1.next; } else{ cur.next = l2; cur = cur.next; l2 = l2.next; } } if(l1 == null)cur.next = l2; else cur.next = l1; return ans; } }

移动零

题目：https://leetcode-cn.com/problems/move-zeroes/ 思考：循环遍历数组，设置一个标记index【表示数组中非零个数】，如果数非零，把数组往前提，这样就把所有非零数赋值（移动）完毕。

class Solution { public void moveZeroes(int[] nums) { if(nums == null || nums.length <=1) return; int index = 0; for(int i=0;i<nums.length;i++){ if(nums[i] != 0){ nums[index++] = nums[i]; } } for(int i=index;i<nums.length;i++){ nums[i] = 0; } } }

2019.11.6

有效的字母异位词

题目：https://leetcode-cn.com/problems/valid-anagram/ 思考：判断两个字符串中的字符是否完全相同。

//憨憨计数比较法 class Solution { public boolean isAnagram(String s, String t) { int[] sc = new int[26]; int[] tc = new int[26]; for(char ch : s.toCharArray()){ sc[ch - 'a']++; } for(char ch : t.toCharArray()){ tc[ch-'a']++; } for(int i=0;i<26;i++){ if(sc[i] != tc[i]){ return false; } } return true; } }

买卖股票的最佳时机Ⅱ

题目：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 思考：怎么说，看题解会发现是道思维题而不是算法题，可以当天抛出当天买入别的。

class Solution { public int maxProfit(int[] prices) { int ans = 0; for(int i=1;i<prices.length;i++){ if(prices[i]>prices[i-1]){ ans+=prices[i]-prices[i-1]; } } return ans; } }

2019.11.7

快乐树

题目：https://leetcode-cn.com/problems/happy-number/ 思考：根据题解的快慢指针法：

如果给定的数字最后会一直循环重复，那么快的指针（值）一定会追上慢的指针（值），也就是两者一定会相等。 如果没有循环重复，那么最后快慢指针也会相等，且都等于1。

class Solution { public boolean isHappy(int n) { int fast = n; int slow = n; do{ slow = quareSum(slow); fast = quareSum(fast); fast = quareSum(fast); }while(slow != fast); if(fast==1){ return true; } else{ return false; } } private int quareSum(int m){ int sum = 0; while(m!=0){ sum+=(m%10)*(m%10); m/=10; } return sum; } }

2019.11.8

报数

题目： 思考：只会老实人做法，循环，每次分析。

当对字符串进行修改的时候，需要使用 StringBuffer 和 StringBuilder 类 在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类

class Solution { public String countAndSay(int n) { String ans = "1"; if(n == 1)return ans; for(int i=0;i<n-1;i++){ StringBuffer s = new StringBuffer(); char t = ans.charAt(0); int count = 0; for(int j=0;j<ans.length();j++){ if(t!=ans.charAt(j)){ s.append(count); s.append(t); t=ans.charAt(j); count=1; } else{ count++; } } s.append(count); s.append(ans.charAt(ans.length()-1)); ans = s.toString(); } return ans; } }

2019.11.11

昨天由于感情问题心情不好，不想学习。

缺失数字

题目：https://leetcode-cn.com/problems/missing-number/ 思考：计算出如果数字不缺失时，数组的和【数列求和晓得伐，首项加尾项的和乘高除以2】，计算出此时缺失数字时的数组的和【一个循环】，两项相减得出的值就是答案。

class Solution { public int missingNumber(int[] nums) { int sum = 0; int length = nums.length; for(int i=0;i<length;i++){ sum+=nums[i];//计算数组和 } length+=1;//不缺失数字时的数组长度 int ans = (length-1)*length/2 - sum;//首项是0省略 return ans; } }

2019.11.12

买卖股票的最佳时机

题目:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 思考：【今天之前买入的最小值】【今天卖出的最大获利】 比较【每天的最大获利】，取最大值即可

class Solution { public int maxProfit(int[] prices) { if(prices.length<=1)return 0; int minn = prices[0]; int maxx = 0; for(int i=1;i<prices.length;i++){ maxx = Math.max(maxx,prices[i]-minn); minn = Math.min(minn,prices[i]); } return maxx; } }

存在重复元素

题目：https://leetcode-cn.com/problems/contains-duplicate/ 思考：

Set自带去重，如果去重后的长度小于原长度，则返回true

class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> res = new HashSet<>(); for(int i : nums){ res.add(i); } return res.size()<nums.length?true:false; } }

2019.11.13

两数之和

题目：https://leetcode-cn.com/problems/two-sum/ 思考：利用哈希表的性质，键值对（数值，下标）

class Solution { public int[] twoSum(int[] nums, int target) { int[] index = new int[2]; HashMap<Integer,Integer> hash = new HashMap<>(); for(int i=0;i<nums.length;i++){ if(hash.containsKey(nums[i])){ index[0]=i; index[1]=hash.get(nums[i]); return index; } hash.put(target-nums[i],i); } return index; } }

近段时间忙于其他事务，随机更新。

2019.11.20

最大子序和

题目：https://leetcode-cn.com/problems/maximum-subarray/ 思考：讲道理这题用贪心（？比较符合我的思路，但是要按要求用分治法写我就很苦恼了（用暴力的就憨憨了）【看了分治法题解感想：可以，但是我拒绝】

//算贪心吗（？） class Solution { public: int maxSubArray(vector<int>& nums) { int ans = nums[0]; int sum = 0; for(int i=0 ;i<nums.size();i++){ if(sum > 0){ sum+=nums[i]; } else{ sum = nums[i]; } ans = max(ans,sum); } return ans; } }; //动态规划 class Solution { public: int maxSubArray(vector<int>& nums) { int ans = nums[0]; int dp[nums.size()+1]; for(int i=0;i<nums.size();i++){ dp[i] = 0; } dp[0] = nums[0]; for(int i=1;i<nums.size();i++){ dp[i]=max(dp[i-1]+nums[i],nums[i]); ans = max(dp[i],ans); } return ans; } };