算法题集锦go、java

func twoSum(nums []int, target int) []int {hashTable := map[int]int{}for i,x := range(nums){if p,ok := hashTable[target-x];ok{return []int{p,i}}hashTable[x]=i}return nil
}

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> hashtable = new HashMap<Integer,Integer>();for(int i=0;i<nums.length;i++){if(hashtable.containsKey(target-nums[i])){return new int[]{hashtable.get(target-nums[i]),i};}hashtable.put(nums[i],i);}return new int[0];}
}

回文数

func isPalindrome(x int) bool {if x<0 || (x %10 ==0 && x!=0){return false}revertedNumber := 0for x > revertedNumber {revertedNumber = revertedNumber * 10 + x%10x /= 10}return x == revertedNumber || x==revertedNumber/10
}

class Solution {public boolean isPalindrome(int x) {if (x <0 || (x %10 == 0 && x !=0)){return false;}int revertedNumber = 0;while (x>revertedNumber){revertedNumber = revertedNumber *10 + x%10;x /=10;}return x == revertedNumber || x==revertedNumber/10;}
}

罗马数字转整数串

func romanToInt(s string) int {var symbolValues = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}n := len(s)var ans = 0for i := range(s){value := symbolValues[s[i]]if i < n-1 && value < symbolValues[s[i+1]]{ans -= value}else{ans+=value}}return ans}

class Solution {Map<Character, Integer> symbolValues = new HashMap<>(){{put('I',1);put('V',5);put('X', 10);put('L', 50);put('C', 100);put('D', 500);put('M', 1000);}};public int romanToInt(String s) {int ans = 0;int n =s.length();for (int i = 0;i<n;i++){int value = symbolValues.get(s.charAt(i));if (i <n-1 && value < symbolValues.get(s.charAt(i+1))){ans -= value;}else{ans +=value;}}return ans;}
}

最长公共前缀

func longestCommonPrefix(strs []string) string {if len(strs) == 0{return ""}firststr := strs[0]n := len(firststr)for i:=0;i<n;i++ {for j:=1;j<len(strs);j++{if (len(strs[j]) <= i || strs[j][i] !=firststr[i]){return firststr[:i]}}}return firststr
}

有效的括号

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0){return "";}String prefix = strs[0];int n = prefix.length();for(int i=0;i<n;i++){for (int j=1;j<strs.length;j++){if (strs[j].length() <= i || strs[j].charAt(i) != prefix.charAt(i)){return prefix.substring(0,i);}}}return prefix;}
}

func isValid(s string) bool {var n int = len(s)if (n%2==1){return false}pairs := map[byte]byte{')':'(',']':'[','}':'{'}stack := []byte{}for _,c := range []byte(s){if _ ,ok := pairs[c];ok{if len(stack)==0 || stack[len(stack)-1] != pairs[c]{return false}stack=stack[:len(stack)-1]}else{stack = append(stack,c)}}return len(stack) == 0
}

合并两个有序列表

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {dummy := &ListNode {}cur := dummyfor list1 != nil && list2 != nil{if list1.Val < list2.Val{cur.Next = list1list1=list1.Next}else{cur.Next = list2list2=list2.Next}cur = cur.Next}if list1 != nil{cur.Next=list1}else{cur.Next = list2}return dummy.Next}

/*** 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) {ListNode dummy = new ListNode();ListNode cur = dummy;while (list1 != null && list2 != null) {if (list1.val<list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null){cur.next = list1;}else{cur.next = list2;}return dummy.next;}
}

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {if list1 == nil {return list2}if list2 == nil {return list1}if list1.Val <list2.Val{list1.Next=mergeTwoLists(list1.Next,list2)return list1}list2.Next = mergeTwoLists(list1,list2.Next)return list2}

/*** 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;}if (list1.val < list2.val){list1.next = mergeTwoLists(list1.next,list2);return list1;}else{list2.next = mergeTwoLists(list1,list2.next);return list2;}}
}

删除有序数组中的重复项

func removeDuplicates(nums []int) int {var i,j intj=0for i=1;i<len(nums);i++ {if nums[i]!=nums[j]{j+=1nums[j]=nums[i]}}return j+1
}

class Solution {public int removeDuplicates(int[] nums) {int j = 0;for (int i=0;i< nums.length;i++){if (nums[i] != nums[j]){j+=1;nums[j]=nums[i];}}return j+1;}
}

移除元素

class Solution {public static int removeElement(int[] nums, int val) {int j = 0;for(int i=0;i<nums.length;i++){if(nums[i] !=val){nums[j]=nums[i];j+=1;}}return j;}
}

func removeElement(nums []int, val int) int {j := 0for i := 0;i<len(nums);i++{if nums[i]!=val{nums[j]=nums[i]j+=1}}return j
}

找出字符串中第一个匹配项的下标