按lc的热度总结的题目，我看了不少面经，总感觉他们出的算法题，不会太难，肯定是比较热门的题。
https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]方法很多，看个人，这一套根据我个人准备的，准确且快即可。
双指针
class Solution {
public int[] twoSum(int[] nums, int target) {
int p1 = 0, p2 = nums.length - 1;
while (p1 < p2) {
int sum = nums[p1] + nums[p2];
if (sum < target)
p1++;
else if (sum > target)
p2--;
else return
new int[] {p1, p2};
}
return new int[]{};
}
}https://leetcode-cn.com/problems/add-two-numbers/
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807- 两个链表相加，先判断边界
- 创建一个新的链表
- while中也要注意边界
- 两个链表的值、进位相加
- 是否赋值给进位
- 三个链表移动指针
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode p1 = l1;
ListNode p2 = l2;
ListNode l3 = new ListNode(-1);
ListNode p3 = l3;
int carried = 0;
while (p1 != null || p2 != null) {
int a = p1 != null ? p1.val : 0;
int b = p2 != null ? p2.val : 0;
p3.next = new ListNode((a + b + carried) % 10);
carried = (a + b + carried) / 10;
p3 = p3.next;
p1 = p1 != null ? p1.next : null;
p2 = p2 != null ? p2.next : null;
}
p3.next = carried != 0 ? new ListNode(1) : null;
return l3.next;
}
}https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。HashMap+两个指针 两个指针分别记录字母的起始和结束，用map来存
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0, j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}https://leetcode-cn.com/problems/longest-palindromic-substring/
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。中心扩展
- 两种情况
- 奇数长度
- 偶数长度
- 取最长，求起始和结束位置
- 用substring即可
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
int start = 0, end = 0; // 记录起始位置
for (int i = 0; i < s.length(); i++) {
// 两种情况 以i为中心，以i和i+1为中心
int len1 = expand(s, i - 1, i + 1); // 中心扩展
int len2 = expand(s, i, i + 1);
int len = Math.max(len1, len2); // 取最长的长度
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 这里要注意
return r - l - 1;
}
}https://leetcode-cn.com/problems/zigzag-conversion/
class Solution {
// 0| 1 5 9 13
// 1| 2 4 6 8 10 12 14 16
// 2| 3 7 11 15
// 每一行右边的字符的 ’索引值’ 都是其左边的字符的 ’索引值’ 加上它 ’下面剩余行数’ 的两倍或 ’上面行数’ 的两倍（交替相加）
// 以第二行为例，
// 对于4这个字符而言， 4 = 2(左边的索引) + 2(两倍) * 1(下面有一行)
// 6 = 4 + 2 * 1(上面有一行)
// 8 = 6 + 2 * 1(下面有一行)
public String convert(String s, int numRows) {
if (numRows <= 1)
return s;
char[] cs = s.toCharArray();
String res = "";
for (int i = 0; i < numRows; i++){
int up = i; // 上方的行数
int down = numRows - 1 - i; // 下方的行数
int temp = i;
int cnt = 0;
while (temp < cs.length){
if (cnt % 2 == 0 && down != 0) {
res += cs[temp];
temp += 2 * down;
} else if(cnt % 2 != 0 && up != 0){
res += cs[temp];
temp += 2 * up;
}
cnt++;
}
}
return res;
}
}https://leetcode-cn.com/problems/reverse-integer/
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。输入: 123
输出: 321
输入: -123
输出: -321
输入: 120
输出: 21class Solution {
public int reverse(int x) {
注意题目条件
long ans = 0;
while(x != 0) {
// 常用公式
ans = ans * 10 + x % 10;
x /= 10;
}
// 判断是否溢出
if(ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
return 0;
}
return (int)ans;
}
}https://leetcode-cn.com/problems/palindrome-number/
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。输入: 121
输出: true
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。class Solution {
public boolean isPalindrome(int x) {
// 0也是回文数
if (x == 0)
return true;
// 特殊条件
if (x < 0 || x % 10 == 0)
return false;
// 只需要一半
int right = 0;
while ( x > right) {
right = right * 10 + x % 10;
x /= 10;
}
return x == right || x == right / 10;
}
}https://leetcode-cn.com/problems/container-with-most-water/
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。输入：[1,8,6,2,5,4,8,3,7]
输出：49class Solution {
public int maxArea(int[] height) {
int max = 0;
for (int i = 0, j = height.length - 1; i < j;) {
// 双指针，谁小取谁，判断移动
int minHeight = height[i] < height[j] ? height[i++] : height[j--];
// 每一次都要维护最大值
max = Math.max(max, (j - i + 1) * minHeight);
}
return max;
}
}https://leetcode-cn.com/problems/longest-common-prefix/
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
String str = strs[0];
// 循环用indexOf和substring
for(int i = 1; i < strs.length; i++) {
while(strs[i].indexOf(str) != 0) {
// 每次substring去掉最后一位
str = str.substring(0, str.length() - 1);
}
}
return str;
}
}https://leetcode-cn.com/problems/3sum/
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]这道题三要素：
- 排序
- 双指针
- 去重复
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序的目的就是来告别重复
Arrays.sort(nums);
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// 判断是否元素大于0,大于0，没必要操作了
if (nums[i] > 0) break;
// 判断是否重复
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 双指针操作
int l = i + 1, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] < -nums[i]) l++;
else if (nums[l] + nums[r] > -nums[i]) r--;
else {
// 相等了哈
ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
// 防止重复
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
return ls;
}
}哪种代码好理解就用哪种
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序
Arrays.sort(nums);
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) { //跳过可能重复的
// 转化为两数之和
int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
while(l < r) {
if (nums[l] + nums[r] == sum) {
ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++; // 还是一样，跳过重复
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (nums[l] + nums[r] < sum) {
while (l < r && nums[l] == nums[l + 1]) l++;
l++;
} else {
while (l < r && nums[r] == nums[r - 1]) r--;
r--;
}
}
}
}
return ls;
}
}https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].回溯 不需要标记 但是记得deleteCharAt
class Solution {
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> combinnations = new ArrayList<>();
if (digits == null || digits.length() == 0) return combinnations;
doCombination(new StringBuilder(), combinnations, digits);
return combinnations;
}
private void doCombination(StringBuilder prefix, List<String> combinnations, final String digits) {
if (prefix.length() == digits.length()) {
combinnations.add(prefix.toString());
return;
}
int curDigits = digits.charAt(prefix.length()) - '0';
String letters = KEYS[curDigits];
for (char c : letters.toCharArray()) {
prefix.append(c);
doCombination(prefix, combinnations, digits);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.快慢指针 分情况
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
// 这里没懂， 得举例子就懂了
if (fast == null)
return head.next;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 这里也懂了...举个例子就行
slow.next = slow.next.next;
return head;
}
}https://leetcode-cn.com/problems/valid-parentheses/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false栈思想
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (stack.isEmpty())
stack.push(c);
else if(isSym(stack.peek(), c))
stack.pop();
else
stack.push(c);
}
return stack.isEmpty();
}
private boolean isSym(char c1, char c2) {
return (c1 == '(' && c2 == ')')
|| (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
}https://leetcode-cn.com/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}https://leetcode-cn.com/problems/generate-parentheses/
class Solution {
List<String> ret = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs("", 0, 0, n);
return ret;
}
public void dfs(String ans, int cnt1, int cnt2, int n){
if (cnt1 > n || cnt2 > n)
return;
if (cnt1 == n && cnt2 == n)
ret.add(ans);
if (cnt1 >= cnt2){
String ans1 = new String(ans);
dfs(ans + "(", cnt1 + 1, cnt2, n);
dfs(ans + ")", cnt1, cnt2 + 1, n);
}
}
}class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy, cur = head, next;
dummy.next = head;
ListNode p = head;
int len = 0;
while (p != null){
len++;
p = p.next;
}
//
for (int i = 0; i < len / k; i++) {
for (int j = 0; j < k - 1; j++) {
next = cur.next;
// 注意这三步
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
// 移动的时候注意
pre = cur;
cur = pre.next;
}
return dummy.next;
}
}https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。class Solution {
public int removeDuplicates(int[] nums) {
int p = 0;
for(int i = 1; i < nums.length; i++) {
if(nums[p] != nums[i]) {
nums[++p] = nums[i];
}
}
return p+1;
}
}https://leetcode-cn.com/problems/remove-element/
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。class Solution {
public int removeElement(int[] nums, int val) {
int p = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] != val)
nums[p++] = nums[i];
}
return p;
}
}https://leetcode-cn.com/problems/implement-strstr/
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。输入: haystack = "hello", needle = "ll"
输出: 2class Solution {
public int strStr(String haystack, String needle) {
int l = haystack.length(), n = needle.length();
for(int start = 0; start < l - n + 1; start++) {
// subtring + equals
if(haystack.substring(start, start + n).equals(needle)) {
return start;
}
}
return -1;
}
}https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
变相的二分，稍微有点难度
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if(nums[mid] < nums[right]) {
// 注意边界条件
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
} else {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
}https://leetcode-cn.com/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 2
输出: 1
输入: [1,3,5,6], 7
输出: 4
输入: [1,3,5,6], 0
输出: 0二分法 但要考虑边界
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0;
int h = nums.length - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
if (nums[mid] < target)
l = mid + 1;
else if (nums[mid] > target)
h = mid - 1;
else
return mid;
}
// 注意边界
if (h < 0 && l == 0)
return (l + h) % 2 + 1;
else
return (l + h) / 2 + 1;
}
}https://leetcode-cn.com/problems/count-and-say/
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “一个 1 ”，记作 11
描述前一项，这个数是 11 即 “两个 1 ” ，记作 21
描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211
描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221输入: 1
输出: "1"
解释：这是一个基本样例。
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。StringBuffer + cnt
class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
String str = "1";
for (int i = 0; i < n - 1; i++) {
StringBuffer sb = new StringBuffer();
int count = 0;
char code = str.charAt(0);
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) != code) {
sb.append(count);
sb.append(code);
code = str.charAt(j);
count = 1;
} else {
count++;
}
}
sb.append(count);
sb.append(str.charAt(str.length() - 1));
str = sb.toString();
}
return str;
}
}https://leetcode-cn.com/problems/trapping-rain-water/
双指针
class Solution {
public int trap(int[] height) {
int min = 0, max = 0;
int l = 0, r = height.length - 1;
int res = 0;
while(l < r) {
// 双指针维护最小值
min = height[height[l] < height[r] ? l++ : r--];
// 接着维护最大值
max = Math.max(max, min);
// 累加差值
res += max - min;
}
return res;
}
}https://leetcode-cn.com/problems/multiply-strings/
class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
if (len1 == 0 || len2 == 0) return "0";
int[] mul = new int[len1 + len2];
for (int i = len1 - 1; i >= 0; i--){
for (int j = len2 - 1; j >= 0; j--){
int n = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + mul[i + j + 1];
mul[i + j + 1] = n % 10;
mul[i + j] += n / 10;
}
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < len1 + len2 - 1 && mul[i] == 0) i++;
while (i < len1 + len2) sb.append(mul[i++]);
return sb.toString();
}
}https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int preSum = nums[0];
int maxSum = preSum;
for (int i = 1; i < nums.length; i++) {
// 注意条件
preSum = preSum > 0 ? preSum + nums[i] : nums[i];
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}
}https://leetcode-cn.com/problems/jump-game/
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。贪心
class Solution {
public boolean canJump(int[] nums) {
if (nums.length <= 1) return true;
int n = nums.length;
int max = nums[0];
for (int i = 1; i < n - 1; i++) {
// 注意条件
if (i <= max) {
// 最远索引
max = Math.max(max, nums[i] + i);
} else {
break;
}
}
// 注意判断
return max >= n - 1;
}
}https://leetcode-cn.com/problems/plus-one/
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。正常操作 加法中常用 a = x % 10 b = x / 10
class Solution {
public int[] plusOne(int[] digits) {
int length = digits.length;
int[] res = new int[length + 1];
int carry = 1;
for (int i = length - 1; i >= 0 ; i--) {
int sums = digits[i] + carry;
res[i] = sums % 10;
carry = sums / 10;
}
if (carry == 1) {
res[0] = 1;
return res;
}
return Arrays.copyOfRange(res,0,length);
}
}https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶自底向上
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int pre2 = 1, pre1 = 2;
for (int i = 3; i <= n; i++) {
int cur = pre2 + pre1;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}https://leetcode-cn.com/problems/merge-sorted-array/
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]三指针
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1, index2 = n - 1;
int indexMerge = m + n - 1;
while (index1 >= 0 || index2 >= 0) {
if (index1 < 0) {
nums1[indexMerge--] = nums2[index2--];
} else if (index2 < 0) {
nums1[indexMerge--] = nums1[index1--];
} else if (nums1[index1] > nums2[index2]) {
nums1[indexMerge--] = nums1[index1--];
} else {
nums1[indexMerge--] = nums2[index2--];
}
}
}https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 3
/ \
9 20
/ \
15 7
[
[3],
[9,20],
[15,7]
]队列
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null)
continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (list.size() != 0)
ret.add(list);
}
return ret;
}
}https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。class Solution {
public int maxProfit(int[] prices) {
// 边界
if(prices.length == 0) return 0;
// 长度
int n = prices.length;
// min
int min = prices[0];
// max
int max = 0;
for (int i = 1; i < n; i++) {
// 一直找最小的股
min = prices[i] < min ? prices[i] : min;
// 遍历一圈，存最大的利润
max = Math.max(max, prices[i] - min);
}
return max;
}
}https://leetcode-cn.com/problems/majority-element/
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。输入: [3,2,3]
输出: 3class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}https://leetcode-cn.com/problems/house-robber/
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。class Solution {
public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}https://leetcode-cn.com/problems/reverse-linked-list/
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULLclass Solution {
public ListNode reverseList(ListNode head) {
// 尾递归
// return reverse(null, head);
// 头插
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
private ListNode reverse(ListNode pre, ListNode cur) {
if (cur == null) return pre;
ListNode next = cur.next;
cur.next = pre;
return reverse(cur, next);
}
}https://leetcode-cn.com/problems/implement-stack-using-queues/
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空class MyStack {
private Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
// 加完取长度
int cnt = queue.size();
// 倒置
while (cnt-- > 1) {
queue.add(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}https://leetcode-cn.com/problems/move-zeroes/
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]- 先把不是0的移动左
- 最后陆续加0
class Solution {
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0)
nums[idx++] = num;
}
while (idx < nums.length) {
nums[idx++] =0;
}
}
}https://leetcode-cn.com/problems/distribute-candies-to-people/
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] ans = new int[num_people];
int i;
for (i = 0; candies > 0; i++) {
ans[i % num_people] += i + 1;
candies -= i + 1;
}
ans[(i - 1) % num_people] += candies;
return ans;
}
}https://leetcode-cn.com/problems/rotting-oranges/
class Solution {
public int orangesRotting(int[][] grid) {
// 俺就不判断了，直接上
int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int m = grid.length, n = grid[0].length;
int cnt = 0; // 表示新鲜的橘子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1)
cnt++; // 新鲜橘子计数
else if (grid[i][j] == 2)
q.add(new Pair<>(i, j)); // 腐烂橘子的坐标
}
}
if (cnt == 0 || q.size() == m * n)
return 0;
int step = 0; // 轮数
while (cnt > 0 && !q.isEmpty()){
int size = q.size();
while (size-- > 0) {
Pair<Integer, Integer> p = q.poll();
int x = p.getKey(), y = p.getValue();
for (int[] d : dir) {
int newX = x + d[0];
int newY = y + d[1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
continue;
}
if (grid[newX][newY] == 1) {
grid[newX][newY] = 2;
q.add(new Pair<>(newX, newY));
cnt--;
}
}
}
step++;
}
return cnt > 0 ? -1 : step;
}
}https://leetcode-cn.com/problems/merge-k-sorted-lists/
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6最小堆
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
ListNode dummy = new ListNode(0);
ListNode p = dummy;
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
while (!queue.isEmpty()) {
p.next = queue.poll();
p = p.next;
if (p.next != null) queue.add(p.next);
}
return dummy.next;
}
}分治
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}https://leetcode-cn.com/problems/swap-nodes-in-pairs/
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。给定 1->2->3->4, 你应该返回 2->1->4->3.class Solution {
public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode pre = node;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next, l2 = pre.next.next;
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return node.next;
}
}https://leetcode-cn.com/problems/longest-valid-parentheses/
class Solution {
public int longestValidParentheses(String s) {
int ans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++){
if (s.charAt(i) == ')') {
int j = i - dp[i - 1] - 1;
if (j >= 0 && s.charAt(j) == '(')
dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0);
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]双指针+二分法
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
int last = findFirst(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[] {-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}
private int findFirst(int[] nums, int target) {
int l = 0, h = nums.length; // h 的初始值和往常不一样
while (l < h) {
int m = l + ( h - l) / 2;
if (nums[m] >= target) h = m;
else l = m + 1;
}
return l;
}
}https://leetcode-cn.com/problems/permutations/
给定一个 没有重复 数字的序列，返回其所有可能的全排列。输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]dfs
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList)); // 重新构造一个List
return;
}
for (int i = 0; i < visited.length; i++) {
if (visited[i]) continue;
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
}https://leetcode-cn.com/problems/merge-intervals/
给出一个区间的集合，请合并所有重叠的区间。输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new ArrayList<>();
int i = 0;
int n = intervals.length;
while (i < n) {
int l = intervals[i][0];
int r = intervals[i][1];
while (i < n - 1 && r >= intervals[i + 1][0]) {
r = Math.max(r, intervals[i + 1][1]);
i++;
}
list.add(new int[] {l, r});
i++;
}
return list.toArray(new int[list.size()][2]);
}
}https://leetcode-cn.com/problems/length-of-last-word/
给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。输入: "Hello World"
输出: 5class Solution {
public int lengthOfLastWord(String s) {
String[] strs = s.split(" ");
if(strs.length == 0) return 0;
return strs[strs.length-1].length();
}
}https://leetcode-cn.com/problems/add-binary/
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') carry++;
if (j >= 0 && b.charAt(j--) == '1') carry++;
// 注意这里
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}https://leetcode-cn.com/problems/symmetric-tree/
给定一个二叉树，检查它是否是镜像对称的。
1
/ \
2 2
/ \ / \
3 4 4 3class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
}https://leetcode-cn.com/problems/valid-palindrome/
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。输入: "A man, a plan, a canal: Panama"
输出: true
输入: "race a car"
输出: false双指针
class Solution {
public boolean isPalindrome(String s) {
if (s.equals("")) return true;
s = s.toLowerCase();
char[] sChar = s.toCharArray();
int l = 0, r = sChar.length - 1;
while (l <= r) {
if (sChar[l] == sChar[r]) {
l++;
r--;
} else if (!isNormalChar(sChar[l])) {
l++;
} else if (!isNormalChar(sChar[r])) {
r--;
} else {
return false;
}
}
return true;
}
private boolean isNormalChar(char a){
return Character.isLowerCase(a) || Character.isUpperCase(a) || Character.isDigit(a);
}
}https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。 3
/ \
9 20
/ \
15 7class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
return 1 + Math.max(l, r);
}
}https://leetcode-cn.com/problems/single-number/
输入: [2,2,1]
输出: 1异或
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for (int num : nums)
ret = ret ^ num;
return ret;
}
}https://leetcode-cn.com/problems/linked-list-cycle/
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode l1 = head, l2 = head.next;
while (l1 != null && l2 != null && l2.next != null) {
if (l1 == l2) {
return true;
}
l1 = l1.next;
l2 = l2.next.next;
}
return false;
}
}https://leetcode-cn.com/problems/number-of-islands/
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。dfs
class Solution {
private int m, n;
private int[][] direaction = {{0,1},{0,-1},{1,0},{-1,0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '0') {
dfs(grid, i, j);
islandsNum++;
}
}
}
return islandsNum;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >=n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
for (int[] d : direaction) {
dfs(grid, i + d[0], j + d[1]);
}
}
}https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4快排
class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l , h);
if (j == k) {
break;
} else if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] arr, int l, int r) {
int pivot = l;
int index = pivot + 1;
for (int i = index; i <= r; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index++);
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}https://leetcode-cn.com/problems/longest-palindrome/
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。class Solution {
public int longestPalindrome(String s) {
int[] cnts = new int[256];
for (char c : s.toCharArray()) {
cnts[c]++;
}
int palindrome = 0;
// 偶数个字母加起来，就算不是偶数个，也拿偶数个，比如5拿4
for (int cnt : cnts) {
palindrome += (cnt / 2) * 2;
}
// 小于，则说明有个字母或多个字母是奇数个，拿一放中间
if (palindrome < s.length()) {
palindrome++;
}
return palindrome;
}
}https://leetcode-cn.com/problems/middle-of-the-linked-list/
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。快慢指针
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head, q = head;
while (q != null && q.next != null) {
q = q.next.next;
p = p.next;
}
return p;
}
}https://leetcode-cn.com/problems/first-missing-positive/
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。输入: [1,2,0]
输出: 3
输入: [3,4,-1,1]
输出: 2
输入: [7,8,9,11,12]
输出: 1
怎么会怎么来，排序，接着遍历。
class Solution {
public int firstMissingPositive(int[] nums) {
int ans = 1;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > ans) break;
if (nums[i] == ans) ans++;
}
return ans;
}
}html
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右dp
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}输入: "the sky is blue"
输出: "blue is sky the"
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。用了api
class Solution {
public String reverseWords(String s) {
String[] words = s.trim().split(" +");
Collections.reverse(Arrays.asList(words));
return String.join(" ", words);
}
}https://leetcode-cn.com/problems/min-stack/
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。辅助栈
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
dataStack.push(x);
minStack.push(minStack.isEmpty() ? x : Math.min(minStack.peek(), x));
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return min;
}
}https://leetcode-cn.com/problems/longest-increasing-subsequence/
给定一个无序的整数数组，找到其中最长上升子序列的长度。输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。dp
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1); // 关键这里，
}
}
}
return Arrays.stream(dp).max().orElse(0);
}
}https://leetcode-cn.com/problems/coin-change/
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
输入: coins = [2], amount = 3
输出: -1完全背包
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
for (int coin : coins) {
for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
if (i == coin) {
dp[i] = 1;
} else if (dp[i] == 0 && dp[i - coin] != 0) {
dp[i] = dp[i - coin] + 1;
} else if (dp[i - coin] != 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：trueclass Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
// 遍历数组求总和
for (int num : A) {
sum += num;
}
// 数组A的和如果不能被3整除直接返回false
if (sum % 3 != 0) {
return false;
}
// 遍历数组累加，每累加到目标值cnt加1，表示又找到1段
sum /= 3;
int curSum = 0, cnt = 0;
for (int i = 0; i < A.length; i++) {
curSum += A[i];
if (curSum == sum) {
cnt++;
curSum = 0;
}
}
// 最后判断是否找到了3段（注意如果目标值是0的话可以大于3段）
return cnt == 3 || (cnt > 3 && sum == 0);
}
}https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。类似于map的数组即可。双map
class Solution {
public int countCharacters(String[] words, String chars) {
int[] hash = new int[26];
for (char ch : chars.toCharArray()) {
hash[ch - 'a']++;
}
int[] tmp = new int[26];
int len = 0;
for (String word : words) {
Arrays.fill(tmp, 0);
boolean flag = true;
for (char ch : word.toCharArray()) {
tmp[ch - 'a']++;
if (tmp[ch - 'a'] > hash[ch - 'a'])
flag = false;
}
len += flag ? word.length() : 0;
}
return len;
}
}https://leetcode-cn.com/problems/subsets/
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
tempSubset.add(nums[i]);
backtracking(i + 1, tempSubset, subsets, size, nums);
tempSubset.remove(tempSubset.size() - 1);
}
}
}https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。输入: 1->1->2
输出: 1->2
输入: 1->1->2->3->3
输出: 1->2->3class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
}https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
给定一个二叉树，返回它的中序 遍历。输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]栈
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left; // 遍历到做左
}
TreeNode node = stack.pop(); // 从下往上弹
ret.add(node.val);
cur = node.right; // 弹完遍历右
}
return ret;
}
}https://leetcode-cn.com/problems/same-tree/
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: falseclass Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}https://leetcode-cn.com/problems/pascals-triangle/
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0; i < numRows; i++) {
List<Integer> curRow = new ArrayList<>();
for(int j = 0; j <= i; j++) {
if(j == 0 || j == i) {
curRow.add(1);
continue;
}
if(i == 0 || i == 1) {
continue;
}
List<Integer> preRow = ans.get(i - 1);
int value = preRow.get(j - 1) + preRow.get(j);
curRow.add(value);
}
ans.add(curRow);
}
return ans;
}
}https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
双指针，A走完，走B，B走完，走A
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while (l1 != l2) {
l1 = (l1 == null) ? headB : l1.next;
l2 = (l2 == null) ? headA : l2.next;
}
return l1;
}
}https://leetcode-cn.com/problems/happy-number/
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1class Solution {
public boolean isHappy(int n) {
if(n == 1) return true;
HashSet<Integer> set = new HashSet<>();
while(2 > 1) {
int sum = 0;
while (n > 0) {
sum += (n % 10) *(n % 10);
n /= 10;
}
if(sum == 1) return true;
if(!set.add(sum)) return false;
n = sum;
}
}
}https://leetcode-cn.com/problems/palindrome-linked-list/
请判断一个链表是否为回文链表。
输入: 1->2
输出: false
输入: 1->2->2->1
输出: trueclass Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
// 找中点
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast != null) slow = slow.next;
// cut
cut(head, slow);
// 比较
return isEqual(head, reverse(slow));
}
public void cut (ListNode head, ListNode cutNode) {
ListNode node = head;
while(node.next != cutNode) {
node = node.next;
}
node.next = null;
}
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
public boolean isEqual(ListNode l1, ListNode l2) {
while(l1 != null && l2 != null) {
if(l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
}https://leetcode-cn.com/problems/reverse-string/
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]双指针
class Solution {
public void reverseString(char[] s) {
int p1 = 0, p2 = s.length - 1;
while(p1 < p2 ){
swap(s, p1++, p2--);
}
}
public void swap(char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}https://leetcode-cn.com/problems/max-area-of-island/
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。class Solution {
private int m, n;
private int[][] direaction = {{0,1},{0,-1},{1,0},{-1,0}};
public int maxAreaOfIsland(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}
private int dfs(int[][] grid, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int area = 1;
for (int[] d : direaction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}
}https://leetcode-cn.com/problems/daily-temperatures/
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。递减栈
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int t = stack.pop();
res[t] = i - t;
}
stack.push(i);
}
return res;
}
}https://leetcode-cn.com/problems/combination-sum/
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtracking(new ArrayList<>(), combinations, 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
int start, int target, final int[] candidates) {
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
tempCombination.remove(tempCombination.size() - 1);
}
}
}
}https://leetcode-cn.com/problems/sort-colors/ 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
```html
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
zero和two作为双指针
class Solution {
public void sortColors(int[] nums) {
int zero = -1, one = 0, two = nums.length;
while (one < two) {
if (nums[one] == 0) {
swap(nums, ++zero, one++);
} else if (nums[one] == 2){
swap(nums, --two, one);
} else {
++one;
}
}
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
3
/ \
9 20
/ \
15 7
2class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
int l = minDepth(root.left);
int r = minDepth(root.right);
if(l == 0 || r == 0) return l + r + 1;
return Math.min(l, r) + 1;
}
}https://leetcode-cn.com/problems/triangle/
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]dp
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size() == 0) return 0;
int row = triangle.size();
int[][] dp = new int[row][triangle.get(row - 1).size()];
// 初始化
for(int i = 0; i < row; i++) {
for (int j =0; j < triangle.get(i).size(); j++) {
dp[i][j] = triangle.get(i).get(j);
}
}
// 从下往上， 初始化最后一行
for (int i = 0; i < triangle.get(row - 1).size(); i++) {
dp[row - 1][i] = triangle.get(row - 1).get(i);
}
// 动态规划
for (int i = row - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
return ret;
}
}https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ret);
return ret;
}
}https://leetcode-cn.com/problems/maximum-product-subarray/
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。dp
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int ans = Integer.MIN_VALUE;
int[] dpMax = new int[nums.length + 1];
int[] dpMin = new int[nums.length + 1];
dpMax[0] = 1;
dpMin[0] = 1;
for (int i = 1; i <= nums.length; i++) {
if (nums[i-1] < 0) {
int temp = dpMax[i-1];
dpMax[i-1] = dpMin[i-1];
dpMin[i-1] = temp;
}
dpMax[i] = Math.max(dpMax[i-1]*nums[i-1], nums[i-1]);
dpMin[i] = Math.min(dpMin[i-1]*nums[i-1], nums[i-1]);
ans = Math.max(ans, dpMax[i]);
}
return ans;
}
}https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null) return null;
// 双指针
int p1 = 0, p2 = numbers.length - 1;
while (p1 < p2) {
int sum = numbers[p1] + numbers[p2];
if (sum == target) return new int[]{p1+1, p2+1};
else if (sum < target) p1++;
else p2--;
}
return null;
}
}https://leetcode-cn.com/problems/rotate-array/
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int start, int end) {
while(start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}https://leetcode-cn.com/problems/invert-binary-tree/
4
/ \
2 7
/ \ / \
1 3 6 9
4
/ \
7 2
/ \ / \
9 6 3 1class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
}https://leetcode-cn.com/problems/valid-anagram/
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。输入: s = "anagram", t = "nagaram"
输出: true
输入: s = "rat", t = "car"
输出: falseclass Solution {
public boolean isAnagram(String s, String t) {
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnts[c - 'a']--;
}
for (int c : cnts) {
if (c != 0) return false;
}
return true;
}
}https://leetcode-cn.com/problems/find-the-duplicate-number/
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
输入: [1,3,4,2,2]
输出: 2
输入: [3,1,3,4,2]
输出: 3快慢指针
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}https://leetcode-cn.com/problems/is-subsequence/
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
s = "abc", t = "ahbgdc"
返回 true.
s = "axc", t = "ahbgdc"
返回 false.class Solution {
public boolean isSubsequence(String s, String t) {
// 这里用到了String到indexof
int inx = -1;
for (char c : s.toCharArray()) {
inx = t.indexOf(c, inx + 1);
if (inx == -1) return false;
}
return true;
}
}https://leetcode-cn.com/problems/add-two-numbers-ii/
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7双栈
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
ListNode head = new ListNode(-1);
int carray = 0;
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carray != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carray;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carray = sum / 10;
}
return head.next;
}
private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}
}https://leetcode-cn.com/problems/rectangle-overlap/
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：falseclass Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
if (rec2[1] >= rec1[3] || rec1[1] >= rec2[3]) {
return false;
}
if (rec1[0] >= rec2[2] || rec1[2] <= rec2[0]) {
return false;
}
return true;
}
}https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。class Solution {
public boolean hasGroupsSizeX(int[] deck) {
// hash
HashMap<Integer, Integer> map = new HashMap<>();
for(int num : deck) {
if(map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 最大公约数
int t = 0;
for(int a : map.values()) {
t = gcd(t, a);
}
return t >= 2;
}
// 最大公约数
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
输入：str1 = "LEET", str2 = "CODE"
输出：""class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
return str2.substring(0, gcd(str1.length(), str2.length()));
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} //源于离散数学及其应用的算法：（以3 4 5 2 1 为例）
//从后往前寻找第一次出现的正序对：（找到 4,5）
//之后因为从5 开始都是逆序，所以把他们反转就是正序：3 4 1 2 5
//之后4 的位置应该是：在它之后的，比他大的最小值（5）
//交换这两个值：得到 3 5 1 2 4
// 对于初始即为逆序的序列，将在反转步骤直接完成
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
if (len < 2) return;
int i = len - 1;
while (i > 0 && nums[i - 1] >= nums[i])
i--; // 从后向前找第一个正序，这里最后i指向的是逆序起始位置
reverse(nums, i, len - 1); // 翻转后面的逆序区域，使其变为正序
if (i == 0) return;
int j = i - 1;
while(i < len && nums[j] >= nums[i])
i++; // 找到第一个比nums[j]大的元素，交换即可
// 交换
swap(nums, i, j);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}https://leetcode-cn.com/problems/valid-sudoku/
class Solution {
public boolean isValidSudoku(char[][] board) {
// 记录某行，某位数字是否已经被摆放
boolean[][] row = new boolean[9][9];
// 记录某列，某位数字是否已经被摆放
boolean[][] col = new boolean[9][9];
// 记录某3x3宫格内，某位数字是否已经被摆放
boolean[][] block = new boolean[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '1';
int blockIdx = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || block[blockIdx][num]) {
return false;
} else {
row[i][num] = true;
col[j][num] = true;
block[blockIdx][num] = true;
}
}
}
}
return true;
}
}https://leetcode-cn.com/problems/combination-sum-ii/
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
Arrays.sort(candidates);
backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
boolean[] hasVisited, int start, int target, final int[] candidates) {
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
continue;
}
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
hasVisited[i] = true;
backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates);
hasVisited[i] = false;
tempCombination.remove(tempCombination.size() - 1);
}
}
}
}https://leetcode-cn.com/problems/permutations-ii/
给定一个可包含重复数字的序列，返回所有不重复的全排列。输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
Arrays.sort(nums); // 排序
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList));
return;
}
for (int i = 0; i < visited.length; i++) {
if (i != 0 && nums[i] == nums[i -1] && !visited[i - 1]) {
continue; // 防止重复
}
if (visited[i]) continue;
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
}给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}
}https://leetcode-cn.com/problems/word-search/
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 falseclass Solution {
private final static int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
private int m;
private int n;
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0 || board[0].length == 0) return false;
m = board.length;
n = board[0].length;
boolean[][] hasVisited = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (backtracking(0, r, c, hasVisited, board, word)) {
return true;
}
}
}
return false;
}
private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
if (curLen == word.length()) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) return false;
visited[r][c] = true;
for (int[] d : direction) {
if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) return true;
}
visited[r][c] = false;
return false;
}
}https://leetcode-cn.com/problems/decode-ways/
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。dp
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0) {
dp[i] += dp[i - 1];
}
if (s.charAt(i - 2) == '0') continue;
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}https://leetcode-cn.com/problems/balanced-binary-tree/
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
3
/ \
9 20
/ \
15 7
truelass Solution {
private boolean res = true;
public boolean isBalanced(TreeNode root) {
Depth(root);
return res;
}
private int Depth (TreeNode root) {
if (root == null) return 0;
int l = Depth(root.left);
int r = Depth(root.right);
if (Math.abs(l - r) > 1) res = false;;
return 1 + Math.max(l , r);
}
}https://leetcode-cn.com/problems/word-break/
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
来输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: falseclass Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word: wordDict) {
// 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word.equals(s.substring(i - len , i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}https://leetcode-cn.com/problems/contains-duplicate/
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
输入: [1,2,3,1]
输出: trueclass Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) {
return true;
}
}
return false;
}
}https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}https://leetcode-cn.com/problems/product-of-array-except-self/
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
输入: [1,2,3,4]
输出: [24,12,8,6]class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] products = new int[n];
Arrays.fill(products, 1);
int left = 1;
for (int i = 1; i < n; i++) {
left *= nums[i - 1];
products[i] *= left;
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
products[i] *= right;
}
return products;
}
}https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
给定两个数组，编写一个函数来计算它们的交集。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
ArrayList<Integer> list1 = new ArrayList<>();
for (int num : nums1) {
list1.add(num);
}
ArrayList<Integer> list2 = new ArrayList<>();
for (int num : nums2) {
if (list1.contains(num)) {
list2.add(num);
list1.remove(num);
}
}
return list2.stream().mapToInt(Integer::valueOf).toArray();
}
}https://leetcode-cn.com/problems/hamming-distance/
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;
}
}https://leetcode-cn.com/problems/subtree-of-another-tree/
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
3
/ \
4 5
/ \
1 2
4
/ \
1 2 class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
if (t == null && s == null) return true;
if (t == null || s == null) return false;
if (t.val != s.val) return false;
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
}https://leetcode-cn.com/problems/palindromic-substrings/
class Solution {
private int cnt = 0;
public int countSubstrings(String s) {
for (int i = 0; i < s.length(); i++) {
extendSubstrings(s, i, i); // 奇数长度
extendSubstrings(s, i, i + 1); // 偶数长度
}
return cnt;
}
private void extendSubstrings(String s, int start, int end) {
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
cnt++;
}
}
}https://leetcode-cn.com/problems/valid-palindrome-ii/ 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入: "aba"
输出: True
输入: "abca"
输出: True
解释: 你可以删除c字符。class Solution {
public boolean validPalindrome(String s) {
// 普通判断回文串用前后双指针即可，但是，难点在于如果去删除一个元素后的字符串是不是回文串
// 如果前后指针的元素不相等，此时子串的范围（i+1，j）或（j-1）的俩子串只要任意一个是，则结果是
// 否则，则不是
int i =0, j = s.length() - 1;
while(i < j) {
if(s.charAt(i) != s.charAt(j)) {
return isVaild(s, i+1, j) || isVaild(s, i, j-1);
}
i++;
j--;
}
return true;
}
public boolean isVaild(String s, int i, int j) {
while(i < j) {
if(s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}https://leetcode-cn.com/problems/lru-cache/
class LRUCache {
private int cap;
private Map<Integer, Integer> map = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
int value = map.get(key);
// 查一次，就将查到到仍在队尾
map.remove(key);
map.put(key,value);
return value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
} else if (map.size() == cap) {
// 满了
Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
iterator.next();
iterator.remove();
}
map.put(key, value);
}
}https://leetcode-cn.com/problems/subsets-ii/
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
continue;
}
tempSubset.add(nums[i]);
hasVisited[i] = true;
backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
hasVisited[i] = false;
tempSubset.remove(tempSubset.size() - 1);
}
}
}https://leetcode-cn.com/problems/surrounded-regions/
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
X X X X
X O O X
X X O X
X O X X
X X X X
X X X X
X X X X
X O X Xclass Solution {
private int[][] direction = {{0,1},{0,-1},{1,0},{-1,0}};
private int m, n;
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
m = board.length;
n = board[0].length;
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(board, 0, i);
dfs(board, m - 1, i);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int r, int c) {
if(r<0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
for (int[] d : direction) {
dfs(board, r + d[0], c + d[1]);
}
}
}https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
输入: [3,4,5,1,2]
输出: 1
输入: [4,5,6,7,0,1,2]
输出: 0class Solution {
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h]) {
h = m;
} else {
l = m + 1;
}
}
return nums[l];
}
}https://leetcode-cn.com/problems/number-of-1-bits/ 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans = 0;
while(n != 0) {
n &= n - 1;
ans++;
}
return ans;
}
}https://leetcode-cn.com/problems/house-robber-ii/
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int first, int last) {
int pre2 = 0, pre1 = 0;
for (int i = first; i <= last; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}https://leetcode-cn.com/problems/contains-duplicate-ii/
输入: nums = [1,2,3,1], k = 3
输出: true
输入: nums = [1,0,1,1], k = 1
输出: trueclass Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if(set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
}https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1class Solution {
public int kthSmallest(TreeNode root, int k) {
int leftCnt = count(root.left);
if (leftCnt == k - 1) return root.val;
if (leftCnt > k - 1) return kthSmallest(root.left, k);
return kthSmallest(root.right, k - leftCnt - 1);
}
private int count (TreeNode node) {
if (node == null) return 0;
return 1 + count(node.left) + count(node.right);
}
}https://leetcode-cn.com/problems/power-of-two/
输入: 1
输出: true
解释: 2的2次方 = 1
输入: 16
输出: true
解释: 2的四次方 = 16
输入: 218
输出: falseclass Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
}https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue {
private Stack<Integer> in;
private Stack<Integer> out;
/** Initialize your data structure here. */
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
in.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
in2Out();
return out.pop();
}
/** Get the front element. */
public int peek() {
in2Out();
return out.peek();
}
private void in2Out() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}https://leetcode-cn.com/problems/missing-number/
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
输入: [3,0,1]
输出: 2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8class Solution {
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret = ret ^ i ^ nums[i];
}
return ret ^ nums.length;
}
}https://leetcode-cn.com/problems/perfect-squares/
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
输入: n = 13
输出: 2
解释: 13 = 4 + 9.class Solution {
public int numSquares(int n) {
List<Integer> squareList = generateSquareList(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int square : squareList) {
if (square > i) break;
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}
private List<Integer> generateSquareList(int n) {
List<Integer> squareList = new ArrayList<>();
int diff = 3;
int square = 1;
while (square <= n) {
squareList.add(square);
square += diff;
diff += 2;
}
return squareList;
}
}https://leetcode-cn.com/problems/odd-even-linked-list/
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULLclass Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return head;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。class Solution {
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
cnt++;
}
}
if (cnt < k) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}
}https://leetcode-cn.com/problems/first-unique-character-in-a-string/
class Solution {
public int firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if(map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}https://leetcode-cn.com/problems/add-strings/
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
while (carry == 1 || i >= 0 || j >= 0) {
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
str.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return str.reverse().toString();
}
}https://leetcode-cn.com/problems/merge-two-binary-trees/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return null;
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}https://leetcode-cn.com/problems/partition-list/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode node1 = dummy1, node2 = dummy2;
while (head != null){
if (head.val < x){
node1.next = head;
head = head.next;
node1 = node1.next;
node1.next = null;
} else {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
}
}
node1.next = dummy2.next;
return dummy1.next;
}
}