LeetCode1-9
本文更多是作为一个习题笔记，没有太多讲解
1、两数之和
题目请点击链接 ↑
最先想到暴力解法，直接双循环，但是这样复杂度为n平方
public int[] twoSum(int[] nums, int target) {
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[i] + nums[j] == target) {
int[] twoSum = new int[]{j, i};
return twoSum;
}
}
}
return null;
}
优化：将内层循环变更为HashMap，可以将复杂度降为n
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {//Map把O（N）降为O（1）
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
小结：HashMap可以降低搜索复杂度
2、两数相加
题目请点击链接 ↑
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = new ListNode(0);//哑结点
ListNode p1 = l1, p2 = l2, curr = ans;//使用p=p.next方式迭代时必须重新声明
int flag = 0;
while (p1 != null || p2 != null) {
int x = (p1 == null) ? 0 : p1.val;
int y = (p2 == null) ? 0 : p2.val;
int sum = x + y + flag;
flag = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p1 != null) p1 = p1.next;//必须声明p1,p2，若直接使用l1,l2，这一步会修改l1、l1的引用
if (p2 != null) p2 = p2.next;
}
if (flag > 0) curr.next = new ListNode(flag);
return ans.next;
小结：刚开始一直在纠结怎么返回，看了下答案发现了哑结点这种用法，对链表运用不太熟练，还需练习。。。
3、无重复字符的最长子串
题目请点击链接 ↑
暴力双循环这太蠢了
static int lengthOfLongestSubstring(String s) {
char[] cs = s.toCharArray();
List<Character> al = new ArrayList<>();
int max = 0;
int num = 0;
for (int i = 0; i < cs.length; i++) {
for (int j = i; j < cs.length; j++) {
if (!al.contains(cs[j])) {
al.add(cs[j]);
num++;
max = (num > max) ? num : max;
} else {
break;
}
}
al.clear();
num = 0;
}
return max;
}
滑窗思想：
static int lengthOfLongestSubstring2(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// 滑窗 [i, j]
if (!set.contains(cs[j])) {
set.add(cs[j++]);
ans = Math.max(ans, j - i);
} else {
set.remove(cs[i++]);
}
}
return ans;
}
优化的滑窗：
//优化的滑动窗口
static int lengthOfLongestSubstring3(String s) {
char[] cs = s.toCharArray();
int n = cs.length, ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(cs[j])) {
i = Math.max(map.get(cs[j]), i);
}
ans = Math.max(ans, j - i + 1);
map.put(cs[j], j + 1);
}
return ans;
}
不看别人思路我估计是想不出来滑窗这种思想的，还得多练练。
4、寻找两个有序数组的中位数
//再看自己以前写的代码居然不能一眼看懂了？？？看了下提交记录战胜77%
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double ans;
int[] sum = new int[nums1.length + nums2.length];
//暴力构建新数组
for (int i = 0, j = 0, k = 0; k < sum.length; k++) {
if (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
sum[k] = nums1[i];
i++;
} else {
sum[k] = nums2[j];
j++;
}
} else if (i >= nums1.length && j < nums2.length) {
sum[k] = nums2[j];
j++;
} else if (i < nums1.length && j >= nums2.length) {
sum[k] = nums1[i];
i++;
}
}
//求中位数
if (sum.length % 2 == 1) {
ans = (double) sum[(sum.length - 1) / 2];
} else {
ans = (double) (sum[sum.length / 2] + sum[(sum.length - 1) / 2]) / 2;
}
return ans;
看了下官方解题没看太明白，应该是利用了中位数的性质。
5、最长回文子串
题目请点击链接 ↑
……
这是我最初的解法，向两边扫描，一堆变量差点没把自己绕晕，看看官方的中心扩展，够简洁：
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
其实这个题是典型的动态规划，不过我的动态区划是弱点，接下来准备集中练习动态规划
6、Z字形变换
题目请点击链接 ↑
看到这一题我最先想到的是将改变后的字符串从右向左横着看，变换就是一串字符串挨个往4行里面放（设行为4），这样两边比中间的行字符少
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder sb = new StringBuilder();
char[] cs = s.toCharArray();
LinkedList[] lls = new LinkedList[numRows];
for (int i = 0; i < numRows; i++) {
lls[i] = new LinkedList<Character>();
}
int flag = 0, p = 0;
for (int i = 0; i < cs.length; i++) {
//flag=0表示从上往下挨个放，=1表示从下往上放
if (flag == 0) {
if (p < numRows - 1) {
lls[p++].add(cs[i]);
continue;
} else {
flag = 1;
lls[p--].add(cs[i]);
}
} else {
if (p > 0) {
lls[p--].add(cs[i]);
continue;
} else {
flag = 0;
lls[p++].add(cs[i]);
}
}
}
for (int i = 0; i < numRows; i++) {
while (lls[i].size() > 0)
sb.append(lls[i].removeFirst());
}
return sb.toString();
}
官方解法基本上也是这种思路：
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
通过当前行和当前下标进行追踪。
还有种思路是按行访问，也就是：
道理是很简单，不过当时对每个字符的位置规律没怎么想，这个思路的难点就在找到每个字符的位置规律。下面贴代码
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
7、整数反转
题目请点击链接 ↑
对于这种反转题目最先想到就是变化为字符串，从官方解题思路下边的评论看大多数人也都是这样23333
public int reverse(int x) {
if (x < 10 && x > -10) {
return x;
}
int ans;
boolean flag = false;
if (x < 0) {
x = -x;
flag = true;
}
StringBuilder sb = new StringBuilder(String.valueOf(x));
try {
ans = Integer.valueOf(sb.reverse().toString());
} catch (NumberFormatException e) {
return 0;
}
if (flag) ans = -ans;
return ans;
}
官方给的解法是从后往前取出原数组的每个数，然后构建新的数：
//pop operation:取出每位数
pop = x % 10;
x /= 10;
//push operation:构建新数
temp = rev * 10 + pop;
rev = temp
不过构建新数是很容易溢出，官方给出了这样的解释：
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
还是觉得字符串更简单2333
8、字符串转整数
题目请点击链接 ↑
现在看到我当时的解法……emmm……这写的都是啥？完全暴力破解？？连trim()方法都没用？判断字符不用char直接用ASCII码23333，没眼看了,折叠折叠。
有空还是仔细看看正则吧，像这种能用正则的……
看了下大佬们的解法，果然思路清晰了好多：
public int myAtoi(String str) {
//去除掉前后的空格
String strr = str.trim();
//存储最终过滤出来的字符串
String strrr = null;
//字符串不为空时并且字符串不全是空白字符串时才转换
if(strr != null && strr.isEmpty() == false){
char f = strr.charAt(0);
//判断字符串中的第一个非空格字符是不是一个有效整数字符
if(f >= '0' && f <= '9' || f == '+'|| f == '-'){
strrr = strr.substring(0,1); // 把第一位放进去(只能是数字、正负号)
//这时候循环只要数字，因为正负号只能出现在第一位
for(int i = 1; i<strr.length();i++){
if(strr.charAt(i) >= '0' && strr.charAt(i) <= '9'){
strrr = strr.substring(0,i+1);
}
//这是遇到不符合要求的字符，直接忽略剩余元素
else{break;}
}
}
}
//判断最终字符串是否为空或则只有一个正负号
if(strrr == null || strrr.equals("+") || strrr.equals("-"))
//此时strrr是String对象，如果使用==比较则比较的时内存地址
return 0;
//最终转换成的数字
int num = 0;
//使用异常机制打印结果
try{
num = Integer.parseInt(strrr);
}catch (Exception e){
if(strrr.charAt(0) == '-')
return Integer.MIN_VALUE;
return Integer.MAX_VALUE;
}
return num;
}
9、回文数
最开始的思路居然不是转化字符串反转再比较，而是转化数组再比较，居然战胜98.95%（原来是下边有要求不能将整数转化为字符串）：
public boolean isPalindrome(int x) {
int count = 0;
int y = x;
boolean ans = false;
if (x < 0) {
return false;
} else if (x >= 0 && x < 10) {
return true;
} else {
while (y > 0) {
y = y / 10;
count++;
}
int[] ints = new int[count];
y = x;
for (int i = 0; i < ints.length; i++) {
ints[i] = y % 10;
y = y / 10;
}
for (int i = 0; i < count - i - 1; i++) {
int j = count - i - 1;
if (ints[i] == ints[j]) {
ans = true;
continue;
} else {
ans = false;
break;
}
}
return ans;
}
}
这里有一个讲解，对这题说的很清楚，这是链接
总结，作为一个菜鸟做LeetCode还是有点吃力的，接下来需要看看动态规划和正则，此文仅作为习题笔记而已。