Skip to content

Commit 74a7b25

Browse files
zhedahhtzhedahht
committed
Initial commit for question 45
1 parent dd86813 commit 74a7b25

5 files changed

Lines changed: 310 additions & 1 deletion

File tree

‎44_DigitsInSequence/DigitsInSequence.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
// 作者：何海涛
44
//==================================================================
55

6-
// 面试题43：数字序列中某一位的数字
6+
// 面试题44：数字序列中某一位的数字
77
// 题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这
88
// 个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一
99
// 个函数求任意位对应的数字。

‎45_SortArrayForMinNumber/45_SortArrayForMinNumber.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>{4E630ECB-8B73-460F-80CB-F51950115361}</ProjectGuid>
23+
<Keyword>Win32Proj</Keyword>
24+
<RootNamespace>My45_SortArrayForMinNumber</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="SortArrayForMinNumber.cpp" />
146+
</ItemGroup>
147+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
148+
<ImportGroup Label="ExtensionTargets">
149+
</ImportGroup>
150+
</Project>

‎45_SortArrayForMinNumber/45_SortArrayForMinNumber.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="SortArrayForMinNumber.cpp">
19+
<Filter>Source Files</Filter>
20+
</ClCompile>
21+
</ItemGroup>
22+
</Project>

‎45_SortArrayForMinNumber/SortArrayForMinNumber.cpp‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
//==================================================================
2+
// 《剑指Offer——名企面试官精讲典型编程题》代码
3+
// 作者：何海涛
4+
//==================================================================
5+
6+
// 面试题45：把数组排成最小的数
7+
// 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼
8+
// 接出的所有数字中最小的一个。例如输入数组{3, 32, 321}，则打印出这3个数
9+
// 字能排成的最小数字321323。
10+
11+
#include "cstdio"
12+
#include <string>
13+
#include <algorithm>
14+
15+
int compare(const void* strNumber1, const void* strNumber2);
16+
17+
// int型整数用十进制表示最多只有10位
18+
const int g_MaxNumberLength = 10;
19+
20+
char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];
21+
char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];
22+
23+
void PrintMinNumber(const int* numbers, int length)
24+
{
25+
if(numbers == nullptr || length <= 0)
26+
return;
27+
28+
char** strNumbers = (char**)(new int[length]);
29+
for(int i = 0; i < length; ++i)
30+
{
31+
strNumbers[i] = new char[g_MaxNumberLength + 1];
32+
sprintf(strNumbers[i], "%d", numbers[i]);
33+
}
34+
35+
qsort(strNumbers, length, sizeof(char*), compare);
36+
37+
for(int i = 0; i < length; ++i)
38+
printf("%s", strNumbers[i]);
39+
printf("\n");
40+
41+
for(int i = 0; i < length; ++i)
42+
delete[] strNumbers[i];
43+
delete[] strNumbers;
44+
}
45+
46+
// 如果[strNumber1][strNumber2] > [strNumber2][strNumber1], 返回值大于0
47+
// 如果[strNumber1][strNumber2] = [strNumber2][strNumber1], 返回值等于0
48+
// 如果[strNumber1][strNumber2] < [strNumber2][strNumber1], 返回值小于0
49+
int compare(const void* strNumber1, const void* strNumber2)
50+
{
51+
// [strNumber1][strNumber2]
52+
strcpy(g_StrCombine1, *(const char**)strNumber1);
53+
strcat(g_StrCombine1, *(const char**)strNumber2);
54+
55+
// [strNumber2][strNumber1]
56+
strcpy(g_StrCombine2, *(const char**)strNumber2);
57+
strcat(g_StrCombine2, *(const char**)strNumber1);
58+
59+
return strcmp(g_StrCombine1, g_StrCombine2);
60+
}
61+
62+
// ====================测试代码====================
63+
void Test(const char* testName, int* numbers, int length, const char* expectedResult)
64+
{
65+
if(testName != nullptr)
66+
printf("%s begins:\n", testName);
67+
68+
if(expectedResult != nullptr)
69+
printf("Expected result is: \t%s\n", expectedResult);
70+
71+
printf("Actual result is: \t");
72+
PrintMinNumber(numbers, length);
73+
74+
printf("\n");
75+
}
76+
77+
void Test1()
78+
{
79+
int numbers[] = {3, 5, 1, 4, 2};
80+
Test("Test1", numbers, sizeof(numbers)/sizeof(int), "12345");
81+
}
82+
83+
void Test2()
84+
{
85+
int numbers[] = {3, 32, 321};
86+
Test("Test2", numbers, sizeof(numbers)/sizeof(int), "321323");
87+
}
88+
89+
void Test3()
90+
{
91+
int numbers[] = {3, 323, 32123};
92+
Test("Test3", numbers, sizeof(numbers)/sizeof(int), "321233233");
93+
}
94+
95+
void Test4()
96+
{
97+
int numbers[] = {1, 11, 111};
98+
Test("Test4", numbers, sizeof(numbers)/sizeof(int), "111111");
99+
}
100+
101+
// 数组中只有一个数字
102+
void Test5()
103+
{
104+
int numbers[] = {321};
105+
Test("Test5", numbers, sizeof(numbers)/sizeof(int), "321");
106+
}
107+
108+
void Test6()
109+
{
110+
Test("Test6", nullptr, 0, "Don't print anything.");
111+
}
112+
113+
114+
int main(int argc, char* argv[])
115+
{
116+
Test1();
117+
Test2();
118+
Test3();
119+
Test4();
120+
Test5();
121+
Test6();
122+
123+
return 0;
124+
}
125+

