0%

Posted on In

1. 题目描述

题目描述

2. 我的解法

我的解法特别弱，就是遍历一遍字符串，用switch 分情况讨论，遇到特殊情况就多余一位判断

1
 class Solution {
2
    public int romanToInt(String s) {
3
        int len = s.length();
4
        int sum = 0;
5
        for (int i=0;i<len;i++)
6
        {
7
            char c=s.charAt(i);
8
            switch(c)
9
            {
10
                case 'I': 
11
                if(i+1<len)
12
                        {
13
                            if(s.charAt(i+1)=='V')
14
                                {sum+=4;
15
                                i++;
16
                                break;
17
                                }
18
                            else if(s.charAt(i+1)=='X')
19
                            {
20
                                sum+=9;
21
                                i++;
22
                                break;
23
                            }
24
                        }
25
                sum+=1;break;
26
                case 'V':sum+=5;break;
27
                case 'X':
28
                if(i+1<len)
29
                        {
30
                            if(s.charAt(i+1)=='L')
31
                                {sum+=40;
32
                                i++;
33
                                break;
34
                                }
35
                            else if(s.charAt(i+1)=='C')
36
                            {
37
                                sum+=90;
38
                                i++;
39
                                break;
40
                            }
41
                        }
42
                    sum+=10;break;
43
                case 'L':sum+=50;break;
44
                case 'C':
45
                if(i+1<len)
46
                        {
47
                            if(s.charAt(i+1)=='D')
48
                                {sum+=400;
49
                                i++;
50
                                break;
51
                                }
52
                            else if(s.charAt(i+1)=='M')
53
                            {
54
                                sum+=900;
55
                                i++;
56
                                break;
57
                            }
58
                        }
59
                sum+=100;break;
60
                case 'D':sum+=500;break;
61
                case 'M':sum+=1000;break;
62
            }
63
        }
64
        return sum;
65
    }
66
}

3 解法二

别人的优雅的解法都是充分利用了罗马数字的特性。如IV=4，正常读=6 IX=9 正常读=11.正常读比正确读大2.所以提前-2。但是鉴于indexOf的效率O(nm)，就是遍历查找，应该挺慢的

1
 public int romanToInt(String s) {
2
     int sum=0;
3
     //提前减2
4
    if(s.indexOf("IV")!=-1){sum-=2;}
5
    if(s.indexOf("IX")!=-1){sum-=2;}
6
    if(s.indexOf("XL")!=-1){sum-=20;}
7
    if(s.indexOf("XC")!=-1){sum-=20;}
8
    if(s.indexOf("CD")!=-1){sum-=200;}
9
    if(s.indexOf("CM")!=-1){sum-=200;}
10
11
    char c[]=s.toCharArray();
12
    int count=0;
13
14
   for(;count<=s.length()-1;count++){
15
       if(c[count]=='M') sum+=1000;
16
       if(c[count]=='D') sum+=500;
17
       if(c[count]=='C') sum+=100;
18
       if(c[count]=='L') sum+=50;
19
       if(c[count]=='X') sum+=10;
20
       if(c[count]=='V') sum+=5;
21
       if(c[count]=='I') sum+=1;
22
23
   }
24
25
   return sum;
26
27
}

时间复杂度：O（n+6n2)==(13n)
解法一和解法二的时间截图

3.解法三

规律的第二中理解 IV=4。可以理解为-1+5=4。IX=9 可以理解为 -1+10=9其他的特殊情况亦然,这个比解法二块一些，还是比解法一慢 5ms，getVal部分换成map应该更快

1
private int getVal(char c){
2
      switch (c){
3
          case 'M':
4
              return 1000;
5
          case 'D':
6
              return 500;
7
          case 'C':
8
              return 100;
9
          case 'L':
10
              return 50;
11
          case 'X' :
12
              return 10;
13
          case 'V':
14
              return 5;
15
          case 'I':
16
              return 1;
17
      }
18
      throw new IllegalArgumentException("unsupported character");
19
  }
