// 逆向双指针的方法
var merge = function(nums1, m, nums2, n) {
  let p1 = m-1,p2 = n-1,p = m+n-1  //三个指针，第一个用来遍历数组1中的每个值。
  //第二个用来遍历数组2中的每一个值，第三个用来存数据，从数组1的最后一个位置开始。
  while(p1>=0 && p2>=0){ // 双指针，从两个数组的最后一个数开始，倒着比较值的大小。
    if (nums2[p2]>=nums1[p1]){
      nums1[p] = nums2[p2]
      p2--
    }
    else{
      nums1[p] = nums1[p1]
      p1--
    }
    p--
  }
  while(p2>=0){//如果数组2中还有剩余的元素，全部放在数组1的前面
    nums1[p] = nums2[p2]
    p2--
    p--
  }
};

var twoSum = function(nums, target) {
  let map = new Map()
  // 判断target-当前元素的结果是否存在于map中，如果存在返回下标
  for (let i=0;i<nums.length;i++){
    if (map.has(target-nums[i])){
      return [map.get(target-nums[i]),i]
    }
    //如果不存在，设置当前元素为键，当前元素下表为值
    else{
      map.set(nums[i],i)
    }
  }
}

var threeSum = function (nums) {
  let res = []
  nums = nums.sort((a,b)=>a-b) //首先要进行排序
  for (let i = 0; i < nums.length-2; i++) {  //减2是因为求得是三个元素的和。
    if (i > 0 && nums[i] == nums[i - 1]) continue //a去重
    let left = i + 1,right = nums.length - 1 //指定双指针
    while (left < right) {
      let sum = nums[i]+nums[left]+nums[right]
      if (sum>0) right--
      if (sum<0) left++
      if(sum===0){
        res.push([nums[i],nums[left],nums[right]])
        //后两个数去重逻辑，如果指针指向下一个元素与当前相同，跳过该元素
        while(left<right && nums[left] === nums[left+1]) left++
        while(left<right && nums[right] === nums[right-1]) right--
        left++     //忘记调整这两个了
        right--
      }
    }
  }
  return res
}

