LeetCode刷题之路

开门见山：向量 vector 是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。 与string相同, vector 同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版。不过向量能根据需要进行随意大小的调整。
在向量这儿遍历可以采取一种迭代器的方法：类型为iterator，遍历器不但表示位置，还可以表示前后移动.

 vector<int>::iterator t ;
    for(t=a.begin(); t!=a.end(); t++)
        cout<<*t<<" " ;

插入一个学习向量vector的博客：https://www.cnblogs.com/aminxu/p/4686332.html

为了运行时间复杂度的优化，选择一种更有效的方法来检查数组中是否存在目标元素，如果存在，找出它的索引，保持数组中每个元素与其索引相互对应的最好方法是哈希表常以空间换速度的方式
https://blog.csdn.net/u013468917/article/details/51362156
学到一个原理：ArrayList使用的是数组来存储数据，HashMap是用哈希表来存储，两者运行时间的差距在contains和containsKey方法上。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

或者【更加简单：在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。】：

public int[] twoSum(int[] nums, int target) {        
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();               
		 for(int i=0; i<nums.length; i++){         
			 if(map.containsKey(target-nums[i])){         
 				 return new int[]{map.get(target-nums[i]), i};         
 			}         
  			map.put(nums[i], i);        
		 }       
 	  return null;   
 }

今天偶遇大佬，学到了c++中的一个比较全面的库，stl，（linklist），学习到其中有好多已经写好的各种数据结构内容，例如链表之类的都是已经写好的，向量的本质今天算是记清楚了，此容器主要的特点是可以改变大小的，无需设置大小于初始化，可以直接push_back.
蒟蒻入门：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *l3;
        ListNode *l4;
        int jinwei=0;
        while(l1!=NULL||l2!=NULL||jinwei!=0){
            int sum=(l1==NULL?0:l1->val)+(l2==NULL?0:l2->val)+jinwei;
            jinwei=sum/10;
        ListNode *newNode = new ListNode(sum%10);
         if (l3 == NULL) {
          l3 = newNode;
          l4 = newNode;
         } else{
          l4->next = newNode;   
          l4 = l4->next;
        }
            l1=l1==NULL?NULL:l1->next;
            l2=l2==NULL?NULL:l2->next;
        }
        return l3;
    }
};

未知错误，算是服气了！！！（不知代码问题何在）
不过根据题解学到了一种方法，不一定建立链表就必须非得按头节点输出，完全可以返回head.next，或者这种方法等价于设置空头，然后在最后的时候将其delete掉
如下：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;//进位位
        ListNode *head = new ListNode(0);//这个空头，后面要删掉
        ListNode *nextTemp= head;
        while (l1 != nullptr || l2 != nullptr|| carry)
        {
            nextTemp->next = new ListNode(0);//新建一个节点
            nextTemp = nextTemp->next;
            int x = (l1) ? l1->val : 0;
            int y = (l2) ? l2->val : 0;
            int temp = carry + x + y;
            nextTemp->val = temp % 10;
            carry = temp / 10;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        ListNode *returnVal = head->next;
        delete head;//头结点没有用
        return returnVal;
    }
};

标准答案：

class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode preHead(0), *p = &preHead;
int carry = 0;
while (l1 || l2 || carry) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
carry = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return preHead.next;
};

**注：**竟然找到了C语言产生随机数【C语言中语句scrand((time(NULL));表示设置一个随机种子，每次运行都能保证随机种子不同，在C语言中rand()函数可以用来产生随机数，但并不是真正意义上的随机数，是一个伪随机数，它是根据一个数，称为种子，为基准以某个递推公式推算出来的系数

杨辉三角问题：
118~~~~~

 public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if(numRows<1) return result;
        for(int i=0;i<numRows;++i){
            List<Integer> list = Arrays.asList(new Integer[i+1]);
            list.set(0,1);list.set(i,1);
            for(int j=1;j<i;j++){
                list.set(j,result.get(i-1).get(j-1)+result.get(i-1).get(j));
            }
            result.add(list);
        }
        return result;
    }

List 是一种非常好用的数据结构，需要将一个数组转换为List，可以使用 java.util 包下的 Array.asList方法，在程序中有体现。(对于使用指南，直接点击上边的Array List)。
此处对杨辉三角的部分特点进行揭示：：

1. 首先看第n行数：1，11，121，1331…都是11次幂
2. 再看第n行的和：1，2，4，8…都是2次幂
3. 斜列的和为拐角处元素的值
4. 隐藏了斐波那契数列：1，1，2，3，5，8…

上边的这道题算是对杨辉三角的整体的遍历，还收藏了一道关于杨辉三角的单行查询的题
119~~~~~~

public List<Integer> getRow(int rowIndex) {
        List<Integer>res = new ArrayList<>(rowIndex+1);
        long index=1;
        for(int i=0;i<=rowIndex;i++){
            res.add((int)index);
            index = index*(rowIndex-i)/(i+1);
        }
        return res;
    }

算法~数学 ^ _ ^
通过了解杨辉三角的内在特点，想到一种方法，通过计算11^n来计算所要求的行的数字串，然后提取各个位上的数字，进行存储输出……
首先插入计算11的n次幂的代码：

int pow(int n){
int sum = 1; int tmp = 11;
while(n!=0){
  if(n&1==1){ sum*=tmp;}
  tmp*=tmp; n=n>>1;
  }
  return result;}

之后即可进行11的次幂运算
此处有两种方法进行提取操作：

• 依次提取计算结果的每位上的数字，通过十六进制&和>>运算，存进向量——可以执行
• 直接将数字转化为字符串

 sprintf(temp, "%d", num);
 for (register int i=0; i<strlen(temp); i++) {cout << temp[i] << endl;}

————完成