Leetcode 刷题记录！！！不信自己今年找不到工作！！！

love1point

本帖最后由 love1point 于 2015-6-26 17:21 编辑

Reverse words in a string: https://leetcode.com/problems/reverse-words-in-a-string/
idea: 此题还是有点难度的，尤其最后一行代码。通过这题学到，string的很多题目用StringBuilder

6.26.2015 更新：看了网上的讨论，这题一个for 循环应该是时间复杂度最低的了。首先用正则表达式把String 根据空格把单词分开放到数组里，但空格不包含进去，就是这行代码 String[] str = s.split(" ");
str 就是 ["the", "sky", "is", "blue"]. 然后从最后面开始，即blue这个string, 依次把单词加入到 string里。最后把stringbuilder 输出。也不是一次就能写出这样，比如最后一句，也是要通过test case来更改代码的，

public class Solution {
public String reverseWords(String s) {
if(s == null || s.length() == 0)
{
return s;
}
String[] str = s.split(" ");
StringBuilder sb = new StringBuilder();
for(int i = str.length-1; i >= 0; i--)
{
if(!str.equals(""))
{
sb.append(str).append(" ");
}
}
return sb.length() == 0? "" : sb.substring(0,sb.length()-1);
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-25 10:46 编辑

Search insert position: https://leetcode.com/problems/search-insert-position/
idea: 经过一次很仔细的探讨，此题已很熟练。二分查找法

public class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left <= right)
{
int mid = (left + right) / 2;
if(nums[mid] == target)
{
return mid;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return left;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-16 10:41 编辑

Pascal's triangle: https://leetcode.com/problems/pascals-triangle/
idea：此题其实不难，此题对于掌握好ArrayList的用法很有帮助

public class Solution {
public List<ArrayList<Integer>> generate(int numRows) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(numRows <= 0)
{
return result;
}
ArrayList<Integer> prev = new ArrayList<Integer>();
prev.add(1);
result.add(prev);
for(int i = 2; i <= numRows; i++)
{
ArrayList<Integer> curr = new ArrayList<Integer>();
curr.add(1);
for(int j = 0; j < prev.size()-1; j++)
{
curr.add(prev.get(j) + prev.get(j+1));
}
curr.add(1);
result.add(curr);
prev = curr;
}
return result;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-16 09:44 编辑

Linked list cycle ii: https://leetcode.com/problems/linked-list-cycle-ii/
idea: 网上大部分解法也是这种。网上还有个定理大概说，要指出他们的相遇点，必须让其中一个节点在相遇后回到 head节点，然后fast 和 slow再每次加1，再相遇的点就是 cycle开始的点

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null)
{
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
{
fast = head;
while(fast != slow)
{
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-16 09:41 编辑

Maximum depth of binary tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/
idea: 这题用递归做很简单。可用3个节点为例进行过代码。注意递归要有退出，即 if（root == null) 这种

public class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-27 19:03 编辑

Remove linked list elements: https://leetcode.com/problems/remove-linked-list-elements/
idea：这道题还是要多遍记忆才能掌握好，用到三个辅助变量，helper, p , q6.27.2015更新，经过linked lists专题复习，现在看这题已经变得容易了

public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode helper = new ListNode(0);
helper.next = head;
ListNode p = helper;
ListNode q = head;
while(q != null)
{
if(q.val == val)
{
p.next = q.next;
}
else
{
p=p.next;
}
q=q.next;
}
return helper.next;
}
}

复制代码

rogerdai

楼主可以放到github，看代码更方便些

love1point

rogerdai 发表于 2015-6-1 15:51
楼主可以放到github，看代码更方便些

嗯，但是直接放在一亩三分地更多人可得的啊。放github 链接可能没那么多人可以看到
谢谢你的建议

love1point

本帖最后由 love1point 于 2015-6-25 11:38 编辑

Word break：https://leetcode.com/problems/word-break/
idea: 这题如下解法我觉得比较难，比较难记下来，如果我发现更好解法，我再更新

6.25.2015: 看了网上的大部分解法，这题还是用动态规划去解，因为要保存已有的已经比较过的word。现在代码还是很容易记住的。多写几遍就可以了。可以用题目给的例子去把如下代码走一边哈。

public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
boolean[] result = new boolean[s.length() + 1];
result[0] = true;
for(int i = 0 ; i < s.length(); i++)
{
if(!result[i])
{
continue;
}
for(String word : wordDict)
{
int length = word.length();
int end = i + length;
if(end > s.length())
{
continue;
}
if(result[end])
{
continue;
}
if(s.substring(i, end).equals(word))
{
result[end] = true;
}
}
}
return result[s.length()];
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-16 09:36 编辑

Anagrams:  https://leetcode.com/problems/anagrams/

觉得这题比较难，不看别人的答案的话 (6月1日我觉得这题比较难，6月15日，这种题我觉得比较简单了，因为自己理解了怎么做，这就是进步吧)

这题用到了HashMap。字符串是不能对里面的元素排序。我们只能将他们转化到数组才能用 Arrays.sort()进行排序。就是如下三行代码，记住它，以后会常用到。这道题其实和如下这题很像(http://www.lintcode.com/en/problem/two-strings-are-anagrams/)，只不过lintcode这题更简单，只有两个字符串，而本题是有一个字符串数组。思路是一样的
         char[] arr = strs.toCharArray();
         Arrays.sort(arr);
         String t = String.valueOf(arr);

public class Solution {
public ArrayList<String> anagrams(String[] strs) {
ArrayList<String> result = new ArrayList<String>();
if(strs == null || strs.length == 0)
{
return result;
}
HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
for(int i = 0; i<strs.length; i++)
{
char[] arr = strs.toCharArray();
Arrays.sort(arr);
String t = String.valueOf(arr);
if(map.get(t) == null)
{
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(i);
map.put(t,l);
}
else
{
map.get(t).add(i);
}
}
for(ArrayList<Integer> l : map.values())
{
if(l.size() > 1)
{
for(Integer i : l)
{
result.add(strs);
}
}
}
return result;
}
}

复制代码

Leetcode 刷题记录！！！不信自己今年找不到工作！！！

浏览过的版块