var reverseList = function(head) {
  let prev = null
  let cur = head
  while(cur){
    // 这一步我忘记了，没有把next的值保存下来，直接给cur.next赋值了
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev //最后一个cur是null，他前面一个才是第一个有值的节点
};

function quickSort(arr) {
  //终止条件
  if (arr.length <= 1) return arr
  //找基准,选择最后一个元素作为基准
  let std = arr.length - 1
  //用来存储左右两个数组
  let leftArr = [],
    rightArr = []
  for (let i = 0; i < std && i != std; i++) {
    if (arr[i] <= arr[std]) leftArr.push(arr[i])
    else rightArr.push(arr[i])
  }
  //分别处理左右两个子数组
  return [...quickSort(leftArr), arr[std], ...quickSort(rightArr)]
}
console.log(quickSort([5, 2, 9, 1, 7, 6,3,80,34]))

var dailyTemperatures = function(temperatures) {
  let n = temperatures.length
  let stack = [0]
  let res = Array(n).fill(0)
  for(let i=1;i<n;i++){
    let top = stack[stack.length-1]
    //小于和等于的情况，直接压入栈
    if (temperatures[i] === temperatures[top]){
      stack.push(i)
    }
    else if(temperatures[i] < temperatures[top]){
      stack.push(i)
    }
    //当前元素大于栈顶元素的情况，要计算距离，
    //删掉栈顶元素知道所有小于当前元素的栈顶元素被删完，压入当前元素
    else{
      while (stack.length && temperatures[i] > temperatures[stack[stack.length-1]]) {
        top = stack.pop()
        res[top] = i-top
      }
      stack.push(i)
    }
  }
  return res
};

var nextGreaterElement = function (nums1, nums2) {
  const m = nums1.length
  const n = nums2.length
  let stack = [nums2[0]]
  let res = Array(m).fill(-1)
  let map = new Map()
  for (let i = 0; i < m; i++) {
    map.set(nums1[i],i)
  }
  for (let j = 1; j < n; j++) {
    let top = stack[stack.length-1]
    if (nums2[j]<top || nums2===top) stack.push(nums2[j])
    else{
        // console.log(res)
        while(stack.length && nums2[j]>stack[stack.length-1]){
          top = stack.pop()
          if (map.has(top)){
            res[map.get(top)] = nums2[j]

          }
        }
        stack.push(nums2[j])
      }
  }
  return res
}

var nextGreaterElements = function(nums) {
  let n = nums.length
  let res = Array(n).fill(-1)
  let stack = [0]
  for(let i=1;i<n*2;i++){
    let j = i
    if (i>=n)  j = i - n
    while (stack.length && nums[j] > nums[stack[stack.length - 1]]) {
      let top = stack.pop()
      res[top] = nums[j]
    }
    stack.push(j)
  }
  return res
};

var trap = function(height) {
  let n = height.length
  let res = 0
  let stack = [0]
  for(let i=1;i<n;i++){
    while(stack.length && height[i]>height[stack[stack.length-1]]){
        let top = stack.pop()
        if (stack.length === 0) break
        let topl = stack[stack.length-1]
        res += (Math.min(height[i],height[topl])-height[top]) * (i-topl-1)
    }
    stack.push(i)
  }
  return res
};

var largestRectangleArea = function(heights) {
  heights = [0,...heights,0]
  let n = heights.length
  let maxArea = 0
  let stack =[0]
  for (let i=1;i<n;i++){
    while(heights[i]<heights[stack[stack.length-1]]){
      let top = stack.pop()
      let topl = stack[stack.length-1]
      let w = i-topl-1
      maxArea = Math.max(maxArea,w*heights[top])
    }
    stack.push(i)
  }
  return maxArea
};

function wardrobeFinishing(m, n, cnt) {
  const digitSum = (num) => {
    let sum = 0
    while (num) {
      sum += num % 10
      num = Math.floor(num / 10)
    }
    return sum
  }

  const visited = Array.from({ length: m }, () => Array(n).fill(false))
  let count = 0

  const dfs = (i, j) => {
    if ( i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || digitSum(i) + digitSum(j) > cnt)
      return
    visited[i][j] = true
    count++
    dfs(i + 1, j) // 向下移动
    dfs(i, j + 1) // 向右移动
  }

  dfs(0, 0) // 从(0, 0)开始搜索
  return count
}

var wordPuzzle = function(grid, target) {
  const h = grid.length,
    w = grid[0].length;
  const direction = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];
  const visited = Array.from({ length: h }, () => Array(w).fill(false));

  const check = (i, j, k) => {
    if (grid[i][j] != target[k]) return false;
    else if (k == target.length - 1) return true; // 修正比较操作

    visited[i][j] = true;
    //向四分方向寻找
    for (let [dx, dy] of direction) { // 添加let声明
      let newi = i + dx, newj = j + dy;
      if (newi >= 0 && newi < h && newj >= 0 && newj < w && !visited[newi][newj]) { // 修正条件判断
        if (check(newi, newj, k + 1)) {
          return true; // 找到匹配后立即返回true
        }
      }
    }
    visited[i][j] = false;
    return false;
  };
  // 第一个字母的判断
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (check(i, j, 0)) {
        return true;
      }
    }
  }
  return false;
}

var wordPuzzle = function(grid, target) {
  const h = grid.length,
        w = grid[0].length;
  const directions = [
    [0, 1],  // 右
    [0, -1], // 左
    [1, 0],  // 下
    [-1, 0]  // 上
  ];

  const visited = Array.from({ length: h }, () => Array(w).fill(false));

  const dfs = (i, j, k) => {
    if (i < 0 || i >= h || j < 0 || j >= w || visited[i][j] || grid[i][j] !== target[k]) {
      return false;
    }
    if (k === target.length - 1) {
      return true;
    }
    visited[i][j] = true;
    for (const [di, dj] of directions) {
      if (dfs(i + di, j + dj, k + 1)) {
        return true;
      }
    }
    visited[i][j] = false; // 回溯
    return false;
  };

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (grid[i][j] === target[0] && dfs(i, j, 0)) {
        return true;
      }
    }
  }
  return false;
};

