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

love1point

本帖最后由 love1point 于 2015-6-15 18:03 编辑

Linked List cycle: https://leetcode.com/problems/linked-list-cycle/

idea: 网上大部分解法都是这种，快慢指针，快的每次走两步，慢的每次走两步，如果有环，二者肯定会相遇，就像在800米跑道，俩同学一起跑步，二者速度不同，最终他们肯定会相遇，因操场是圆的

public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
if(head == null)
{
return false;
}
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(fast == slow)
{
return true;
}
}
return false;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-15 18:08 编辑

Binary tree preorder traversal: https://leetcode.com/problems/binary-tree-preorder-traversal/
idea: 递归代码比较简单。前序顺序就是根，左，右。理解了此题，inorder和postorder就改一行代码的顺序即可。

public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root == null)
{
return result;
}
helper(root, result);
return result;
}
public List<Integer> helper(TreeNode root, List<Integer> result)
{
if(root == null)
{
return result;
}
else
{
result.add(root.val);
}
helper(root.left, result);
helper(root.right, result);
return result;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-15 18:10 编辑

Reverse Linked List: https://leetcode.com/problems/reverse-linked-list/
idea: 此代码应该是网上能找到的最短的代码了。可以用俩个节点为例子进行过代码。用到了递归。

public class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
{
return head;
}
ListNode second = head.next;
head.next = null;
ListNode rest = reverseList(second);
second.next = head;
return rest;
}
}

复制代码

calalia

楼楼加油~~

love1point

本帖最后由 love1point 于 2015-6-15 18:16 编辑

Climbing stairs: https://leetcode.com/problems/climbing-stairs/
idea: 这题用动归。代码走一遍，很容易记下了。每次能爬一格或者两格，比如在第三格，它只能从第一格或第二格来的。所以。f(n) = f(n-1) + f(n-2)，f(n) 为爬到第n 格的可能性组合。初始状态f(0) =1,因为第一格只有一种可能性，就是从地面到第一格爬一步。f(1) = 2，两种，从地面直接爬两格，或者一格一格爬，从地面到一楼，一楼到二楼。

public class Solution {
public int climbStairs(int n) {
if(n == 0)
{
return 0;
}
int[] f = new int[3];
f[0] = 1;
f[1] = 2;
if(n == 1)
{
return f[0];
}
if(n == 2)
{
return f[1];
}
for(int i = 2; i < n; i++)
{
f[2] = f[0] + f[1];
f[0] = f[1];
f[1] = f[2];
}
return f[2];
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-6-22 15:30 编辑

Count primes: https://leetcode.com/problems/count-primes/

idea: 目前我还没找到比较容易记忆和理解的解法，暂且跟着代码走一遍好了，感觉好像也不太会考这种题。以后有看到好的代码再取代了。

更新：已找到很好解释改代码的算法思想，再次体会到算法思想的牛逼。先假设大于等于2的数且小于n的数为Prime, 如果该数为prime，在循环范围内，它的2倍数就不是prime。

public class Solution {
public int countPrimes(int n) {
if(n <= 2)
{
return 0;
}
boolean[] result = new boolean[n];
for(int i = 2; i < n; i++)
{
result[i] = true;
}
for(int i = 2; i < n; i++)
{
if(result[i])
{
for(int j = 2 * i; j < n; j += i)
{
result[j] = false;
}
}
}
int count = 0;
for(int i = 2; i < n; i++)
{
if(result[i])
{
count++;
}
}
return count;
}
}

复制代码

PeaceinUESTC

我想问下你怎么知道自己刷题的时候答案是正确的或者最优解？

love1point

PeaceinUESTC 发表于 2015-5-31 12:27
我想问下你怎么知道自己刷题的时候答案是正确的或者最优解？

我这些代码都是在leetcode accepted之后贴上来的。但不一定是最优解啊

love1point

本帖最后由 love1point 于 2015-6-15 18:21 编辑

Sort colors: https://leetcode.com/problems/sort-colors/

idea: 这题暂且记住如下代码，代码还是比较好记得。思路就是我们先把0排在一起，1排在一起，剩下的就是2了。

public class Solution {
public void sortColors(int[] nums) {
int index0 = 0;
int index1 =0;
for(int i = 0; i < nums.length; i++)
{
if(nums == 0)
{
nums = 2;
nums[index1++] = 1;
nums[index0++] = 0;
}
else
{
if(nums == 1)
{
nums = 2;
nums[index1++] = 1;
}
}
}
}
}

复制代码

love1point

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

implement strStr()： https://leetcode.com/problems/implement-strstr/

idea：记住要用 if(flag) 来控制输出。用个具体例子来过代码，比如 haystack 为 apple, needle 为 ap.

public class Solution {
public int strStr(String haystack, String needle) {
int m = haystack.length();
int n = needle.length();
for(int i = 0; i < m - n + 1; i++)
{
boolean check = true;
for(int j = 0; j < n; j++)
{
if(haystack.charAt(i+j) != needle.charAt(j))
{
check = false;
break;
}
}
if(check)
{
return i;
}
}
return -1;
}
}

复制代码

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

浏览过的版块