20
21
  public int romanToInt(String s) {
22
      int res = 0;
23
      if(s.length() == 0) return res;
24
      for (int i = 0; i < s.length() - 1; i++) {
25
          int cur = getVal(s.charAt(i));
26
          int nex = getVal(s.charAt(i+1));
27
          if(cur < nex){
28
              res -= cur;
29
          }else{
30
              res += cur;
31
          }
32
      }
33
      return res + getVal(s.charAt(s.length()-1));
34
  }

Posted on In

题目描述（中等题目）

题目描述

  • 输入”/a/../../b/../c//.//“输出“/c”
  • 不考虑”./d”.”../dfd.df” 这种两种情况

我的解法

1
class Solution {
2
    public String simplifyPath(String path) {
3
        Stack<String> stack = new Stack<String>();
4
        for(String ss:path.split("/"))
5
        {
6
            if(!ss.equals("..")&&!ss.equals(".")&&!ss.equals(""))
7
                 stack.push(ss);
8
            else if(ss.equals("..")&&!stack.empty())
9
                stack.pop();
10
        }
11
        String out="";
12
        while(!stack.empty())
13
        {
14
            out = "/"+stack.pop()+out;
15
        }
16
        if(out.equals(""))
17
        return "/";
18
        return out;
19
    }
20
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

扩展

String的用法

Stack的用法

Posted on In

1 题目描述（中等难度）

题目描述

2 我的解法

思路：需要两遍扫描才可得到结果，不够高效

  • 计算链表的长度，计算需删除正数第几个节点
  • 找到需要删除的节点的前序，直接删去节点即可
    1
    /**
    2
     * Definition for singly-linked list.
    3
     * public class ListNode {
    4
     *     int val;
    5
     *     ListNode next;
    6
     *     ListNode(int x) { val = x; }
    7
     * }
    8
     */
    9
    class Solution {
    10
        public ListNode removeNthFromEnd(ListNode head, int n) {
    11
            if(head==null)return null;
    12
            //先计算节点个数
    13
            int dotnum=0;
    14
            ListNode l3=head;
    15
            while(l3!=null)
    16
            {
    17
                dotnum++;
    18
                l3 = l3.next;
    19
            }
    20
            //删除到处第n个节点
    21
            int delindex=dotnum-n;
    22
            if(delindex==0)return head.next;//如果删除第一个节点，则直接返回
    23
            ListNode pre=head;
    24
            for(int i=0 ;i<delindex-1;i++)//找到被删节点的前一个节点
    25
                pre=pre.next;
    26
            l3=pre.next;//被删节点
    27
            pre.next=l3.next;
    28
            return head;
    29
        }
    30
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

3 解法二

使用快慢指针：优点这里我们用到的快慢指针其实没有必要，快慢指针的一个优点是，不需要知道链表长度就可以找到倒数第 n 个节点。
问题：我的解法没有考虑，通过一次遍历的方式解决问题。
方法：设置快慢指针，两者间隔n个节点，当快指针到达链尾时，慢指针正好指向删除节点的前序节点。

1
public ListNode removeNthFromEnd(ListNode head, int n) {
2
    ListNode dummy = new ListNode(0);
3
    dummy.next = head;//加空指针，不用特判删除链首的情况
4
    ListNode first = dummy;//快指针
5
    ListNode second = dummy;//慢指针
6
    //第一个指针先移动 n 步
7
    for (int i = 1; i <= n + 1; i++) {
8
        first = first.next;
9
    } 
10
    //第一个指针到达终点停止遍历
11
    while (first != null) {
12
        first = first.next;
13
        second = second.next;
14
    }
15
    second.next = second.next.next;//删去节点
16
    return dummy.next;
17
}

不设置空指针版
1
class Solution {
2
    public ListNode removeNthFromEnd(ListNode head, int n) {
3
        ListNode first = head;
4
        ListNode second = head;
5
        for(int i=0;i<=n;i++)
6
        {
7
            if(first==null)
8
                return head.next;
9
            first = first.next;
10
        }
11
        while(first!=null)
12
        {
13
            first=first.next;
14
            second=second.next;
15
        }
16
        second.next=second.next.next;
17
        return head;
18
    }
19
}

Posted on Edited on In

1. 题目描述（中等难度）

题目描述

