Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 88eda20

Browse filesBrowse files
author
Administrator
committed
commit
1 parent 3c7c449 commit 88eda20
Copy full SHA for 88eda20

File tree

Expand file treeCollapse file tree

91 files changed

+3171
-0
lines changed
Filter options

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree

91 files changed

+3171
-0
lines changed

‎.idea/modules.xml

Copy file name to clipboardExpand all lines: .idea/modules.xml
+35Lines changed: 35 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎【054】【SpiralMatrix】/src/Solution.java

Copy file name to clipboard
+111Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
4+
/**
5+
* Author: 王俊超
6+
* Date: 2015-08-21
7+
* Time: 17:11
8+
* Declaration: All Rights Reserved !!!
9+
*/
10+
public class Solution {
11+
/**
12+
* <pre>
13+
* 原题
14+
* Given a matrix of m x n elements (m rows, n columns), return all elements
15+
* of the matrix in spiral order.
16+
* For example,
17+
* Given the following matrix:
18+
*
19+
* [
20+
* [ 1, 2, 3 ],
21+
* [ 4, 5, 6 ],
22+
* [ 7, 8, 9 ]
23+
* ]
24+
*
25+
* You should return [1,2,3,6,9,8,7,4,5].
26+
* 题目大意
27+
* 给定一个m*n的矩阵，输入所有元素的螺旋顺序。
28+
*
29+
* 解题思路
30+
* 使用计算输出的方法，先处理上面一行，再处理右边一列，再处理下面一行，再处理左边一列，
31+
* 一直这样操作，直到所有的元素都处理完。
32+
* </pre>
33+
*
34+
* @param matrix
35+
* @return
36+
*/
37+
public List<Integer> spiralOrder(int[][] matrix) {
38+
List<Integer> result = new ArrayList<>(50);
39+
40+
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
41+
return result;
42+
}
43+
44+
// 只有一行的情况
45+
if (matrix.length == 1) {
46+
for (int i : matrix[0]) {
47+
result.add(i);
48+
}
49+
50+
return result;
51+
}
52+
53+
// 只有一列的情况
54+
if (matrix[0].length == 1) {
55+
for (int i = 0; i < matrix.length; i++) {
56+
result.add(matrix[i][0]);
57+
}
58+
59+
return result;
60+
}
61+
62+
// 计算有多少圈
63+
int row = matrix.length;
64+
int col = matrix[0].length;
65+
int cycle = row < col ? row : col;
66+
cycle = (cycle + 1) / 2;
67+
68+
int round = 0; // 记录当前是第几圈
69+
int left = 0;
70+
int right = matrix[0].length - 1;
71+
int top = 0;
72+
int down = matrix.length - 1;
73+
int total = col * row;
74+
int count = 0;
75+
while (round < cycle) {
76+
77+
// 上面一行
78+
for (int i = left; i <= right && count < total; i++) {
79+
count++;
80+
result.add(matrix[round][i]);
81+
}
82+
top++; //
83+
84+
// 右边一列
85+
for (int i = top; i <= down && count < total; i++) {
86+
count++;
87+
result.add(matrix[i][col - round - 1]);
88+
}
89+
right--;
90+
91+
// 底下一行
92+
for (int i = right; i >= left && count < total; i--) {
93+
count++;
94+
result.add(matrix[row - round - 1][i]);
95+
96+
}
97+
down--;
98+
99+
// 左边一列
100+
for (int i = down; i >= top && count < total; i--) {
101+
count++;
102+
result.add(matrix[i][round]);
103+
}
104+
left++;
105+
106+
round++;
107+
}
108+
109+
return result;
110+
}
111+
}

‎【054】【SpiralMatrix】/【054】【SpiralMatrix】.iml

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

‎【058】【LengthOfLastWord】/src/Solution.java

Copy file name to clipboard
+54Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/**
2+
* Author: 王俊超
3+
* Date: 2015-08-21
4+
* Time: 19:27
5+
* Declaration: All Rights Reserved !!!
6+
*/
7+
public class Solution {
8+
/**
9+
* <pre>
10+
* 原题
11+
* Given a string s consists of upper/lower-case alphabets and empty space characters ' ',
12+
* return the length of last word in the string.
13+
* If the last word does not exist, return 0.
14+
* Note: A word is defined as a character sequence consists of non-space characters only.
15+
* For example,
16+
* Given s = "Hello World",
17+
* return 5.
18+
*
19+
* 题目大意
20+
* 给定一个由大小写字母组和空格组成的字符串，返回字符串中的最后一个单词长度。
21+
*
22+
* 解题思路
23+
* 先从后找第一个字母的位置x，如果没有找到就返回0，如果找到，再找第一个空格的位记为y(y可能是-1，
24+
* 因为没有找到空格)，返回结果x-y。
25+
* </pre>
26+
*
27+
* @param s
28+
* @return
29+
*/
30+
public int lengthOfLastWord(String s) {
31+
32+
int index = s.length() - 1;
33+
34+
// 从后面向前找第一个不是' '的字符
35+
while (index >= 0 && s.charAt(index) == ' ') {
36+
index--;
37+
}
38+
39+
if (index < 0) {
40+
return 0;
41+
}
42+
43+
int tmp = index;
44+
45+
// 执行到下面说明存在最后一个单词
46+
47+
// 从后面向前找第一个是' '的字符
48+
while (index >= 0 && s.charAt(index) != ' ') {
49+
index--;
50+
}
51+
52+
return tmp - index;
53+
}
54+
}

‎【058】【LengthOfLastWord】/【058】【LengthOfLastWord】.iml

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

