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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-9-18 05:52:44 | 只看该作者
全局:
这两天我在想如何才能把一道题目很清晰的表达出来,并且代码可以一次性写出来without errors.
1. 思路需要足够清晰,这是重点也是基础, 足够清晰是指完全知道每个分支应该写些什么
2. 沉下心要淡定, 不能因为一个题目看似复杂而慌张, 曾经面试的时候,题目简单但是判断逻辑较多, 就开始不淡定
3. 写代码追求: 从上到下,从整体到局部的写作思路
4. Double check 自己的写完的代码, 包括思路和语法
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-18 06:40:56 | 只看该作者
全局:
计算字符串的相似度, 给定两个字符串, 可以对字符串进行两种操作: 删除一个字符 or 修改一个字符, 请问最少需要多少次操作可以使得两个字符串相同.
比如给定: abcg, abc
有两种操作: 删除第一个字符串的a, b, c, g, 然后再删除第二个字符串的a, b, c, 一共7次操作使得两个字符串相同
或者直接删除第一个字符串的字符g, 一共操作一次使得两个字符串相同, 最短次数就是1

代码相对来说很容易,但是需要优化一下避免递归的重复计算
  1. def Solution(a, b, matrix):
  2.     # avoid repeatedly evoking the function
  3.     if a == "" or b == "":
  4.         return max(len(a), len(b))

  5.     if a[0] == b[0]:
  6.         return Solution(a[1:], b[1:], matrix)
  7.     else:
  8.         # parameterize by tuple
  9.         if (a[1:], b) in matrix:
  10.             p1 = matrix[(a[1:], b)]
  11.         else:
  12.             p1 = Solution(a[1:], b, matrix)
  13.             matrix[(a[1:], b)] = p1

  14.         if (a[1:], b[1:]) in matrix:
  15.             p2 = matrix[(a[1:], b[1:])]
  16.         else:
  17.             p2 = Solution(a[1:], b[1:], matrix)
  18.             matrix[(a[1:], b[1:])] = p1

  19.         if (a, b[1:]) in matrix:
  20.             p3 = matrix[(a, b[1:])]
  21.         else:
  22.             p3 = Solution(a, b[1:], matrix)
  23.             matrix[(a, b[1:])] = p1

  24.         return 1 + min(p1, p2, p3)


  25. if __name__ == "__main__":
  26.     print Solution("alutdon", "abcde", {})
复制代码

补充内容 (2018-9-18 06:49):
https://github.com/shenweihai1/a ... auty-Of-Programming

补充内容 (2018-9-18 06:49):
https://github.com/shenweihai1/a ... auty-Of-Programming

补充内容 (2018-10-23 07:55):
代码还是显得太长了!
回复

使用道具 举报

🔗
seraphiclori 2018-9-19 12:11:09 | 只看该作者
全局:
厉害了十三岁 求监督
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-19 12:53:57 | 只看该作者
全局:
看了一下2way partition问题,还有一题3way partition, 和2way思路一模一样