  • 概述：涉及到倒数第几个节点的问题。我的思路是将问题转化为正数第几个的问题，或使用快慢指针。

    2. 我的解法

思路：

  • 先得到链表的节点数，即节点长度
  • 再计算旋转点是正数的第几个数。
  • 计算新的k值，忽略重复旋转的次数
  • 如果最后k==0，说明无需旋转，直接输出。
  • 设置pre指针。pre的next指向需要旋转的链表的第一个节点。将他们整体移到首部
    问题：我的解法太过复杂，在计算链表长度时，可以保存链表的尾指针，这样在第二遍循环时，就不用寻找了。
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
class Solution {
10
    public ListNode rotateRight(ListNode head, int k) {
11
        if(head==null)return null;//如果链表为空
12
        //先计算节点数量
13
        ListNode l1=head;
14
        int dotnum=0;
15
        while(l1!=null)
16
        {
17
            dotnum++;
18
            l1=l1.next;
19
        }
20
        //倒转
21
        if(k>=dotnum)
22
            k=k%dotnum;
23
        if(k==0) return head//0属于特判，相当于没有反转，之前没有考虑到
24
        ListNode pre=head;
25
        int rotalteindex=dotnum-k;// 计算可得，pre的下一个节点就是要倒转的序列
26
        while(pre!=null)
27
        {
28
            if(rotalteindex==1)
29
            {
30
                ListNode ro=pre.next;
31
                pre.next=null;
32
                pre=ro;
33
                while(ro.next!=null)//找到旋转链表的尾部指针，使其直接指向总链表的head
34
                 ro=ro.next;
35
                ro.next=head;
36
                head=pre;//更新head
37
                break;
38
            }
39
            pre=pre.next;
40
            rotalteindex--;
41
        }
42
        return head;
43
    }
44
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
    解决问题：
    1
    /**
    2
     * Definition for singly-linked list.
    3
     * public class ListNode {
    4
     *     int val;
    5
     *     ListNode next;
    6
     *     ListNode(int x) { val = x; }
    7
     * }
    8
     */
    9
    class Solution {
    10
        public ListNode rotateRight(ListNode head, int k) {
    11
            if(head==null)return null;
    12
            //先计算节点数量
    13
            ListNode l1=head;
    14
            ListNode tail=l1;
    15
            int dotnum=0;
    16
            while(l1!=null)
    17
            {
    18
                dotnum++;
    19
                tail=l1;//记录尾指针
    20
                l1=l1.next;
    21
    22
            }
    23
            //倒转
    24
            if(k>=dotnum)
    25
                k=k%dotnum;
    26
            if(k==0) return head;//0属于特判，相当于没有反转，之前没有考虑到
    27
            ListNode pre=head;
    28
            int rotalteindex=dotnum-k;// 计算可得，pre的下一个节点就是要倒转的序列
    29
            while(pre!=null)
    30
            {
    31
                if(rotalteindex==1)
    32
                {
    33
                    ListNode ro=pre.next;
    34
                    pre.next=null;
    35
                    tail.next=head;//直接使用尾指针
    36
                    head=ro;
    37
                    break;
    38
                }
    39
                pre=pre.next;
    40
                rotalteindex--;
    41
            }
    42
            return head;
    43
        }
    44
    }

    3方法二：

    这道题不能直接使用快慢指针，不求链表总长，因为k是一个任意大的数，存在重复旋转的问题。
    如果k<=链表总长，那么可以直接用快慢指针
    1
    class Solution {
    2
        public ListNode rotateRight(ListNode head, int k) {
    3
            if(head==null)return null;
    4
           //利用快慢指针
    5
           ListNode first=head;
    6
           ListNode second=head;
    7
           for(int i=0;i<k;i++)
    8
                first=first.next;
    9
            while(first.next!=null)//使快指针最后指向尾节点
    10
            {
    11
                first=first.next;
    12
                second=second.next;
    13
            }
    14
            ListNode newhead=second.next;
    15
            second.next=null;
    16
            first.next=head;
    17
            head=newhead;
    18
            return newhead;
    19
        }
    20
    }

