📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: hurricane_e
跳转到指定楼层
上一主题 下一主题
收起左侧

[CS61B_Spring 2015] Discussion3-Arrays vs. Linked Lists

🔗
 楼主| hurricane_e 2015-6-16 04:47:56 | 只看该作者
全局:
xiaobai024 发表于 2015-6-16 01:22
求问一下 2015 的视频是在哪里呢? 我看到YouTube上面还是2014的

https://berkeley-cs61b.github.io/public_html/index.html 课程主帖里有链接~
回复

使用道具 举报

🔗
xiaobai024 2015-6-16 04:53:33 | 只看该作者
全局:
hurricane_e 发表于 2015-6-16 04:47
https://berkeley-cs61b.github.io/public_html/index.html 课程主帖里有链接~

谢谢咯~~~不知道61A 是不是也有类似的链接?
回复

使用道具 举报

🔗
Casualet 2015-6-17 23:56:04 | 只看该作者
全局:
1:


Only if thecapacity is larger than the size of the array.


2:


3:
public class SentinelSList {
  private SNode front;
  private SNode back;

  public SentinelSList() {
    this.back = new SNode(0, null);
    this.front = new SNode(0, back);
}

  public void insert(double val, int position) {
        int i=0;
        SNode temp=new SNode(val,null);
        SNode next=front;
        while(next.next!=back){
             if(i==position){
                SNode t=next.next;
                next.next=temp;
                temp.next=t;
                return ;
             }else{
            next=next.next;
            i++;
         }      

       }
       SNode tBack=back;
       back=new SNode(0,null);
       tBack.val=val;
       tBack.next=back;        
}

  public static int []  xify(int [] x){

       int sum=0;
      for(int i=0;i<x.length;i++){
             sum+=x[i];
      }

      int [] re=new int[sum];

      int i=0;
      int j=0;
      int temp=0;
      for(;i<x.length;i++){
        for(temp=0;temp<x[i];temp++){
             re[j++]=x[i];
         }

     }
   return re;
  }


  public void printList(){
       SNode s=front.next;
       while(s!=back){
          System.out.println(s.val+" ");   
          s=s.next;
      }


   }

  public static void main(String args[] ){
       SentinelSList s=new SentinelSList();

       s.insert(1,0);
       s.insert(2,1);
       s.insert(3,2);
       s.insert(4,3);
       s.insert(5,4);
       s.insert(6,-1);
       s.insert(7,10);
       s.printList();
       int [] input={3,2,1};
       input=xify(input);
       for(int i=0;i<input.length;i++){
         System.out.print(input[i]+" ");
      }
  }
}




每天一题,先赶上进度再来看大家的代码吧...


回复

使用道具 举报

🔗
whosays 2015-6-18 00:27:29 | 只看该作者
全局:
Array Insertion:
public class arrayOp {
        public static int[] insert(int[] x, int val, int position) {
                int[] y = new int[x.length + 1];
                int i = 0;
                y[position] = val;
                while (i < y.length) {
                        if (i > position) {
                                y[i] = x[i-1];

                        } else if (i < position) {  
                                y[i] = x[i];
                        }
                        i += 1;
                }
                return y;
        } // close insert method
}

SList:
public class SList {
        // instantiation
        private SNode head;
        public SList (double item) {
                head = new SNode(item, null);
        }

        // insert val to the indexed position
        public void insert(double val, int position){
        // my own codes start here                
                if ((head == null) || (position == 0)) {
                        head = new SNode (val, head); // invalid insert position & reach the right position
                } else {
                        while ((position != 0) && (head != null)){
                                head = head.next;
                                position -= 1;
                        } // close while loop
                        SNode oldHead = head;
                        head = new SNode(val, oldHead);
                }
        } // close insert method
SentinelList:
public class SList {
        // instantiation
        private SNode head;
        public SList (double item) {
                head = new SNode(item, null);
        }

