搜索
体验新版
<
一亩三分地»论坛 › 专业技术 › 刷题 › Leetcode 刷题记录！！！不信自己今年找不到工作！！！
1 ...161718192021222324下一页
返回列表 发新帖
楼主: love1point
跳转到指定楼层
上一主题 下一主题
收起左侧

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

 
刷题
🔗
 楼主| love1point 2015-8-1 08:47:27 | 只看该作者
全局：
Find Minimum in Rotated Sorted Array: https://leetcode.com/problems/fi ... tated-sorted-array/
  1. public class Solution {
  2.     public int findMin(int[] nums) {
  3.         int l = 0;
  4.         int r = nums.length - 1;
  5.         while( l < r)
  6.         {
  7.             int m = (l + r) / 2;
  8.             if(nums[m] >= nums[l] && nums[l] > nums[r])
  9.             {
  10.                 l = m + 1;
  11.             }
  12.             else
  13.             {
  14.                 r = m;
  15.             }
  16.         }
  17.         return nums[l];
  18.     }
  19. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-2 08:41:46 | 只看该作者
全局：
Valid Anagram: https://leetcode.com/problems/valid-anagram/

Idea: This problem is subsets problem of Anagrams, and it is easier than Anagrams. Second kill (We should MiaoSha).
  1. public class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.         char[] s1 = s.toCharArray();
  4.         Arrays.sort(s1);
  5.         String s2 = String.valueOf(s1);
  6.         
  7.         char[] t1 = t.toCharArray();
  8.         Arrays.sort(t1);
  9.         String t2 = String.valueOf(t1);
  10.         
  11.         if(s2.equals(t2))
  12.         {
  13.             return true;
  14.         }
  15.         else
  16.         {
  17.             return false;
  18.         }
  19.     }
  20. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-3 00:33:20 | 只看该作者
全局：
Search a 2D Matrix:  https://leetcode.com/problems/search-a-2d-matrix/
  1. public class Solution {
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
  4.         {
  5.             return false;
  6.         }
  7.         
  8.         int m = matrix.length;
  9.         int n = matrix[0].length;
  10.         
  11.         int l = 0;
  12.         int r = m * n - 1;
  13.         
  14.         while(l <= r)
  15.         {
  16.             int medium = (l + r) / 2;
  17.             int mx = medium / n;
  18.             int my = medium % n;
  19.             
  20.             if(matrix[mx][my] == target)
  21.             {
  22.                 return true;
  23.             }
  24.             else if(matrix[mx][my] < target)
  25.             {
  26.                 l = medium + 1;
  27.             }
  28.             else
  29.             {
  30.                 r = medium - 1;
  31.             }
  32.         }
  33.         return false;
  34.     }
  35. }

复制代码
Coderust: Hacking the Coding Interview
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-9 10:56:37 | 只看该作者
全局：
Best Time to Buy and Sell Stock III : https://leetcode.com/problems/be ... and-sell-stock-iii/
  1. public class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices == null || prices.length < 2)
  4.         {
  5.             return 0;
  6.         }
  7.         
  8.         int[] left = new int[prices.length];
  9.         int[] right = new int[prices.length];
  10.         
  11.         left[0] = 0;
  12.         int min = prices[0];
  13.         for(int i = 1; i < prices.length; i++)
  14.         {
  15.             min = Math.min(min, prices[i]);
  16.             left[i] = Math.max(left[i - 1], prices[i] - min);
  17.         }
  18.         
  19.         right[prices.length - 1] = 0;
  20.         int max = prices[prices.length - 1];
  21.         for(int i = prices.length - 2; i >= 0; i--)
  22.         {
  23.             max = Math.max(max, prices[i]);
  24.             right[i] = Math.max(right[i + 1], max - prices[i]);
  25.         }
  26.         
  27.         int profit = 0;
  28.         for(int i = 0; i < prices.length; i++)
  29.         {
  30.             profit = Math.max(profit, left[i] + right[i]);
  31.         }
  32.         return profit;
  33.     }
  34. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-9 10:57:07 | 只看该作者
