//你可以新创建一个链表,也可以在原有的链表上操作,这里选新创建的链表
//(1)两数相加,最重要的就是考虑进位,每次赋值,记得加上进位;
//(2)最后一个数是否为1,取决于最高位是否有进位;
//(3)循环条件,只要有一个链表不为空就可以继续进行
//(4)代码如下:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode(-1), *p = head;//head为移动指针,p为固定指针
int carry = 0, data = 0;
while (l1 || l2){
if (l1){
data += l1->val;
l1 = l1->next;
}
if (l2){
data += l2->val;
l2 = l2->next;
}
if (carry == 1){
data ++;
}
head->next = new ListNode(data % 10);
head = head->next;
carry = data / 10;
data = 0;
}
if (carry){
head->next = new ListNode(1);
}
return p->next;
}
//提前说好,这个题目直接使用pow(x, n)是直接能过的,但是这样就考察不到这个题的算法了,我们使用快速幂来解答
double quick(double base, long long n){
double result = 1;
while (n){
if (n&1){
result *= base;
}
base = base * base;
n >>= 1;
}
return result;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quick(x, N) : 1.0/quick(x, -N);
}
//这题可以直接使用next_permutation()但是考察不到算法点:这题可以用dfs来解答
//next_permutation()
std::string getPermutation(int n, int k) {
int num[n];
for (int i = 1; i <= n; i ++){
num[i - 1] = i;
}
int len = 0;
std::string str = "";
do{
if (len == k){
for (int i = 0; i < n; i ++){
str += std::to_string(num[i]);
}
break;
}
}while(std::next_permutation(num, num + n));
}
//dfs
vector <int> nums;
int vis[10] = {0}, cnt = 0, flag = 0;
string str = "";
void getStr(){
for (auto c : nums){
str += to_string(c);
}
}
void dfs (vector <int>& nums, int n, int k, int sum){
if (sum >= n){
cnt ++;
if (cnt == k){
flag = 1;
getStr();
}
return;
}
for (int i = 1; i <= n; i ++){
if (vis[i] == 0 && flag == 0){
nums.push_back(i);
vis[i] = 1;
dfs (nums, n, k, sum + 1);
nums.pop_back();
vis[i] = 0;
}
}
}
string getPermutation(int n, int k) {
dfs (nums, n, k, 0);
return str;
}
//这题还是可以直接用sqrt()直接得到答案,但是得不到训练;
//sqrt
int mySqrt(int x) {
return std::sqrt(x);
}
//牛顿迭代法x = (x + a / x) / 2;
int mySqrt(int x){
double a = x, res = x, tmp = 0;
if (x == 0)return 0;
while (true){
res = (res + a / res) / 2; //牛顿迭代法,a一直不变,x一直迭代变化
if ((int)tmp == (int)res)break;
tmp = res;
}
return (int)res;
}
std::unordered_map <int, int> mapp;
int judgeHappy(int n){
int sum = 0;
while (n){
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
while (n != 1){
mapp[n] = 1;
n = judgeHappy(n);
if (mapp[n] == 1)return false;
}
return true;
}
int calculate(string s) {
stack<int> st;
unsigned int ans = 0, num = 0, op = 1;
st.push(op);
for (auto c : s){
if (c == ' ')continue;
if (c >= '0' && c <= '9'){
num = num * 10 + c - '0';
}else{
ans += op * num;
num = 0;
if (c == '+') op = st.top();
if (c == '-') op = -st.top();
if (c == '(') st.push(op);
if (c == ')') st.pop();
}
}
// -22 + 1 + 23
return ans + op * num;
}
bool isPowerOfTwo(int n) {
if (n <= 0)return false;
if (n & (n - 1)) //将最低位的一清0,如果为2的幂,那就一个1.清0会变为0
return false;
else
return true;
}
bool isUgly(int n) {
for (int i = 0; pow (2, i) <= n; i ++){
for (int j = 0; pow (3, j) <= n; j ++){
for (int k = 0; pow (5, k) <= n; k ++){
if (pow(2, i) * pow(3, j) * pow(5, k) == n)
return true;
}
}
}
return false;
}
bool isPowerOfThree(int n)
{
if(n < 1) return false;
while(n % 3 == 0)
{
n = n / 3;
}
return n == 1;
}
long long maxn = 0, m;
void dfs(long long s, long long sum, long long k, long long total){
if (sum > m)return;
if (sum == m && k > 1){
maxn = max(maxn, total);
return;
}
for (long long i = s; i <= m; i ++){
dfs (i, sum + i, k + 1, total * i);
}
}
int integerBreak(int n) {
m = n;
dfs (1, 0, 0, 1);
return maxn;
}
int maximumProduct(vector<int>& nums) {
decltype (nums.size()) len = nums.size(), sum = 1;
sort (nums.begin(), nums.end(), [&](const int& a, const int& b){return a > b;});
int a1 = nums[0] * nums[1] * nums[2];
int a2 = nums[len - 1] * nums[len - 2] * nums[0];
return max(a1, a2);
}
//分析:
//(1)第一部分:dp[i] = dp[i - 1] * 10 + ...; dp[i - 1]为i - 1位数重复的数目,,对于i位:只需要再后面加0-9也
//必然重复
//(2)如果前i-1位不重复呢,比如12, 21什么的,只需要排列组合即可:第一位有9种放法,后面都是10种也就是9*pow(10, i-2)
//这个放法是包括了dp[i - 1]的所以减去,然后最后一位只要与前i-1种一个一样就行了。即乘以i-1
//dp[i] = dp[i - 1] * 10 + (pow (10, i - 2) * 9 - dp[i - 1]) * (i - 1)
int countNumbersWithUniqueDigits(int n) {
vector <int> dp(n + 2);
for (int i = 2; i <= n; i ++){
dp[i] = dp[i - 1] * 10 + (pow (10, i - 2) * 9 - dp[i - 1]) * (i - 1);
}
int sum = 0;
for (auto v : dp){
sum += v;
}
return pow (10, n) - sum;//总的减去重复的就是答案,
}
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, t = 2, pos = 0, cnt = 0;
vector<vector<int>> ans;
while(cnt < R * C){
//遍历步长,每转两下就会增加一步
for(int i = 0; i < t / 2; i ++){
if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
ans.push_back({r0, c0}), ++ cnt;
r0 += fx[pos][0];
c0 += fx[pos][1];
}
pos = (pos + 1) % 4;
t ++;
}
return ans;
}
vector<int> diStringMatch(string s) {
vector <int> vt;
int maxLen = s.size(), minLen = 0;
for (auto c : s){
if (c == 'I'){
vt.push_back(minLen);
minLen ++;
}else{
vt.push_back(maxLen);
maxLen --;
}
}
vt.push_back(maxLen);
return vt;
}
int largestPerimeter(vector<int>& nums) {
sort(nums.begin(), nums.end(), [&](const int& a, const int& b){return a > b;});
for (int i = 0; i < nums.size() - 2; i ++){
if (nums[i + 1] + nums[i + 2] > nums[i])return nums[i] + nums[i + 1] + nums[i + 2];
}
return 0;
}
//对于1, 2, 3, 4, 5很不明显不能直接遍历每个子序列,肯定会超时
//题目求宽度,也就是说:一个子序列中只有最大值和最小值有用,其他的都无用,,
//那可以让各个数为最大值和最小值,比如:2为最小值是有多少种子序列?
//那肯定是3,4, 5随机排列3, 4,5可以不选也可以选,,所以一共有 8种
//2为最大值有2种,,然后把所有的最大值相加之后减去所有最小值的种数就是答案;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll answer = 0;
int sumSubseqWidths(vector<int>& A){
vector <int> B;
B.push_back(1LL);
for (int i = 1; i < A.size(); i ++){
B.push_back(B[B.size() - 1] * 2 % MOD);
}
sort(A.begin(), A.end());
for (ll i = 0; i < A.size(); i ++){
ll y = (B[i] - B[B.size() - i - 1] + MOD) % MOD;
y = A[i] * y % MOD;
answer = (answer + y) % MOD;
}
return (int)answer;
}
//数字N如果是奇数,它的约数必然都是奇数;若为偶数,则其约数可奇可偶。
//无论N初始为多大的值,游戏最终只会进行到N=2时结束,那么谁轮到N=2时谁就会赢。
//因为爱丽丝先手,N初始若为偶数,爱丽丝则只需一直选1,使鲍勃一直面临N为奇数的情况,这样爱丽丝稳赢;
//N初始若为奇数,那么爱丽丝第一次选完之后N必为偶数,那么鲍勃只需一直选1就会稳赢
bool divisorGame(int n) {
return !(n & 1);
}
class Solution {
int ans = 0;
public:
int numSquarefulPerms(vector<int>& A) {
vector<bool> vis(A.size(), false);
sort(A.begin(), A.end());
dfs(A, 0, -1, vis);
return ans;
}
void dfs(vector<int>& A, int count, int prev, vector<bool>& vis)
{
if(count == A.size())
{
ans++;
return;
}
for(int i = 0; i < A.size(); ++i)
{
if(i > 0 && !vis[i-1] && A[i-1]==A[i])
continue;// 剪枝
if(!vis[i] && (prev == -1 || ok(prev, A[i])))
{
vis[i] = true;
dfs(A, count+1, A[i], vis);
vis[i] = false;
}
}
}
bool ok(int a, int b)
{
int num = sqrt(a+b);
return num*num == a+b;
}
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。