1. 用递归求第n项的值
1，2，4，2，3，6，12，6，3，....求第n项值
代码：
#include <stdio.h> int fun(int n, int *x, int *y) { int sum = 0, i; int size = 0; int dd = 1; for (i = 1; i <= (*x); i++) { sum += (2 * i - 1); } if (sum == n) { *y = 2 * (*x) - 1; return (*x); } else if (sum > n) { (*y) = n - (sum - (2 * (*x) - 1)); size = 2 * (*x) - 1; dd = (*x); for (i = 2; i <= (*y); i++) { if (i <= (*x)) dd *= 2; else dd /= 2; } return dd; } else { (*x)++; return fun(n, x, y); } } int main() { int n; int row = 1, col = 0; int val; row = 1; col = 0; printf("请输入n："); scanf("%d", &n); val = fun(n, &row, &col); printf("第%d项是：%d\n", n, val); return 0; }
输入输出：
请输入n：7
第7项是：12
2. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
代码：
#include<iostream> #include<vector> using namespace std; class Solution { public: int minPathSum(vector<vector<int>> grid) { int i, j; int gridRowSize = grid.size(); int gridColSize = grid[0].size(); vector<vector<int>> dp(gridRowSize, vector<int>(gridColSize)); dp[0][0] = grid[0][0]; int sum = dp[0][0]; for (i = 1; i < gridRowSize; i++) { sum += grid[i][0]; dp[i][0] = sum; } sum = dp[0][0]; for (i = 1; i < gridColSize; i++) { sum += grid[0][i]; dp[0][i] = sum; } for (i = 1; i < gridRowSize; i++) { for (j = 1; j < gridColSize; j++) { dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]); } } return dp[gridRowSize - 1][gridColSize - 1]; } }; int main() { Solution s; vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}}; cout << s.minPathSum(grid) << endl; grid = {{1,2,3},{4,5,6}}; cout << s.minPathSum(grid) << endl; return 0; }
输出：
7
12
3. 二进制求和
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: string addBinary(string a, string b) { string res; int carry = 0; int i = a.length() - 1; int j = b.length() - 1; for (; i >= 0 && j >= 0; i--, j--) { if (a[i] == '1' && b[j] == '1') { if (carry > 0) { res.push_back('1'); } else { res.push_back('0'); } carry = 1; } else if (a[i] == '0' && b[j] == '0') { if (carry > 0) { res.push_back('1'); } else { res.push_back('0'); } carry = 0; } else { if (carry > 0) { res.push_back('0'); carry = 1; } else { res.push_back('1'); carry = 0; } } } while (i >= 0) { if (a[i--] == '1') { if (carry > 0) { res.push_back('0'); carry = 1; } else { res.push_back('1'); carry = 0; } } else { res.push_back(carry + '0'); carry = 0; } } while (j >= 0) { if (b[j--] == '1') { if (carry > 0) { res.push_back('0'); carry = 1; } else { res.push_back('1'); carry = 0; } } else { res.push_back(carry + '0'); carry = 0; } } if (carry > 0) { res.push_back('1'); } reverse(res.begin(), res.end()); return res; } }; int main() { Solution s; cout << s.addBinary("11", "1") << endl; cout << s.addBinary("1010", "1011") << endl; return 0; }
输出：
100
10101
