基础题

1. 互补查找

• 题目描述:

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

  查找一组数据中是否有两个数之和等于给出的数，并且确定这两个数的位置。于是在扫描的过程中，我们只需要查看前面扫描过的是否有与当前数关于给出的target互补的数即可，因此可建立一个关于value与位置的hash表，对于每一个新数据，查看其互补数据是否在hash表中，若在则找到，返回互补数据hash读取的位置和当前位置。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hash;
        vector<int> res(2,-1);
        for(int i = 0; i < nums.size(); i++)
        { 
            if(hash.count(target-nums[i]))
               {
                   res[0] = hash[target-nums[i]];
                   res[1] = i;
                   return res;
               }
            hash[nums[i]]=i;
        }
               return res;
    }
};

2. 大数求和（链表）

• 题目描述：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

 对于此类题，严格按照运算规则模拟即可。对加法不要忘记进位，若考虑效率，在两数位数相差很大的时候，短的链表加完后便可直接将剩余没加的和进位符作加法即可。

class Solution {
public:
    ListNode* carryTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* L3 = new ListNode(-1);
        int sum = 0, carry = 0;
        ListNode* res = L3;
        ListNode* p=l1, *q=l2;
        while(p!=NULL&& q!=NULL )
        {
            sum = q->val+p->val+carry;
            res->next =new ListNode(sum % 10);
            carry = sum / 10;
            p = p->next;
            q = q->next;
            res = res->next;
        }
        if(p)
        {
            while(p)
            {
                sum = carry + p->val;
                res->next = new ListNode(sum % 10);
                carry = sum / 10;
                p=p->next;
                res = res->next;
            }
        }
        else if(q){
            while(q)
            {
                sum = carry + q->val;   
                res->next = new ListNode(sum % 10);
                carry = sum / 10;
                q = q->next;
                res = res->next;
            }
        }
        if(carry)
        {
            res->next = new ListNode(1);
        }
        return L3->next;
    }
};

若考虑代码简洁，上述情形可统一起来，当它们其中有一个还未加完时都进入循环，在内部再进行判断是否作加法。代码如下：

class Solution {
public:
    ListNode* carryTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(-1);//存放结果的链表
        ListNode* h=head;//移动指针
        int sum=0;//每个位的加和结果
        bool carry=false;//进位标志
        while(l1!=NULL||l2!=NULL)
        {
            sum=0;
            if(l1!=NULL)
            {
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum+=l2->val;
                l2=l2->next;
            }
            if(carry)
                sum++;
            h->next=new ListNode(sum%10);
            h=h->next;
            carry=sum>=10?true:false;
        }
        if(carry)
        {
            h->next=new ListNode(1);
        }
        return head->next;
    }
};

旋转矩阵

找规律可得矩阵$m(i, j)$位置顺时针旋转后得到的值是$m(n - j - 1, i)$处的值，将矩阵分为四块，则每次旋转与i，j相关的需要改动的有四个，关系如下

$$\begin{aligned} m(i, j) &= m (n - j - 1, i)\\ m (n - j - 1, i) &= m (n - i - 1, n - j - 1)\\ m (n - i - 1, n - j - 1) &= m (j , n - i - 1)\\ m (j , n - i - 1) &= m (i, j)\\ \end{aligned}$$

这四个赋值是循环的，因此可以通过三个交换来代替，形如：

$$a = b\\ b = c\\ c = d\\ d = a$$

的循环赋值，可以通过下述交换得到同样的效果

$$swap(a, d)\\ swap(a, c)\\ swap(a, b)\\$$

矩阵分块的时候还需考虑奇数情况，这时只要在分块时在其中一维增加一行或一列即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(n == 0) { return; }
        int r = n >> 1; 
        int c = (n + 1) >> 1; 
        for(int i = 0; i < r; ++ i) {
            for(int j = 0; j < c; ++ j) {
                swap(matrix[i][j], matrix[j][n-i-1]);
                swap(matrix[i][j], matrix[n-i-1][n-j-1]);
                swap(matrix[i][j], matrix[n-j-1][i]);
            }
        }
    }
};