【数据结构与算法】LeetCode：day9
1. 路径总和
解题思路：向下进行递归求解：满足hasPathSum(TreeNode root, int sum)
等价于满足 hasPathSum(root.right, sum -val) 或 hasPathSum(root.left, sum -val)
寻找退出条件：当最后一次递归时 sum - root.val == 0
代码实现：1234567891011121314151617181920/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean hasPathSum(TreeNode root, int sum) { ...
【数据结构与算法】LeetCode：day8
1. 爬楼梯
我的思路：写出前五项观察结果：
1：1
2：2
3：3
4：5
5：8
……
可知结果为斐波那契数列，直接用递归的方法求解斐波那契数列第 n 项
代码实现：1234567class Solution { public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); }}
执行结果：
由于递归及其耗费时间，时间复杂度为 O(2^n)，导致求解超时
更好的解法：
1234567891011class Solution { public int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; i++) { p = ...
【数据结构与算法】LeetCode：day7
1. 搜索插入位置
我的思路：使用二分查找
代码实现：1234567891011121314151617181920class Solution { public int searchInsert(int[] nums, int target) { if (nums.length==) return 0; int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right -left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid - 1; ...
【数据结构与算法】LeetCode：day6
1. 有效的括号
我的思路：知道要用到栈，但是实际操作的时候出现了问题！
好的思路：
建立一个堆栈
当遇到 (、[、{ 的时候，将与之对应的括号放入堆栈
当遇到 )、]、} 时，说明栈顶一 定是与之相对应的括号，如果堆栈为空或者栈顶不是与之相对应的括号，则括号无效
最后如果堆栈为空则说明括号有效！
代码实现：123456789101112class Solution { public boolean isValid(String s) { LinkedList<Character> stack = new LinkedList<>(); for (char c: s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '[') stack.push(']'); ...
【数据结构与算法】LeetCode：day5
1. 回文数
我的思路：直接将整数转化为字符串，使用字符串相关的函数将字符串反转后与原串作比较
代码实现：123456class Solution { public boolean isPalindrome(int x) { return new StringBuilder(String.valueOf(x)).toString() .equals(new StringBuilder(String.valueOf(x)).reverse().toString()); }}
执行结果：
可以看出执行效率较差、占用空间也较多！
更好的方法：
映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。
第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。但是，如果反转后的数字大于 \text{int.MAX}int.MAX，我们将遇到整数溢出问题。
按照第二个想法，为了避免数字反转 ...
【数据结构与算法】LeetCode：day4
1. 各位相加
我的思路：
如果 num < 10 则直接返回 num
如果 num > 10 ，则将 num 各位相加得到 res
res < 10 直接返回
res >= 10 带入函数进行递归
我的代码：1234567891011121314151617class Solution { public int addDigits(int num) { if (num < 10) { return num; } int res = 0; while (num >= 10) { res += num % 10; num /= 10; } res += num; while (res >= 10) { res = addDigits(res); } ...
【数据结构与算法】LeetCode：day3
1. 数组异或操作
2. 左旋转字符串
3. 删除中间节点
思路：题目中链表只给了要删除的节点，我们通过已知节点可以删除他的下一个节点，但是无法删除他本身
我们可以将他下一个节点的值赋给当前节点，那么该节点就变得和下一个节点一样了，此时我们只需删除下一个节点即可。
代码：1234567891011121314/** * 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; }}
4. 二进制求和
不全对的一个想法：通 ...
【数据结构与算法】LeetCode：day2
1. 顺时针打印矩阵
本题稍有难度，算是简单题中的难题，思考、实现过程花费将近两个小时，最后还是参考了官方答案，头大~
我的思路：设置循环，从外层依次向内遍历
设置两个变量：height、width分别表示向上（下）、向左（右）遍历的次数
每一次循环：
向右遍历
height--
向下遍历
width--
向左遍历
height--
向上遍历
width--
然而始终没有想明白外层循环结束的时机….
更好的方法：
引入四个变量（top、left、bottom、right）来标识边界更加直观！
每次循环结束，整个边界向内收缩一圈：
left++;
right--;
top++;
bottom--;
1234567891011121314151617181920212223242526272829303132class Solution { public int[] spiralOrder(int[][] matrix) { if (matrix == null || matrix.length == 0 || ...
【数据结构与算法】LeetCode：day18
1. 单词规律
思路：HashMap将 pattern 中的字母和 str 中的单词使用 HashMap 进行一一映射
注意：需要对 pattern 和 str 进行双向映射（也可以判断 map 中是否已经包含了 value）
如果只是完成了 pattern -> str 的映射，则下例仍会判断错误
12pattern = "abba"str = "dog dog dog dog"
123456789101112131415161718192021222324252627282930313233343536class Solution { public boolean wordPattern(String pattern, String str) { return wordPatternHelper1(pattern, str) && wordPatternHelper2(pattern, str); } // str -> patt ...
【数据结构与算法】LeetCode：day17
1. 回文链表
思路一：使用数组由于链表只能单向访问，故我们可以将链表中的值先保存到 List 中，再使用双指针分别指向 List 的头尾来依次判断对应元素是否相等
（也可以将所有的节点值入栈中，再比较各节点元素和栈顶元素是否相等）
12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public boolean isPalindrome(ListNode head) { // 存入List ArrayList<Integer> list = new ArrayList<>(); while (h ...
