Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0c99dbb

Browse files
committed
feat: add some solution for leetcode.
1 parent8ad7320 commit0c99dbb

File tree

7 files changed

+238
-5
lines changed

7 files changed

+238
-5
lines changed

‎src/com/yeahqing/easy/_0001/Solution.javarenamed to‎src/com/yeahqing/easy/_001/Solution.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
1-
packagecom.yeahqing.easy._0001;
1+
packagecom.yeahqing.easy._001;
22

33
importcom.yeahqing.structure.Interval;
4-
importcom.yeahqing.util.IOUtil;
54

6-
importjava.util.*;
5+
importjava.util.Arrays;
6+
importjava.util.HashMap;
77

88
/**
99
* @author YeahQing
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packagecom.yeahqing.hard._004;
2+
3+
/**
4+
* @author YeahQing
5+
* @date 2022/9/29
6+
*/
7+
classSolution {
8+
/**
9+
* 给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的中位数 。
10+
* 算法的时间复杂度应该为 O(log (m+n)) 。
11+
* @param nums1 数组1
12+
* @param nums2 数组2
13+
* @return 中位数
14+
*/
15+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
16+
if (nums1.length >nums2.length) {
17+
returnfindMedianSortedArrays(nums2,nums1);
18+
}
19+
20+
intm =nums1.length;
21+
intn =nums2.length;
22+
intleft =0,right =m;
23+
// median1：前一部分的最大值
24+
// median2：后一部分的最小值
25+
intmedian1 =0,median2 =0;
26+
27+
while (left <=right) {
28+
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
29+
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
30+
inti = (left +right) /2;
31+
intj = (m +n +1) /2 -i;
32+
33+
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
34+
intnums_im1 = (i ==0 ?Integer.MIN_VALUE :nums1[i -1]);
35+
intnums_i = (i ==m ?Integer.MAX_VALUE :nums1[i]);
36+
intnums_jm1 = (j ==0 ?Integer.MIN_VALUE :nums2[j -1]);
37+
intnums_j = (j ==n ?Integer.MAX_VALUE :nums2[j]);
38+
39+
if (nums_im1 <=nums_j) {
40+
median1 =Math.max(nums_im1,nums_jm1);
41+
median2 =Math.min(nums_i,nums_j);
42+
left =i +1;
43+
}else {
44+
right =i -1;
45+
}
46+
}
47+
48+
return (m +n) %2 ==0 ? (median1 +median2) /2.0 :median1;
49+
}
50+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packagecom.yeahqing.jianzhioffer._1_056_1;
2+
3+
importcom.yeahqing.structure.Interval;
4+
5+
importjava.util.Arrays;
6+
7+
/**
8+
* @author YeahQing
9+
* @date 2022/9/28
10+
*/
11+
classSolution {
12+
/**
13+
* 剑指 Offer 56 - I. 数组中数字出现的次数 middle
14+
* 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
15+
* @param nums = [4,1,4,6]
16+
* @return int[]
17+
*/
18+
publicint[]singleNumbers(int[]nums) {
19+
// 1. 所有值做异或，只出现一次的两个数字异或一定不为0
20+
intnum =0;
21+
for (intn :nums) {
22+
// num = a ^ b, a和b表示只出现一次的两个数字
23+
num ^=n;
24+
}
25+
// 2. 找到最低位的1
26+
intdiv =1;
27+
while ((div &num) ==0) {
28+
div <<=1;// 从最低位开始判断num哪一位为1
29+
}
30+
// 3. 按照这一位将原数组分组，就是把a和b分别分到两组，之后进行异或就可以得到两个只出现一次的数字
31+
inta =0,b =0;
32+
for (intn :nums) {
33+
// 同样的数字与的结果一定是相同的，也就是会分到同一个组
34+
if ((div &n) ==0) {
35+
a ^=n;
36+
}else {
37+
b ^=n;
38+
}
39+
}
40+
returnnewint[]{a,b};
41+
}
42+
43+
publicstaticvoidmain(String[]args) {
44+
Solutionsolution =newSolution();
45+
int[]nums =Interval.createTestData("[4,1,4,6]");
46+
int[]ret =solution.singleNumbers(nums);
47+
System.out.println(Arrays.toString(ret));
48+
}
49+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packagecom.yeahqing.jianzhioffer._2_001;
2+
3+
/**
4+
* @author YeahQing
5+
* @date 2022/9/28
6+
*/
7+
classSolution {
8+
/***
9+
* 剑指 Offer II 001. 整数除法
10+
* 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。
11+
* 注意：
12+
* 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2
13+
* 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,2^31−1]。本题中，如果除法结果溢出，则返回 2^31−1
14+
* @param a 整数a
15+
* @param b 整数b
16+
* @return a/b
17+
*/
18+
publicintdivide(inta,intb) {
19+
intMIN =Integer.MIN_VALUE,MAX =Integer.MAX_VALUE;
20+
intMIN_LIMIT =MIN >>1;// -1073741824
21+
if(a ==MIN &&b == -1)returnMAX;// 特判
22+
booleanisPos = (a >=0 ||b <=0) && (a <=0 ||b >=0);
23+
if(a >0)a = -a;
24+
if(b >0)b = -b;
25+
intans =0;// 最终的商
26+
while(a <=b) {
27+
intd =b,c =1;// d为当前除数，c为当前商
28+
while(d >=MIN_LIMIT &&d +d >=a) {// 通过第一个条件防止d + d溢出
29+
d +=d;// 当前除数倍增，也可以用 d <<= 1;
30+
c +=c;// 当前商倍增，也可以用 c <<= 1;
31+
}
32+
a -=d;// a剩余部分
33+
ans +=c;// 累计当前商
34+
}
35+
returnisPos ?ans : -ans;
36+
}
37+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packagecom.yeahqing.medium._002;
2+
3+
importcom.yeahqing.structure.ListNode;
4+
5+
/**
6+
* @author YeahQing
7+
* @date 2022/9/29
8+
*/
9+
classSolution {
10+
/***
11+
* 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
12+
* 请你将两个数相加，并以相同形式返回一个表示和的链表。
13+
* 来源：力扣（LeetCode）
14+
* @param l1 非空链表1
15+
* @param l2 非空链表2
16+
* @return l1 + l2
17+
*/
18+
publicListNodeaddTwoNumbers(ListNodel1,ListNodel2) {
19+
ListNodepre =newListNode();
20+
ListNodecur =pre;
21+
intcarry =0;
22+
while (l1 !=null ||l2 !=null) {
23+
inta =l1 ==null ?0 :l1.val;
24+
intb =l2 ==null ?0 :l2.val;
25+
intsum =a +b +carry;
26+
carry =sum /10;
27+
sum %=10;
28+
cur.next =newListNode(sum);
29+
cur =cur.next;
30+
if (l1 !=null)l1 =l1.next;
31+
if (l2 !=null)l2 =l2.next;
32+
}
33+
if (carry ==1) {
34+
cur.next =newListNode(carry);
35+
}
36+
returnpre.next;
37+
}
38+
}
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packagecom.yeahqing.structure;
2+
3+
/**
4+
* @author YeahQing
5+
* @date 2022/9/29
6+
* Definition for singly-linked list.
7+
*/
8+
publicclassListNode {
9+
publicintval;
10+
publicListNodenext;
11+
publicListNode() {}
12+
publicListNode(intval) {this.val =val; }
13+
publicListNode(intval,ListNodenext) {this.val =val;this.next =next; }
14+
}
15+

‎src/com/yeahqing/util/IOUtil.java

Lines changed: 46 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,15 +9,59 @@
99
* @date 2022/9/28
1010
*/
1111
publicclassIOUtil {
12-
publicstaticint[]readNums() {
12+
/***
13+
* 读取一行以正则表达式分割的数组，[1,2,3,4] "," or [1_2_3_4] "_" or [1 2 3 4] " "
14+
* @return int[]
15+
*/
16+
publicstaticint[]readNums(Stringregex) {
1317
Scannerscan =newScanner(System.in);
1418

15-
String[]arr =scan.nextLine().split(",");
19+
String[]arr =scan.nextLine().split(regex);
1620

1721
int[]nums =newint[arr.length];
1822
for (inti =0;i <nums.length;i++) {
1923
nums[i] =Integer.parseInt(arr[i]);
2024
}
2125
returnnums;
2226
}
27+
28+
/***
29+
* 读取一个整数n并返回一个nxn的二维数组
30+
* @param eq 是否是方阵，即行列是否相同
31+
* @return int[][]
32+
*/
33+
publicstaticint[][]readArr2D(booleaneq) {
34+
Scannerscan =newScanner(System.in);
35+
intn =scan.nextInt();
36+
intm =eq ?n :scan.nextInt();
37+
int[][]arr =newint[n][m];
38+
for (inti =0;i <n;i++) {
39+
for (intj =0;j <m;j++) {
40+
arr[i][j] =scan.nextInt();
41+
}
42+
}
43+
returnarr;
44+
}
45+
46+
publicstaticvoidreadArr2DType2() {
47+
Scannerscan =newScanner(System.in);
48+
intT =scan.nextInt();
49+
while (T >0) {
50+
T--;
51+
intm =scan.nextInt();
52+
intn =scan.nextInt();
53+
int[][]arr =newint[m][n];
54+
for (inti =0;i <n;i++) {
55+
for (intj =0;j <m;j++) {
56+
arr[i][j] =scan.nextInt();
57+
}
58+
}
59+
60+
for (int[]row :arr)
61+
for (intv :row)
62+
System.out.println(v);
63+
64+
}
65+
}
66+
2367
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp