这道题本可以用暴力，但是用hash /**
@param {number[]} nums
@param {number} target
@return {number[]} */ var twoSum = function(nums, target) { const prevNums = {}; for(let i = 0;i<nums.length;i++){ const curNum = nums[i]; const targetNum = target - curNum; const targetNumIndex = prevNums[targetNum]; if(targetNumIndex !== undefined) { return [targetNumIndex,i] }//cun //ruguo bucunzai //meicicunru dangqian deyuansuhesuoyin prevNums[curNum] = i;
}
};
} 1 } 这道题由于数组的特性，建立快慢指针两种形式。 var removeDuplicates = function(nums) { var j = 0; var n = nums.length for(var i =0 ;i<=nums.length;i++){ if( nums[i]!= nums[i-1]){ j++ nums[j] = nums[i] } } return j+1 }; 本题实现了两个整数相加，只不过两个整数都是链表的结构存储的，返回的整数也是链表。 /**
Definition for singly-linked list. function ListNode(val) { this.val = val; 1 this.next = null; 1 } / /* @param {ListNode} l1 @param {ListNode} l2 @return {ListNode} */ var addTwoNumbers = function(l1, l2) { let node = new ListNode(‘head’); let temp = node; let add = 0; let sum = 0; while(l1 || l2){ sum = (l1 ? l1.val :0) + (l2 ? l2.val : 0) + add; temp.next = new ListNode(sum % 10); temp = temp.next; add = sum>=10 ? 1:0; l1 && (l1 = l1.next); l2 && (l2 = l2.next); } add && (temp.next = new ListNode(add)); return node.next ; };js中有几个对象是链表结构必须的 data数据域的东西要存储的元素 next链表的指向 所以返回node的属性next 最长不重复的子字符串的长度
var lengthOfLongestSubstring = function(s) { const occ= new Set(); let rk = -1, ans = 0; //定义右指针 初始化为-1 代表没有重复的 let n = s.length for (let i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格，移除一个字符 occ.delete(s.charAt(i - 1)); } while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) { //集合的has方法 // 不断地移动右指针 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = Math.max(ans, rk - i + 1); } return ans;
};
动态规划问题 主要问题是在问题结构非线性问题 一种是在结构上的子问题的大问题 一种是寻找动态方程 var longestPalindrome = function(s) { if(!s || s.length === 0) return “”; let res = s[0]; const dp = []; for(let i = s.length;i>=0;i–){ dp[i]=[]; for(let j= i;j<s.length;j++){ if(j - i === 0) dp[i][j] == true else if(j-i === 1 && s[i] === s[j]){ dp[i][j] == true } else if(s[i]==s[j]&& dp[i + 1][j -1]){ dp[i][j] == true } if(dp[i][j] && j-i +1>res.length){ res = a.slice(i,j+1) } } } return res
};
二叉树dp；偷劫
二叉树的时间复杂度logn 队列O(n) 单调队列 栈的分类O(n) 单调栈 堆 的实现
二叉树搜索的时间复杂度O（你！）
数组 二维 三维
// 罗马数字互转，我认为他涉及基本数据类型的转换 class Solution { public int romanToInt(String s) { Map<String, Integer> map = new HashMap<>(); map.put(“I”, 1); map.put(“IV”, 4); map.put(“V”, 5); map.put(“IX”, 9); map.put(“X”, 10); map.put(“XL”, 40); map.put(“L”, 50); map.put(“XC”, 90); map.put(“C”, 100); map.put(“CD”, 400); map.put(“D”, 500); map.put(“CM”, 900); map.put(“M”, 1000);
int ans = 0; for(int i = 0;i < s.length();) { if(i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) { ans += map.get(s.substring(i, i+2)); i += 2; } else { ans += map.get(s.substring(i, i+1)); i ++; } } return ans;} 1 2 3 4 5 6 7 8 9 10 11 12 } var intToRoman = function(num) { var Q = ["", “M”, “MM”, “MMM”]; var B = ["", “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, “CM”]; var S = ["", “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, “XC”]; var G = ["", “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, “IX”]; return Q[Math.floor(num/1000)] + B[Math.floor((num%1000)/100)] + S[Math.floor((num%100)/10)] + G[num%10]; };
链表 最长公共前缀第二道题与第一数组本身可以看作是链表。然后用substr截取数据 可以把 字符串 用作做data域中，next指针自然就看成数组的索引，然后再用字符串对象方法截取前缀
/**
@param {string[]} strs @return {string} */ var longestCommonPrefix = function(strs) { if(strs.length == 0) return “”; let ans = strs[0];//这里ans是一个字符串 for(let i =1;i<strs.length;i++) { let j=0; for(;j<ans.length && j < strs[i].length;j++) { if(ans[j] != strs[i][j]) break; } ans = ans.substr(0, j); if(ans === “”) return ans; } return ans; }; 三数之和hash三个元素会出现重复 用双指针 本题利用 双指针遍历数组 与15题类似 const threeSumClosest = (nums, target) => { nums.sort((a, b) => a - b); let res = nums[0] + nums[1] + nums[nums.length - 1]; for (let i = 0; i < nums.length - 2; i++) { const n1 = nums[i]; let left = i + 1; let right = nums.length - 1; while (left < right) { const n2 = nums[left]; const n3 = nums[right]; const sum = n1 + n2 + n3; sum > target ? right-- : left++; if (Math.abs(sum - target) < Math.abs(res - target)) { res = sum; } } } return res; }
数据结构中的树是一种有向无环无回路的特殊的图。 生成树就是一种机器精简结构。 入度初度 有两个著名的算法是bfs dfs算法来遍历数据结构
