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

love1point

path sum ii: https://leetcode.com/problems/path-sum-ii/

idea: 一看这题又是用dfs解决的，套上dfs的模板，代码很快敲出来，这三行代码是我出错的地方，
我一直在想用 result.add(l) 这一行代替以下这三行。但总是不行。实际上dfs题目需要这样写，避免 l 里最后一个数据被抹了。
credit to zhuli19901106 的讨论哈

ArrayList<Integer> temp = new ArrayList<Integer>();
temp.addAll(l);
result.add(temp);

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList();
if(root == null)
{
return result;
}
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(root.val);
dfs(root, sum-root.val, l, result);
return result;
}
public void dfs(TreeNode node, int sum, ArrayList<Integer> l, List<List<Integer>> result)
{
if(node.left == null && node.right == null && sum == 0)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.addAll(l);
result.add(temp);
}
if(node.left != null)
{
l.add(node.left.val);
dfs(node.left, sum - node.left.val, l, result);
l.remove(l.size()-1);
}
if(node.right != null)
{
l.add(node.right.val);
dfs(node.right, sum - node.right.val, l, result);
l.remove(l.size()-1);
}
}
}

复制代码

love1point

Remove Nth Node From End of List ： https://leetcode.com/problems/remove-nth-node-from-end-of-list/

idea: 先算出链表长度，然后指针跑到要被删除节点的前一个节点，然后把要被删除节点的前一个节点的next 指向要被删除节点的下一个。但有bug，就是这种[1], 1
解决bug的方法，加个判断，我发现这个是我之前代码没过的原因，就是要删的是表头，怎么处理，我加了处理这种情况的代码就过了哈，多亏 zhuli19901106 的提醒
if(length == n)
      {
         head = head.next;
         return head;
      }

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode p = head;
while(p != null)
{
length++;
p = p.next;
}
p = head;
if(length == n)
{
head = head.next;
return head;
}
for(int i = 0; i < length - n - 1; i++)
{
p = p.next;
}
p.next = p.next.next;
return head;
}
}

复制代码

love1point

Majority element ii: https://leetcode.com/problems/majority-element-ii/

idea: 这题要求常量空间，自然不能考虑hashmap了。用到了一下这个算法思想解决： http://www.cs.rug.nl/~wim/pub/whh348.pdf

public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
int a = 0;
int b = 0;
int counta = 0;
int countb = 0;
for(Integer i : nums)
{
if(i == a)
{
counta++;
}
else if(i == b)
{
countb++;
}
else if(counta == 0)
{
a = i;
counta++;
}
else if(countb == 0)
{
b = i;
countb++;
}
else
{
counta--;
countb--;
}
}
counta = 0;
countb = 0;
for(Integer i : nums)
{
if(i == a)
{
counta++;
}
else if(i == b)
{
countb++;
}
}
if(counta > nums.length / 3)
{
result.add(a);
}
if(countb > nums.length / 3)
{
result.add(b);
}
return result;
}
}

复制代码

love1point

kth smallest element in a bst: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

idea: bst 中序遍历有序。其实这题很早就有了，只不过lc最近才加进来。注意这个，这里是 p = q.right; 而不是 p= p.right

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int result = 0;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode p = root;
while(!s.isEmpty() || p != null)
{
if(p != null)
{
s.push(p);
p = p.left;
}
else
{
TreeNode q = s.pop();
k--;
if(k == 0)
{
result = q.val;
}
p = q.right;
}
}
return result;
}
}

复制代码

love1point

本帖最后由 love1point 于 2015-7-3 18:53 编辑

Basic calculator: https://leetcode.com/problems/basic-calculator/

idea: 没啥算法思想，就是分情况讨论

感谢 zhuli19901106 提醒。这行 cur = cur * 10 + s.charAt(++i) - '0';
如果写成 cur = cur * 10 + s.charAt(i+1) - '0'; 就超因为i 不变了，死循环。

public class Solution {
public int calculate(String s) {
int result = 0;
int sign = 1;
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(Character.isDigit(c))
{
int cur = c - '0';
while(i + 1 < s.length() && Character.isDigit(s.charAt(i+1)))
{
cur = cur * 10 + s.charAt(++i) - '0';
}
result = result + cur * sign;
}
else if(c == '+')
{
sign = 1;
}
else if(c == '-')
{
sign = -1;
}
else if(c == '(')
{
stack.push(result);
result = 0;
stack.push(sign);
sign = 1;
}
else if(c == ')')
{
result = stack.pop()*result + stack.pop();
sign = 1;
}
}
return result;
}
}

复制代码

love1point

Power of two: https://leetcode.com/problems/power-of-two/

idea: 这题为位操作题。

public class Solution {
public boolean isPowerOfTwo(int n) {
if( n <= 0)
{
return false;
}
if((n & (n - 1)) == 0)
{
return true;
}
return false;
}
}

复制代码

love1point

Count complete tree nodes: https://leetcode.com/problems/count-complete-tree-nodes/

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int countNodes(TreeNode root)
{
if(root == null)
{
return 0;
}
int left = getLeft(root) + 1;
int right = getRight(root) + 1;
if(left == right)
{
return (2<<(left - 1)) - 1;
}
else
{
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
public int getLeft(TreeNode root)
{
int count = 0;
while(root.left != null)
{
count++;
root = root.left;
}
return count;
}
public int getRight(TreeNode root)
{
int count = 0;
while(root.right != null)
{
count++;
root = root.right;
}
return count;
}
}

复制代码

PickleRickPapa

楼主我要步你后尘了！

PickleRickPapa

一起加油！

love1point

PickleRickPapa 发表于 2015-7-8 01:41
楼主我要步你后尘了！

啥后尘？刷题找工作吗？

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

点评

评分

浏览过的版块