Leetcode Hacking Practice -- Solution in Java Part 3

文章內容

LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.

To be successful in a technical interview, we believe it is mainly repeating these three important steps:

Code. Read. Discuss.

We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.

1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.

We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !

This is Part 3 (Java Solution)

Part 1: www.westca.com/Forums/...inese.html

Part 2: www.westca.com/Forums/...inese.html

點擊: 0 | 評論: 91 | 分類: 缺省 | 論壇: IT人生 | 論壇帖子

分享:

分享到微信

文章評論

五月花.

無題

歪脖，不要為了磅磅丟了自己哦

2014-09-27 00:52:37 | 引用

無題

五月花. 寫道:

歪脖，不要為了磅磅丟了自己哦

我發英文貼沒有鎊

2014-09-27 00:53:17 | 引用

webdriver

無題

S算法問題: Spiral Matrix
問題描述:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

2014-09-28 21:11:57 | 引用

無題

算法問題推薦解法來了...

...

解法（Java）

代碼:






import java.util.ArrayList;





public class SpiralMatrix {

   public ArrayList<Integer> spiralOrder(int[][] matrix) {

      ArrayList<Integer> list = new ArrayList<Integer>();

      if (matrix.length == 0)

         return list;

      int beginX = 0, endX = matrix.length - 1;

      int beginY = 0, endY = matrix[0].length - 1;

      while (true) {

         for (int i = beginY; i <= endY; i++) {

            list.add(matrix[beginX][i]);

         }

         if (++beginX > endX)

            break;

         for (int i = beginX; i <= endX; i++) {

            list.add(matrix[i][endY]);

         }

         if (beginY > --endY)

            break;

         for (int i = endY; i >= beginY; i--) {

            list.add(matrix[endX][i]);

         }

         if (beginX > --endX)

            break;

         for (int i = endX; i >= beginX; i--) {

            list.add(matrix[i][beginY]);

         }

         if (++beginY > endY)

            break;

      }

      return list;

   }

}

2014-09-28 21:13:07 | 引用

webdriver

無題

S算法問題: Search in Rotated Sorted Array
問題描述:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

2014-09-28 21:18:02 | 引用

無題

算法問題推薦解法來了...

Binary search. O(lgn) eg. [4 5 6] -7- 8 1 2, 5 6 0 -1- [2 3 4]

解法（Java）

代碼:




public class SearchinRotatedSortedArray {

   public int search(int[] A, int target) {

      int low = 0;

      int high = A.length - 1;

      int mid = 0;

      while (low <= high) {

         mid = (low + high) / 2;

         if (A[mid] == target)

            return mid;

         else {

            if (A[low] <= A[mid]) {

               if (target >= A[low] && target < A[mid]) {

                  high = mid - 1;

               } else {

                  low = mid + 1;

               }

            } else {

               if (target <= A[high] && target > A[mid]) {

                  low = mid + 1;

               } else {

                  high = mid - 1;

               }

            }

         }

      }

      return -1;

   }

}

2014-09-28 21:18:12 | 引用

webdriver

無題

S算法問題: Search Insert Position
問題描述:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4
[1,3,5,6], 0 -> 0

2014-09-28 21:18:33 | 引用

無題

算法問題推薦解法來了...

Binary search.

解法（Java）

代碼:




public class SearchInsertPosition {

   public int searchInsert(int[] A, int target) {

      int length = A.length;

      if (A.length == 0)

         return 0;

      int i = 0, j = length - 1;

      while (i < j) {

         int mid = (i + j) / 2;

         if (A[mid] == target)

            return mid;

         if (A[mid] < target) {

            i = mid + 1;

         } else {

            j = mid - 1;

         }

      }

      return A[i] < target ? i + 1 : i;

   }

}

2014-09-28 21:18:53 | 引用

webdriver

無題

S算法問題: Set Matrix Zeroes
問題描述:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

2014-09-28 21:19:44 | 引用

無題

算法問題推薦解法來了...

Use first row and column as auxiliary spaces instead of newly allocating ones.

解法（Java）

代碼:




public class SetMatrixZeroes {

   public void setZeroes(int[][] matrix) {

      int row = matrix.length;

      if (row == 0)

         return;

      int col = matrix[0].length;

      for (int i = 0; i < row; i++) {

         for (int j = 0; j < col; j++) {

            if (matrix[i][j] == 0) {

               for (int k = 0; k < col; k++) {

                  if (matrix[i][k] != 0)

                     matrix[i][k] = -1;

               }

               for (int f = 0; f < row; f++) {

                  if (matrix[f][j] != 0)

                     matrix[f][j] = -1;

               }

            }

         }

      }

      for (int i = 0; i < row; i++) {

         for (int j = 0; j < col; j++) {

            if (matrix[i][j] == -1) {

               matrix[i][j] = 0;

            }

         }

      }

   }

}

2014-09-28 21:20:14 | 引用

webdriver

發表評論

回到頂部▲