全局：
Number of Islands: https://leetcode.com/problems/number-of-islands/
  1. public class Solution {
  2.     int m = 0;
  3.     int n = 0;
  4.     public int numIslands(char[][] grid) {
  5.         if(grid == null || grid.length == 0 || grid[0].length == 0)
  6.         {
  7.             return 0;
  8.         }
  9.         int result = 0;
  10.         m = grid.length;
  11.         n = grid[0].length;
  12.         for(int i = 0; i < m; i++)
  13.         {
  14.             for(int j = 0; j < n; j++)
  15.             {
  16.                 if(grid[i][j] == '1')
  17.                 {
  18.                     result++;
  19.                     dfs(grid, i, j);
  20.                 }
  21.             }
  22.         }
  23.         return result;
  24.     }
  25.    
  26.     public void dfs(char[][] grid, int i, int j)
  27.     {
  28.         if(i < 0 || i >= m || j < 0 || j >= n)
  29.         {
  30.             return;
  31.         }
  32.         if(grid[i][j] == '1')
  33.         {
  34.             grid[i][j] = '2';
  35.             dfs(grid, i - 1, j);
  36.             dfs(grid, i + 1, j);
  37.             dfs(grid, i, j - 1);
  38.             dfs(grid, i, j + 1);
  39.         }
  40.     }
  41. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-9 10:57:49 | 只看该作者
全局：
Set Matrix Zeroes: https://leetcode.com/problems/set-matrix-zeroes/
  1. public class Solution {
  2.     public void setZeroes(int[][] matrix) {
  3.         boolean firstRowZero = false;
  4.         boolean firstColumnZero = false;
  5.         
  6.         for(int i = 0; i < matrix.length; i++)
  7.         {
  8.             if(matrix[i][0] == 0)
  9.             {
  10.                 firstColumnZero = true;
  11.                 break;
  12.             }
  13.         }
  14.         
  15.         for(int i = 0; i < matrix[0].length; i++)
  16.         {
  17.             if(matrix[0][i] == 0)
  18.             {
  19.                 firstRowZero = true;
  20.                 break;
  21.             }
  22.         }
  23.         
  24.         for(int i = 1; i < matrix.length; i++)
  25.         {
  26.             for(int j = 1; j < matrix[0].length; j++)
  27.             {
  28.                 if(matrix[i][j] == 0)
  29.                 {
  30.                     matrix[i][0] = 0;
  31.                     matrix[0][j] = 0;
  32.                 }
  33.             }
  34.         }
  35.         
  36.          for(int i = 1; i < matrix.length; i++)
  37.          {
  38.             for(int j = 1; j < matrix[0].length; j++)
  39.             {
  40.                 if(matrix[i][0] == 0 || matrix[0][j] == 0)
  41.                 {
  42.                     matrix[i][j] = 0;
  43.                 }
  44.             }
  45.          }
  46.          
  47.          if(firstColumnZero)
  48.          {
  49.              for(int i = 0; i < matrix.length; i++)
  50.              {
  51.                  matrix[i][0] = 0;
  52.              }
  53.          }
  54.          
  55.           if(firstRowZero)
  56.          {
  57.              for(int i = 0; i < matrix[0].length; i++)
  58.              {
  59.                  matrix[0][i] = 0;
  60.              }
  61.          }
  62.     }
  63. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-9 11:33:20 | 只看该作者
全局：
Construct Binary Tree from Inorder and Postorder Traversal: https://leetcode.com/problems/co ... ostorder-traversal/
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  12.         int inStart = 0;
  13.         int inEnd = inorder.length - 1;
  14.         int postStart = 0;
  15.         int postEnd = postorder.length - 1;
  16.         return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);
  17.     }
  18.    
  19.     public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd)
  20.     {
  21.         if(inStart > inEnd || postStart > postEnd)
  22.         {
  23.             return null;
  24.         }
  25.         
  26.         int rootValue = postorder[postEnd];
  27.         TreeNode root = new TreeNode(rootValue);
  28.         
  29.         int k = 0;
  30.         for(int i = 0; i < inorder.length; i++)
  31.         {
  32.             if(inorder[i] == rootValue)
  33.             {
  34.                 k = i;
  35.                 break;
  36.             }
  37.         }
  38.         
  39.         root.left = buildTree(inorder, inStart, k - 1, postorder, postStart, postStart + k - inStart - 1);
  40.         root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k - inStart, postEnd - 1);
  41.         return root;
  42.     }
  43. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-10 01:42:15 | 只看该作者
