目录
代码部分
题9
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考评论进行修改后的代码：
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
else if (x == 0) return true;
else
{
int xorigion = x;
int X = 0;
while (x != 0)
{
X = X * 10 + x % 10;
x = x / 10;
}
if(X == xorigion) return true;
else return false;
}
}
}首先判断掉特殊情况。对于剩下来的，通过一个while循环求得他的回文数。最后判断return。
题13
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
自己的代码，有点长，但是时间100%，内存95%：
class Solution {
public int romanToInt(String s) {
char [] S = s.toCharArray();
int res = 0;
for(int i = 0 ; i < S.length ; i ++)
{
if((i+1)< S.length)
{
if(S[i] == 'I')
{
if(S[i+1] != 'V' && S[i+1] != 'X')
{
res += 1;
}
else if(S[i+1] == 'V')
{
res += 4;
i ++;
}
else if(S[i+1] == 'X')
{
res += 9;
i ++;
}
}
else if(S[i] == 'X')
{
if(S[i+1] != 'L' && S[i+1] != 'C')
{
res += 10;
}
else if(S[i+1] == 'L')
{
res += 40;
i ++;
}
else if(S[i+1] == 'C')
{
res += 90;
i ++;
}
}
else if(S[i] == 'C')
{
if(S[i+1] != 'D' && S[i+1] != 'M')
{
res += 100;
}
else if(S[i+1] == 'D')
{
res += 400;
i ++;
}
else if(S[i+1] == 'M')
{
res += 900;
i ++;
}
}
else if(S[i] == 'V') res += 5;
else if(S[i] == 'L') res += 50;
else if(S[i] == 'D') res += 500;
else if(S[i] == 'M') res += 1000;
}
else
{
if(S[i] == 'I') res +=1;
else if(S[i] == 'V') res += 5;
else if(S[i] == 'X') res += 10;
else if(S[i] == 'L') res += 50;
else if(S[i] == 'C') res += 100;
else if(S[i] == 'D') res += 500;
else if(S[i] == 'M') res += 1000;
}
}
return res;
}
}运用了编译原理的思想，先判断两个一组的字符（IV，IX，XL，XC，CD，CM），再判断单个字符。
题14
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。
修了几遍之后的暴力递归代码：
class Solution {
public String longestCommonPrefix(String[] strs) {
int len = strs.length ;
String res;
if(len == 0) return "";
if(len == 1) return strs[0];
if(strs[0].length() == 0) return "";
char [] string1 , string2 , nextarray;
string1 = strs[0].toCharArray();
string2 = strs[1].toCharArray();
nextarray = new char[200];
for(int i = 0 ; i < 200 ; i++)
{
nextarray[i] = 'A';
}
int i = 0;
while(i < string1.length && i < string2.length && string1[i] == string2[i])
{
nextarray[i] = string1[i];
i ++;
}
String nextstring = new String(nextarray);
String [] tonext = new String[len-1];
tonext[0] = nextstring;
for(int j = 1 ; j < len -1 ; j ++)
{
tonext[j] = strs[j+1];
}
if(len == 2)
{
i = 0;
while(nextarray[i] != 'A') i ++;
nextstring = nextstring.substring(0,i);
return nextstring;
}
res = longestCommonPrefix(tonext);
return res;
}
}先判断掉特殊情况。将前两个字符串转数组，声明初始化char数组nextarray用于存放前缀。求前两个字符串的最长前缀，存入nextarray数组。声明字符串nextstring将nextarray数组转为字符串，将nextstring字符串与剩余字符串存入字符串数组tonext。
判断若当前只有两个字符串，则return当前的最长前缀。
进递归。
题20
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
自己的代码如下，使用栈解决：
class Solution {
public boolean isValid(String s) {
char[] S = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i = 0 ; i < S.length ; i++)
{
if(S[i] == '(') stack.push(')');
else if(S[i] == '[') stack.push(']');
else if(S[i] == '{') stack.push('}');
else
{
if(stack.isEmpty() == true) return false;
else if(S[i] != stack.pop()) return false;
}
}
if(stack.isEmpty()) return true;
else return false;
}
}对于每个前括号（(，[，{），进栈它对应的另一半括号，这样可以在出栈比较时减少判断的次数。
题4
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
自己的代码如下，过长了，有很大改进空间：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 , len2;
len1 = nums1.length;
len2 = nums2.length;
int flag1 = (len1+len2)/2;;
int med1 = 0 , med2 = 0;
double med11 ,med22 , med = 0;
if(len1 == 0 && len2 ==0) return med;
if((len1+len2)%2 == 0) //偶数
{
int i1 = 0 , i2 = 0;
for(int i = flag1 ; i >= 0 ; i--)
{
if(i != 0)
{
if(i1 == len1)
{
med1 = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med1 = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med1 = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med1 = nums1[i1];
i1 ++;
}
}
else if(i == 0)
{
if(i1 == len1)
{
med2 = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med2 = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med2 = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med2 = nums1[i1];
i1 ++;
}
}
}
med11 = (double)med1;
med22 = (double)med2;
med = (med11 + med22) / 2;
}
else //奇数
{
int i1 = 0 , i2 = 0;
for(int i = flag1 ; i >= 0 ; i--)
{
if(i1 == len1)
{
med = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med = nums1[i1];
i1 ++;
}
}
}
return med;
}
} 先判断掉特殊情况。判断两个数组的长度之和为偶数还是奇数，并分开来运算。偶数需要取中间两个数求平均值，奇数需要取中间一个数，也即偶数需要取小的数与
小的数，而奇数需要取
小的数。通过for循环取得数，在循环中需首先判断越界情况。
题21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
自己的代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){return list2;}
if(list2 == null){return list1;}
ListNode root = new ListNode();
ListNode res = root;
while(list1 != null && list2 != null)
{
if(list1.val <= list2.val)
{
res.next = list1;
res = res.next;
list1 = list1.next;
}
else
{
res.next = list2;
res = res.next;
list2 = list2.next;
}
}
if(list1 == null && list2 != null)
{
res.next = list2;
}
else if(list2 == null && list1 != null)
{
res.next = list1;
}
return root.next;
}
}先判断掉特殊情况。判断原链表val值，并将小者节点接到目标链表上。若一条用完，就把另一条直接接上去。
题15
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
借鉴修改后的代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
int a , b , c , j , k;
if(len < 3) {return res;}
if(len == 3 && nums[0]+nums[1]+nums[2] != 0) {return res;}
if(len == 3 && nums[0]+nums[1]+nums[2] == 0)
{
res.add(Arrays.asList(nums[0],nums[1],nums[2]));
return res;
}
Arrays.sort(nums);
for(int i = 0 ; i < len ; i++)
{
if(nums[i] > 0) {return res;}
if(i > 0 && nums[i] == nums[i-1]) {continue;}
a = nums[i];
j = i + 1;
k = len -1;
while(j < k)
{
b = nums[j];
c = nums[k];
if(a + b + c == 0)
{
res.add(Arrays.asList(a,b,c));
j ++;
k --;
while(j < k && j > i + 1 && nums[j] == nums[j-1]) {j ++;}
while(j < k && k < len -1 && nums[k] == nums[k+1]) {k --;}
}
else if(a + b + c > 0) {k--;}
else if(a + b + c < 0) {j++;}
}
}
return res;
}
}先判断掉特殊情况。先对数组排序。使用for循环进行nums[i]的顺序遍历，判断掉特殊情况。使用j，k来定位i后面的数组部分，并分别指向这一部分的首和尾。利用while循环保证j始终在k之前。判断三者之和是否等于0，并根据与0关系调整j，k位置。
在其中加入防止重复取数的判断。
java小知识部分
题9
有特殊情况的话先判断掉。
题13
对于数组、链表都要判断是否越界的问题。
+=，-=连起来才是一个运算符，中间不可以加空格。
题14
数组长度是.length，字符串长度是.length()。
字符串截断用：
nextstring = nextstring.substring(0,i);题20
栈的各种操作：
Stack<Character> stack = new Stack<Character>(); //栈的声明
stack.push(')'); //入栈
stack.isEmpty() //出栈
stack.pop() //判断栈空题4
if判断中先判断越界情况再判断其他情况。
题15
数据类型List，意为List由List组成，内层List由int组成。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();加入新的数据的方法：
res.add(Arrays.asList(nums[0],nums[1],nums[2]));排序方法：
Arrays.sort(nums);