Skip to content

Commit 8cd030c

Browse files
kuringkuring
committed
add some
1 parent 468de1e commit 8cd030c

4 files changed

Lines changed: 154 additions & 3 deletions

File tree

‎README.md‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,8 @@ LeetCode C++ Solutions
1010
[Isomorphic Strings](https://leetcode.com/problemset/algorithms/) | [C++](./src/isomorphicStrings/isomrphic_strings.cpp) | Easy | yes|
1111
[Remove Linked List Elements](https://leetcode.com/submissions/detail/26726335/) | [C++](./src/removeLinkedListElements/remove_linked_list_elements.cpp) | Easy | yes|
1212
[Happy Number](https://leetcode.com/problems/happy-number/) | [C++](./src/happyNumber/happy_number.cpp) | Easy | yes|
13-
[Reverse Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./src/numberOf1Bits/number_of_1bits.cpp) | Easy | yes|
13+
[House Robber](https://leetcode.com/problems/house-robber/) | [C++](./src/houseRobber/house_robber.cpp) | Easy | yes|
14+
[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./src/numberOf1Bits/number_of_1bits.cpp) | Easy | yes|
1415
[Reverse Bits](https://leetcode.com/problems/reverse-bits/) | [C++](./src/reverseBits/reverse_bits.cpp) | Easy | yes|
1516
[Rotate Array](https://leetcode.com/problems/rotate-array/) | [C++](./src/rotateArray/rotate_array.cpp) | Easy | yes|
1617
[Factorial Trailing Zeroes](https://leetcode.com/problems/factorial-trailing-zeroes/) | [C++](./src/FactorialTrailingZeroes/factorial_trailing_zeroes.cpp) | Easy | yes|
@@ -116,13 +117,13 @@ LeetCode C++ Solutions
116117
|[Edit Distance](https://oj.leetcode.com/problems/edit-distance/)| [C++](./src/editDistance/editDistance.cpp)|Hard|
117118
|[Simplify Path](https://oj.leetcode.com/problems/simplify-path/)| [C++](./src/simplifyPath/simplifyPath.cpp)|Medium|yes|
118119
|[Climbing Stairs](https://oj.leetcode.com/problems/climbing-stairs/)| [C++](./src/climbStairs/climbStairs.cpp)|Easy|yes|
119-
|[Sqrt(x)](https://oj.leetcode.com/problems/sqrtx/)| [C++](./src/sqrt/sqrt.cpp)|Medium|
120+
|[Sqrt(x)](https://oj.leetcode.com/problems/sqrtx/)| [C++](./src/sqrt/sqrt.cpp)|Medium|yes|
120121
|[Text Justification](https://oj.leetcode.com/problems/text-justification/)| [C++](./src/textJustification/textJustification.cpp)|Hard|
121122
|[Plus One](https://oj.leetcode.com/problems/plus-one/)| [C++](./src/plusOne/plusOne.cpp)|Easy|yes|
122123
|[Valid Number](https://oj.leetcode.com/problems/valid-number/)| [C++](./src/validNumber/validNumber.cpp)|Easy|
123124
|[Add Binary](https://oj.leetcode.com/problems/add-binary/)| [C++](./src/addBinary/addBinary.cpp)|Easy|yes|
124125
|[Merge Two Sorted Lists](https://oj.leetcode.com/problems/merge-two-sorted-lists/)| [C++](./src/mergeTwoSortedList/mergeTwoSortedList.cpp)|Easy|
125-
|[Minimum Path Sum](https://oj.leetcode.com/problems/minimum-path-sum/)| [C++](./src/minimumPathSum/minimumPathSum.cpp)|Medium|
126+
|[Minimum Path Sum](https://oj.leetcode.com/problems/minimum-path-sum/)| [C++](./src/minimumPathSum/minimumPathSum.cpp)|Medium|yes|
126127
|[Unique Paths II](https://oj.leetcode.com/problems/unique-paths-ii/)| [C++](./src/uniquePaths/uniquePaths.II.cpp)|Medium|yes|
127128
|[Unique Paths](https://oj.leetcode.com/problems/unique-paths/)| [C++](./src/uniquePaths/uniquePaths.cpp)|Medium|yes|
128129
|[Rotate List](https://oj.leetcode.com/problems/rotate-list/)| [C++](./src/rotateList/rotateList.cpp)|Medium|yes|

‎src/houseRobber/house_robber.cpp‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
#include <string>
2+
#include <iostream>
3+
#include <vector>
4+
5+
using namespace std;
6+
7+
/**
8+
* 采用动态规划思路完成，用贪心算法是不合适的，比如7,8,7用贪心算法得到的结果为8，而结果应该为14
9+
* f(n) = max(f(n-1), f(n-2) + nums[i])
10+
* 代码中的max_vector可以优化为用两个变量，这里不再做优化处理
11+
*/
12+
int rob(vector<int>& nums)
13+
{
14+
if (nums.size() == 0)
15+
{
16+
return 0;
17+
}
18+
else if (nums.size() == 1)
19+
{
20+
return nums[0];
21+
}
22+
23+
vector<int> max_vector(nums.size(), 0);
24+
max_vector[0] = nums[0];
25+
max_vector[1] = max(nums[0], nums[1]);
26+
for (size_t i = 2; i < nums.size(); i++)
27+
{
28+
max_vector[i] = max(max_vector[i - 1], max_vector[i - 2] + nums[i]);
29+
}
30+
31+
return max_vector[nums.size() - 1];
32+
}
33+
34+
int main()
35+
{
36+
vector<int> nums = {4, 5, 7, 9, 3, 6};
37+
cout << rob(nums) << endl;
38+
return 1;
39+
}

‎src/minimumPathSum/minimum_path_sum.cpp‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
#include <string>
2+
#include <iostream>
3+
#include <vector>
4+
5+
using namespace std;
6+
7+
int minPathSum(vector<vector<int>>& grid, size_t row, size_t column, size_t m, size_t n, vector<vector<int> > &cache)
8+
{
9+
cout << "m=" << m << "n=" << n << endl;
10+
if (m >= row && n >= column)
11+
{
12+
return grid[m][n];
13+
}
14+
15+
if (cache[m][n] != -1)
16+
{
17+
return cache[m][n];
18+
}
19+
20+
int result;
21+
if (m >= row)
22+
{
23+
result = minPathSum(grid, row, column, m, n + 1, cache) + grid[m][n];
24+
}
25+
else if (n >= column)
26+
{
27+
result = minPathSum(grid, row, column, m + 1, n, cache) + grid[m][n];
28+
}
29+
else
30+
{
31+
result = min(minPathSum(grid, row, column, m + 1, n, cache), minPathSum(grid, row, column, m, n + 1, cache)) + grid[m][n];
32+
}
33+
cache[m][n] = result;
34+
return result;
35+
}
36+
37+
/**
38+
* 深度优先搜索法，并使用缓存保存结果，减少不必要循环
39+
*/
40+
int minPathSum(vector<vector<int>>& grid)
41+
{
42+
size_t row = grid.size();
43+
if (row == 0)
44+
{
45+
return 0;
46+
}
47+
size_t column = grid[0].size();
48+
if (column == 0)
49+
{
50+
return 0;
51+
}
52+
53+
vector<vector<int> > result(row, vector<int>(column, -1));
54+
return minPathSum(grid, row - 1, column - 1, 0, 0, result);
55+
}
56+
57+
int main()
58+
{
59+
vector<vector<int> > result = {{1,2}, {5,6}, {1,1}};
60+
cout << minPathSum(result) << endl;
61+
return 1;
62+
}

‎src/sqrt/sqrt_kuring.cpp‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
#include <string>
2+
#include <iostream>
3+
#include <vector>
4+
5+
using namespace std;
6+
7+
/**
8+
* 二分搜索法，需要注意边界的处理，这里还用到了last变量，这个也是需要注意的
9+
*/
10+
int mySqrt(int x)
11+
{
12+
if (x < 2)
13+
{
14+
return x;
15+
}
16+
int left = 1;
17+
int right = x / 2;
18+
int last = 0;
19+
20+
while (left <= right)
21+
{
22+
int middle = left + (right - left) / 2;
23+
if (x / middle > middle)
24+
{
25+
last = middle;
26+
left = middle + 1;
27+
}
28+
else if (x / middle < middle)
29+
{
30+
right = middle - 1;
31+
}
32+
else
33+
{
34+
return middle;
35+
}
36+
}
37+
38+
return last;
39+
}
40+
41+
int main()
42+
{
43+
mySqrt(2);
44+
for (int i = 0; i < 101; i++)
45+
{
46+
cout << "sqrt " << i << " = " << mySqrt(i) << endl;
47+
}
48+
return 1;
49+
}

0 commit comments

Comments
 (0)