    4 总结

    对于针对链表中倒数第n个节点的问题，可以使用快慢指针或先求链表总长len，在计算节点正数的顺序。使用第一中方法的前提是k<=len.

Posted on In

官方文档

1. String类简述

1.1 类结构

public final class String
extents: Object
implements:

  • Serializable
  • Comparable
  • CharSequence

1.2 综述

  • 由于是final类，所以String是constant，创建后就不能修改。但String buffers支持可变string。由于String对象的不可变性，使其可以被分享。
  • String concatenation：Java的设计着提供了‘+’操作符，方便将其他对象转化为string。通过StringBuilder（or StringBuffer）类支持多个String连接
  • -String converson：Java的设计着提供了‘+’操作符，方便的将其他对象转化为string。通过Object类的toString（）方法。

    2. Constructor Summary-构建方法

  • String()
  • String(byte[] bytes)

    3 Method Summary

  • char charAt(int index)
  • int codePointAt(int index)
  • int compareTo(String anotherString)
  • int compareToIgnoreCase(String str)
  • String concat(String str)
  • boolean contains(CharSuquence s)
  • boolean contentEquals(CharSuquence s)
  • boolean equals(Object anObject)
  • byte[] getBytes()
  • int indexOf()
  • int indexOf(int ch)
  • int indexOf(int ch,int fromIndex)
  • int indexOf(String str)
  • int indexOf(String str, int fromIndex)
  • boolean isEmpty()
  • int lastIndexOf()
  • int length()
  • String replace(char oldChar, char newChar)
  • Stirng[] split(String regex)
  • String substring(int beginIndex,in endIndex)
  • char[] toCharArray()
  • static String valueOf(char c)

Posted on In

1. 题目描述（中等题目）

题目描述

  • 就是查找字符串中最长的一个回文字串，结果唯一

    2 我的解法

