Blogs

0%

LintCode记录

发表于 更新于 分类于
本文字数： 9k 阅读时长 ≈ 15 分钟

记录刷的那些麻烦的题

二叉树的所有路径：

1
/**
2
 * Definition of TreeNode:
3
 * public class TreeNode {
4
 *     public int val;
5
 *     public TreeNode left, right;
6
 *     public TreeNode(int val) {
7
 *         this.val = val;
8
 *         this.left = this.right = null;
9
 *     }
10
 * }
11
 */
12
//递归解法：
13
public List binaryTreePaths(TreeNode root) {
14
    List<String> leftList=new ArrayList<>();
15
    if(root==null)
16
        return leftList;
17
    if(root.left!=null){
18
        for(String list:binaryTreePaths(root.left))
19
            leftList.add(root.val+"->"+list);
20
    }
21
    if(root.right!=null){
22
        for(String list:binaryTreePaths(root.right))
23
            leftList.add(root.val+"->"+list);
24
    }
25
    if(root.right==null&&root.left==null){
26
        leftList.add(String.valueOf(root.val));
27
    }
28
    return leftList;
29
}
30
31
//非递归解法：
32
public class Solution {
33
  public List binaryTreePaths(TreeNode root) {
34
    List list=new ArrayList<>();
35
    if(root==null)
36
  return list;
37
  boolean down=true;
38
  Stack stack=new Stack<>();
39
  Stack result=new Stack<>();
40
  TreeNode test=root;
41
  while(true){
42
    if(test.left!=null&&test.right!=null){
43
      if(down){
44
        if(test==root){
45
          result.push(String.valueOf(test.val));
46
          result.push(String.valueOf(test.val));
47
        }
48
        else{
49
          String str=result.pop();
50
          result.push(str+"->"+String.valueOf(test.val));
51
          result.push(str+"->"+String.valueOf(test.val));
52
        }
53
        stack.push(test);
54
        test=test.left;
55
        down=true;
56
        }else{
57
          result.push(String.valueOf(result.pop()));
58
          test=test.right;
59
          down=true;
60
        }
61
      }else if(test.left!=null){
62
        if(test==root){
63
          result.push(String.valueOf(test.val));
64
        }else
65
          result.push(result.pop()+"->"+String.valueOf(test.val));
66
          test=test.left;
67
        }else if(test.right!=null){
68
            if(test==root){
69
                result.push(String.valueOf(test.val));
70
            }else
71
                result.push(result.pop()+"->"+String.valueOf(test.val));
72
                test=test.right;
73
        }else{
74
            if(test==root){
75
                list.add(String.valueOf(test.val));
76
            }else{
77
                list.add(result.pop()+"->"+String.valueOf(test.val));
78
            }
79
            if(stack.empty())
80
                break;
81
            test=stack.pop();
82
            down=false;
83
        }
84
    }
85
    return list;
86
  }
87
}

动态规划：上楼问题。一次一个或者两个台阶，上N层楼。

1
// 递归：消耗太大，简直变态
2
public class Solution {
3
    /**
4
     * @param n: An integer
5
     * @return: An integer
6
     */
7
    public int climbStairs(int n) {
8
        if(n==0){
9
            return 0;
10
        }else if(n==1){
11
            return 1;
12
        }else if(n==2){
13
            return 2;
14
        }else{
15
        // write your code here
16
        return climbStairs(n-1)+climbStairs(n-2);
17
      }
18
    }
19
}
20
21
// 非递归解法：
22
public class Solution {
23
    /**
24
     * @param n: An integer
25
     * @return: An integer
26
     */
27
    public int climbStairs(int n) {
28
        if(n==0){
29
            return 1;
30
        }else if(n==1){
31
            return 1;
32
        }else if(n==2){return 2;}else{
33
        int last=1;
34
        int swap;
35
        int result=2;
36
        for(int i=0;i<n-2;i++){
37
            swap=result;
38
            result+=last;
39
            last=swap;
40
        }
41
        return result;
42
      }
43
    }
44
}

非递归的二叉树后序遍历

应该还有更简洁的方式

1
/**
2
 * Definition of TreeNode:
3
 * public class TreeNode {
4
 *     public int val;
5
 *     public TreeNode left, right;
6
 *     public TreeNode(int val) {
7
 *         this.val = val;
8
 *         this.left = this.right = null;
9
 *     }
10
 * }
11
 */
