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

Commitb08db0e

Browse files
committed
3Sum
1 parentc84a78d commitb08db0e

File tree

2 files changed

+94
-6
lines changed

2 files changed

+94
-6
lines changed

‎adventOfCode/2018/AdventOfCode2018.ipynb

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2194,7 +2194,7 @@
21942194
},
21952195
{
21962196
"cell_type":"code",
2197-
"execution_count":240,
2197+
"execution_count":21,
21982198
"metadata": {
21992199
"scrolled":true
22002200
},
@@ -2205,7 +2205,7 @@
22052205
},
22062206
{
22072207
"cell_type":"code",
2208-
"execution_count":241,
2208+
"execution_count":22,
22092209
"metadata": {},
22102210
"outputs": [
22112211
{
@@ -2215,10 +2215,9 @@
22152215
"traceback": [
22162216
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
22172217
"\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
2218-
"\u001b[0;32m<ipython-input-241-1647e797e953>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 54\u001b[0m \u001b[0mip_reg\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mprogram\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mload_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlines\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 55\u001b[0m \u001b[0mregs\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 56\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrun_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mip_reg\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mprogram\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
2219-
"\u001b[0;32m<ipython-input-241-1647e797e953>\u001b[0m in \u001b[0;36mrun_program\u001b[0;34m(regs, ip_reg, program, max_cycles)\u001b[0m\n\u001b[1;32m 42\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mip\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 43\u001b[0m \u001b[0mfunc_name\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mprogram\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 44\u001b[0;31m \u001b[0mrun_opcode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfunc_name\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 45\u001b[0m \u001b[0mip\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 46\u001b[0m \u001b[0mcycles\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
2220-
"\u001b[0;32m<ipython-input-241-1647e797e953>\u001b[0m in \u001b[0;36mrun_opcode\u001b[0;34m(regs, func_name, *args)\u001b[0m\n\u001b[1;32m 22\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mfunc_name\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfunctions\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 23\u001b[0m \u001b[0;31m#print(*args)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 24\u001b[0;31m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunctions\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mfunc_name\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 25\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 26\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mload_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlines\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
2221-
"\u001b[0;32m<ipython-input-241-1647e797e953>\u001b[0m in \u001b[0;36m<lambda>\u001b[0;34m(regs, a, b, c)\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0;34m'addi'\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;34m'mulr'\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0;34m'muli'\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 6\u001b[0m \u001b[0;34m'banr'\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m&\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;34m'bani'\u001b[0m \u001b[0;34m:\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m&\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
2218+
"\u001b[0;32m<ipython-input-22-1647e797e953>\u001b[0m in\u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m 54\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mprogram\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mload_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlines\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 55\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 56\u001b[0;31m\u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrun_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mprogram\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
2219+
"\u001b[0;32m<ipython-input-22-1647e797e953>\u001b[0m in \u001b[0;36mrun_program\u001b[0;34m(regs, ip_reg, program, max_cycles)\u001b[0m\n\u001b[1;32m 42\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mip\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 43\u001b[0m \u001b[0mfunc_name\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mprogram\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 44\u001b[0;31m \u001b[0mrun_opcode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfunc_name\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mb\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 45\u001b[0m \u001b[0mip\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mip_reg\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 46\u001b[0m \u001b[0mcycles\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
2220+
"\u001b[0;32m<ipython-input-22-1647e797e953>\u001b[0m in \u001b[0;36mrun_opcode\u001b[0;34m(regs, func_name, *args)\u001b[0m\n\u001b[1;32m 22\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mfunc_name\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfunctions\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 23\u001b[0m \u001b[0;31m#print(*args)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 24\u001b[0;31m \u001b[0mregs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunctions\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mfunc_name\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mregs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 25\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 26\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mload_program\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlines\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
22222221
"\u001b[0;31mKeyboardInterrupt\u001b[0m:"
22232222
]
22242223
}
@@ -2279,6 +2278,11 @@
22792278
"#solution 1\n",
22802279
"ip_reg, program = load_program(lines)\n",
22812280
"regs = [0]*6\n",
2281+
"\n",
2282+
"num = 5000000\n",
2283+
"min_num = (0, 0)\n",
2284+
"for i in range(num):\n",
2285+
"\n",
22822286
"print(run_program(regs, ip_reg, program)[0])"
22832287
]
22842288
},

‎leetcode/15-3Sum.cpp

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
classSolution {
2+
3+
#defineV std::vector
4+
using vi = V<int>;
5+
6+
public:
7+
8+
V<vi>threeSum(vi& nums)
9+
{
10+
V<vi> res;
11+
12+
// Sort numbers (increasing order)
13+
std::sort(nums.begin(), nums.end());
14+
//print_vec(nums);
15+
16+
for (int i =0; i < nums.size(); i++)
17+
{
18+
// Skip the same values
19+
if (i>0 && nums[i-1] == nums[i])
20+
{
21+
continue;
22+
}
23+
// Set the indexes
24+
int sum =0;
25+
int left_idx = i +1;
26+
int right_idx = nums.size()-1;
27+
constint value = nums[i];
28+
while (left_idx < right_idx)
29+
{
30+
sum = value + nums[left_idx] + nums[right_idx];
31+
// If sum == 0, add it to the result checking if already exist
32+
if (sum ==0)
33+
{
34+
//std::cout<<"value: "<<value<<" l_idx: "<<left_idx<<" r_idx: "<<right_idx<<'\n';
35+
//std::cout<<'['<<value<<','<<nums[left_idx]<<','<<nums[right_idx]<<"]\n";
36+
res.push_back({value, nums[left_idx], nums[right_idx]});
37+
38+
// Skip the same values
39+
while(left_idx < nums.size()-1 && nums[left_idx] == nums[left_idx+1])
40+
{
41+
left_idx++;
42+
}
43+
left_idx++;
44+
45+
// Skip the same values
46+
while(right_idx >0 && nums[right_idx] == nums[right_idx-1])
47+
{
48+
right_idx--;
49+
}
50+
right_idx--;
51+
}
52+
// If sum < 0, increase the left_idx
53+
elseif (sum <0)
54+
{
55+
// Skip the same values
56+
while(left_idx < nums.size()-1 && nums[left_idx] == nums[left_idx+1])
57+
{
58+
left_idx++;
59+
}
60+
left_idx++;
61+
}
62+
// If sum > 0, decrease the right index
63+
else
64+
{
65+
// Skip the same values
66+
while(right_idx >0 && nums[right_idx] == nums[right_idx-1])
67+
{
68+
right_idx--;
69+
}
70+
right_idx--;
71+
}
72+
}
73+
}
74+
return res;
75+
}
76+
77+
78+
private:
79+
voidprint_vec(const vector<int>& v)
80+
{
81+
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout,""));
82+
std::cout <<'\n';
83+
}
84+
};

0 commit comments

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