npm install @amap/amap-jsapi-loader

import AMapLoader from '@amap/amap-jsapi-loader'
// 初始化地图时要配置key，和密钥
// 因为我没配置密钥导致我的提示一直不出来，搞了好久才成功
AMapLoader.load({
  "key": "你的高德地图API密钥", // 请替换成你的高德地图API密钥
  "version": "2.0", // API版本号
  "plugins": [] // 需要使用的插件列表
}).then((AMap) => {
  // 高德地图API已成功加载，现在可以通过AMap对象进行地图开发了
}).catch(e => {
  console.log(e); // 加载错误
});

// 在index.html中通过CDN的方式引入
<script type="text/javascript">
     window._AMapSecurityConfig = {
            securityJsCode:'安全密钥',
        }
    </script>
<script src="https://webapi.amap.com/maps?v=2.0&key=我的key"></script>
<script src="https://webapi.amap.com/ui/1.1/main.js"></script>

//使得id为inputId的input元素可以实现搜索提示
const initAutocomplete = (inputId) => {
  // 延迟执行，确保DOM元素已经渲染
      nextTick(() => {
        AMap.plugin('AMap.AutoComplete', () => {
          const autoOptions = {
            input: inputId
          };
          const autoComplete = new AMap.Autocomplete(autoOptions);
          //选中某个poi之后的操作，获取poi的经纬度用于后续路径规划
          autoComplete.on('select', (e) => {
            console.log('select', e)
            if (inputId === 'tipinput1') {
              startPoint.value = e.poi.name;
              startCoor.value.lng = e.poi.location.lng;
              startCoor.value.lat = e.poi.location.lat;
              // startCity.value = e.poi.sdcode;
            } else {
              endPoint.value = e.poi.name;
              endCoor.value.lng = e.poi.location.lng;
              endCoor.value.lat = e.poi.location.lat;
              // endCity.value = e.poi.adcode ;
            }
          });
        });
      });
};

//封装好的axios
import instance from "./outServeRequest.js"
// 访问高德地图api，获取数据;v3有polyline，v5没有
const url = '/amap/v3/direction/'
const key = '我的key'
export function getRoute(routeOpt,originCoor,destinationCoor,) {
  let routeUrl = ''
  if (routeOpt === 'integrated') {
    //后面两个city的值是城市的adcode
    routeUrl = `${url}/transit/${routeOpt}?&key=${key}&origin=${originCoor.lng},${originCoor.lat}&destination=${destinationCoor.lng},${destinationCoor.lat}&city=110000&cityd=110000`
  } else {
    routeUrl = `${url}${routeOpt}?&key=${key}&origin=${originCoor.lng},${originCoor.lat}&destination=${destinationCoor.lng},${destinationCoor.lat}`
  }
  return routeUrl
}
// 发起get请求
export function getRouteData(routeOpt,originCoor,destinationCoor) {
  const routeUrl = getRoute(routeOpt,originCoor,destinationCoor)
  return instance.get(routeUrl)
}

vite.config.js
export default defineConfig({
  server: {
      proxy: {
        // 代理所有到 /amap 的请求到 https://restapi.amap.com
        '/amap': {
          //第三方地址，这里用amap代理了，那么请求的地址就应该时amap开头
          target: 'https://restapi.amap.com', // 目标地址
          changeOrigin: true, // 必须设置为true，以便代理服务器发送请求时更改Origin头信息
          rewrite: (path) => path.replace(/^\/amap/, ''), // 将请求地址中的 /amap 替换为空，因为实际的API地址中不包含 /amap
          secure: false,
          xfwd: true,
        }
      }
    }
})

