状态转移方程:
二维数组方式
dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0]; (i > 0 && j == 0)
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[j - 1];(i == 0 && j > 0)
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]; (i > 0 && j > 0)
一维数组方式
dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];(j > 0)
dp[j] = obstacleGrid[i][j] == 1 ? 0 : dp[j] + dp[j - 1];(j > 0)
时间复杂度O(mn) 遍历一遍二维数组,m为行数,n为列数
空间复杂度O(n) n为原始二维数据的列数,一维数组dp损耗
执行0ms,击败100%的用户
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[] dp = new int[obstacleGrid[0].length];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < obstacleGrid.length; i++) {
dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
for (int j = 1; j < obstacleGrid[0].length; j++) {
dp[j] = obstacleGrid[i][j] == 1 ? 0 : dp[j] + dp[j - 1];
}
}
return dp[obstacleGrid[0].length - 1];
}
}
暴力方式
执行38ms,击败35.96%的用户
class Solution {
public int firstUniqChar(String s) {
for (int i = 0; i < s.length(); i++) {
boolean isExist = true;
// 往后查
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
isExist = false;
break;
}
}
// 往前查
for (int j = i - 1; j >= 0; j--) {
if (s.charAt(i) == s.charAt(j)) {
isExist = false;
break;
}
}
if (isExist) return i;
}
return -1;
}
}
使用一维数组方式
执行21ms,击败59.93%的用户
class Solution {
public int firstUniqChar(String s) {
List<Integer>[] dp = new List[26];
for (int i = 0; i < 26; i++) dp[i] = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
dp[s.charAt(i) - 'a'].add(i);
}
for (int i = 0; i < s.length(); i++) {
if (dp[s.charAt(i) - 'a'].size() == 1) return dp[s.charAt(i) - 'a'].get(0);
}
return -1;
}
}
时间复杂度O(n)
空间复杂度O(n)
执行1ms,击败100%的用户
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
int length = chars.length;
int times = length / (2 * k);
int remainder = length % (2 * k);
int left = 0, right = 0;
for (int i = 0; i < times; i++) {
left = i * 2 * k; right = left + k - 1;
reverse(chars, left, right);
}
left = 2 * k * times;
right = remainder < k ? length - 1 : left + k - 1;
reverse(chars, left, right);
return new String(chars);
}
private void reverse(char[] chars, int left, int right) {
while (left < right) {
char temp = chars[right]; chars[right] = chars[left]; chars[left] = temp;
left++; right--;
}
}
}
官方精简写法
class Solution {
public String reverseStr(String s, int k) {
char[] a = s.toCharArray();
for (int start = 0; start < a.length; start += 2 * k) {
int i = start, j = Math.min(start + k - 1, a.length - 1);
while (i < j) {
char tmp = a[i];
a[i++] = a[j];
a[j--] = tmp;
}
}
return new String(a);
}
}
时间复杂度O(n) n为str的长度
空间复杂度O(1)
执行2ms,击败99.69%的用户
class Solution {
public int myAtoi(String str) {
// 1.去除首部空格
// 2.处理正负号
// 3.处理有效数字
int i = 0; boolean is_negative = false;
while (i < str.length() && str.charAt(i) == ' ') i++;
if (i == str.length()) return 0;
if (str.charAt(i) == '-') is_negative = true;
if (str.charAt(i) == '-' || str.charAt(i) == '+') i++;
int result = 0, toplimit = Integer.MAX_VALUE / 10, lowerlimit = Integer.MIN_VALUE / 10;
while (i < str.length() && str.charAt(i) <= '9' && str.charAt(i) >= '0') {
int temp = str.charAt(i++) - '0';
if (!is_negative && (result > toplimit || (result == toplimit && temp >= 7))) return Integer.MAX_VALUE;
if (is_negative && (-result < lowerlimit || (-result == lowerlimit && temp >= 8))) return Integer.MIN_VALUE;
result = result * 10 + temp;
}
return !is_negative ? result : -result;
}
}
dp方式
时间复杂度O(n)
空间复杂度O(n)
执行1ms,击败100%的用户
public int longestValidParentheses(String s) {
int maxLength = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
int needIndex = i - dp[i - 1] - 1;
if (needIndex < 0) continue;
if (s.charAt(i) == ')' && s.charAt(needIndex) == '(') {
dp[i] = dp[i - 1] + 2;
if (needIndex - 1 >= 0) {
dp[i] += dp[needIndex - 1];
}
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
}