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

Commit4987697

Browse files
author
applewjg
committed
FirstMissingPositive MultiplyString
Change-Id: Ifc15f13e1eafe05764a65f31ebc4180de554a853
1 parentaa4ab7a commit4987697

File tree

2 files changed

+85
-0
lines changed

2 files changed

+85
-0
lines changed

‎FirstMissingPositive.java

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 20, 2014
4+
Problem: First Missing Positive
5+
Difficulty: Medium
6+
Source: https://oj.leetcode.com/problems/first-missing-positive/
7+
Notes:
8+
Given an unsorted integer array, find the first missing positive integer.
9+
For example,
10+
Given [1,2,0] return 3,
11+
and [3,4,-1,1] return 2.
12+
Your algorithm should run in O(n) time and uses constant space.
13+
14+
Solution: Although we can only use constant space, we can still exchange elements within input A!
15+
Swap elements in A and try to make all the elements in A satisfy: A[i] == i + 1.
16+
Pick out the first one that does not satisfy A[i] == i + 1.
17+
*/
18+
publicclassSolution {
19+
publicintfirstMissingPositive_1(int[]A) {
20+
for(inti=0;i<A.length;i++)
21+
if(A[i]<=0)A[i]=A.length+2;
22+
for(inti=0;i<A.length;i++)
23+
{
24+
if(Math.abs(A[i])<A.length+1)
25+
{
26+
intcur =Math.abs(A[i])-1;
27+
A[cur] = -Math.abs(A[cur]);
28+
}
29+
}
30+
for(inti=0;i<A.length;i++)
31+
if(A[i]>0)returni+1;
32+
returnA.length+1;
33+
}
34+
intfirstMissingPositive_2(intA[],intn) {
35+
for(inti=0;i<n;i++){
36+
while(A[i]>=1&&A[i]<=n&&A[i]!=A[A[i]-1]) {
37+
inttmp =A[i];
38+
A[i] =A[tmp -1];
39+
A[tmp -1] =tmp;
40+
}
41+
}
42+
inti=0;
43+
for(i=0;i<n;i++){
44+
if(A[i]!=i+1)break;
45+
}
46+
returni+1;
47+
}
48+
}

‎MultiplyStrings.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 20, 2014
4+
Problem: Multiply Strings
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/multiply-strings/
7+
Notes:
8+
Given two numbers represented as strings, return multiplication of the numbers as a string.
9+
Note: The numbers can be arbitrarily large and are non-negative.
10+
11+
Solution: Just like what we do when multiplying integers.
12+
*/
13+
publicclassSolution {
14+
publicStringmultiply(Stringnum1,Stringnum2) {
15+
intl1 =num1.length(),l2 =num2.length();
16+
if (l1 ==0 ||l2 ==0)returnnewString("");
17+
if (num1.charAt(0) =='0' ||num2.charAt(0) =='0')returnnewString("0");
18+
StringBuffersb =newStringBuffer();
19+
int[]res =newint[l1+l2];
20+
for (inti =0;i <l1; ++i) {
21+
for (intj =0;j <l2; ++j) {
22+
res[i+j+1] += (num1.charAt(i)-'0') *(num2.charAt(j)-'0');
23+
}
24+
}
25+
intc =0;
26+
for (inti =res.length -1;i>=1; --i) {
27+
res[i] +=c;
28+
c =res[i] /10;
29+
res[i] =res[i] %10;
30+
sb.insert(0,res[i]);
31+
}
32+
if (c !=0 ||res[0] !=0) {
33+
sb.insert(0,c+res[0]);
34+
}
35+
returnsb.toString();
36+
}
37+
}

0 commit comments

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