Skip to content

Commit 6fa0f9d

Browse files
zhedahhtzhedahht
committed
Initial commit for question 59(2)
1 parent a9f4a45 commit 6fa0f9d

5 files changed

Lines changed: 324 additions & 1 deletion

File tree

‎59_01_MaxInSlidingWindow/MaxInSlidingWindow.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ vector<int> maxInWindows(const vector<int>& num, unsigned int size)
4646
return maxInWindows;
4747
}
4848

49-
// ==================== Test Code ====================
49+
// ====================测试代码====================
5050
void Test(const char* testName, const vector<int>& num, unsigned int size, const vector<int>& expected)
5151
{
5252
if(testName != nullptr)

‎59_02_QueueWithMax/59_02_QueueWithMax.vcxproj‎

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<ItemGroup Label="ProjectConfigurations">
4+
<ProjectConfiguration Include="Debug|Win32">
5+
<Configuration>Debug</Configuration>
6+
<Platform>Win32</Platform>
7+
</ProjectConfiguration>
8+
<ProjectConfiguration Include="Release|Win32">
9+
<Configuration>Release</Configuration>
10+
<Platform>Win32</Platform>
11+
</ProjectConfiguration>
12+
<ProjectConfiguration Include="Debug|x64">
13+
<Configuration>Debug</Configuration>
14+
<Platform>x64</Platform>
15+
</ProjectConfiguration>
16+
<ProjectConfiguration Include="Release|x64">
17+
<Configuration>Release</Configuration>
18+
<Platform>x64</Platform>
19+
</ProjectConfiguration>
20+
</ItemGroup>
21+
<PropertyGroup Label="Globals">
22+
<ProjectGuid>{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}</ProjectGuid>
23+
<Keyword>Win32Proj</Keyword>
24+
<RootNamespace>My59_02_QueueWithMax</RootNamespace>
25+
<WindowsTargetPlatformVersion>8.1</WindowsTargetPlatformVersion>
26+
</PropertyGroup>
27+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
28+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
29+
<ConfigurationType>Application</ConfigurationType>
30+
<UseDebugLibraries>true</UseDebugLibraries>
31+
<PlatformToolset>v140</PlatformToolset>
32+
<CharacterSet>Unicode</CharacterSet>
33+
</PropertyGroup>
34+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration">
35+
<ConfigurationType>Application</ConfigurationType>
36+
<UseDebugLibraries>false</UseDebugLibraries>
37+
<PlatformToolset>v140</PlatformToolset>
38+
<WholeProgramOptimization>true</WholeProgramOptimization>
39+
<CharacterSet>Unicode</CharacterSet>
40+
</PropertyGroup>
41+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration">
42+
<ConfigurationType>Application</ConfigurationType>
43+
<UseDebugLibraries>true</UseDebugLibraries>
44+
<PlatformToolset>v140</PlatformToolset>
45+
<CharacterSet>Unicode</CharacterSet>
46+
</PropertyGroup>
47+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration">
48+
<ConfigurationType>Application</ConfigurationType>
49+
<UseDebugLibraries>false</UseDebugLibraries>
50+
<PlatformToolset>v140</PlatformToolset>
51+
<WholeProgramOptimization>true</WholeProgramOptimization>
52+
<CharacterSet>Unicode</CharacterSet>
53+
</PropertyGroup>
54+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
55+
<ImportGroup Label="ExtensionSettings">
56+
</ImportGroup>
57+
<ImportGroup Label="Shared">
58+
</ImportGroup>
59+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
60+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
61+
</ImportGroup>
62+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
63+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
64+
</ImportGroup>
65+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
66+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
67+
</ImportGroup>
68+
<ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
69+
<Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
70+
</ImportGroup>
71+
<PropertyGroup Label="UserMacros" />
72+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
73+
<LinkIncremental>true</LinkIncremental>
74+
</PropertyGroup>
75+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
76+
<LinkIncremental>true</LinkIncremental>
77+
</PropertyGroup>
78+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
79+
<LinkIncremental>false</LinkIncremental>
80+
</PropertyGroup>
81+
<PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
82+
<LinkIncremental>false</LinkIncremental>
83+
</PropertyGroup>
84+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
85+
<ClCompile>
86+
<PrecompiledHeader>
87+
</PrecompiledHeader>
88+
<WarningLevel>Level3</WarningLevel>
89+
<Optimization>Disabled</Optimization>
90+
<PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
91+
</ClCompile>
92+
<Link>
93+
<SubSystem>Console</SubSystem>
94+
<GenerateDebugInformation>true</GenerateDebugInformation>
95+
</Link>
96+
</ItemDefinitionGroup>
97+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
98+
<ClCompile>
99+
<PrecompiledHeader>
100+
</PrecompiledHeader>
101+
<WarningLevel>Level3</WarningLevel>
102+
<Optimization>Disabled</Optimization>
103+
<PreprocessorDefinitions>_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
104+
</ClCompile>
105+
<Link>
106+
<SubSystem>Console</SubSystem>
107+
<GenerateDebugInformation>true</GenerateDebugInformation>
108+
</Link>
109+
</ItemDefinitionGroup>
110+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
111+
<ClCompile>
112+
<WarningLevel>Level3</WarningLevel>
113+
<PrecompiledHeader>
114+
</PrecompiledHeader>
115+
<Optimization>MaxSpeed</Optimization>
116+
<FunctionLevelLinking>true</FunctionLevelLinking>
117+
<IntrinsicFunctions>true</IntrinsicFunctions>
118+
<PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
119+
</ClCompile>
120+
<Link>
121+
<SubSystem>Console</SubSystem>
122+
<EnableCOMDATFolding>true</EnableCOMDATFolding>
123+
<OptimizeReferences>true</OptimizeReferences>
124+
<GenerateDebugInformation>true</GenerateDebugInformation>
125+
</Link>
126+
</ItemDefinitionGroup>
127+
<ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
128+
<ClCompile>
129+
<WarningLevel>Level3</WarningLevel>
130+
<PrecompiledHeader>
131+
</PrecompiledHeader>
132+
<Optimization>MaxSpeed</Optimization>
133+
<FunctionLevelLinking>true</FunctionLevelLinking>
134+
<IntrinsicFunctions>true</IntrinsicFunctions>
135+
<PreprocessorDefinitions>NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
136+
</ClCompile>
137+
<Link>
138+
<SubSystem>Console</SubSystem>
139+
<EnableCOMDATFolding>true</EnableCOMDATFolding>
140+
<OptimizeReferences>true</OptimizeReferences>
141+
<GenerateDebugInformation>true</GenerateDebugInformation>
142+
</Link>
143+
</ItemDefinitionGroup>
144+
<ItemGroup>
145+
<ClCompile Include="QueueWithMax.cpp" />
146+
</ItemGroup>
147+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
148+
<ImportGroup Label="ExtensionTargets">
149+
</ImportGroup>
150+
</Project>

‎59_02_QueueWithMax/59_02_QueueWithMax.vcxproj.filters‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<ItemGroup>
4+
<Filter Include="Source Files">
5+
<UniqueIdentifier>{4FC737F1-C7A5-4376-A066-2A32D752A2FF}</UniqueIdentifier>
6+
<Extensions>cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx</Extensions>
7+
</Filter>
8+
<Filter Include="Header Files">
9+
<UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>
10+
<Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>
11+
</Filter>
12+
<Filter Include="Resource Files">
13+
<UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>
14+
<Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms</Extensions>
15+
</Filter>
16+
</ItemGroup>
17+
<ItemGroup>
18+
<ClCompile Include="QueueWithMax.cpp">
19+
<Filter>Source Files</Filter>
20+
</ClCompile>
21+
</ItemGroup>
22+
</Project>

‎59_02_QueueWithMax/QueueWithMax.cpp‎

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
//==================================================================
2+
// 《剑指Offer——名企面试官精讲典型编程题》代码
3+
// 作者：何海涛
4+
//==================================================================
5+
6+
// 面试题59（二）：队列的最大值
7+
// 题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，
8+
// 如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个
9+
// 滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}，
10+
11+
#include <cstdio>
12+
#include <deque>
13+
#include <exception>
14+
15+
using namespace std;
16+
17+
template<typename T> class QueueWithMax
18+
{
19+
public:
20+
QueueWithMax() : currentIndex(0)
21+
{
22+
}
23+
24+
void push_back(T number)
25+
{
26+
while(!maximums.empty() && number >= maximums.back().number)
27+
maximums.pop_back();
28+
29+
InternalData internalData = { number, currentIndex };
30+
data.push_back(internalData);
31+
maximums.push_back(internalData);
32+
33+
++currentIndex;
34+
}
35+
36+
void pop_front()
37+
{
38+
if(maximums.empty())
39+
throw new exception("queue is empty");
40+
41+
if(maximums.front().index == data.front().index)
42+
maximums.pop_front();
43+
44+
data.pop_front();
45+
}
46+
47+
T max() const
48+
{
49+
if(maximums.empty())
50+
throw new exception("queue is empty");
51+
52+
return maximums.front().number;
53+
}
54+
55+
private:
56+
struct InternalData
57+
{
58+
T number;
59+
int index;
60+
};
61+
62+
deque<InternalData> data;
63+
deque<InternalData> maximums;
64+
int currentIndex;
65+
};
66+
67+
// ====================测试代码====================
68+
void Test(const char* testName, const QueueWithMax<int>& queue, int expected)
69+
{
70+
if(testName != nullptr)
71+
printf("%s begins: ", testName);
72+
73+
if(queue.max() == expected)
74+
printf("Passed.\n");
75+
else
76+
printf("FAILED.\n");
77+
}
78+
79+
int main(int argc, char* argv[])
80+
{
81+
QueueWithMax<int> queue;
82+
// {2}
83+
queue.push_back(2);
84+
Test("Test1", queue, 2);
85+
86+
// {2, 3}
87+
queue.push_back(3);
88+
Test("Test2", queue, 3);
89+
90+
// {2, 3, 4}
91+
queue.push_back(4);
92+
Test("Test3", queue, 4);
93+
94+
// {2, 3, 4, 2}
95+
queue.push_back(2);
96+
Test("Test4", queue, 4);
97+
98+
// {3, 4, 2}
99+
queue.pop_front();
100+
Test("Test5", queue, 4);
101+
102+
// {4, 2}
103+
queue.pop_front();
104+
Test("Test6", queue, 4);
105+
106+
// {2}
107+
queue.pop_front();
108+
Test("Test7", queue, 2);
109+
110+
// {2, 6}
111+
queue.push_back(6);
112+
Test("Test8", queue, 6);
113+
114+
// {2, 6, 2}
115+
queue.push_back(2);
116+
Test("Test9", queue, 6);
117+
118+
// {2, 6, 2, 5}
119+
queue.push_back(5);
120+
Test("Test9", queue, 6);
121+
122+
// {6, 2, 5}
123+
queue.pop_front();
124+
Test("Test10", queue, 6);
125+
126+
// {2, 5}
127+
queue.pop_front();
128+
Test("Test11", queue, 5);
129+
130+
// {5}
131+
queue.pop_front();
132+
Test("Test12", queue, 5);
133+
134+
// {5, 1}
135+
queue.push_back(1);
136+
Test("Test13", queue, 5);
137+
138+
return 0;
139+
}

‎CodingInterviewChinese2.sln‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -148,6 +148,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "58_02_LeftRotateString", "5
148148
EndProject
149149
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "59_01_MaxInSlidingWindow", "59_01_MaxInSlidingWindow\59_01_MaxInSlidingWindow.vcxproj", "{7ECE0AB7-A33A-447D-9AC4-FCCB5801BD0D}"
150150
EndProject
151+
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "59_02_QueueWithMax", "59_02_QueueWithMax\59_02_QueueWithMax.vcxproj", "{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}"
152+
EndProject
151153
Global
152154
GlobalSection(SolutionConfigurationPlatforms) = preSolution
153155
Debug|Any CPU = Debug|Any CPU
@@ -870,6 +872,16 @@ Global
870872
{7ECE0AB7-A33A-447D-9AC4-FCCB5801BD0D}.Release|x64.Build.0 = Release|x64
871873
{7ECE0AB7-A33A-447D-9AC4-FCCB5801BD0D}.Release|x86.ActiveCfg = Release|Win32
872874
{7ECE0AB7-A33A-447D-9AC4-FCCB5801BD0D}.Release|x86.Build.0 = Release|Win32
875+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Debug|Any CPU.ActiveCfg = Debug|Win32
876+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Debug|x64.ActiveCfg = Debug|x64
877+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Debug|x64.Build.0 = Debug|x64
878+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Debug|x86.ActiveCfg = Debug|Win32
879+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Debug|x86.Build.0 = Debug|Win32
880+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Release|Any CPU.ActiveCfg = Release|Win32
881+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Release|x64.ActiveCfg = Release|x64
882+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Release|x64.Build.0 = Release|x64
883+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Release|x86.ActiveCfg = Release|Win32
884+
{4F8F1673-C98B-48ED-9DEB-C1BB16683AB0}.Release|x86.Build.0 = Release|Win32
873885
EndGlobalSection
874886
GlobalSection(SolutionProperties) = preSolution
875887
HideSolutionNode = FALSE

0 commit comments

Comments
 (0)