        // insert val to the indexed position
        public void insert(double val, int position){
        // my own codes start here                
                if ((head == null) || (position == 0)) {
                        head = new SNode (val, head); // invalid insert position & reach the right position
                } else {
                        while ((position != 0) && (head != null)){
                                head = head.next;
                                position -= 1;
                        } // close while loop
                        SNode oldHead = head;
                        head = new SNode(val, oldHead);
                }
        } // close insert method
回复

使用道具 举报

🔗
whosays 2015-6-18 00:31:00 | 只看该作者
全局:
本帖最后由 whosays 于 2015-6-18 00:35 编辑
a0106660 发表于 2015-6-14 11:43
感觉你们插入的循环方法和我不一样。我是先求出SIZE  然后用SIZE 判断插入位置合不合法,再用for 循环插入 ...

我也引入了size,个人理解这题就是两个sentinel node。如果再做细点就跟老师课上的例子一样,可以在前插或在后插,并分别get前后的新元素,我觉得只做这题只要实现前、后插的一种就够了。欢迎讨论
回复

使用道具 举报

🔗
西风吹草 2015-6-20 12:01:50 | 只看该作者
全局:
本帖最后由 西风吹草 于 2015-6-20 12:09 编辑

1.
        public static int[] insert(int[] x, int val, int position){
                int[] y = new int[x.length + 1];
                System.arraycopy(x, 0, y, 0, position);
                y[position] = val;
                System.arraycopy(x, position, y, position + 1, x.length - position);
                return y;
        }

2.
public class SList {
        private SNode head;
        public void insert(double val, int position){
                for (int i = 0; i < position && head != null; i ++){
                        head = head.next;
                }
                head = new SNode(val, head);
        }
}

3b.


评分

参与人数 1大米 +20 收起 理由
zzwcsong + 20

查看全部评分

回复

使用道具 举报

🔗
Kengo 2015-10-16 10:23:34 | 只看该作者
全局:
  1. /** Singly linked lists
  2. */

  3. public class SNode {
  4.     public SNode next;
  5.     public double val;
  6.     public SNode(double val, SNode next) {
  7.         this.next = next;
  8.         this.val = val;
  9.     }
  10.    
  11. }

  12. /** Singly linked list
  13. */

  14. public class SList {
  15.     public SNode head;
  16.     public int size;
  17.     /** insert a value val at position
  18.      *  destructive approach
  19.      *  if the position is invalid, insert the node at the end
  20.      */
  21.    
  22.     public SList(double val) {
  23.         head = new SNode(val, null);
  24.         size = 1;
  25.     }

  26.     public SList() {
  27.         this.head = null;
  28.         size = 0;
  29.     }

  30.     public void insertBack(double val) {
  31.         SNode p = head;

  32.         if (head == null) {
  33.             head = new SNode(val, null);
  34.         
  35.         } else {
  36.             while(p.next != null) {
  37.                 p = p.next;
  38.             }
  39.             p.next = new SNode(val, p.next);
  40.             size += 1;
  41.         }
  42.     }


  43.     public void insert(double val, int position) {
  44.         SNode p = head;
  45.         if (position < 0 || position >= size){
  46.             insertBack(val);
  47.         } else if (position == 0) {
  48.             head = new SNode(val, head);
  49.             size += 1;
  50.         } else {

  51.             for(int i = 0; i < position - 1; i++) {
  52.                 p = p.next;
  53.             }
  54.             p.next = new SNode(val, p.next);
  55.             size += 1;
  56.         }
  57.     }


  58.     public void printList() {
  59.         SNode p = head;
  60.         while( p != null) {
  61.             System.out.println(p.val);
  62.             p = p.next;
  63.         }

  64.     }



  65.     public static void main(String[] args) {
  66.         SList list = new SList(5.0);

  67.         list.insert(6, 1);
  68.         list.insert(2, 2);
  69.         list.insert(10, 1);
  70.         list.insert(10, 0);

  71.         int inValidPos1 = -1;
  72.         int inValidPos2 = 5;

  73.         list.insert(11, inValidPos1);
  74.         list.insert(12, inValidPos2);

  75.         list.printList();
  76.     }
  77. }

  78. /** Insert elements into a SentinelList.
  79. * if the posiiton is invalid, insert the node at the end
  80. */