12
public class Solution {
13
    /**
14
     * @param root: The root of binary tree.
15
     * @return: Postorder in ArrayList which contains node values.
16
     */
17
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
18
        ArrayList list=new ArrayList();
19
        TreeNode node=root;
20
        if(root==null)
21
            return list;
22
        Stack<TreeNode> stack=new Stack<>();
23
        boolean down=true;
24
        Stack<TreeNode> last=new Stack<>();
25
        last.push(new TreeNode(0));
26
        while(true){
27
            if(node.left!=null&&node.right!=null){
28
                if(down){
29
                    stack.push(node);
30
                    stack.push(node);
31
                    node=node.left;
32
                    down=true;
33
                }else{
34
                    if(node==last.peek()){
35
                        list.add(node.val);
36
                         if(stack.empty())
37
                            break;
38
                        node=stack.pop();
39
                        last.pop();
40
                    }else{
41
                        last.push(node);
42
                        node=node.right;
43
                        down=true;
44
                    }
45
                }
46
            }
47
            else if(node.left!=null){
48
                if(down){
49
                    stack.push(node);
50
                    node=node.left;down=true;
51
                }else{
52
                    list.add(node.val);
53
                    if(stack.empty())
54
                            break;
55
                    node=stack.pop();
56
                }
57
            }else if(node.right!=null){
58
                if(down){
59
                    stack.push(node);
60
                     node=node.right;down=true;
61
                }else{
62
                    list.add(node.val);
63
                    if(stack.empty())
64
                            break;
65
                    node=stack.pop();
66
                }
67
            }else{
68
                list.add(node.val);
69
                if(stack.empty())
70
                    break;
71
                node=stack.pop();
72
                down=false;
73
            }
74
        }
75
        return list;
76
    }
77
}

二叉树的复制 非递归

1
public class Solution {
2
    /**
3
     * @param root: The root of binary tree
4
     * @return root of new tree
5
     */
6
    public TreeNode cloneTree(TreeNode root) {
7
        if(root==null)
8
            return null;
9
        TreeNode another=new TreeNode(root.val);
10
        TreeNode test=root;
11
        TreeNode test2=another;
12
        boolean down=true;
13
        Stack<TreeNode> stack1=new Stack<>();
14
        Stack<TreeNode> stack2=new Stack<>();
15
        while(true){
16
            if(test.left!=null&&test.right!=null){
17
                if(down){
18
                    stack1.push(test);
19
                    stack2.push(test2);
20
                    test2.left=new TreeNode(test.left.val);
21
                    test=test.left;
22
                    test2=test2.left;
23
                    continue;
24
                }else{
25
                    test2.right=new TreeNode(test.right.val);
26
                    test=test.right;
27
                    test2=test2.right;
28
                    down=true;
29
                    continue;
30
                }
31
            }
32
            else if(test.left!=null){
33
                test2.left=new TreeNode(test.left.val);
34
                test=test.left;
35
                test2=test2.left;
36
            }else if(test.right!=null){
37
                test2.right=new TreeNode(test.right.val);
38
                test=test.right;
39
                test2=test2.right;
40
            }else{
41
                if(stack1.empty())
42
                    break;
43
                test=stack1.pop();
44
                test2=stack2.pop();
45
                down=false;
46
            }
47
        }
48
        return another;
49
    }
50
}

二分查找

本来是很简单的问题，但是不知道position为啥要减一，回头再看.

