二叉树层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class levelOrder {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
int count = queue.size();
List<Integer> list = new ArrayList<>();
while (count > 0) {
TreeNode remove = queue.remove();
list.add(remove.val);
if(remove.left!=null){
queue.add(remove.left);
}
if(remove.right!=null){
queue.add(remove.right);
}
count--;
}
result.add(list);
}
return result;
}
}
|
环形链表
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class hasCycle {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}
|
相交链表
1
2
3
4
5
6
7
8
9
10
11
| public class getIntersectionNode {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null && headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
|
约瑟夫环
https://leetcode.cn/problems/find-the-winner-of-the-circular-game/
每叫到k号移出一个人，就相当于胜者的位置向前移了k位，假设我们知道胜者的位置，用逆推思想得到递归公式。
1
2
3
4
5
6
7
8
9
| public class findTheWinner {
public int findTheWinner(int n, int k) {
int p = 0;
for (int i = 2; i <= n; i++) {
p = (p + k) % i;
}
return p + 1;
}
}
|
多数元素
https://leetcode.cn/problems/majority-element/?favorite=2cktkvj
1
2
3
4
5
6
| public class majorityElement {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
|
反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class reverseList {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
|
翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class invertTree {
public TreeNode invertTree(TreeNode root) {
invert(root);
return root;
}
public static void invert(TreeNode root) {
if (root == null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null) invert(root.left);
if (root.right != null) invert(root.right);
}
}
|
回文链表
转换成数组用双指针法不写了
反转后半部分链表并与前半链表比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public class isPalindrome {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
ListNode p1 = head;
ListNode p2 = reverseList(endOfFirstHalf(head).next);
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return result;
}
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
public static ListNode endOfFirstHalf(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
|
判断子序列
https://leetcode.cn/problems/is-subsequence/
双指针法不写
dp方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class isSubsequence {
public boolean isSubsequence(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[m + 1][26];
for (int i = 0; i < 26; i++) {
dp[m][i] = m;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
if (t.charAt(i) == 'a' + j)
dp[i][j] = i;
else
dp[i][j] = dp[i + 1][j];
}
}
int add = 0;
for (int i = 0; i < n; i++) {
if (dp[add][s.charAt(i) - 'a'] == m)
return false;
add = dp[add][s.charAt(i) - 'a'] + 1;
}
return true;
}
}
|
移动零
https://leetcode.cn/problems/move-zeroes/
暴力解
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class moveZeroes {
public void moveZeroes(int[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = i; j > 0; j--) {
if (nums[j - 1] == 0) {
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}
}
}
}
}
|
双指针一次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class moveZeroes {
public void moveZeroes(int[] nums) {
if (nums == null) return;
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j++;
}
}
}
}
|
比特位计数
https://leetcode.cn/problems/counting-bits/
暴力解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class countBits {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0; i <= n; i++) {
int count = 0;
int j = i;
while (j != 0) {
if (j % 2 == 1)
count++;
j /= 2;
}
result[i] = count;
}
return result;
}
}
|
万物皆可dp。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class countBits {
public int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0; i <= n; i++) {
if (i % 2 == 0) {
result[i] = result[i / 2];
}
if (i % 2 == 1) {
result[i] = result[i - 1] + 1;
}
}
return result;
}
}
|
找到所有数组中消失的数字
https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class findDisappearedNumbers {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0)
result.add(i + 1);
}
return result;
}
}
|
汉明距离
https://leetcode.cn/problems/hamming-distance/?favorite=2cktkvj
1
2
3
4
5
| public class hammingDistance {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
|
两数相加
https://leetcode.cn/problems/add-two-numbers/?favorite=2cktkvj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class addTwoNumbers {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
if (carry > 0)
tail.next = new ListNode(carry);
return head;
}
}
|
无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class lengthOfLongestSubstring {
public int lengthOfLongestSubstring(String s) {
int max = 0;
int left = 0;
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (hashMap.containsKey(s.charAt(i))) {
left = Math.max(left, hashMap.get(s.charAt(i)) + 1);
}
hashMap.put(s.charAt(i), i);
max = Math.max(max, i - left + 1);
}
return max;
}
}
|