‎【059】【SpiralMatrixII】/src/Solution.java

Copy file name to clipboard
+75Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
/**
2+
* Author: 王俊超
3+
* Date: 2015-08-21
4+
* Time: 19:28
5+
* Declaration: All Rights Reserved !!!
6+
*/
7+
public class Solution {
8+
/**
9+
* <pre>
10+
* 原题
11+
* Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
12+
* For example,
13+
* Given n = 3,
14+
* You should return the following matrix:
15+
*
16+
* [
17+
* [ 1, 2, 3 ],
18+
* [ 8, 9, 4 ],
19+
* [ 7, 6, 5 ]
20+
* ]
21+
*
22+
* 题目大意
23+
* 给定一个整数n，生成一个n*n的矩阵，用1-n^2的数字进行螺旋填充。
24+
*
25+
* 解题思路
26+
* 采用计算生成法，对每一个位置计算对应的数。
27+
* </pre>
28+
*
29+
* @param n
30+
* @return
31+
*/
32+
public int[][] generateMatrix(int n) {
33+
int[][] result = new int[n][n];
34+
35+
int layer;
36+
int k;
37+
for (int i = 0; i < n; i++) {
38+
for (int j = 0; j < n; j++) {
39+
layer = layer(i, j, n); // 当前坐标外有几层
40+
// n * n - layer * layer外围层使用的最后一个数字（也是最大的）
41+
// 坐标所在的当前层使用的第一个数字
42+
k = n * n - (n - 2 * layer) * (n - 2 * layer) + 1;
43+
result[i][j] = k;
44+
45+
// (n - 2 * layer - 1)：四个(n - 2 * layer - 1)就是（x，y）坐标所在层的所有元素个数
46+
if (i == layer) { // 情况一、坐标离上边界最近
47+
result[i][j] = k + j - layer;
48+
} else if (j == n - layer - 1) { // 情况二、坐标离右边界最近
49+
result[i][j] = k + (n - 2 * layer - 1) + i - layer;
50+
} else if (i == n - layer - 1) { // 情况三、坐标离下边界最近
51+
result[i][j] = k + 3 * (n - 2 * layer - 1) - (j - layer);
52+
} else { // 情况三、坐标离左边界最近
53+
result[i][j] = k + 4 * (n - 2 * layer - 1) - (i - layer);
54+
}
55+
}
56+
}
57+
58+
return result;
59+
}
60+
61+
/**
62+
* 在一个n*n的矩阵中，计算（x,y）坐标外有多少层，坐标从0开始计算
63+
*
64+
* @param x 横坐标
65+
* @param y 纵坐标
66+
* @param n 矩阵大小
67+
* @return 坐标外的层数
68+
*/
69+
public int layer(int x, int y, int n) {
70+
x = x < n - 1 - x ? x : n - 1 - x; // 计算横坐标离上下边界的最近距离
71+
y = y < n - 1 - y ? y : n - 1 - y; // 计算纵坐标离左右边界的最近距离
72+
73+
return x < y ? x : y; // 较小的值为坐标的外围层数
74+
}
75+
}

‎【059】【SpiralMatrixII】/【059】【SpiralMatrixII】.iml

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

‎【062】【UniquePaths】/src/Solution.java

Copy file name to clipboard
+63Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/**
2+
* Author: 王俊超
3+
* Date: 2015-08-21
4+
* Time: 19:30
5+
* Declaration: All Rights Reserved !!!
6+
*/
7+
public class Solution {
8+
/**
9+
* <pre>
10+
* 原题
11+
* A robot is located at the top-left corner of a m x n grid
12+
* (marked ‘Start’ in the diagram below).
13+
* The robot can only move either down or right at any point in time.
14+
* The robot is trying to reach the bottom-right corner of the grid
15+
* (marked ‘Finish’ in the diagram below).
16+
* How many possible unique paths are there?
17+
*
18+
* Above is a 3 x 7 grid. How many possible unique paths are there?
19+
* Note: m and n will be at most 100.
20+
*
21+
* 题目大意
22+
* 一个机器人在一个m*n的方格的左上角。
23+
* 机器人只能向右或都向下走一个方格，机器人要到达右下角的方格。
24+
* 请问一共有多少种唯一的路径。
25+
* 注意：ｍ和ｎ最大不超100。
26+
*
27+
* 解题思路
28+
* 典型的动态规划问题，对问题使用动态规划的方法进行求解。
29+
* 用一个ｍ*n的组数A保存结果。
30+
* 对于A数组中的元素有。
31+
* 1、当x=0或者y=0时有A[x][y] = 1；
32+
* 2、当x>=1并且y>=1时有A[\x][\y] = A[x-1][y]+A[\x][y-1]。
33+
* 3、所求的结点就是A[m-1][n-1]。
34+
* </pre>
35+
*
36+
* @param m
37+
* @param n
38+
* @return
39+
*/
40+
public int uniquePaths(int m, int n) {
41+
int[][] result = new int[m][n];
42+
43+
// 第一列的解
44+
for (int i = 0; i < m; i++) {
45+
result[i][0] = 1;
46+
}
47+
48+
// 第一行的解
49+
for (int i = 1; i < n; i++) {
50+
result[0][i] = 1;
51+
}
52+
53+
// 其它位置的解
54+
for (int i = 1; i < m; i++) {
55+
for (int j = 1; j < n; j++) {
56+
result[i][j] = result[i - 1][j] + result[i][j - 1];
57+
}
58+
}
59+
60+
// 所求的解
61+
return result[m - 1][n - 1];
62+
}
63+
}

‎【062】【UniquePaths】/【062】【UniquePaths】.iml

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.