1
public int binarySearch(int[] nums, int target) {
2
         if (nums == null)
3
            return -1;
4
        int position = nums.length;
5
        int[] temp = nums;
6
7
        while (true) {
8
            int len = temp.length;
9
            if (len == 2) {
10
                if (temp[0] == target)
11
                    return position - 2;
12
                else if(temp[1] == target)
13
                    return position-1;
14
                else
15
                    return -1;
16
            } else if (len == 1) {
17
                if(temp[0]==target)
18
                    return position-1;
19
                else
20
                    return -1;
21
            }
22
            len = len / 2;
23
            if (temp[len] >= target) {
24
                position = position-temp.length+len+1;
25
                temp = Arrays.copyOfRange(temp, 0, len + 1);
26
            } else {
27
                temp = Arrays.copyOfRange(temp, len + 1, temp.length);
28
            }
29
        }

二叉树的层次遍历

一层一层的输出二叉树： 基本解法

1
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
2
       // write your code here
3
       ArrayList<ArrayList<Integer>> result=new ArrayList<>();
4
       ArrayList<Integer> list=new ArrayList<>();
5
       if(root==null)
6
           return result;
7
       TreeNode currentNode=root;
8
       Queue queue=new LinkedList();
9
       int index=0;
10
       int index2=0;
11
       while(true){
12
           list.add(currentNode.val);
13
           if(currentNode.left!=null){
14
               queue.add(currentNode.left);
15
               index2++;
16
           }
17
           if(currentNode.right!=null){
18
               queue.add(currentNode.right);
19
               index2++;
20
           }
21
           if(index==0){
22
               index=index2;
23
               index2=0;
24
               result.add(new ArrayList(list));
25
               list.clear();
26
               if(queue.isEmpty())
27
                   break;
28
           }
29
           currentNode=(TreeNode)queue.remove();
30
           index--;
31
       }
32
       return result;
33
   }

二叉树的路径和

我觉得我的智商有问题…

1
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
2
        TreeNode node = root;
3
        List<List<Integer>> list = new ArrayList<>();
4
        if (root == null)
5
            return list;
6
        if (target == node.val) {
7
            if (node.left == null && node.right == null) {
8
                List l = new ArrayList();
9
                l.add(node.val);
10
                list.add(l);
11
                return list;
12
            }
13
        } else if (target < node.val&&node.left == null && node.right == null) {
14
            return null;
15
        }
16
        if (node.left != null) {
17
           List  l = binaryTreePathSum(node.left, target - node.val);
18
            if (l != null)
19
            for (int i = 0; i < l.size(); i++) {
20
                List ll = (List) l.get(i);
21
                List lll = new ArrayList();
22
                lll.add(node.val);
23
                lll.addAll(ll);
24
                list.add(lll);
25
            }
26
        }
27
        if (node.right != null) {
28
            List l = binaryTreePathSum(node.right, target - node.val);
29
            if (l != null)
30
            for (int i = 0; i < l.size(); i++) {
31
                List ll = (List) l.get(i);
32
                List lll = new ArrayList();
33
                lll.add(node.val);
34
                lll.addAll(ll);
35
                list.add(lll);
36
            }
37
38
        }
39
          return list;
40
    }

几个出错了的点：

  • 没考虑负数
  • new ArrayList(i)的参数i不是初始值，是initCapacity初始容量

二叉查找树的删除元素

1
public TreeNode removeNode(TreeNode root, int value) {
2
       // write your code here
3
        if(root==null)
4
           return null;
5
       if(root.val==value){
6
           if(root.left!=null){
7
               TreeNode retuNode=root;
8
               root=root.left;
9
               TreeNode max=root;
10
               while(max.right!=null){
11
                   max=max.right;
12
               }
13
               max.right=retuNode.right;
14
               return root;
15
           }else if(root.right!=null){
16
               root=root.right;
17
               return root;
18
           }
19
           return null;
20
       }else if(value<root.val){
21
           root.left=removeNode(root.left,value);
22
           return root;
23
       }else if(value>root.val){
24
           root.right=removeNode(root.right,value);
25
           return root;
26
       }
27
       return null;
28
   }

最长无重复字符的子串

这个简单，不过就是不知道使用了hashmap的话,时间复杂度应该怎么算

1
public int lengthOfLongestSubstring(String s) {
2
        // write your code here
3
       if (s.equals("")) {
4
            return 0;
5
        }
6
        char[] c = s.toCharArray();
7
        int start = 0;
8
        int end = 0;
9
        int length = 1;
10
        HashSet set = new HashSet();
11
        while (end < c.length) {
12
            boolean added = set.add(c[end]);
13
            length = set.size() > length ? set.size() : length;
14
15
            if (!added) {
16
                while (c[start] != c[end]) {
17
                    set.remove(c[start]);
18
                    start++;
19
                }
20
                start++;
21
            }
22
            end++;
23
        }
24
        return length;
25
    }