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

Implement queue using stacks:   https://leetcode.com/problems/implement-queue-using-stacks/

1. class MyQueue {
   
2.     // Push element x to the back of queue.
   
3.     Stack<Integer> s1 = new Stack<Integer>();
   
4.     Stack<Integer> s2 = new Stack<Integer>();
   
5.     public void push(int x) {
   
6.         s1.push(x);
   
7.     }
   
8. 
   
9.     // Removes the element from in front of queue.
   
10.     public void pop() {
    
11.         if(!s2.empty())
    
12.         {
    
13.             s2.pop();
    
14.         }
    
15.         else
    
16.         {
    
17.             while(!s1.empty())
    
18.             {
    
19.                 s2.push(s1.pop());
    
20.             }
    
21.             s2.pop();
    
22.         }
    
23.     }
    
24. 
    
25.     // Get the front element.
    
26.     public int peek() {
    
27.         if(!s2.empty())
    
28.         {
    
29.             return s2.peek();
    
30.         }
    
31.         else
    
32.         {
    
33.             while(!s1.empty())
    
34.             {
    
35.                 s2.push(s1.pop());
    
36.             }
    
37.             return s2.peek();
    
38.         }
    
39.     }
    
40. 
    
41.     // Return whether the queue is empty.
    
42.     public boolean empty() {
    
43.         return s1.empty() && s2.empty();
    
44.     }
    
45. }

复制代码

Number of digit one:  https://leetcode.com/problems/number-of-digit-one/

1. public class Solution {
   
2.     public int countDigitOne(int n) {
   
3.         int result = 0;
   
4.         for(long i = 1; i <= n; i = i * 10)
   
5.         {
   
6.             long a = n / i;
   
7.             long b = n % i;
   
8.             result += (a + 8) / 10 * i;
   
9.             if(a % 10 == 1)
   
10.             {
    
11.                 result += b + 1;
    
12.             }
    
13.         }
    
14.         return result;
    
15.     }
    
16. }

复制代码

Maximal square:  https://leetcode.com/problems/maximal-square/

idea: 涉及到二维数组的，双重循环是必不可少的。

1. public class Solution {
   
2.     public int maximalSquare(char[][] matrix) {
   
3.         int result = 0;
   
4.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
   
5.         {
   
6.             return 0;
   
7.         }
   
8.         
   
9.         int m = matrix.length;
   
10.         int n = matrix[0].length;
    
11.         
    
12.         int[][] dp = new int[m][n];
    
13.         
    
14.         for(int i = 0; i < m; i++)
    
15.         {
    
16.             if(matrix[i][0] == '1')
    
17.             {
    
18.                 dp[i][0] = 1;
    
19.                 result = 1;
    
20.             }
    
21.         }
    
22.         
    
23.         for(int j = 0; j < n; j++)
    
24.         {
    
25.             if(matrix[0][j] == '1')
    
26.             {
    
27.                 dp[0][j] = 1;
    
28.                 result = 1;
    
29.             }
    
30.         }
    
31.         
    
32.         for(int i = 1; i < m; i++)
    
33.         {
    
34.             for(int j = 1; j < n; j++)
    
35.             {
    
36.                 if(matrix[i][j] == '0')
    
37.                 {
    
38.                     dp[i][j] = 0;
    
39.                 }
    
40.                 else
    
41.                 {
    
42.                     dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1]) + 1;
    
43.                     result = Math.max(dp[i][j], result);
    
44.                 }
    
45.             }
    
46.         }
    
47.         return result * result;
    
48.     }
    
49. }

复制代码

Palindrome linked list: https://leetcode.com/problems/palindrome-linked-list/

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. public class Solution {
   
10.     public boolean isPalindrome(ListNode head) {
    
11.        Stack<Integer> stack = new Stack<Integer>();
    
12.        ListNode fast = head;
    
13.        ListNode slow = head;
    
14.       
    
15.        while(fast != null && fast.next != null)
    
16.        {
    
17.            stack.push(slow.val);
    
18.            slow = slow.next;
    
19.            fast = fast.next.next;
    
20.        }
    
21.       
    
22.        if(fast != null)
    
23.        {
    
24.            slow = slow.next;
    
25.        }
    
26.       
    
27.        while(!stack.isEmpty())
    
28.        {
    
29.            int top = stack.pop();
    
30.            if(top != slow.val)
    
31.            {
    
32.                return false;
    
33.            }
    
34.            slow = slow.next;
    
35.        }
    
36.        return true;
    
37.     }
    
38. }

复制代码

love1point 发表于 2015-7-6 19:00
Count complete tree nodes: https://leetcode.com/problems/count-complete-tree-nodes/

这个写法真巧妙，复杂度跟我的非递归版本一样，都是O(log^2(n))

love1point 发表于 2015-7-8 22:24
Number of digit one:  https://leetcode.com/problems/number-of-digit-one/

这题是数位动归的题目，用暴力枚举的办法在面试中肯定是不能pass的，比如n = 两亿，如何解？

love1point 发表于 2015-7-10 11:25
Palindrome linked list: https://leetcode.com/problems/palindrome-linked-list/

这题还有O(1)空间复杂度的做法。楼主的方法中用到了栈，所以空间复杂度是O(n)。

继续琢磨琢磨？

love1point 发表于 2015-7-6 18:09
Power of two:  https://leetcode.com/problems/power-of-two/

idea: 这题为位操作题。

这题还有另一个等效的写法，用的是树状数组中的lowbit操作。

zhuli19901106 发表于 2015-7-10 14:24
这题还有O(1)空间复杂度的做法。楼主的方法中用到了栈，所以空间复杂度是O(n)。

继续琢磨琢磨？

嗯，题目follow up要求 o(1)空间。

我再看看

zhuli19901106 发表于 2015-7-10 14:22
这题是数位动归的题目，用暴力枚举的办法在面试中肯定是不能pass的，比如n = 两亿，如何解？

这道题，对我来说有难度。看来难点的题目很多都用dp