Skip to content

Commit 25990a0

Browse files
zhedahhtzhedahht
committed
Initial commit for question 43
1 parent 6bb8477 commit 25990a0

11 files changed

Lines changed: 355 additions & 39 deletions

File tree

‎13_RobotMove/RobotMove.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,7 @@ int getDigitSum(int number)
7474
// ====================测试代码====================
7575
void test(char* testName, int threshold, int rows, int cols, int expected)
7676
{
77-
if (testName != NULL)
77+
if (testName != nullptr)
7878
printf("%s begins: ", testName);
7979

8080
if (movingCount(threshold, rows, cols) == expected)

‎41_ StreamMedian/StreamMedian.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ template<typename T> class DynamicArray
7777
// ====================测试代码====================
7878
void Test(char* testName, DynamicArray<double>& numbers, double expected)
7979
{
80-
if(testName != NULL)
80+
if(testName != nullptr)
8181
printf("%s begins: ", testName);
8282

8383
if(abs(numbers.GetMedian() - expected) < 0.0000001)

‎43_NumberOf1/43_NumberOf1.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>{0EA1A952-E722-43BF-B785-8A9FA7236683}</ProjectGuid>
23+
<Keyword>Win32Proj</Keyword>
24+
<RootNamespace>My43_NumberOf1</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="NumberOf1.cpp" />
146+
</ItemGroup>
147+
<Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
148+
<ImportGroup Label="ExtensionTargets">
149+
</ImportGroup>
150+
</Project>

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

‎43_NumberOf1/NumberOf1.cpp‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
//==================================================================
2+
// 《剑指Offer——名企面试官精讲典型编程题》代码
3+
// 作者：何海涛
4+
//==================================================================
5+
6+
// 面试题43：从1到n整数中1出现的次数
7+
// 题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如
8+
// 输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
9+
10+
#include <cstdio>
11+
#include <cstring>
12+
#include <cstdlib>
13+
14+
// ====================方法一====================
15+
int NumberOf1(unsigned int n);
16+
17+
int NumberOf1Between1AndN_Solution1(unsigned int n)
18+
{
19+
int number = 0;
20+
21+
for(unsigned int i = 1; i <= n; ++ i)
22+
number += NumberOf1(i);
23+
24+
return number;
25+
}
26+
27+
int NumberOf1(unsigned int n)
28+
{
29+
int number = 0;
30+
while(n)
31+
{
32+
if(n % 10 == 1)
33+
number ++;
34+
35+
n = n / 10;
36+
}
37+
38+
return number;
39+
}
40+
41+
// ====================方法二====================
42+
int NumberOf1(const char* strN);
43+
int PowerBase10(unsigned int n);
44+
45+
int NumberOf1Between1AndN_Solution2(int n)
46+
{
47+
if(n <= 0)
48+
return 0;
49+
50+
char strN[50];
51+
sprintf(strN, "%d", n);
52+
53+
return NumberOf1(strN);
54+
}
55+
56+
int NumberOf1(const char* strN)
57+
{
58+
if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
59+
return 0;
60+
61+
int first = *strN - '0';
62+
unsigned int length = static_cast<unsigned int>(strlen(strN));
63+
64+
if(length == 1 && first == 0)
65+
return 0;
66+
67+
if(length == 1 && first > 0)
68+
return 1;
69+
70+
// 假设strN是"21345"
71+
// numFirstDigit是数字10000-19999的第一个位中1的数目
72+
int numFirstDigit = 0;
73+
if(first > 1)
74+
numFirstDigit = PowerBase10(length - 1);
75+
else if(first == 1)
76+
numFirstDigit = atoi(strN + 1) + 1;
77+
78+
// numOtherDigits是01346-21345除了第一位之外的数位中1的数目
79+
int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);
80+
// numRecursive是1-1345中1的数目
81+
int numRecursive = NumberOf1(strN + 1);
82+
83+
return numFirstDigit + numOtherDigits + numRecursive;
84+
}
85+
86+
int PowerBase10(unsigned int n)
87+
{
88+
int result = 1;
89+
for(unsigned int i = 0; i < n; ++ i)
90+
result *= 10;
91+
92+
return result;
93+
}
94+
95+
// ====================测试代码====================
96+
void Test(const char* testName, int n, int expected)
97+
{
98+
if(testName != nullptr)
99+
printf("%s begins: \n", testName);
100+
101+
if(NumberOf1Between1AndN_Solution1(n) == expected)
102+
printf("Solution1 passed.\n");
103+
else
104+
printf("Solution1 failed.\n");
105+
106+
if(NumberOf1Between1AndN_Solution2(n) == expected)
107+
printf("Solution2 passed.\n");
108+
else
109+
printf("Solution2 failed.\n");
110+
111+
printf("\n");
112+
}
113+
114+
void Test()
115+
{
116+
Test("Test1", 1, 1);
117+
Test("Test2", 5, 1);
118+
Test("Test3", 10, 2);
119+
Test("Test4", 55, 16);
120+
Test("Test5", 99, 20);
121+
Test("Test6", 10000, 4001);
122+
Test("Test7", 21345, 18821);
123+
Test("Test8", 0, 0);
124+
}
125+
126+
int main(int argc, char* argv[])
127+
{
128+
Test();
129+
130+
return 0;
131+
}
132+

‎CodingInterviewChinese2.sln‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "41_ StreamMedian", "41_ Str
100100
EndProject
101101
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "42_GreatestSumOfSubarrays", "42_GreatestSumOfSubarrays\42_GreatestSumOfSubarrays.vcxproj", "{9456A0AB-267A-4F6C-82C2-54C4288A625B}"
102102
EndProject
103+
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "43_NumberOf1", "43_NumberOf1\43_NumberOf1.vcxproj", "{0EA1A952-E722-43BF-B785-8A9FA7236683}"
104+
EndProject
103105
Global
104106
GlobalSection(SolutionConfigurationPlatforms) = preSolution
105107
Debug|Any CPU = Debug|Any CPU
@@ -582,6 +584,16 @@ Global
582584
{9456A0AB-267A-4F6C-82C2-54C4288A625B}.Release|x64.Build.0 = Release|x64
583585
{9456A0AB-267A-4F6C-82C2-54C4288A625B}.Release|x86.ActiveCfg = Release|Win32
584586
{9456A0AB-267A-4F6C-82C2-54C4288A625B}.Release|x86.Build.0 = Release|Win32
587+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Debug|Any CPU.ActiveCfg = Debug|Win32
588+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Debug|x64.ActiveCfg = Debug|x64
589+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Debug|x64.Build.0 = Debug|x64
590+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Debug|x86.ActiveCfg = Debug|Win32
591+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Debug|x86.Build.0 = Debug|Win32
592+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Release|Any CPU.ActiveCfg = Release|Win32
593+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Release|x64.ActiveCfg = Release|x64
594+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Release|x64.Build.0 = Release|x64
595+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Release|x86.ActiveCfg = Release|Win32
596+
{0EA1A952-E722-43BF-B785-8A9FA7236683}.Release|x86.Build.0 = Release|Win32
585597
EndGlobalSection
586598
GlobalSection(SolutionProperties) = preSolution
587599
HideSolutionNode = FALSE

‎Utilities/Array.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ void Swap(int* num1, int* num2)
2323

2424
int Partition(int data[], int length, int start, int end)
2525
{
26-
if(data == nullptr || length <= 0 || start < 0 || end >= length)
26+
if(data == nullptrptr || length <= 0 || start < 0 || end >= length)
2727
throw new std::exception("Invalid Parameters");
2828

2929
int index = RandomInRange(start, end);

0 commit comments

Comments
 (0)