‎CodingInterviewChinese2.sln‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "43_NumberOf1", "43_NumberOf
104104
EndProject
105105
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "44_DigitsInSequence", "44_DigitsInSequence\44_DigitsInSequence.vcxproj", "{BAD4AEDF-70EE-4CA9-AEFF-71670CF249DF}"
106106
EndProject
107+
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "45_SortArrayForMinNumber", "45_SortArrayForMinNumber\45_SortArrayForMinNumber.vcxproj", "{4E630ECB-8B73-460F-80CB-F51950115361}"
108+
EndProject
107109
Global
108110
GlobalSection(SolutionConfigurationPlatforms) = preSolution
109111
Debug|Any CPU = Debug|Any CPU
@@ -606,6 +608,16 @@ Global
606608
{BAD4AEDF-70EE-4CA9-AEFF-71670CF249DF}.Release|x64.Build.0 = Release|x64
607609
{BAD4AEDF-70EE-4CA9-AEFF-71670CF249DF}.Release|x86.ActiveCfg = Release|Win32
608610
{BAD4AEDF-70EE-4CA9-AEFF-71670CF249DF}.Release|x86.Build.0 = Release|Win32
611+
{4E630ECB-8B73-460F-80CB-F51950115361}.Debug|Any CPU.ActiveCfg = Debug|Win32
612+
{4E630ECB-8B73-460F-80CB-F51950115361}.Debug|x64.ActiveCfg = Debug|x64
613+
{4E630ECB-8B73-460F-80CB-F51950115361}.Debug|x64.Build.0 = Debug|x64
614+
{4E630ECB-8B73-460F-80CB-F51950115361}.Debug|x86.ActiveCfg = Debug|Win32
615+
{4E630ECB-8B73-460F-80CB-F51950115361}.Debug|x86.Build.0 = Debug|Win32
616+
{4E630ECB-8B73-460F-80CB-F51950115361}.Release|Any CPU.ActiveCfg = Release|Win32
617+
{4E630ECB-8B73-460F-80CB-F51950115361}.Release|x64.ActiveCfg = Release|x64
618+
{4E630ECB-8B73-460F-80CB-F51950115361}.Release|x64.Build.0 = Release|x64
619+
{4E630ECB-8B73-460F-80CB-F51950115361}.Release|x86.ActiveCfg = Release|Win32
620+
{4E630ECB-8B73-460F-80CB-F51950115361}.Release|x86.Build.0 = Release|Win32
609621
EndGlobalSection
610622
GlobalSection(SolutionProperties) = preSolution
611623
HideSolutionNode = FALSE

0 commit comments

Comments
 (0)