th3242342.jpg
7. 整数反转
利用数组 + 字符串的
API，切割，翻转，再拼接
var reverse = function (x) {
let result = 0
if (x < 0) {
let num1 = Math.abs(x) + ''
result = -(num1.split('').reverse().join(''))
} else {
x = x + ''
result = parseInt(x.split('').reverse().join(''))
}
if (result > Math.pow(2, 31) || result < -Math.pow(2, 31)) {
return 0
}
return result
};
9. 回文数
var isPalindrome = function (x) {
x = x + ''
let left = 0
let right = x.length - 1
while (left <= right) {
if (x[left] === x[right]) {
left++
right--
} else {
return false
}
}
return true
};
14. 最长公共前缀
let longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) {
return ''
}
// 取出第一个作为对照
let prevs = strs[0]
for (let i = 0; i < strs.length; i++) {
// 每一轮对照都要从第一个字符的开头进行比对
let j = 0
for (; j < prevs.length && j < strs[i].length; j++) {
if (prevs.charAt(j) !== strs[i].charAt(j)) {
break
}
}
prevs = prevs.substring(0, j)
if (prevs === '') {
return ''
}
}
return prevs
}
20. 有效的括号
let isValid = function(s) {
let map = {
'{': '}',
'[': ']',
'(': ')'
}
let stack = []
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
stack.push(s[i])
} else if (s[i] !== map[stack.pop()]) {
return false
}
}
return stack.length === 0
}
21. 合并两个有序链表
var mergeTwoLists = function(l1, l2) {
// 因为需要返回新的链表，所以需要构建一个新的节点
let newNode = new ListNode('start'), tmp = newNode
while(l1 && l2) {
if (l1.val >= l2.val) {
tmp.next = l2
l2 = l2.next
} else {
tmp.next = l1
l1 = l1.next
}
tmp = tmp.next
}
tmp.next = l1 === null ? l2 : l1
return newNode.next
};
26. 删除有序数组中的重复项
let removeDuplicates = function(nums) {
let left = 0
for (let right = 1; right < nums.length; right++) {
if (nums[right - 1] === nums[right]) {
left++
} else {
nums[right - left] = nums[right]
}
}
return nums.length - left
}
53. 最大子序和
var maxSubArray = function(nums) {
let max = -Infinity
let dp = []
let n = nums.length
for (let i = -1; i < n; i++) {
dp[i] = 0
}
for (let i = 0; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
max = Math.max(max, dp[i])
}
return max
}
70. 爬楼梯
第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去。
var climbStairs = function (n) {
if (n == 1) { return 1; }
if (n == 2) { return 2; }
let a = 1, b = 2, temp;
for (let i = 3; i <= n; i++) {
temp = a;
a = b;
b = temp + b;
}
return b;
};
88. 合并两个有序数组
var merge = function(nums1, m, nums2, n) {
let len1 = m - 1
let len2 = n - 1
let len = m + n - 1
while(len2 >= 0) {
if (len1 < 0) {
nums1[len--] = nums2[len2--]
continue
}
nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--] : nums2[len2--]
}
};
104. 二叉树的最大深度
层序遍历，获取二叉树的最大深度
let maxDepth = function(root) {
if (!root) return 0
let que = [root], res = 0
while(que.length) {
let temp = []
for (let i = 0; i < que.length; i++) {
if (que[i].left) {
temp.push(que[i].left)
}
if (que[i].right) {
temp.push(que[i].right)
}
}
res += 1
que = temp
}
return res
}
121. 买卖股票的最佳时机
var maxProfit = function(prices) {
let max = 0, min= prices[0]
for (let i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i])
max = Math.max(max, prices[i] - min)
}
return max
};
136. 只出现一次的数字
var singleNumber = function(nums) {
for (let item of nums) {
if (nums.indexOf(item) === nums.lastIndexOf(item))
return item
}
};
141. 环形链表
有 fast 和 slow 两个指针，一慢一快，如果链表是有环的，那么走的快的那个指针迟早会跟慢指针重合的
var hasCycle = function(head) {
let fast = = head
while (slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if(slow === fast) {
return true
}
}
return false
};
