一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3792|回复: 28
收起左侧

[算法题] LeetCode 刷题贴 JAVA代码,每日更新

[复制链接] |试试Instant~ |关注本帖
helifort 发表于 2014-12-25 12:42:10 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 helifort 于 2014-12-25 19:37 编辑

此贴用于刷题训练,保证每日更新,包括cleencode新题在内所有leetcode题目
You have solved 24 / 169 problems.

ARRAY
BINARY TREE
DP
LINKED LIST
  • Add Two Numbers
  • Merge Two Sorted Lists
  • Swap Nodes in Pairs
  • Merge K Sorted Linked Lists

MATH
  • Palindrome Number
  • Plus One
  • Reverse Integer

STRING
  • String to Integer
  • Valid Palindrome
  • Longest Palindromic Substring
  • Longest Substring with At Most Two Distinct Characters
  • Longest Substring Without Repeating Characters
  • One Edit Distance
  • Read N Characters Given Read4
  • Reverse Words in a String
  • Rotate String
  • Implement strStr()
  • Valid Number


                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

BINARY TREE
Validate Binary Search Tree
Given a binary tree, determine if it is a valid Binary Search Tree (BST).
Solution:
Time: O(n)
Space: O(n) stack space
Code:
  1. public class ValidateBinarySearchTree {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  4.     }

  5.     private boolean valid(TreeNode node, int low, int high) {
  6.         if (node == null) {
  7.             return true;
  8.         }
  9.         if (node.val > low && node.val < high) {
  10.             return valid(node.left, low, node.val)
  11.                     && valid(node.right, node.val, high);
  12.         } else {
  13.             return false;
  14.         }
  15.     }
  16. }
复制代码
今天提交的这个代码,本人看不出啥问题,但是OJ没有过,失败的case是
67 / 74 test cases passed.
Input:
{2147483647}
Output:
false
Expected:
true
请大神指示,哪里有问题。



Freetymekiyan 发表于 2014-12-25 13:55:02 | 显示全部楼层
flyaway25 发表于 2014-12-25 00:46
bst里面的node不能相等,那个返回true的逻辑还应该是>和

是的,疏忽疏忽
我要表达的意思是这段代码只要input里面有2147483647或-2147483648就会fail
回复 支持 1 反对 0

使用道具 举报

