8000 jz offer · rchen102/Leetcode-Notes@1c9f944 · GitHub
[go: up one dir, main page]
Skip to content

Commit 1c9f944

Browse files
author
rchen102
committed
jz offer
1 parent 6b4da6d commit 1c9f944

File tree

5 files changed

+202
-0
lines changed

5 files changed

+202
-0
lines changed

‎JZandNC/jz 17.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
class Solution {
2+
public int[] printNumbers(int n) {
3+
char[] arr = new char[n+1];
4+
List<Integer> res = new ArrayList<>();
5+
Arrays.fill(arr, '0');
6+
while (increment(arr)) {
7+
res.add(Integer.parseInt(new String(arr)));
8+
}
9+
return res.stream().mapToInt(Integer::intValue).toArray();
10+
}
11+
12+
public boolean increment(char[] num) {
13+
int carry = 1;
14+
for (int i = num.length - 1; i >= 0; i--) {
15+
if (carry == 0) break;
16+
char cur = num[i];
17+
int val = cur - '0';
18+
int sum = carry + val;
19+
// 判断是否需要进位
20+
if (sum >= 10) {
21+
carry = 1;
22+
sum -= 10;
23+
} else {
24+
carry = 0;
25+
}
26+
num[i] = (char) ('0' + sum);
27+
}
28+
if (num[0] != '0') return false;
29+
return true;
30+
}
31+
}

‎JZandNC/jz 26.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
class Solution {
2+
public boolean isSubStructure(TreeNode A, TreeNode B) {
3+
if (A == null || B == null) return false;
4+
boolean res = dfs(A, B);
5+
if (res) return true;
6+
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
7+
}
8+
9+
public boolean dfs(TreeNode A, TreeNode B) {
10+
if (B == null) return true; // B 已经遍历完了
11+
if (A == null) return false; // A 已经遍历完了，B 还没有
12+
if (A.val != B.val) return false;
13+
return dfs(A.left, B.left) && dfs(A.right, B.right);
14+
}
15+
}

‎JZandNC/jz 46.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class Solution {
2+
public int translateNum(int num) {
3+
// 1. 从前往后，dp 推导（本题不太方便）
4+
// dp[i] 以 nums[i] 结尾的字符串，可以翻译的数量，下标从 1 开始
5+
// dp[i] = dp[i-1] 或者 dp[i-1] + dp[i-2]（当 nums[i] 和 nums[i-1] 组成的元素 < 26）
6+
// 2. 从后往前计算，本质相同
7+
// dp[i] [i..end] 这部分可以组成的字符串数量
8+
int prev = 1; // dp[0]
9+
int cur< 8000 /span> = 1; // dp[1]
10+
int prevDigit = num % 10;
11+
num = num / 10;
12+
while (num != 0) {
13+
int digit = num % 10;
14+
num = num / 10;
15+
// 计算翻译方法
16+
int res = cur;
17+
if (digit != 0 && digit * 10 + prevDigit <= 25) res += prev;
18+
// 更新相关参数，为下轮循环做准备
19+
prev = cur;
20+
cur = res;
21+
prevDigit = digit;
22+
}
23+
return cur;
24+
}
25+
}