全局：
Binary Tree Zigzag Level Order Traversal : https://leetcode.com/problems/bi ... el-order-traversal/
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  12.         List<List<Integer>> result = new ArrayList();
  13.         if(root == null)
  14.         {
  15.             return result;
  16.         }
  17.         
  18.         LinkedList<TreeNode> curr = new LinkedList<TreeNode>();
  19.         LinkedList<TreeNode> next = new LinkedList<TreeNode>();
  20.         curr.push(root);
  21.         boolean flag = true;
  22.         ArrayList<Integer> number = new ArrayList<Integer>();
  23.         
  24.         while(!curr.isEmpty())
  25.         {
  26.             while(!curr.isEmpty())
  27.             {
  28.                 TreeNode head = curr.pop();
  29.                 number.add(head.val);
  30.                
  31.                 if(flag)
  32.                 {
  33.                     if(head.left != null)
  34.                     {
  35.                         next.push(head.left);
  36.                     }
  37.                     
  38.                     if(head.right != null)
  39.                     {
  40.                         next.push(head.right);
  41.                     }
  42.                 }
  43.                 else
  44.                 {
  45.                     if(head.right != null)
  46.                     {
  47.                         next.push(head.right);
  48.                     }
  49.                     
  50.                     if(head.left != null)
  51.                     {
  52.                         next.push(head.left);
  53.                     }
  54.                 }
  55.             }
  56.             result.add(number);
  57.             number = new ArrayList<Integer>();
  58.             curr = next;
  59.             next = new LinkedList<TreeNode>();
  60.             flag = !flag;
  61.         }
  62.         return result;
  63.     }
  64. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-10 02:40:54 | 只看该作者
全局：
Integer to Roman: https://leetcode.com/problems/integer-to-roman/
  1. public class Solution {
  2.     public String intToRoman(int num) {
  3.         StringBuilder result = new StringBuilder();
  4.         String[] symbol = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
  5.         int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  6.         for (int i = 0; i < value.length; i++)
  7.         {
  8.             while (num >= value[i])
  9.             {
  10.                 result.append(symbol[i]);
  11.                 num -= value[i];
  12.             }
  13.         }
  14.         return result.toString();
  15.     }
  16. }
复制代码
回复

使用道具 举报

🔗
 楼主| love1point 2015-8-10 03:10:26 | 只看该作者
全局：
Word search: https://leetcode.com/problems/word-search/
  1. public class Solution {
  2.     public boolean exist(char[][] board, String word) {
  3.         int m = board.length;
  4.         int n = board[0].length;
  5.         
  6.         boolean result = false;
  7.         for(int i = 0; i < m; i++)
  8.         {
  9.             for(int j = 0; j < n; j++)
  10.             {
  11.                 if(dfs(board, word, i, j, 0))
  12.                 {
  13.                     result = true;
  14.                 }
  15.             }
  16.         }
  17.         return result;
  18.     }
  19.    
  20.     public boolean dfs(char[][] board, String word, int i, int j, int k)
  21.     {
  22.         int m = board.length;
  23.         int n = board[0].length;
  24.         
  25.         if(i < 0 || i >= m || j < 0 || j >= n)
  26.         {
  27.             return false;
  28.         }
  29.         
  30.         if(board[i][j] == word.charAt(k))
  31.         {
  32.             char temp = board[i][j];
  33.             board[i][j] = '@';
  34.             
  35.             if(k == word.length() - 1)
  36.             {
  37.                 return true;
  38.             }
  39.             else
  40.             {
  41.                 if(dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i, j - 1, k + 1) || dfs(board, word, i, j + 1, k + 1))
  42.                 {
  43.                     return true;
  44.                 }
  45.             }
  46.             board[i][j] = temp;
  47.         }
  48.         return false;
  49.     }
  50. }
复制代码
回复

使用道具 举报

下一页 »
1 ...161718192021222324下一页
返回列表 发新帖
B Color Link Quote Code
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒：
  • ☑ 禁止发布广告，拉群，贴个人联系方式：找人请去🔗同学同事飞友，拉群请去🔗拉群结伴，广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑，过后则不能删帖。为防止被骚扰甚至人肉，不要公开留微信等联系方式，如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名：面经（美国面经、中国面经、数科面经、PM面经），抖包袱（美国、中国）和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表