winng的一月题目

作者: winng伍寅 | 来源:发表于2019-01-30 14:35 被阅读0次

winng的一月题目
winng的入坑题目记录
winng的二月第一周题目
实用主义：JS判断给定日期是第几周
二月，你好
IF YOU
没有人必须沉重的活着
没有题目，就是最好的题目😊
没有题目就是最好的题目
【诗集】接龙悬赏一月精选诗集

[1] 反转一个三位数 |lintcode37

思路：算出三位数每个位都是什么然后加一下

//C++
  int reverseInteger(int number) {
    int b,s,g;
    b=number/100;
    s=(number-b*100)/10;
    g=number-b*100-s*10;
    number=g*100+s*10+b;
    return number;
    }

优化：直接 return

    return g*100+s*10+b;

Python（用了50ms呢，是C++的10倍）：

  def reverseInteger(self, number):
    b=number/100
    s=(number-b*100)/10
    g=number-b*100-s*10
    return g*100+s*10+b

[2] 大小写转换 |lintcode145

思路：ASCII码直接减32

  char lowercaseToUppercase(char character) {
    return character-32;
    }

优化：https://blog.csdn.net/u012925008/article/details/45505465

大写字母	ASCII(10)	ASCII(2)	ASCII(2)	ASCII(10)	小写字母
A	65	01 0 00001	01 1 00001	97	a
B	66	01 0 00010	01 1 00010	98	b
…	…	…	…	…	…
Z	90	01 0 11010	01 1 11010	122	z

则有三种转换大小写的位运算c[i] |= 32 //A2a、c[i] &= 95 //a2A和c[i] ^= 32，分别是大写字母或0100000，小写字母与1011111，大小写字母非0100000

  char lowercaseToUppercase(char character) {
    return character&95;
    }

优化后速度快了2ms（8ms->6ms），还是快了不少的。但将95写成2进制或16进制并不会加快运行速度，反而会让速度降到50ms。

Python（用时50ms，且并不会因为采用位运算增快）：

  def lowercaseToUppercase(self, character):
    return chr(ord(character)-32)

[3] 斐波那契数列 |lintcode366

思路1：使用递归，1和2输出1,3以上输出前两个的fib()

  int fibonacci(int n) {
    if(n==1) return 0;
    else if(n==2) return 1;
    else {
      return fibonacci(n-1)+fibonacci(n-2);
      }
    }

但是在数据大的时候出现超时，因为递归的分支较多或层数较深的时候会导致程序运行超时或递归栈爆炸。

当n=40的时候，需要计算次数是大约是 $1+2^1+2^2+...+2^{39}=2^{40}-1$ 实际是 $(\frac{1+\sqrt5}{2})^n≈ 10^{12}$ 明显会超时

思路2：使用迭代，减少时间复杂度

  int fibonacci(int n) {
    int f1=0, f2=1,f3=1;
    for(int i=0;i<(n-1);i++){
      f3=f1+f2;
      f1=f2;
      f2=f3;
    }
    return f1;
  }

这种写法速度最快（5ms）

  int fibonacci(int n) {
    int f1=0, f2=1;
    for (int i=0;i<(n-1)/2;i++){
      f1=f1+f2;
      f2=f1+f2;
    }
    if(n%2==1) return f1;
    else return f2;
  }

第二种写法空间占用较小，减少了一半的循环，但是多了一个判断，所以在数据不是很大的时候并没有第一种快（？）。
另外，在判断n是不是奇数的时候使用与运算（&）会使时间增加到50ms。（？）

Python（用时101ms）：

  def fibonacci(self, n):
    f1=0
    f2=1
    i=2
    while i<n:
      f1=f1+f2
      f2=f1+f2
      i+=2
    if n%2==1:
      return f1
    else:
      return f2

[4] 矩阵面积 |lintcode454

Python（用时302ms）：

  class Rectangle:
    def __init__(self,width,height):
      self.w=width
      self.h=height
    def getArea(self):
      return self.w*self.h

有人用了50ms，并不知道他是怎么做到的

[5]整数排序 |lintcode463

思路：简单的选择排序（用时51ms）

  void sortIntegers(vector<int> &A) {
    int tmp;
    for(int i=0;i!=A.size();i++)
      for(int j=i+1;j!=A.size();j++)
        if(A.at(i)>A.at(j)) swap(A[i],A[j]);
  }