Freetymekiyan 发表于 2014-12-25 12:48:50 | 显示全部楼层
if (node.val > low && node.val < high) {
换成>=和<=
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 13:23:19 | 显示全部楼层
Freetymekiyan 发表于 2014-12-25 12:48
if (node.val > low && node.val < high) {
换成>=和

谢谢大神指点,不过,改成>= <=之后还是没过测试,失败的例子如下。貌似相等的就应该是false

64 / 74 test cases passed.
Status: Wrong Answer
Submitted: 0 minutes ago
Input:        {1,1}
Output:        true
Expected:        false
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2014-12-25 13:38:24 | 显示全部楼层
helifort 发表于 2014-12-25 00:23
谢谢大神指点,不过,改成>=

Sorry node.val是要在low和high的range当中
我的意思其实是,Integer.MAX_VALUE和Integer.MIN_VALUE也可以是node的值
看input是Integer.MAX_VALUE,你的code直接会返回false
回复 支持 反对

使用道具 举报

flyaway25 发表于 2014-12-25 13:46:41 | 显示全部楼层
helifort 发表于 2014-12-25 13:23
谢谢大神指点,不过,改成>=

bst里面的node不能相等,那个返回true的逻辑还应该是>和<。把那个input的low和high换成null试试,然后里面加个判定只有在low和high不是null的情况下比较大小。
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 13:49:33 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 18:06 编辑

另一个O(n)时间复杂度的方法,就是用in order 的方式遍历BST,判断遍历的节点是单调递增的,需要定义一个全局变量存放前缀节点。
Time: O(n)
Space: O(n)

code:
  1. public class Solution {
  2.     private TreeNode prev;
  3.     public boolean isValidBST(TreeNode root) {
  4.         prev = null;
  5.         return isIncreasing(root);
  6.     }

  7.     private boolean isIncreasing(TreeNode node) {
  8.         if (node == null) {
  9.             return true;
  10.         }
  11.         if (isIncreasing(node.left)) {
  12.             if (prev != null && prev.val >= node.val) {
  13.                 return false;
  14.             }
  15.             prev = node;
  16.             return isIncreasing(node.right);
  17.         }
  18.         return false;
  19.     }
  20. }
复制代码
这段代码OJ成功了
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 14:07:05 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 18:08 编辑
flyaway25 发表于 2014-12-25 13:46
bst里面的node不能相等,那个返回true的逻辑还应该是>和

谢谢fly大神,这次对了,因为测试case是int最大值

code:
  1. public class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return valid(root, null, null);
  4.     }

  5.     private boolean valid(TreeNode node, Integer left, Integer right) {
  6.         if (node == null) {
  7.             return true;
  8.         }
  9.         if ((left == null || left < node.val) && (right == null || right > node.val)) {
  10.             return valid(node.left, left, (Integer)node.val)
  11.                     && valid(node.right, (Integer)node.val, right);
  12.         }
  13.         return false;
  14.     }
  15. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 14:34:52 | 显示全部楼层
Freetymekiyan 发表于 2014-12-25 13:38
Sorry node.val是要在low和high的range当中
我的意思其实是,Integer.MAX_VALUE和Integer.MIN_VALUE也可 ...

对,明白了。
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 14:46:46 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 17:20 编辑

BINARY TREE

Maximum Depth of Binary Tree

O(n) runtime, O(log n) space – Recursion:
  1. public int maxDepth(TreeNode root) {
  2.     if (root == null) {
  3.         return 0;
  4.     }
  5.     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  6. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 16:48:31 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 17:18 编辑

BINARY TREE
Minimum Depth of Binary Tree


O(n) runtime, O(log n) space – DFS:
496 ms
  1. public int minDepth(TreeNode root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }

  5.         if (root.left == null) {
  6.             return minDepth(root.right) + 1;
  7.         }

  8.         if (root.right == null) {
  9.             return minDepth(root.left) + 1;
  10.         }
  11.         return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  12. }
复制代码
O(n) runtime, O(n) space – BFS:
428 ms
  1. public int minDepthBFS(TreeNode root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  6.         int depth = 1;
  7.         queue.add(root);
  8.         TreeNode rightMost = root;
  9.         while (!queue.isEmpty()) {
  10.             TreeNode node = queue.poll();
  11.             if (node.left == null && node.right == null) {
  12.                 break;
  13.             }
  14.             if (node.left != null) {
  15.                 queue.add(node.left);
  16.             }
  17.             if (node.right != null) {
  18.                 queue.add(node.right);
  19.             }
  20.             if (node == rightMost) {
  21.                 depth++;
  22.                 rightMost = (node.right != null) ? node.right : node.left;
  23.             }
  24.         }
  25.         return depth;
  26. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 17:01:20 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 19:13 编辑

ARRAY
Missing Ranges


Given a sorted integer array where the range of elements are [0, 99] inclusive, return its
missing ranges.
For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

Example Questions Candidate Might Ask:
Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.
Q: What if the given array contains all elements from the ranges?
A: Return an empty list, which means no range is missing.

Code:GitHub link
  1. public class MissingRanges {
  2.     public List<String> findMissingRanges(int[] A, int lower, int upper) {
  3.         List<String> ranges = new ArrayList<String>();
  4.         if (A == null || A.length == 0) {
  5.             ranges.add(getRange(lower, upper));
  6.             return ranges;
  7.         }
  8.         int n = A.length;
  9.         int prev = lower - 1;
  10.         for (int i = 0; i <= n; i++) {
  11.             int curr;
  12.             if (i == n) {
  13.                 curr = upper + 1;
  14.             } else {
  15.                 curr = A\[i\];
  16.             }
  17.             if (curr - prev >= 2) {
  18.                 ranges.add(getRange(prev + 1, curr - 1));
  19.             }
  20.             prev = curr;
  21.         }
  22.         return ranges;
  23.     }

  24.     private String getRange(int from, int to) {
  25.         if (from == to) {
  26.             return String.valueOf(from);
  27.         } else {
  28.             return from + "->" + to;
  29.         }
  30.     }
  31. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 17:47:01 | 显示全部楼层
STRING
Longest Substring with At Most Two Distinct Characters


Given a string S, find the length of the longest substring T that contains at most two
distinct characters.
For example,
Given S = “eceba”,
T is "ece" which its length is 3.

Code:
  1. public int lengthOfLongestSubstring(String s) {
  2.         if (s == null || s.length() == 0) {
  3.             return 0;
  4.         }
  5.         if (s.length() == 1) {
  6.             return 1;
  7.         }
  8.         Queue<Character> queue = new LinkedList<Character>();
  9.         int i = 0;
  10.         int maxLength = 0;
  11.         for (int j = 0; j < s.length(); j++) {
  12.             while (queue.contains(s.charAt(j))) {
  13.                 queue.poll();
  14.                 i++;
  15.             }
  16.             queue.offer(s.charAt(j));
  17.             maxLength = Math.max(j - i + 1, maxLength);
  18.         }
  19.         return maxLength;
  20.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 18:34:06 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 19:23 编辑

ARRAY
Two Sum II – Input array is sorted


Similar to Question [1. Two Sum], except that the input array is already sorted in
ascending order.
github link
Code:
  1. public class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         if (numbers == null || numbers.length == 0) {
  4.             return new int[]{-1, -1};
  5.         }
  6.         int arg1 = -1;
  7.         int arg2 = -1;
  8.         for (int i = 0; i < numbers.length; i++) {
  9.             int j = binarySearch(numbers, target - numbers[i], i + 1);
  10.             if (j != -1) {
  11.                 arg1 = i + 1;
  12.                 arg2 = j + 1;
  13.                 break;
  14.             }
  15.         }
  16.         return new int[]{arg1, arg2};
  17.     }

  18.     private int binarySearch(int[] numbers, int target, int start) {
  19.         int l = start;
  20.         int r = numbers.length - 1;
  21.         int m = l;
  22.         while (l + 1 < r) {
  23.             m = l + (r - l) / 2;
  24.             if (numbers[m] == target) {
  25.                 return m;
  26.             } else if (numbers[m] > target) {
  27.                 r = m;
  28.             } else {
  29.                 l = m;
  30.             }
  31.         }

  32.         if (numbers[l] == target) {
  33.             return l;
  34.         }
  35.         if (numbers[r] == target) {
  36.             return r;
  37.         }
  38.         return -1;
  39.     }
  40. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 19:22:38 | 显示全部楼层
ARRAY
Two Sum

github link
Code:
Use O(n) extra space to store number's position
  1. public class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         if (numbers == null || numbers.length == 0) {
  4.             return new int[]{-1, -1};
  5.         }
  6.         int arg1 = -1;
  7.         int arg2 = -1;
  8.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  9.         for (int i = 0; i < numbers.length; i++) {
  10.             int tmp = target - numbers[i];
  11.             if (map.containsKey(tmp)) {
  12.                 arg1 = map.get(tmp) + 1;
  13.                 arg2 = i + 1;
  14.                 break;
  15.             }
  16.             map.put(numbers[i], i);
  17.         }
  18.         return new int[]{arg1, arg2};
  19.     }
  20. }
复制代码
Code:
use two pointers with O(1) space
  1. public int[] twoSumTwoPointers(int[] numbers, int target) {
  2.         int i = 0;
  3.         int j = numbers.length - 1;
  4.         while (i < j) {
  5.             if (numbers[i] + numbers[j] == target) {
  6.                 return new int[]{i + 1, j + 1};
  7.             } else if (numbers[i] + numbers[j] > target) {
  8.                 j--;
  9.             } else {
  10.                 i++;
  11.             }
  12.         }
  13.         return new int[]{-1, -1};
  14.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-25 19:27:55 | 显示全部楼层
本帖最后由 helifort 于 2014-12-25 19:32 编辑

DP
Edit Distance


Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Code:
github link
  1. public class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         if (word1 == null && word2 == null) {
  4.             return 0;
  5.         }
  6.         int len1 = word1.length();
  7.         int len2 = word2.length();
  8.         int[][] dp = new int[len1 + 1][len2 + 1];
  9.         for (int i = 0; i <= len1; i++) {
  10.             dp[i][0] = i;
  11.         }
  12.         for (int i = 0; i <= len2; i++) {
  13.             dp[0][i] = i;
  14.         }
  15.         for (int i = 1; i <= len1; i++) {
  16.             for (int j = 1; j <= len2; j++) {
  17.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  18.                     dp[i][j] = dp[i - 1][j - 1];
  19.                 } else {
  20.                     dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
  21.                 }
  22.             }
  23.         }
  24.         return dp[len1][len2];
  25.     }
  26. }
复制代码
回复 支持 反对

使用道具 举报

robend 发表于 2014-12-27 17:34:22 | 显示全部楼层
楼主你现在在美国吗?如果在国内的话,请教一下:怎么拿到的Amazon Online access?
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-27 19:03:46 | 显示全部楼层
这个都不确定能拿到,不过一般是内推
回复 支持 反对

使用道具 举报

 楼主| helifort 发表于 2014-12-27 21:03:34 | 显示全部楼层
robend 发表于 2014-12-27 17:34
楼主你现在在美国吗?如果在国内的话,请教一下:怎么拿到的Amazon Online access?

在国内,有事可私聊
回复 支持 反对

使用道具 举报

zengm321 发表于 2014-12-28 07:32:59 | 显示全部楼层
有些新题,不错啊
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 09:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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