‎JZandNC/jz 50.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// LinkedHashMap
2+
class Solution {
3+
public char firstUniqChar(String s) {
4+
if (s.length() == 0) return ' ';
5+
Map<Character, Integer> map = new LinkedHashMap<>();
6+
for (char ch : s.toCharArray()) {
7+
map.put(ch, map.getOrDefault(ch, 0) + 1);
8+
}
9+
for (char ch : map.keySet()) {
10+
if (map.get(ch) == 1) return ch;
11+
}
12+
return ' ';
13+
}
14+
}
15+
16+
17+
18+
// map 中存储 idx+1，避免 0 有歧义
19+
class Solution {
20+
public char firstUniqChar(String s) {
21+
9E88 if (s.length() == 0) return ' ';
22+
int[] map = new int[256];
23+
for (int i = 0; i < s.length(); i++) {
24+
char ch = s.charAt(i);
25+
if (map[ch] == 0) map[ch] = i+1;
26+
else if (map[ch] >= 1) map[ch] = -1; // 重复出现了，失去了资格
27+
}
28+
int minIdx = s.length();
29+
for (int i = 0; i < map.length; i++) {
30+
if (map[i]-1 >= 0) {
31+
minIdx = Math.min(minIdx, map[i]-1);
32+
}
33+
}
34+
if (minIdx == s.length()) return ' ';
35+
return s.charAt(minIdx);
36+
}
37+
}
38+
39+
// 初始化 map 为 -1
40+
class Solution {
41+
public char firstUniqChar(String s) {
42+
if (s.length() == 0) return ' ';
43+
int[] map = new int[256];
44+
Arrays.fill(map, -1);
45+
for (int i = 0; i < s.length(); i++) {
46+
char ch = s.charAt(i);
47+
if (map[ch] == -1) map[ch] = i;
48+
else if (map[ch] >= 0) map[ch] = -2; // 重复出现了，失去了资格
49+
}
50+
int minIdx = s.length();
51+
for (int i = 0; i < map.length; i++) {
52+
if (map[i] >= 0) {
53+
minIdx = Math.min(minIdx, map[i]);
54+
}
55+
}
56+
if (minIdx == s.length()) return ' ';
57+
return s.charAt(minIdx);
58+
}
59+
}

‎JZandNC/jz 51.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
// 就是个归并排序，不过在归并排序过程中统计了一下逆序对
2+
class Solution {
3+
public int reversePairs(int[] nums) {
4+
// 利用归并排序，合并时，进行计算
5+
if (nums == null || nums.length == 0) return 0;
6+
return countReverse(nums, 0, nums.length - 1);
7+
}
8+
9+
int countReverse(int[] arr, int lo, int hi) {
10+
if (lo >= hi) return 0;
11+
int mid = lo + ((hi - lo) >> 1);
12+
int left = countReverse(arr, lo, mid);
13+
int right = countReverse(arr, mid+1, hi);
14+
int res = merge(arr, lo, hi);
15+
return res + left + right;
16+
}
17+
18+
// merge [lo, mid] [mid+1, hi]
19+
int merge(int[] arr, int lo, int hi) {
20+
int mid = lo + ((hi - lo) >> 1);
21+
int[] tmp = new int[hi-lo+1];
22+
int i = lo, j = mid+1, k = 0;
23+
int res = 0;
24+
while (i <= mid && j <= hi) {
25+
if (arr[i] <= arr[j]) {
26+
tmp[k++] = arr[i++];
27+
}
28+
else {
29+
tmp[k++] = arr[j++];
30+
res += mid - i + 1;
31+
}
32+
}
33+
while (i <= mid) tmp[k++] = arr[i++];
34+
while (j <= hi) tmp[k++] = arr[j++];
35+
k = 0;
36+
while (k < hi - lo + 1) {
37+
arr[lo+k] = tmp[k];
38+
k++;
39+
}
40+
return res;
41+
}
42+
}
43+
44+
45+
// 会超时
46+
class Solution {
47+
public int reversePairs(int[] nums) {
48+
// 冒泡排序，每次交换，逆序度减一
49+
// 插入排序，每次移动，逆序度减一
50+
int res = 0;
51+
int n = nums.length;
52+
boolean flag; // 本轮交换是否有数据交换
53+
for (int i = 0; i < n; i++) {
54+
flag = false;
55+
for (int j = 0; j < n - i - 1; j++) {
56+
if (nums[j] > nums[j+1]) {
57+
swap(nums, j ,j+1);
58+
flag = true;
59+
res++;
60+
}
61+
}
62+
if (!flag) break;
63+
}
64+
return res;
65+
}
66+
67+
void swap(int[] arr, int a, int b) {
68+
int tmp = arr[a];
69+
arr[a] = arr[b];
70+
arr[b] = tmp;
71+
}
72+
}

0 commit comments

Comments
 (0)
0