优化：使用sort函数将vector排序。sort函数使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)，下面的程序用时仅需9ms，可以说很过分了。

  void sortIntegers(vector<int> &A) {
    sort(A.begin(), A.end());
  }

Python：

  def sortIntegers(self, A):
    A.sort();

在python2时sort函数用时50ms，但是在Python3时用了101ms，并不清楚为什么，但是用Python3编写插入排序进行排序的用时更长，为252ms。

  def sortIntegers(self, A):
    i = 1
    while i < len(A):
      itemToInsert = A[i]
      j = i - 1
      while j >= 0:
        if itemToInsert < A[j]:
          A[j+1] = A[j]
          j -= 1
        else:
          break
      A[j+1] = itemToInsert
      i += 1

[6] 链表节点计算 |lintcode466

思路：走一个加一个

  int countNodes(ListNode * head) {
    if(head==NULL) return 0;
    int num=1;
    while(head->next!=NULL){
      head=head->next;
      num++;
    }
    return num;
  }

优化：copy了一下样例，用时从50ms->11ms，大概是因为编码的时候for循环和while循环不一样。不过，局部变量塞进for循环里要更简洁呢。

  int countNodes(ListNode * head){
    int n = 0;
    for(ListNode *p = head;p != NULL;p = p->next)
      n++;
    return n;
  }

[7] 交换数组中的两个元素 |lintcode484

思路：直接用swap函数，用时46ms又快又好。

  void swapIntegers(vector<int> &A, int index1, int index2) {
    swap(A[index1],A[index2]);
  }

关于swap函数的实现：https://www.cnblogs.com/Kernel001/p/7814278.html，从lintcode网站给出的排行榜可以推断出，不管用哪种实现方法来做交换，大都没有swap函数来的快速。在另一篇博文《C++STL中swap函数操作与内存地址改变的简析》(https://blog.csdn.net/iwts_24/article/details/79487501)中，作者对这个现象进行了实践并给出了与解释：

在数组中使用swap函数可以快速地进行交换，因为swap在交换的时候并不是完全将2个容器的元素互换，而是交换了2个容器内的内存地址。除了数组，其他容器在交换后本质上是将内存地址进行了交换，而元素本身在内存中的位置是没有变化的。

[8]二叉树的最大节点 |lintcode632

思路：进行一遍遍历然后记录最大的。因为之前的斐波那契数列用递归炸了，所以这次我没用递归，用的是非递归的遍历方式，用时64ms。

  TreeNode * maxNode(TreeNode * root) {
    if(root==NULL) return NULL;
    TreeNode *max=root;
    queue<TreeNode*> Q;
    Q.push(root);
    while(!Q.empty()){
      TreeNode *front=Q.front();
      if (front->val > max->val) max=front;
      if (front->left!=NULL) Q.push(front->left);
      if (front->right!=NULL) Q.push(front->right);
      Q.pop();
    }
    return max;
  }

然后在网上copy了一个递归实现，但仿佛这种递归每次调用都会多生成一个left和right节点，并不是很好（用时159ms）：

  TreeNode* maxNode(TreeNode* root) {
    if(root==NULL) return NULL;
    TreeNode *left=root;  
    TreeNode *right=root;  
    if (root->left!=NULL) 
      left=maxNode(root->left);  
    if (root->right!=NULL) 
      right=maxNode(root->right);  
    if (left->val>root->val)
      root->val=left->val;
    if (right->val>root->val)
      root->val=right->val;
    return root;
  }

网上copy的另一种递归实现（用时69ms）：

为了防止每次递归调用函数时都重新定义一个新节点，需要在函数外另定义一个新函数，新函数的参数a需要是引用形式。
https://blog.csdn.net/fanglegefang/article/details/70339886

  TreeNode* maxNode(TreeNode* root) {
    TreeNode *a=new TreeNode(-10000);
    if(root==NULL) return NULL;
    max(root,a);
    return a;
  }
  TreeNode *max(TreeNode *root,TreeNode *&a){
    if(root==NULL) return a;
    if(root->val>a->val) a=root;
    max(root->left,a);
    max(root->right,a);
  }