    思路：暴力解法，滑动窗口。从大到小查找，每一个窗口的内容都判断是否时回文，是，就直接返回结果。这样做保证返回的最长回文字串之一。
    1
    //题目思路是 设置滑动窗口，从大到小查找
    2
    class Solution {
    3
        public boolean isPalindromic(String s,int start,int end)
    4
        {
    5
            while(start<end)
    6
                if (s.charAt(start++)!= s.charAt(end--))
    7
                    return false;
    8
            return true;
    9
        }
    10
        public String longestPalindrome(String s) {
    11
            int n = s.length();
    12
            if(n==0)//注意判空
    13
                return "";
    14
            for(int w=n ; w>1 ; w--)//窗口大小
    15
            {
    16
               for(int i=0,j=i+w-1;j<n&&i<n;i++,j++)
    17
                {
    18
                    if(isPalindromic(s,i,j))
    19
                        return s.substring(i,j+1);
    20
                }
    21
            }
    22
            return String.valueOf(s.charAt(0));
    23
        }
    24
    }
  • 时间复杂度：最坏O($n^3$)。主函数与两层循环，每次循环的最大值都是n，所以是$n^2$，在判断回文串时，最大值是n，所以一共O($n^3$)
  • 空间复杂度：O(1)

Posted on

KDD18 Neural Memory Streaming Recommender Networks with Adversarial Training

摘要

随着各种社交媒体和电子商务平台的日益普及，大量的用户行为数据（例如，用户交易数据，评级和评论数据）以前所未有的且不断增长的规模持续生成。研究具有流数据输入的推荐器系统更为现实和实用。用户生成的流数据呈现出独特的属性，例如时间排序，连续和高速，这对曾经非常成功的推荐技术提出了巨大的新挑战。尽管最近已经基于循环神经模型开发了一些时间或顺序推荐器模型，但由于它们的短期记忆和捕获用户信息的能力有限，因此它们大多数只能应用于基于会话的推荐方案。长期稳定的利益。在本文中，我们提出了一种基于神经记忆网络和外部记忆的流式推荐模型，以统一的方式捕获和存储长期稳定利益和短期动态利益。开发了一种基于生成对抗网络（GAN）的自适应负采样框架，以优化我们提出的流推荐模型，有效地克服了传统的负采样方法的局限性，并提高了模型参数推断的有效性。在两个大型推荐数据集上进行了广泛的实验，实验结果表明了我们提出的模型在流推荐场景中的优越性。

introduction

亚马逊，netflix等很多公司依靠推荐系统推荐用户可能消费的媒体内容或产品的能力，获取利润。个性化推荐在现代生活总占有很大的比重
虽然推荐系统吸引了大量研究兴趣，但流式推荐系统的子区域仍未开发。诸如Amazon和Netflix之类的现实世界社交媒体和电子商务平台以前所未有的速度生成了大量的用户项目交互数据（即用户行为数据）。例如，在2017年11月11日的光棍节购物活动中，阿里巴巴进行了近15亿笔交易[30]。此类数据是按时间排序，连续，高速且随时间变化的，这决定了推荐系统中数据的流式传输性质。因此，使用流数据框架研究推荐器系统更为实用。实时流设置对常规推荐器系统提出了巨大的挑战，其中大多数推荐器是为静态设置设计的，并通过批处理学习技术来实现，在处理流情况时，它们通常具有以下缺点：1）重新运行批处理模型所花费的时间导致模型更新延迟； 2）在存在流数据的情况下无法跟踪快速变化的趋势（例如，用户偏好和商品受欢迎程度）； 3）显式存储所有历史数据的大量内存开销。
由于推荐系统本质上是一个增量过程，因此已经采用或开发了一些基于随机梯度下降（SGD）和粒子过滤器[11，54]的在线学习技术来支持流式推荐。但是，它们遭受“短期记忆”的问题，即，由于更新这些模型的算法仅基于最新的数据点，并且不考虑过去的观察结果，因此模型很快就忘记了在早期阶段学到的模式。基于这些在线学习算法的推荐模型无法捕获用户的长期稳定兴趣。最近，提出了一种基于循环神经模型的推荐系统[17，49]来解决流推荐问题，该系统采用递归神经网络（RNN）或长短期记忆（LSTM）来捕获和存储交互项的顺序模式或用户的动态兴趣。这样的模型学习输入数据的连续和表示，并在每个步骤中跨整个存储单元执行全局更新。这些体系结构设计鼓励RNN / LSTM从数据中捕获顺序模式，这使得基于RNN / LSTM的推荐系统特别擅长捕获顺序用户活动模式或用户时间动态。它们通常应用于没有用户资料（即用户的历史互动数据）的基于会话的推荐方案。但是，像在线学习算法一样，RNN / LSTM在建模和捕获用户的长期稳定兴趣方面也有局限性，而这些兴趣几乎不受时间因素的影响。作者认为用户的兴趣几乎不受时间的影响。
为此，我们提出了一种名为神经记忆推荐网络（NMRN）的新型模型。 NMRN受神经图灵机（NTM）[14]和内存网络（NemNN）[37]的启发，由两个主要组件组成：增强的存储用户和商品信息的存储器，以及与用户活动数据交互并读取或读取数据的控制器网络。写的回忆。具有外部存储器的增强控制器网络将存储和处理信息的任务分开，并使网络仅专注于处理存储在其外部的信息。它还增加了存储知识的能力，因此，如有必要，用户的长期和稳定偏好可以保持不变。而且，NMRN可以像物理计算机一样按需灵活，明确地读取和写入存储器。 NMRN鼓励在内存中进行本地更改，而这种直接对内部内存执行本地更新的功能使NMRN能够强大地集成用户最近的交互数据并捕获其新出现的兴趣。
具体而言，NMRN的外部存储器由密钥存储器和值存储器组成。键值存储网络（KV-MemNN）[26，57]的结构使原始的MemNN更适合处理成对数据。给定一个新的用户项交互对（u，v）实时到达系统后，NMRN首先从密钥存储器中生成一个由u激活的软地址。解决过程的灵感来自于注意力机制的最新进展，这种进展在计算机视觉[27，51]和NLP [23，59]领域很流行，但在推荐系统领域却很少研究。推荐器系统中应用的警告机制对于提高检索准确性和模型可解释性很有用。我们的注意力设计的基本思想是学习密钥存储器中的加权表示，然后通过Softmax函数作为软地址将其转换为概率分布。然后，NMRN基于软地址从值存储器中读取数据，从而得出一个既代表长期稳定的矢量

由于未观察到的样本数量非常多，我们采用[24]中提出的负采样方法来提高训练效率。大多数现有的否定抽样方法都使用随机抽样[1，24，38]或基于流行度的抽样策略[5，11]。但是，在这些抽样策略中生成的大多数负面示例可以很容易地与观察到的示例区分开，并且对培训的贡献很小，因为被抽样的项目可能与目标用户完全无关。此外，这些采样方法的适应性不足以生成对抗性负面示例，因为（1）它们是静态的，因此没有考虑到用户与某项之间的估计相似度或接近度在学习过程中会发生变化。例如，用户u和采样的噪声项v之间的相似度在一开始就很高，但是经过几个梯度下降步骤后，相似度就很低； （2）这些采样器是全局采样器，无法反映噪声项的信息量。特定用户。有鉴于此，我们基于生殖对抗网络（GAN）开发了一种自适应噪声采样器[13]来优化我们的模型，该模型同时考虑了特定用户和模型参数的当前值，以自适应地生成“困难”和infor -负面例子。此外，为了同时捕获用户和项目之间的一阶相似度以及用户之间和项目之间的二阶相似度以学习用户和项目的鲁棒表示，我们采用欧氏距离来度量用户之间的相似度灵感来自[19]的产品，而不是广泛采用的点积。
2468
2
总体而言，我们总结了本文的主要贡献：

Posted on

DLD模型总结

1. DLD 综述

我将知识追踪的过程分为两阶段。