  81. public class SentinelSList {
  82.     private SNode front;
  83.     private SNode back;
  84.     private int size;

  85.     public SentinelSList() {
  86.         this.back = new SNode(0, null);
  87.         this.front = new SNode(0, back);
  88.         this.size = 0;
  89.     }

  90.     public void printList() {
  91.         SNode p = front.next;
  92.         while( p != back) {
  93.             System.out.println(p.val);
  94.             p = p.next;
  95.         }

  96.     }

  97.     public void insertBack(double val) {
  98.         SNode p = front.next;

  99.         if (p == back){
  100.             front.next = new SNode(val, back);

  101.         } else {
  102.             while(p.next != back) {
  103.                 p = p.next;
  104.             }
  105.             p.next = new SNode(val, p.next);
  106.             size += 1;
  107.         }
  108.     }

  109.     public void insert(double val, int position) {
  110.         SNode p = front.next;
  111.         if (position < 0 || position >= size){
  112.             insertBack(val);
  113.         } else if (position == 0) {
  114.             front.next = new SNode(val, front.next);
  115.             size += 1;
  116.         } else {

  117.             for(int i = 0; i < position - 1; i++) {
  118.                 p = p.next;
  119.             }
  120.             p.next = new SNode(val, p.next);
  121.             size += 1;
  122.         }
  123.     }

  124.     public static void main(String[] args) {
  125.         SentinelSList list = new SentinelSList();

  126.         list.insert(6, 0);
  127.         list.insert(2, 1);
  128.         list.insert(10, 1);
  129.         list.insert(10, 0);

  130.         int inValidPos1 = -1;
  131.         int inValidPos2 = 5;

  132.         list.insert(11, inValidPos1);
  133.         list.insert(12, inValidPos2);

  134.         list.printList();
  135.     }

  136. }
复制代码

评分

参与人数 1大米 +20 收起 理由
zzwcsong + 20

查看全部评分

回复

使用道具 举报

🔗
HNAKXR 2016-1-31 21:34:48 | 只看该作者
全局:
本帖最后由 HNAKXR 于 2016-1-31 21:37 编辑

1 Array Insertion
  1. import java.util.Arrays;

  2. public class Insert {
  3.         public static int[] insert(int[] x, int val, int position) {
  4.                 int[] result = new int[x.length + 1];
  5.                 for (int i = 0; i < x.length + 1; i++) {
  6.                         if (i < position) {
  7.                                 result[i] = x[i];
  8.                         } else if (i == position) {
  9.                                 result[i] = val;
  10.                         } else {
  11.                                 result[i] = x[i - 1];
  12.                         }
  13.                 }
  14.                 return result;
  15.         }

  16.         public static void main(String[] args) {
  17.                 int[] x = {5, 9, 14, 15};
  18.                 int[] y = insert(x, 6, 2);
  19.                 System.out.println(Arrays.toString(y));
  20.         }
  21. }
复制代码
2 Singly Linked Lists
  1. public class SList {
  2.         private SNode front;

  3.         public void insert(double val, int position) {
  4.                 int i = 0;
  5.                 SNode p = front;

  6.                 if (p == null || position == 0) {
  7.                         front = new SNode(val, front);
  8.                 } else {
  9.                         while (p.next != null && i < position - 1) {
  10.                                 p = p.next;
  11.                                 i++;
  12.                         }
  13.                         p.next = new SNode(val, p.next);
  14.                 }
  15.                 size = size + 1;
  16.         }
  17. }
复制代码
3 Sentinel Nodes
  1. public class SentinelSList {
  2.         private SNode front;
  3.         private SNode back;

  4.          public void insert(double val, int position) {
  5.                 SNode p = front;
  6.                 int i = 0;
  7.                 while (p.next != back && i < position) {
  8.                         p = p.next;
  9.                         i++;
  10.                 }
  11.                 if (i == position) {
  12.                         p.next = new SNode(val, p.next);
  13.                 } else {
  14.                         back.next = new SNode(val, null);
  15.                 }
  16.         }
  17. }
复制代码

评分

参与人数 1大米 +20 收起 理由
zzwcsong + 20

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表