算法知识点————数论和链表

1、n数和

2数和

• 有序（递增）：头尾相加，和目标值比较
• 无序：哈希表（target - cur）

多数和：
​ 先排序
拿一个数（检测 i 和i-1 重复的不选择）
​ 2数和问题 （检测 去重）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> res; //结果是一个二元组 ，每个里面是个vector
        int i,j,k;
        sort(nums.begin(),nums.end());//先排序
        for(i = 0;i<len -2;i++){ //先取一个数
            if( i > 0 && nums[i] == nums[i-1]) continue;//去重，重复元素就不取了
            int temp = 0 - nums[i]; //temp记录剩下两个数和的负值
            int l = i+1,r = nums.size()-1;//左右指针寻找值
            while( l < r){
                 int sum = nums[l] + nums[r] ;
                 if(sum == temp)//找到了
                 {
                    res.push_back({nums[i],nums[l],nums[r]}); //存到结果res中
                    while(l < r && nums[l] == nums[++l]);//去重 l向后面移动
                    while(l < r && nums[r] == nums[--r]);
                 }else if (sum < temp){//和不够
                    l++;
                 }else {
                    r--;
                 }
            }
            
        }
        return res;
    }
};

2、回文数121 回文串abcba

• 负数不是回文数字
• 个位数都是回文数
• 0结尾的数不是回文数
• 从后往前取数 %10 然后和原来的数比较
• 跳出while循环要么是num == x 要么是不等于（大于和小于）
• 最后的可能是12和1或者12和12 或者1和12都算

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        if(x < 10) return true;
        if(x%10 == 0) return false;
        int num = 0;
        while(num < x){//121
            num = num*10 + x%10;//当前值 12
            x/=10;//1
           
        }
      
         if(x == num || num == x/10 || x == num/10) return true;//
         else return false;
    }
};

3、两个链表对应两个数组然后相加，结果在链表中
1->5->8 对应851
1->6->3->9 对应9361

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int carry =0) {
        if(l1 == nullptr && l2 == nullptr){
            return carry ? new ListNode(carry) : nullptr;//如果有进位，创建节点
        }
        if(l1 == nullptr) swap(l1,l2);//如果l1 是空的，l2一定不是空的 ，交换l1和l2保证l1非空
        int sum = carry+l1->val+(l2 ? l2->val :0);
        l1->val = sum%10;//节点保存数位
        l1->next = addTwoNumbers(l1->next,(l2 ? l2->next : nullptr),sum / 10);
        return l1;
    }
};

升级版本：两次反转链表，然后相加，结果返回反转

1->5->8 对应158
1->6->3->9 对应1639

class Solution {
public:

    ListNode* reverseList(ListNode* head){
        if(head == nullptr || head->next == nullptr) return head;
        auto newNode = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newNode;
    }
    

    ListNode *addTwo(ListNode* l1,ListNode* l2 ,int carry = 0){
        if(l1 == nullptr && l2 == nullptr){
            return carry ? new ListNode(carry) :nullptr;
        }
        if(l1 == nullptr) swap(l1,l2);
        carry += l1->val + (l2 ? l2->val : 0);
        l1->val = carry %10;
        l1->next = addTwo(l1->next ,(l2 ? l2->next : nullptr),carry/10);
        return l1;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //两次反转链表，然后相加，结果返回反转
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        auto l3 = addTwo(l1,l2);
        return reverseList(l3);
    }
};

原文地址：https://blog.csdn.net/shan_5233/article/details/142682831

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！