  • 1 第一阶段：根据学生的做题序列，追踪学生的知识状态。——遗忘
  • 2 第二阶段：根据知识状态结合题目，预测学生表现。——题目难度

在阶段一中，遗忘往往伴随着学习出现。经典的艾宾浩斯遗忘曲线阐述了遗忘过程的不规律性，备受推崇的艾宾浩斯学习法更是推荐学习者重复练习，巩固知识，使短期记忆转化为长期记忆。长短期记忆共同影响着学生的学习效果，影响未来的表现。
在阶段二中，学生表现不仅与知识熟练度有关，也和题目难度有关，题目包含知识点，进一步可以得出，与知识点的难度有关。知识点的难度又与题目考查的知识的深度和知识点本身的难度有关。

2. 长短期记忆（遗忘）

2.1 想法启发

在推荐系统领域存在长期兴趣和短期兴趣的问题。四篇论文总结。

  1. IJCAI17 time-lstm：在根据用户的历史行为数据，推荐物品。作者认为，用户具有长期兴趣，以及用户上一时刻访问的物品，在短时间内对下一时刻访问的物品影响较大，也就是短期兴趣。

2.2 长短期记忆的特点

  1. 长期记忆和短期记忆具有不同的遗忘曲线
  2. 长期记忆可以保持较长的时间

2.3 在知识追踪领域结合长短期记忆预测学生表现的现状

2.3.1 现有考虑遗忘模型

  1. 两个BKT模型：仅部分考虑遗忘的影响因素
  2. 两个回归模型，简化了遗忘的过程，不能基于之前的记忆预测表现
  3. 深度学习模型：
    • 3.1 WWW19 全面考虑遗忘影响因素
    • 3.2

      2.4 深度学习模型的“长短期记忆”

      2.4.1 介绍现有卷积神经网络的发展史和特性

      2.4.2 三种改造LSTM的方法

2.5 现有考虑遗忘模型的“长短期记忆”

2.5.1 不能考虑长期记忆和短期记忆不同的衰减率

2.5.2 LSTM存储空间有限

2.6 总结

3. 问题难度

3.1 现有考虑遗忘模型总结

3.2 总结

4. DLD模型构建

4.1 长短期记忆

4.2 问题难度