参看代码
  1. import java.util.Arrays;
  2. public class Two_way_partition {
  3.     private int [] Solution(int []a) {
  4.         if (a.length == 0) {
  5.             return new int[] {};
  6.         }
  7.         int low = 0, mid = 0 ;
  8.         while (mid < a.length) {
  9.             if (a[mid] == 0) {
  10.                 int temp = a[low] ;
  11.                 a[low] = a[mid] ;
  12.                 a[mid] = temp ;
  13.                 mid ++ ;
  14.                 low ++ ;
  15.             } else {
  16.                 mid ++ ;
  17.             }
  18.         }
  19.         return a ;
  20.     }
  21.     public static void main(String args[]) {
  22.         int [] input = new int [] {0, 1, 1, 0, 0, 0, 0, 1} ;
  23.         Two_way_partition obj = new Two_way_partition() ;
  24.         System.out.print(Arrays.toString(obj.Solution(input)));
  25.     }
  26. }
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-20 22:32:25 | 只看该作者
全局:
我现在比较推崇代码可以一次性不做任何修改的写对,这次还不错,代码没做任何修改一次性运行正确
  1. import java.util.Arrays;

  2. public class Find_Max {
  3.     private int[] Solution(int []input) {
  4.         if (input.length == 0) {
  5.             return new int[]{-Integer.MAX_VALUE, -Integer.MAX_VALUE, -Integer.MAX_VALUE} ;
  6.         }
  7.         int pre = input[0] ;
  8.         int sindex = 0 ; // start from the index
  9.         int mmax = -Integer.MAX_VALUE, fnumber = -Integer.MAX_VALUE, lnumber = -Integer.MAX_VALUE ;
  10.         for (int i = 1; i < input.length; i ++) {
  11.             if (pre > 0) {
  12.                 pre = input[i] + pre ;
  13.             } else {
  14.                 pre = input [i] ;
  15.                 sindex = i ;
  16.             }
  17.             if (pre > mmax) {
  18.                 mmax = pre ;
  19.                 fnumber = input[sindex] ;
  20.                 lnumber = input[i] ;
  21.             }
  22.         }
  23.         return new int[]{fnumber, lnumber, mmax};
  24.     }

  25.     public static void main(String args[]) {
  26.         Find_Max obj = new Find_Max() ;
  27.         System.out.println(Arrays.toString(obj.Solution(new int []{-2, 11, -4, 13, -5, -2})));
  28.         System.out.println(Arrays.toString(obj.Solution(new int []{-2, -11, -4, -13, -5, -2})));
  29.         System.out.println(Arrays.toString(obj.Solution(new int []{})));
  30.         System.out.println(Arrays.toString(obj.Solution(new int []{-1, 0, -2})));
  31.         System.out.println(Arrays.toString(obj.Solution(new int []{0, 0, 0, 0})));
  32.     }
  33. }
复制代码

补充内容 (2018-10-23 08:09):
寻找连续和最大的数
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-21 00:06:05 | 只看该作者
全局:
一次性写完查看是否有循环
  1. package linked;

  2. public class Find_Cycle {

  3.     private boolean Solution(Node root) {
  4.         // check if contains cycle
  5.         if (root == null) {
  6.             return false ;
  7.         }
  8.         Node fast = root.next ;
  9.         Node slow = root ;
  10.         while(fast != null && fast != slow) {
  11.             slow = slow.next ;
  12.             if (fast.next != null) {
  13.                 fast = fast.next.next ;
  14.             } else {
  15.                 return false ;
  16.             }
  17.         }

  18.         return fast != null;
  19.     }

  20.     public static void main(String args[]) {

  21.         Find_Cycle obj = new Find_Cycle() ;
  22.         Node n1 = new Node(1) ;
  23.         Node n2 = new Node(2) ;
  24.         Node n3 = new Node(3) ;
  25.         Node n4 = new Node(4) ;
  26.         Node n5 = new Node(5) ;
  27.         n1.setNext(n2);
  28.         n2.setNext(n3);
  29.         n3.setNext(n4);
  30.         n4.setNext(n5);
  31.         n5.setNext(n2);
  32.         System.out.println(obj.Solution(n1)); // true

  33.         Node n11 = new Node(1) ;
  34.         Node n21 = new Node(2) ;
  35.         Node n31 = new Node(3) ;
  36.         n11.setNext(n21);
  37.         n21.setNext(n31);
  38.         System.out.println(obj.Solution(n11)); // false

  39.         Node n111 = new Node(1) ;
  40.         n111.setNext(n111);
  41.         System.out.println(obj.Solution(n111)); // true
  42.     }
  43. }
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-21 12:35:18 | 只看该作者
全局:
对于链表node的复制啥的不熟悉写了一题725出bug了,明天继续看

