宣告：
簡單難度的題基本都不看答案，使用自己的方法來做，如果參考了他人的代碼將會有所標注，
簡單難度的題雖然基本一看就有思路，但是實際撰寫代碼的程序中會出現各種問題，尤其是邊界問題，所以大多代碼并不是一次寫成的，而是使用idea的代碼除錯功能多次嘗試后修改成功的，
1、兩數之和
思路：先固定第一個數，然后找到第二個數使得兩個數相加等于target，一旦找到這樣的兩個數，就直接回傳結果，不再回圈，由于給定的測驗資料必然會有答案，所以無需考慮找不到這樣兩個數的情況，
代碼：
public int[] twoSum(int[] nums, int target) {
int ret[] = new int[2];
boolean flag = true;
for (int i = 0; i < nums.length && flag; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
ret[0] = i;
ret[1] = j;
flag = false;
break;
}
}
}
return ret;
}
7、整數反轉
思路：首先將整數轉換為字串，然后以字串中間為對稱軸，將對稱部分的數字替換；如果是負數，則下標從1開始，否則下標從0開始，最后將字串轉換為整數，此時判斷轉換后的數字如果大小溢位，則回傳0，否則回傳反轉后的整數，
代碼：
public int reverse(int x) {
if (x == 0)
return 0;
boolean fu = false;
String str = new Integer(x).toString();
if (str.length() == 1)
return x;
// 提取負號
try {
str = str.substring(str.indexOf('-'), str.length());
fu = true;
} catch (Exception e) {
}
String strpost = new String();
while (true) {
try {
strpost = str.substring(0, str.lastIndexOf('0'));
} catch (Exception e) {
}
if (strpost.length() + 1 != str.length())
break;
str = strpost;
}
char[] chars = str.toCharArray();
for (int i = fu ? 1 : 0, j = str.length() - 1; i <= (str.length() - 1) / 2; i++, j--) {
char tag = chars[j];
chars[j] = chars[i];
chars[i] = tag;
}
int result = ((Double) Double.valueOf(new String(chars)) > Math.pow(2, 31) - 1) || ((Double) Double.valueOf(new String(chars)) < Math.pow(-2, 31)) ? 0 : (int) Integer.valueOf(new String(chars));
return result;
}
9、回文數
思路：
如果是負數，一定不是回文數
令x為輸入的數，sum為回文數，最后直接回傳判斷x==sum即可
生成sum的方法：
·首先令y=x
·每次獲取y的倒數第i位，當做sum的正數第i位
·使用模運算完成上述功能
代碼：
public boolean isPalindrome(int x) {
if(x<0)
return false;
int y = x;
int sum = 0;
while (y > 0) {
sum = sum * 10 + y % 10;
y=y/10;
}
// if (x == sum)
// return true;
// else
// return false;
return x==sum;
}
13、羅馬數字轉整數
思路：直接case IVXLCDM這些字母的值加入到sum中，但需要處理額外的6種情況：IV、IX、XL、XC、CD、CM，因此在處理I、X、C這三種情況時，需要看一下他們的下一位是不是分別處于這些情況中，
代碼：
public int romanToInt(String s) {
int sum = 0;
char[] str = s.toCharArray();
for (int i = 0; i < str.length; ) {
switch (str[i]){
case 'I':
try {
switch (str[i+1]){
case 'V':
sum+=4;
i+=2;
break;
case 'X':
sum+=9;
i+=2;
break;
default:
sum+=1;
i+=1;
}
}catch (Exception e){
sum+=1;
i+=1;
}finally {
break;
}
case 'X':
try {
switch (str[i+1]){
case 'L':
sum+=40;
i+=2;
break;
case 'C':
sum+=90;
i+=2;
break;
default:
sum+=10;
i+=1;
}
}catch (Exception e){
sum+=10;
i+=1;
}finally {
break;
}
case 'C':
try {
switch (str[i+1]){
case 'D':
sum+=400;
i+=2;
break;
case 'M':
sum+=900;
i+=2;
break;
default:
sum+=100;
i+=1;
}
}catch (Exception e){
sum+=100;
i+=1;
}finally {
break;
}
case 'V':
sum+=5;
i+=1;
break;
case 'L':
sum+=50;
i+=1;
break;
case 'D':
sum+=500;
i+=1;
break;
case 'M':
sum+=1000;
i+=1;
break;
default:
System.out.println("你輸入的不是羅馬字符");
}
}
return sum;
}
14、最長公共前綴
這道題記得除錯了好久，關鍵在于輸入字串中可能有0個或多個空的字串以及變數j的下標問題
思路：
·首先獲取輸入字串中最短的字串長度用作回圈遍歷的終止條件，然后從下標0開始對所有字串下標為0的地方遍歷，一旦遇到哪個下標對應的字符不同，則跳出回圈，
·回圈終止后，截取子串作為回傳值，截取子串時，如果是因為有字符不等而提前終止，則j=j-2；如果是因為所有字符全部相等，則最后j=j-1.
·如何理解呢？因為如果回圈結束是因為跳出回圈導致的，則跳出回圈后j-1這個位置的字符是不同的，而如果回圈結束是因為j==length導致的，說明j-1這個位置的字符都是相同的，所以只減去了1.由于substring函式是左閉右開的，因此這個函式的第二個引數為j+1，
代碼：
public String longestCommonPrefix(String[] strs) {
String cop = new String();
// 求最短length
if (strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
int length = strs[0].length();
if (length == 0) // 防止報錯 先判斷一次
return "";
for (int i = 0; i < strs.length - 1; i++) {
if (length > strs[i + 1].length())
length = strs[i + 1].length();
}
if (length == 0) // 如果所有字串中有一個為空，則直接回傳空
return "";
boolean b = true;
int j;
char[] chars = new char[strs.length];
for (j = 0; j < length && b; j++) {
chars[0] = strs[0].charAt(j);
for (int i = 1; i < strs.length; i++) {
chars[i] = strs[i].charAt(j);
if (chars[i] != chars[i - 1]) {
b = false;
break;
}
}
}
j-=1;
if(!b){
j-=1;
}
cop = strs[0].substring(0, j + 1);
return cop;
}
20、有效的括號
思路：考研資料結構基礎題，使用堆疊即可
代碼：
public boolean isValid(String s) {
Stack stack = new Stack();
for(int i = 0;i<s.length();i++){
try {
switch (s.charAt(i)) {
case ')':
if ((char) stack.pop() != '(')
return false;
break;
case ']':
if ((char) stack.pop() != '[')
return false;
break;
case '}':
if ((char) stack.pop() != '{')
return false;
break;
default:
stack.push(s.charAt(i));
}
}catch (Exception e){
return false;
}
}
if(stack.empty())
return true;
return false;
}
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 l1, ListNode l2) {
if(l1==null&&l2==null)
return null;
ListNode l3 = new ListNode();
ListNode p = l3;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.val = l1.val;
l1 = l1.next;
} else {
p.val = l2.val;
l2 = l2.next;
}
p.next = new ListNode();
p = p.next;
}
while (l1 != null) {
p.val = l1.val;
if (l1.next != null)
p.next = new ListNode();
l1=l1.next;
p=p.next;
}
while (l2 != null) {
p.val = l2.val;
if (l2.next != null)
p.next = new ListNode();
l2=l2.next;
p=p.next;
}
return l3;
}
}
26、原地洗掉排序陣列中的重復項
思路：要求不能使用額外的空間，因此使用兩個指標，第一個指標用于放置陣列中不同的元素，第二個指標用于遍歷整個陣列，
代碼：
public int removeDuplicates(int[] nums) {
if(nums.length==0)
return 0;
int i ,count=1;
for(i=0;i<nums.length-1;i++){
if(nums[i]!=nums[i+1])
nums[count++]=nums[i+1];
}
return count;
}
27、移除元素
思路：又是原地移除元素，如果每洗掉一個元素就把后面的所有元素前移一個，那時間復雜度也太高了，所以當遇到要洗掉的元素的時候，把倒數第count++個元素直接覆寫掉要洗掉的元素就可以了，count初始為1.最后回傳移除元素后的陣列中的數字個數n，判題的時候它會自動只取前n個元素進行檢驗，
代碼：
public int removeElement(int[] nums, int val) {
int i, k;
int count = 1, n = 0;
int length = nums.length;
if (length == 0)
return 0;
if (length == 1) {
if (nums[0] == val)
return 0;
else
return 1;
}
for (i = 0, k = 0; k < length; i++, k++) {
if (nums[i] == val) {
nums[i] = nums[nums.length - count];
i--;
count++;
} else {
n++;
}
}
return n;
}
28、實作strStr()
題目要求找出needle字串在haystack字串中出現的第一個位置，如果不存在則回傳-1
思路：先固定haystack的起始位置index，然后一個一個字符去比較needle，如果從index開始的字符全部和needle相等，則說明找到了，回傳index，如果中途被中斷了，則從index+1的位置開始重新找，如果找到最后也找不到，則回傳-1.
代碼：
public int strStr(String haystack, String needle) {
if (needle.length() == 0)
return 0;
if (needle.length() > haystack.length())
return -1;
int i, j, index = -1;
for (i = 0, j = 0; i < haystack.length() && j < needle.length(); i++) {
if (haystack.charAt(i) == needle.charAt(j) && index == -1) {
index = i;
j++;
} else if (haystack.charAt(i) == needle.charAt(j) && index != -1) {
j++;
} else {
if (index != -1)
i=index;//這個字串的當前位置不對了，也許該字符正好是needle的第一個字符
index = -1;
j = 0;
}
}
if(j==needle.length())
return index;
return -1;
}
35、搜索插入位置
思路：
本質就是二分法插入排序中的一步，需要注意邊界問題
代碼：
public int searchInsert(int[] nums, int target) {
int i = 0, j = nums.length - 1;
int k;
while (i < j) {
k = (i + j) / 2;
if (target > nums[k]) {
if (i != k)
i = k;
else i = k + 1;
} else if (target < nums[k]){
if (j != k)
j = k;
else j = k - 1;
}
else return k;
}
if (nums[i] < target)
return i + 1;
else return i;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/201328.html
標籤：其他
上一篇：Java -- Spring Boot -- 爬蟲從入門到精通 -- 爬取某二手房全部房屋資訊 -- 專案實戰（爬取兩萬+房屋出售資訊）
下一篇：面試官：你手寫過堵塞佇列嗎？