前端使用代理
const url = `/amap/v3/assistant/coordinate/convert?key=${key}&locations=${locations}&coordsys=gps`

不使用代理前的url为
'https://restapi.amap.com/v3/assistant/coordinate/...'

npm install gcoord --save

<script src="https://unpkg.com/gcoord/dist/gcoord.global.prod.js"></script>

const gcoord = require('gcoord');

import gcoord from 'gcoord';

// 将GCJ02坐标转换为WGS84坐标
var result = gcoord.transform([123, 45], gcoord.GCJ02, gcoord.WGS84);
console.log(result);  // [122.99395597, 44.99804071]

// 转换GeoJSON坐标
var geojson = {
  "type": "Point",
  "coordinates": [123, 45]
}
gcoord.transform(geojson, gcoord.GCJ02, gcoord.WGS84);
console.log(geojson.coordinates); // [122.99395597, 44.99804071]

前序方法1
var preorderTraversal = function(root) {
  let res = []
  const dfs = ()=>{
    if (root === null) return
    res.push(root.val)
    dfs(root.left)
    dfs(root.right)
  }
  //调用
  dfs(root)
  return res
};
前序方法2:
var preorderTraversal = function (root) {
  return root
    ? [
        root.val,
        ...preorderTraversal(root.left),
        ...preorderTraversal(root.right)
      ]
    : []
}

中序方法1:
var inorderTraversal = function(root) {
  let res=[]
  const dfs = (r)=>{
    if (r===null) return
    dfs(r.left)
    res.push(r.val)
    dfs(r.right)
  }
  dfs(root)
  return res
};
中序方法2:
var inorderTraversal = function (root) {
  return root
    ? [
        ...inorderTraversal(root.left),
        root.val,
        ...inorderTraversal(root.right)
      ]
    : []
}

后序方法1
var postorderTraversal = function(root) {
  let res = []
  const dfs = (r)=>{
    if (r===null) return
    dfs(r.left)
    dfs(r.right)
    res.push(r.val)
  }
  dfs(root)
  return res
};
后序方法2
var postorderTraversal = function (root) {
  return root
    ? [
        ...postorderTraversal(root.left),
        ...postorderTraversal(root.right),
        root.val
      ]
    : []
}

前序
// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
var preorderTraversal = function (root) {
  let res = []
  if (!root) return res
  let queue = [root]
  while(queue.length){
    cur = queue.pop()
    res.push(cur.val)
    cur.right && queue.push(cur.right)
    cur.left && queue.push(cur.left)
  }
  return res
}

// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转
后序
var postorderTraversal = function (root) {
  let res = []
  if (!root) return res
  let stack = [root]
  while(stack.length){
    cur = stack.pop()
    res.push(cur.val)
    cur.left && stack.push(cur.left)
    cur.right && stack.push(cur.right)
  }
  return res.reverse()
}

中序
var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  if (!root) return res
  const stack = []
  cur = root
  while (cur || stack.length){
    if (cur){
      stack.push(cur)
      cur = cur.left
    }
    else{
      cur = stack.pop()
      res.push(cur.val)
      cur = cur.right
    }
  }
  return res
}

var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    if (!node) {
      res.push(stack.pop().val)
      continue
    }
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null)
    if (node.left) stack.push(node.left) // 左
  }
  return res
}

超时了，129/132
var countSubstrings = function(s) {
  let num = 0
  function isHuiwen(t) {
    let p = 0;q = t.length-1
    while (p<q){
      if (t[p] != t[q]){
        return false
      }
      p++;
      q--
    }
    return true
  }
  for (let i=0;i<s.length;i++){
    for (let j=i+1;j<=s.length;j++){
      console.log(isHuiwen(s.substring(i, j)))
      if (isHuiwen(s.substring(i,j))) num ++
    }
  }
  return num
};

