LeetCode 1
问题：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
https://leetcode-cn.com/problems/two-sum/
/**
* 两数之和
* 1. Map存储着val 对应的下标
* 2. target - num[i] 在Map中有存储，则能算出结果
*/
public class LeetCode1 {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> memo = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int val = target - nums[i];
if (memo.containsKey(val)) {
return new int[]{i, memo.get(val)};
} else {
memo.put(nums[i], i);
}
}
return new int[2];
}
}
LeetCode 20
问题：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
https://leetcode-cn.com/problems/valid-parentheses/
/**
* 有效括号
* 1. 借助Stack 栈先进先出的特性，将左侧括号进入栈
* 2. 当前character不是左侧括号时，则pop出来比对是否匹配
* 3. 注意要判断边界问题（在pop前 memo的大小是否为0，在遍历后，meme的大小是否为0）
*/
public class LeetCode20 {
public boolean isValid(String s) {
LinkedList<Character> memo = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '(') {
memo.push(s.charAt(i));
} else {
if (memo.size() == 0) {
return false;
}
Character pop = memo.pop();
Character c = null;
if (pop.equals('(')) {
c = ')';
}
if (pop.equals('{')) {
c = '}';
}
if (pop.equals('[')) {
c = ']';
}
if (!c.equals(s.charAt(i))) {
return false;
}
}
}
if (memo.size() != 0) {
return false;
}
return true;
}
}
LeetCode 21
问题：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
https://leetcode-cn.com/problems/merge-two-sorted-lists/
/**
* 合并两个有序链表
* 1. 关键在于 使用虚拟头节点
* 2. 记得移动 cur指针
*/
public class LeetCode21 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1 == null && l2 == null) {
return null;
}
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
while (l1 != null) {
cur.next = l1;
l1 = l1.next;
}
while (l2 != null) {
cur.next = l2;
l2 = l2.next;
}
return dummyHead.next;
}
}
LeetCode 53
问题：给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
https://leetcode-cn.com/problems/maximum-subarray/
/**
最大子序和(贪心算法)
res作为历史最佳解，
sum作为当前最佳解，
每一次遍历nums数组时，
都去动态更新res和sum。
动态更新的逻辑为： 如果sum为正数，在有res记录历史最佳值的条件下，可以有恃无恐地继续累加，创造新高；
如果sum为负数，不管下一次遍历值是多少累加后都不会大于它，见风使舵果断取下一个遍历值为当前最佳解。
每一轮遍历结束后，如果当前最佳解优于历史最佳解，就会升任历史最佳解。
*/
public class LeetCode53 {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0) {
sum = sum + num;
} else {
sum = num;
}
res = Math.max(res, sum);
}
return res;
}
}
LeetCode 70
问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
https://leetcode-cn.com/problems/climbing-stairs/
/**
* 爬楼梯
* 斐波拉契数列问题（使用备忘录，处理过的步数直接返回）
* 1. 当n=1和n=2时 直接添加至备忘录且返回
* 2. 当n在备忘录曾经计算过时，直接返回
* 3. 备忘录添加 n的步数 (n-1) + (n-2)
* 4. 返回备忘录的n
*/
public class LeetCode70 {
Map<Integer, Integer> memo = new HashMap<>();
public int climbStairs(int n) {
if (n < 3) {
memo.put(n, n);
return memo.get(n);
}
if (memo.containsKey(n)) {
return memo.get(n);
}
memo.put(n, climbStairs(n - 1) + climbStairs(n - 2));
return memo.get(n);
}
}
LeetCode 101
问题：给定一个二叉树，检查它是否是镜像对称的。
https://leetcode-cn.com/problems/symmetric-tree/
/**
* 给定一个二叉树，检查它是否是镜像对称的。
* <p>
* 1. 假如左子树和右子书都为null(说明只有"root"节点 返回true)
* 2. 左右子树的val 不相等， return false
*/
public class LeetCode101 {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return check(left.left, right.right) && check(left.right, right.left);
}
}
LeetCode 104
问题：给定一个二叉树，找出其最大深度，二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
/**
* 二叉树的最大深度
* 递归找出左边和右边最大的深度 +1 就好了
*/
public class LeetCode104 {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
LeetCode 136
问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
https://leetcode-cn.com/problems/single-number/
/**
* 只出现一次的数字 hashMap 简单解决
*
* 可以用异或运算符
*/
public class LeetCode136 {
// public int singleNumber(int[] nums) {
//
// HashMap<Integer, Integer> map = new HashMap();
//
// for (int num : nums) {
// if (map.containsKey(num)) {
// map.put(num, map.get(num) + 1);
// } else {
// map.put(num, 1);
// }
// }
//
// for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// if (entry.getValue() == 1) {
// return entry.getKey();
// }
// }
//
// return 0;
// }
public int singleNumber(int[] nums) {
int a = 0;
for (int num : nums) {
a = num ^ a;
}
return a;
}
}
LeetCode 155
问题：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。提示：
pop、top和getMin操作总是在 非空栈 上调用。
/**
* 借助 minStack 完成
*
* 首先扔进去一个MaxIntegerVal，这样就不用判空了
*/
class MinStack {
LinkedList<Integer> stack = new LinkedList<>();
LinkedList<Integer> minStack = new LinkedList<>();
/**
* initialize your data structure here.
*/
public MinStack() {
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
stack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
public static void main(String[] args) {
MinStack obj = new MinStack();
obj.push(2);
obj.pop();
int param_3 = obj.top();
int param_4 = obj.getMin();
}
}
LeetCode 160
问题：给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
/**
* 编写一个程序，找到两个单链表相交的起始节点。
* 1. 两个节点相等，那就是相交；用Map来存储即可
*/
public class LeetCode160 {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashMap<ListNode, ListNode> map = new HashMap<>();
if (headA == null || headB == null) {
return null;
}
while (headA != null) {
map.put(headA, headA);
headA = headA.next;
}
while (headB != null) {
if (map.get(headB) != null) {
return headB;
}
headB = headB.next;
}
return null;
}
}
LeetCode 169
问题：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
https://leetcode-cn.com/problems/majority-element/
/**
* 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
*
* 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
*
* 1. Map大法好，遍历直接存储出现的次数，找到最大的即可
* 2. 使用单个变量来记录，剩下的一定是"多数"的元素
* （从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个）
*/
public class LeetCode169 {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> keyVal = new HashMap<>();
for (int num : nums) {
if (keyVal.containsKey(num)) {
keyVal.put(num, keyVal.get(num) + 1);
} else {
keyVal.put(num, 1);
}
}
int max = Integer.MIN_VALUE;
int key = 0;
for (Map.Entry<Integer, Integer> entry : keyVal.entrySet()) {
if (entry.getValue() > max) {
max = entry.getValue();
key = entry.getKey();
}
}
return key;
}
// public int majorityElement(int[] nums) {
// int cand_num = nums[0];
// int count = 1;
// for (int i = 1; i < nums.length; ++i) {
// if (cand_num == nums[i]){
// ++count;
// } else if (--count == 0) {
// cand_num = nums[i];
// count = 1;
// }
// }
// return cand_num;
// }
}
LeetCode 206
问题：给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
https://leetcode-cn.com/problems/reverse-linked-list/
/**
* 反转链表
* 1. 头节点指向 NULL
* 2. 头结点和下一个节点不断往后移
*/
public class LeetCode206 {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
LeetCode 226
问题：翻转一棵二叉树。
https://leetcode-cn.com/problems/invert-binary-tree/
/**
* 反转二叉树
*/
public class LeetCode226 {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
LeetCode 234
问题：给你一个单链表的头节点
head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
https://leetcode-cn.com/problems/palindrome-linked-list/
/**
* 请判断一个链表是否为回文链表。
*
* 借助栈结构，进栈出栈再判断一次
*/
public class LeetCode234 {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
LinkedList<ListNode> stack = new LinkedList<>();
ListNode cur = head;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (!stack.isEmpty()) {
if (!Integer.valueOf(stack.pop().val).equals(Integer.valueOf(head.val))) {
return false;
}
head = head.next;
}
return true;
}
}
LeetCode 283
问题：给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
https://leetcode-cn.com/problems/move-zeroes/
/**
* 283. 移动零
* 遍历数据，只要不为0，则交换到index
* 从index开始，复制为0
*/
public class LeetCode283 {
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index] = nums[i];
index++;
}
}
for (int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
}
LeetCode 448
问题：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
/**
* 448. 找到所有数组中消失的数字
* （不能用额外的空间）
*
* 数字范围1~n，而数组下标0~(n-1)，则可用数组原地标记数字是否出现过
*
*
*/
public class LeetCode448 {
public static List<Integer> findDisappearedNumbers(int... nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
res.add(i + 1);
}
}
return res;
}
}