补充内容 (2018-9-22 06:05):
今天仔细研读了一下代码,两个错误: 1, 做计算的时候优先级弄错了 2. 为空的情况没考虑

补充内容 (2018-10-23 08:14):
代码去哪里了哦
回复

使用道具 举报

🔗
sunnyshr 2018-9-22 02:07:45 | 只看该作者
全局:
帮顶:)))))
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-22 06:06:05 | 只看该作者
全局:
725 修改了三次才把代码提交正确
  1. package linked;

  2. import java.util.Arrays;

  3. public class Split_Parts {
  4.     public ListNode[] Solution(ListNode root, int k) {
  5.         int list_size = 0 ;
  6.         ListNode p = root ;
  7.         while(p != null) {
  8.             list_size ++ ;
  9.             p = p.next ;
  10.         }
  11.         int [] parts = new int [k] ;
  12.         if (list_size == 0) { // special case when root is empty
  13.             parts[0] = 0 ;
  14.         }
  15.         for (int i = 0; i < k; i ++) {
  16.             parts[i] = (list_size / k) + (list_size - k * (list_size / k) > i ? 1: 0); // 优先级处理好,最好加括号保证不错
  17.         }

  18.         ListNode res [] = new ListNode[parts.length] ;
  19.         p = root ;
  20.         ListNode h = root ;
  21.         for (int i = 0; i < parts.length; i ++) {
  22.             int size = parts[i] ;
  23.             if (size == 0) {
  24.                 res[i] = null ;
  25.             } else {
  26.                 ListNode n = h ;
  27.                 res[i] = n ; // current head pointer, new node, must know that
  28.                 size -- ;
  29.                 while(size > 0) {
  30.                     size --;
  31.                     p = p.next ;
  32.                 }
  33.                 h = p.next ;
  34.                 p.next = null ;
  35.                 p = h ;
  36.             }
  37.         }
  38.         return res ;
  39.     }

  40.     private void pintListNode(ListNode [] ps) {
  41.         for (ListNode p: ps) {
  42.             while(p != null) {
  43.                 System.out.print(p.val + " => ");
  44.                 p = p.next ;
  45.             }
  46.             System.out.println("null");
  47.         }
  48.     }

  49.     public static void main(String args[]) {
  50.         ListNode n1 = new ListNode(1) ;
  51.         ListNode n2 = new ListNode(2) ;
  52.         ListNode n3 = new ListNode(3) ;
  53.         ListNode n4 = new ListNode(4) ;
  54.         ListNode n5 = new ListNode(5) ;

  55.         n1.next = n2;
  56.         n2.next = n3;
  57.         n3.next = n4;
  58.         n4.next = n5;

  59.         Split_Parts obj = new Split_Parts() ;
  60.         obj.pintListNode(obj.Solution(n1, 3)) ;
  61.         obj.pintListNode(obj.Solution(null, 3)) ;
  62.     }
  63. }
复制代码

补充内容 (2018-10-23 08:15):
https://leetcode.com/problems/sp ... -parts/description/
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-23 07:15:11 | 只看该作者
全局:
Largest Smaller BST Key
Given a root of a Binary Search Tree (BST) and a number num, implement an efficient function findLargestSmallerKey that finds the largest key in the tree that is smaller than num. If such a number doesn’t exist, return -1. Assume that all keys in the tree are nonnegative.


Mock Interview 比较顺利,程序运行基本一遍就全部case通过,不过沟通还是大问题
  1. int findLargestSmallerKey(Node root, int num) {
  2.       // your code goes here
  3.       if (root == null) {
  4.         return -1 ;
  5.       }
  6.       int cur = root.key ;
  7.       if (cur >= num) {
  8.         return findLargestSmallerKey(root.left, num) ;
  9.       } else  {
  10.         int n =  findLargestSmallerKey(root.right, num) ;
  11.         return Math.max(n, cur) ;
  12.       }
  13.     }
复制代码

回复

使用道具 举报

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

本版积分规则

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