动态规划
var countSubstrings = function(s) {
  let num = 0
  let n = s.length
  let dp = Array.from({length:n},()=>Array(n).fill(false))
  for(let i=n-1;i>=0;i--){
    //j是尾巴，尾巴j大于等于头i
    for(let j=i;j<n;j++){
      if (s[i]==s[j]){
        if (j-i>1) {
          dp[i][j] = dp[i+1][j-1]
        }
        else dp[i][j] = true
      }
      if (dp[i][j] === true) num++
    }
  }
  console.log(dp)
  return num
};

var longestPalindromeSubseq = function(s) {
  let n = s.length
  let dp = Array.from({length:n},()=>Array(n).fill(0))
  for (let i=0;i<n;i++){
    dp[i][i] =1
  }
  for(let i=n-1;i>=0;i--){
    for(let j=i+1;j<n;j++){
      if (i==j) dp[i][j] = 1
      if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1] + 2
      else dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
    }
  }
  return dp[0][n-1]
};

var isSubsequence = function(s, t) {
  let n = s.length
  let m = t.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + 1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  if (dp[n][m] == n) return true
  return false
};

var numDistinct = function(s, t) {
  let n = s.length
  let m = t.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=0;i<=n;i++) {dp[i][0]=1}
  for (let i=1;i<=n;i++){
    for (let j=1;j<=m;j++){
      //相等，可以选择使用s[i-1]或者不使用s[i-1]
      if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
      else dp[i][j] = dp[i-1][j]  //不相等说明s[i-1]用不了得删掉。
    }
  }
  return dp[n][m]
};

var minDistance = function(word1, word2) {
  let n = word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  return n+m-2*dp[n][m]
};

var minDistance = function(word1, word2) {
  let n = word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  //这两个for循环用于初始化dp数组
  for (let i=0;i<=n;i++){
    dp[i][0] = i
  }
  for (let j=0;j<=m;j++){
    dp[0][j] = j
  }
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]
      else dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1)
    }
  }
  return dp[n][m]
};

var minDistance = function(word1, word2) {
  let n= word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=0;i<=n;i++){
    dp[i][0] = i
  }
  for (let j=0;j<=m;j++){
    dp[0][j] = j
  }
  for (let i=1;i<=n;i++){
    for (let j=1;j<=m;j++){
      if (word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1]
      else dp[i][j] = Math.min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1)
    }
  }
  return dp[n][m]
};

var lengthOfLIS = function(nums) {
  let n = nums.length
  let dp = Array(n).fill(1)
  let result = 1
  for(let i=1;i<n;i++){
    for(let j=0;j<i;j++){
      if (nums[i]>nums[j]) dp[i] = Math.max(dp[i],dp[j]+1)
    }
    if (dp[i]>result) result = dp[i]
  }
  return result
};

var findLengthOfLCIS = function(nums) {
  let n = nums.length
  let dp = Array(n).fill(1)
  let result =1
  for(let i=1;i<n;i++){
    if(nums[i]>nums[i-1]) dp[i] = dp[i-1]+1
    if (dp[i]>result) result = dp[i]
  }
  return result
};

var findLength = function(nums1, nums2) {
  let n = nums1.length
  let m = nums2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  let result = 0
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if(nums1[i-1] == nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1
      if (dp[i][j] > result) result = dp[i][j]
    }
  }
  return result
};

var longestCommonSubsequence = function(text1, text2) {
  let n = text1.length
  let m = text2.length
  let dp = Array.from({length:n+1},()=> Array(m+1).fill(0))
  for(let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if (text1[i-1]==text2[j-1]) dp[i][j] = dp[i-1][j-1]+1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  return dp[n][m]
};

var maxUncrossedLines = function(nums1, nums2) {
  let n = nums1.length
  let m = nums2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for(let i = 1;i<=n;i++){
    for(let j = 1;j<=m;j++){
      if (nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  return dp[n][m]
};